简介：这份编译原理上机报告面向正在完成课程设计、需要参考编译器与小型 DBMS 实现思路的计算机专业学生，选题为“DBMS 的设计与实现”。报告以单份 doc 文档交付，压缩包共 1 个文件、约 82KB，正文按项目概况、编译部分、DBMS 部分与总结展开，记录了基于 lex 和 yacc 的词法、语法分析方案，Token 结构、正规式定义、VC++6.0 开发环境，以及数据存储、索引和建库建表、增删改查、事务管理等模块设计。已有 1332 人学习，适合用来对照课程要求梳理上机报告结构、理解编译前端如何与数据库功能衔接，也可作为撰写实验报告和整理实现方案的参考。
1. 编译原理上机报告里最值钱的东西，一般不在正文里
把一条CREATE TABLE t (id INT);喂进 lex/yacc 搭出来的前端，从第一个字符读入到打印出那句Operation is ok，中间要经过几十次 DFA 状态转移、十来次移进与归约。而这份编译原理上机报告的正文，只用"完成词法分析与语法分析"一行就把这段过程盖过去了。
真正值得读的，是被压缩进"存在问题及解决方法"那两行里的东西：为什么 Name 规则会把数字吃掉、为什么单引号不加反斜线就一个字符都匹配不上、为什么sts: sts st这条左递归能让分析栈深度恒定。这些坑背后是同一套状态机加表驱动解析的机制，想清楚了，以后再看任何 SQL 解析器、配置语言解析器甚至正则引擎，骨架都是同一个。
2. 词法分析器不是查表：一条 SQL 是怎么被切成 Token 流的
很多人对词法分析的第一印象是"拿关键字表一个个比"，这跟 lex 实际干的事情差得很远。lex 一秒钟都没在运行时查过关键字表，它把所有正则表达式编译成一台确定有限自动机，yylex()的全部工作就是在这台自动机上走格子。理解这一点，后面所有"为什么这条规则不生效"的问题才有解。
2.1 规则合并：先拼成一个大 NFA，再谈切词
定义文件里每一条规则（正则 + 动作）都会被单独编译成一个 NFA 片段。标准做法是 Thompson 构造：字符边、ε 边、每个片段有唯一入口和唯一出口。关键在于"唯一出口"这个约束，它不是为了好看，而是为了挂动作——自动机走到某个接受态时，生成器需要能唯一确定该执行哪一段 C 代码。如果两条规则共享出口，动作用谁的就说不清了。
所有片段随后用 ε 边并联到一个新的总起点上：
ε → [ "CREATE" ] → (接受, 动作 #1) 新起点 ─ε → [ "DATABASE" ] → (接受, 动作 #2) ε → [ [0-9]+ ] → (接受, 动作 #13) ε → [ 标识符 ] → (接受, 动作 #15)这张图里已经埋了第一个雷："CREATE"和标识符这两条分支，在读过C、R、E、A、T、E这六个字符之后会走到"语义等价"的路径上——它们读的是同样的字符序列。子集构造阶段会把这两条路径合并进同一个 DFA 状态集合，于是这个 DFA 状态同时携带两个接受标记。至于最后执行哪一个，就是第 3 章要讲的最长匹配加规则顺序。
顺带说一句，原文的词法部分定义了struct Token { int type; char *yych; int value; }这样的结构，但生成器实际用的是YYSTYPE加yylval那套。手写的 Token 结构在自动机方案里通常是冗余的，真正被 parser 消费的只有return出去的那个整数类型码，以及通过yylval带过去的语义值。
2.2 子集构造与最长匹配：回退到底发生在哪一步
NFA 转 DFA 用子集构造，DFA 的每个状态是 NFA 状态的一个 ε-闭包集合。真正的实现还要多做两步优化：一是字符等价类划分，256 个字节被映射成几十个类编号，转移表从状态 × 256压到状态 × 类数；二是稀疏矩阵压缩，用base/check/def/meta四个数组把二维表压成一维，查表时靠check数组验证命中。
运行时那套"最长匹配"（maximal munch）的循环，生成代码大致长这样：
/* 变量名取自生成的扫描骨架，循环体是每一轮读一个字符 */ while (1) { yy_c = yy_ec[(unsigned char)*yy_cp]; /* 字节映射到字符等价类 */ while (yy_chk[yy_base[yy_current_state] + yy_c] != yy_current_state) { yy_current_state = yy_def[yy_current_state]; /* 走默认边 */ if (yy_current_state >= 256) yy_c = yy_meta[yy_c]; } yy_current_state = yy_nxt[yy_base[yy_current_state] + yy_c]; if (yy_current_state == 0) break; /* 掉进死状态，停止前进 */ if (yy_accept[yy_current_state]) { /* 接受态，先记下来，不急着返回 */ yy_last_accepting_state = yy_current_state; yy_last_accepting_cpos = yy_cp; } ++yy_cp; } /* 关键一步：退回最近一次接受的位置，而不是当前位置 */ yy_cp = yy_last_accepting_cpos + 1; yy_current_state = yy_last_accepting_state;这段代码里最容易看漏的是"为什么不直接在接受态就返回"。因为词法分析要的是最长的那一段，>和!=就是典型例子：读到>时状态已经接受了，但下一个字符如果是=，应该继续走下去变成!=的一部分。所以实现必须一路走到底，记住最后一次接受的位置，撞墙了再回退。yy_cp回退、缓冲区指针重设，这就是词法层唯一的"后悔药"，而且只用一次。
理解了回退，第 3 章那个"数字被抢走"的现象就有了统一的解释框架：不是规则没写，是自动机在某个位置上做了选择。
2.3 动作挂载点与 yytext 的生命周期
原文的词法动作里有一段容易被跳过的代码：
%{ /* 从 parser 对象里把语义值槽取出来，绑成引用 */ YYSTYPE YYFAR& yylval = *(YYSTYPE YYFAR*)yyparserptr->yylvalptr; %} "CREATE" { return CREATE; } [0-9]+ { return NUMBER; }这个写法挺有意思：yylval不是全局变量，而是每次动作执行时从 parser 对象里现取的引用。配套的入口是parser.yycreate(&lexer)和lexer.yycreate(&parser)，两个对象互相持有指针。这是 C++ 版生成器在 2011 年那会儿对"可重入"给出的朴素答案——把状态从全局挪进对象，同进程里就能同时跑多个扫描器实例。今天换成 flex 的%option reentrant或者手写扫描器，本质是同一件事。
yytext则是另一码事：它指向当前 token 在缓冲区里的首地址，生成代码会在 token 末尾写一个\0，所以能直接当 C 字符串用；yyleng给出长度。注意它的有效期只到下一次调用yylex()为止——如果yylval要带字符串（比如把表名Name传上去），必须在动作里strdup一份，否则后面这条语句的所有标识符都会指向同一块被覆写的内存。这是词法层最经典的悬垂引用源头之一，跟内存管理没关系，纯粹是缓冲区复用。
3. 最长匹配：为什么你写的 ID 规则一次都没触发过
词法规则写完后最常见的一种"看起来能跑"的状态是：关键字都没问题，标点都正常，唯独某条规则像是被注释掉了。原文踩的坑是数字识别不出来，但更普遍的现象在标识符上。这一章把选择规则的两条铁律拆开：先比长度，长度相同再比规则顺序，没有第三条。
3.1 两条规则都能匹配时，DFA 选谁
DFA 走到一个同时挂着多个接受标记的状态时，生成代码不会做任何语义判断，它只做两件事：
- 比较各自匹配到的字符数，选最长的；
- 长度相同时，选规则在文件里出现位置靠前的。
这就是为什么"关键字必须写在标识符规则前面"成了 lex 的常识。"CREATE"和[a-zA-Z][_a-zA-Z0-9]+对输入CREATE都恰好匹配 6 个字符，长度一样，于是看顺序；而对输入CREATEX，标识符规则能匹配 7 个字符，关键字规则只能到 6，最长匹配直接胜出，根本轮不到顺序。换句话说，关键字并不需要一张排除表，它靠的是"等长时的顺序 + 更长时的最长匹配"这两条规则的组合效果。
原文把关键字规则一条条平铺在最前面（CREATE、DATABASE、SELECT……），顺序上是对的。但这么多条平行规则在子集构造阶段会产生大量共享中间态，DFA 状态数比想象的多，这是词法分析器体积膨胀的主要来源，也是实际工程里用"先把标识符扫出来、再查哈希表判定是不是关键字"这个替代方案的原因——多一次哈希查找，换掉几百个状态。
3.2 ID 与 Name 的重叠区：首字符集合一旦写宽就出事
原文的两条标识符规则挨在一起：
[0-9]+ { return NUMBER; } [a-zA-Z][_0-9a-zA-Z()\.\*]* { printf("%s", yytext); return Name; } [a-zA-Z][_a-zA-Z0-9]+ { return ID; }第三条ID是永远不会被返回的。原因很直接：ID允许的字符集合（首字母 + 字母数字下划线）是Name允许集合的子集，Name还多放行了(、)、.、*。任何一个能被ID匹配的串，Name都能匹配同样长度，两者等长，Name在前，胜出。ID这条规则在 DFA 里存在，在接受表里有标记，但永远到不了——生成器不会给你任何警告。
Name那个字符集还带来第二个副作用：SELECT a*b FROM t里的a*b会被整体扫成一个Nametoken，而不是Name加*。因为最长匹配优先，a*b有 3 个字符，比单独一个a长。t.*同理。把().*塞进标识符的字符集，本意是想让table.field、count(*)这种形式在词法层一次过，代价是语法层失去了拆解它们的可能——token 里已经糊成一团了。
至于"Name 把 NUMBER 截获"，机制上只有一种可能：标识符正则的首字符集合里混进了0-9（比如写成[a-zA-Z_0-9]），此时输入100会让标识符规则和 NUMBER 规则同样匹配 3 个字符，若标识符规则在前，数字全变成 Name。这个 bug 的隐蔽之处在于：带数字的标识符（t1）依然正常，只有纯数字字面量出问题，很容易被误判成语法层的事。
3.3 词法层的取舍：token 的粒度由谁决定
这里有个值得琢磨的设计问题：count(*)到底该是一个 token 还是三个？原文选了前者，好处是语法规则可以少几条，坏处是语义阶段还得再把字符串拆一遍，而且拆的时候没有了词法位置信息，报错定位会变差。
我一般会这么理解：词法层只该切出"语法层无法再拆的最小单元"，标识符、字面量、标点。把结构信息（点号、星号、括号）揉进 token，等于把语法分析的活提前干了，却丢掉了语法分析最擅长的东西——上下文。*在SELECT *里是通配符，在算术表达式里是乘号，在count(*)里是聚合参数，这些区分交给语法规则做，比在正则里做要清楚得多。
4. 产生式与移进-归约：三十条语法规则怎么变成一张分析表
词法给了 token 流，接下来 yacc 要在没有任何回溯的前提下，一边读 token 一边判断"现在该把哪几个符号合成一个非终结符"。它靠的是一张提前算好的分析表，运行时只做两件事：查表移进、查表归约。搞清这张表怎么来的，"为什么报 shift/reduce 冲突"就不再是玄学了。
4.1 项集与闭包：一条产生式怎么变成状态
yacc 把每条产生式右部的"当前位置"做成一个项，比如st → create_st · ';'表示已经读完create_st、正等着分号。从一个项出发，如果点的右边是非终结符，就把该非终结符的所有产生式都加进来（闭包），然后对每个可能的下一符号求 GOTO，得到一个新状态。整个过程就是从增广开始式S' → · sts出发的图遍历。
原文的产生式集合，起点是这样的：
sts: sts st { printf("Operation is ok\n"); } | /* empty */ ; st: create_st ';' | show_st ';' | drop_st ';' | use_st ';' | select_st ';' | delete_st ';' | update_st ';' | insert_st ';';这里有一处设计值得单拎出来说：分号没有被放进各个子规则里，而是统一挂在st这一层。这样create_st、select_st这些规则只描述语句"本体"，结尾分号成了所有语句的公共后缀，也是天然的同步点——语法出错时跳到下一个分号就能恢复，这个习惯在实现错误恢复时非常有价值。
分析表由两张子表组成：ACTION 表管终结符，值域是"移进某状态 / 归约某产生式 / 接受 / 报错"；GOTO 表管非终结符，值域是"转到某状态"。栈里同时存状态和符号，归约时弹出产生式右部长度个元素，再把左部压回去。整个解析过程没有递归调用，全靠一个显式的状态栈，这也是 LR 解析器能处理左递归的根本原因。
4.2 左递归与右递归：为什么 LR 偏爱前者
sts: sts st是左递归，sts: st sts是右递归。两者语言等价，但栈行为完全不同。
左递归在 LR 下的行为是：每读完一条语句，立刻用sts st → sts归约，把两条合成一条，栈深度始终维持在两三个元素。右递归则相反，读完第一条语句后不能归约（因为右边还等着sts），只能一直往里压，栈深度随语句数量线性增长。解析一万条语句，右递归的栈就要深一万层。
有意思的是，递归下降（LL）解析器恰恰相反：左递归会让它无限递归，必须改写成右递归或者循环。所以"该用左递归还是右递归"这个问题的答案，取决于你用的是哪一类解析器，不是风格问题。yacc 用 LALR(1)，就老老实实写左递归。
sts: sts st上挂的printf也顺带解释了语义动作的执行时机：动作在归约的瞬间执行，而归约的顺序就是语法树的后序遍历顺序，所以子结构对应的动作一定先于父结构。这条性质在第 6 章还会用到。
4.3 %left AND OR 解决的是什么二义性
conditions那组规则本身是有二义性的：
conditions: condition | '(' conditions ')' | conditions AND conditions | conditions OR conditions;输入a = 1 AND b = 2 OR c = 3时，既可以解析成(a=1 AND b=2) OR c=3，也可以解析成a=1 AND (b=2 OR c=3)，语法树形状不同，求值结果就不同。yacc 遇到这种规则会报移进-归约冲突，默认策略是移进，也就是倾向于继续往右读、后结合，这跟 SQL 里 AND 优先于 OR 的常识不符。
原文用%left AND OR声明了优先级和结合性，冲突就这么消掉了。但这里有个值得推敲的地方：%left在同一行里声明多个 token，含义是它们优先级相同、都是左结合。对a AND b OR c来说，左结合给出的(a AND b) OR c恰好等于 AND 优先的正确结果；可对a OR b AND c，左结合给出(a OR b) AND c，而正确语义应该是a OR (b AND c)——两个结果不一样。要真正表达 AND 高于 OR，得分成两行写，先声明%left OR，再声明%left AND（yacc 里越靠后声明的优先级越高）。
这是个很典型的翻车点：测试用例恰好都只覆盖了前一种顺序，程序跑起来一切正常。
5. 排查：四个把上机报告拖到凌晨的坑
生成器这类工具最难受的地方在于，它不报错，只是安静地做另一件事。下面四条是这类项目里出现频率最高的，每条都按"看到什么、为什么、怎么办"写。
5.1 单引号写成三个引号之后，整条规则消失
现象：想匹配 SQL 里的字符串字面量，规则写成''' { }，编译没报错，运行时发现引号像是被跳过了，或者干脆报"未终结的字符串"。
原因：lex 家族把单引号和双引号当作字面量界定符。'''会被切成"开引号 + 立即闭合（空模式）+ 又开一个引号"，剩下的内容被当成仍在引号里，往后吞掉了一整段规则。生成的自动机里根本没有单引号这条边。
解决：用\'转义，或者用双引号包住它"'"。更彻底的做法是字符串整体成一条规则（'[^']*'之类），由词法层自己负责闭合，别让语法层去拼引号——让语法规则去匹配两个引号之间的内容，会立刻和标识符、数字的规则打起来。
5.2 数字在 token 流里变成了 Name
现象：INSERT INTO t VALUES (100)在100那个位置报语法错误，把 token 流打出来一看，是个Name而不是NUMBER。
原因：标识符正则的首字符集合写宽了，混进了0-9。此时100同时被标识符规则和数字规则接受，长度都是 3，按规则顺序取靠前的那个。
解决：标识符首字符严格写[a-zA-Z]，后续字符才用[_a-zA-Z0-9]。把数字规则放前面只是双保险，真正的约束是等长时的那次顺序比较。排查方法是把每个 token 的类型和文本都打出来（打到 stderr，不是 stdout），一眼就能看出是谁被抢了。
5.3 空产生式让日志多打一行，冲突警告被无视
现象：程序刚启动、一条语句都没输入，先打印了一句Operation is ok；或者生成时报conflicts: 1 shift/reduce，没人当回事。
原因：sts: /* empty */在输入开头就要归约一次，实例化出一个空的sts；而移进-归约冲突的默认策略是移进，多数情况下恰好正确，但在悬空边界上会静默改变结合顺序。
解决：把副作用从空产生式路径上挪走，只在sts st（真正吃完一条语句）时打印。冲突数不为 0 就必须逐条看，用优先级声明或者%prec显式表态，别指望默认策略永远是对的。
5.4 调试 printf 和全角符号留在规则文件里
现象：程序输出里混着CREATE、t、id这些 token 原文；或者生成器报某个符号未定义，翻遍规则也找不到那个名字。
原因：[a-zA-Z]...* { printf("%s", yytext); return Name; }这句调试打印留在了动作里，和程序自己的输出混在同一个 stdout；规则文件里混进了全角标点，比如空产生式后面那个？，生成器会把它当成一个未声明的终结符。
解决：调试输出走 stderr 或者编译期开关；报"undefined token"时先搜一遍规则文件里的非 ASCII 字符。这种问题不玄学，纯粹是肉眼看不见。
6. 语法制导翻译之后：前端做完为什么只算走了一半
归约即执行，是这份报告里最省事也最危险的一个设计。printf写进归约动作，天然拿到了后序遍历的执行顺序，语法分析一结束，所有"执行"也做完了。对打印一句话来说这没问题，对 DBMS 来说问题就大了：归约顺序是由语法结构决定的，而你无法在解析CREATE TABLE的当下就决定要不要真的建表——表可能重名、字段类型可能非法、磁盘可能没空间，这些判断需要的信息，分散在整棵树的各个角落。
所以真实系统会在语法树和存储引擎之间插一层：归约时不执行，只搭节点；解析完成后先做语义检查（表是否存在、字段数是否匹配、类型能否隐式转换），再把树翻译成执行计划，最后交给存储层。这也是为什么很多 SQL 引擎的报错分两类——syntax error和table not found，前者来自第 4 章那张分析表，后者来自这一层。
原文的物理结构那部分空着，只有标题和"图形说明"几个占位字，这恰恰标出了从"能解析"到"能用"的分界线：CREATE TABLE的字段定义要落到一张系统表里，INSERT要按表结构把一行编码成字节，SELECT要能凭表名找到对应的数据文件。缺的不是代码量，是一份元数据设计——schema 存在哪、怎么读回来、更新时怎么保证一致。前端只关心"形状对不对"，后端才关心"东西在不在"。
从那以后我每次写带解析的项目，都会强制先把 token 流和归约序列打出来跑一遍最小样例，哪怕它能跑通——因为能跑通和按你以为的方式跑通，是两件事。希望帮到你。
本文还有配套的精品资源，点击获取
