2011编译原理报告复盘：lex/yacc构建SQL子集解析器避坑

简介：《编译原理上机报告（西安电子科技大学）》面向计算机专业学习编译原理、需要完成课程上机与课程设计的学生，围绕“DBMS 的设计与实现”给出完整报告范例。内容从项目概况、人员分工与完成情况切入，重点梳理基于 lex/yacc（flex/bison）的词法分析与语法分析方案，说明标记流、上下文无关文法、抽象语法树及解析策略，并延伸到 DBMS 的数据存储、索引、缓冲区与事务处理等物理结构，以及库表增删改查、索引使用和事务一致性等核心功能。压缩包仅含 1 个 doc 文件，约 82KB，便于直接查阅和整理。已有 1332 人学习，适合用作上机报告结构参考、实验思路对照与答辩准备材料，也可帮助读者理解编译技术与简单数据库系统之间的衔接方式。

1. 一份 2011 年的编译原理报告：真正值钱的部分在 lex 与 yacc 那两页

翻出这份 2011 年的编译原理报告，多数人第一眼会盯着目录里的“DBMS 的设计与实现”，以为重点在数据库；真正动手干过活的人翻到附录才发现，能用上的东西全在 lex 和 yacc 那两段规则里。它出自某高校计算机专业的一次上机任务，一人独立完成，词法与语法分析跑通了，DBMS 的物理结构和主要功能只写了设计没落地。把这份编译原理报告摊开看，它其实是一份很干净的最小 SQL 子集编译器样本：关键字表、Token 分类、产生式骨架，加上几个当年疼得记忆犹新的冲突点。下面两条线走，一条还原这份报告的骨架，一条把那些坑放到今天的工具链里重新判一遍。

2. 目标语言先钉死：SQL 子集划到哪里才算可控

拿到课程任务之后，我一般做的第一件事不是打开生成器，而是找张纸把要支持的语句一条条抄下来，抄完再决定用哪种文法、哪种工具。顺序颠倒过来的结果通常是：工具界面已经熟悉了，规则写了一半才发现还有三类语句没地方挂。这份报告在这一点上做对了，它先把语句家族列全，再往产生式入口上对号。

2.1 语句清单先列全，再谈工具选型

报告里覆盖的语句按“动词 + 宾语”来切，不是按语法结构切。这个切法值得照搬，因为它和词法层的关键字表、语法层的入口符号基本是一一对应的，不容易漏项，也不容易把两种语义上无关的语句混进同一条产生式。

从表里能看出一件事：这些语句的复杂度差得很远。create_st 只要处理字段列表的递归就够了，成本花在field type这一层的展开上；select_st 则偷懒到 WHERE 后面只能跟一个 conditions，没有 GROUP BY、没有 ORDER BY、没有 JOIN，连子查询都用注释挂起来了。delete_st 和 update_st 更极端，产生式里绑死了必须带 WHERE——真实产品里不带 WHERE 的 DELETE 是合法语句，只是危险，这里直接在文法层面把这种写法判死。当年这么写是聪明的取舍，课程测试用例基本不会卡这些；今天要复现，你得先明确自己是不是也只打算覆盖这批用例，否则文法一放开，冲突数量会立刻翻几倍。

不肯把范围铺大，还有一个更现实的原因：完整 SQL 的文法随便一展开就是上千条产生式，一个上机周期里根本不可能全做对。这份报告做了一个很务实的减法，把子查询、参数占位、VALUES后面跟查询这一整类全用注释挂在 insert_st 下面。减法本身是对的，问题是挂起来之后没人回头补，报告里也没有一句显式的“以下写法不支持”。熟手翻这类报告最容易在这一层被误导，看到注释以为只是暂时注释，其实那条分支从来没跑通过。

2.2 关键字、标识符、数字的边界怎么划

关键字表是从产生式往回推出来的，一共二十来个保留字：CREATE、DATABASE、DATABASES、USE、SHOW、TABLE、TABLES、SELECT、DELETE、INSERT、VALUES、UPDATE、DROP、EXIT、NULLX、INT、CHAR、AND、OR、WHERE、INTO、SET、FROM。这份清单有个细节，DATABASE 和 DATABASES、TABLE 和 TABLES 是两组独立的 token，不是靠单复数规则推导出来的。看起来笨，但对词法分析器来说这是最省事的做法，词法层不做任何形态判断，一个字符串对一个 token，边界一目了然。

真正需要先想清楚的是标识符和数字的边界。字段名能不能带数字？表名能不能带下划线？这份报告给的规则是三条：

[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; }

第二条是这份报告里最需要警惕的一行。字符集里塞了圆括号、点号和星号，本意是想让table.field、count(*)这类写法在词法层一次吃完，省掉语法层的拼接。思路能理解，代价却是后面分析器再也分不开“标识符”和“标点”——一个t1(会被当成一个完整的 Name，右括号和后面的内容全被吞掉。正确的切法是词法层只管原子，标点就是标点，table.field交给语法层的table '.' field去拼，多写一条产生式，换来的是整条链路可调试。

2.3 工具链：带向导的生成器加老编译环境，这套组合的取舍

报告里写的编程环境是 Generator 和 VC++6.0。Generator 这类带 ParserWizard 的工具，和标准 lex/yacc 的差别主要在骨架：它生成的是 C++ 类，%name mylexer定类名，构造函数、析构函数、规则区三段分开写，动作里要拿语义值得走yyparserptr->yylvalptr绕一圈，入口也不是裸的yyparse()，而是parser.yycreate(&lexer)之后调yyparse()。好处是不用自己搭yyin、yyout那一套标准输入输出的脚手架，坏处是报错信息比原生 lex 更绕，规则写错时它不一定告诉你哪一行，只丢一个文法冲突数量出来。

VC++6.0 放到今天是古董，但它有个实际的好处：编译错误少、行为稳定、不会因为 C 标准版本差异把老代码判死。真要复现这套东西，用现在的 gcc 或 clang 去编生成出来的 C++，大概率会撞上一堆隐式类型转换告警，把告警当错误一开就过不去。我的做法是先把整个东西当黑匣子跑通，确认规约没问题，再逐个文件降告警，别一上来就跟编译器较劲，那是最容易把心态搞崩的一步。

3. 词法分析那一层：lex 规则怎么写才不互相截胡

词法分析这段是整份报告里信息密度最高的部分，也是最容易照着抄出错的地方。lex 类的工具判定规则只有两条：最长匹配优先，长度相同时按规则出现的先后顺序。这两条听起来简单，实际写起来几乎所有的“莫名其妙不识别”都是它们俩打架的结果。

3.1 规则顺序即优先级：关键字放前面，标识符垫后

报告里关键字规则全部排在标识符规则之前，这个顺序不是随手写的。CREATE 这六个大写字母，同样能被[a-zA-Z][_0-9a-zA-Z()\.\*]*这条规则匹配上，两条规则命中的长度一样，这时候谁在前谁赢。关键字在前，CREATE 就是 CREATE；关键字在后，它就变成了一个普通 Name，语法分析器那边再等 CREATE 这个 token 就永远等不到，报出来的错会指向一条完全无关的产生式。

同理，多字符运算符必须排在单字符运算符前面。!=和=这两条，如果"="写在"!="前面，输入a != 1时第一个字符!没有规则能匹配，词法分析器要么报错要么跳过，两种结果都很难查。这份报告里"!="单独给了一个 NE token，顺序也放在了"="之后，靠的正是长度优先这一条兜住——两个字符比一个字符长，所以!=先命中。能跑，但我一般会把多字符的明确写在前面，不依赖这条隐式规则，毕竟换个工具这条规则未必一样。

还有一个容易忽略的点：空白和换行必须单独给规则。报告里[ \t]什么都不做直接丢掉，"\n"单独一条也是空的。为什么换行不能并进空白里一起丢？一是行号统计需要在换行时自增，二是某些生成器对\n的处理和空格不一样，混在一起写会在跨平台时出玄学问题。

3.2 单引号、空白、换行这些看不见的坑

报告里明确记了一个问题：识别单引号时没加斜线标示，导致无法识别。这个描述很短，但背后的坑挺典型。在规则文件里，单引号本身就是规则语法的一部分，它既用来界定规则模式，又可能是你要匹配的字符，两种角色撞在一起，解析器会按它自己的理解切分，最后你得到一条语法上合法、语义上完全不是你想要的规则。

正确的写法有两种，一种是用双引号把单引号包起来写成"'"，另一种是加反斜线写成\'。前者可读性更好，后者在大多数工具里都能用。这份报告最后采用的是给单引号单独一条规则、动作留空的方式，等于把字符常量这一整类先跳过去，不算最优解，但在只跑关键字和标识符的场景下足够。

空白字符的处理也有讲究。[ \t]这条规则动作是空的，看起来什么都没做，实际上它把制表符和空格从 token 流里筛掉了，让语法分析器只看到有意义的符号。如果没有这条规则，输入里每多一个空格，词法分析器就会报一个无法识别的字符，错误信息还会指向正确的行号，让人以为是文法写错了。

3.3 Name 与 ID 同时存在时怎么收口

这份报告里同时存在 Name 和 ID 两个标识符 token，这个设计本身就有问题。看规则就明白：Name 的字符集是[a-zA-Z][_0-9a-zA-Z()\.\*]*，ID 的字符集是[a-zA-Z][_a-zA-Z0-9]+，前者是后者的超集，而且排在前面。结果是任何能被 ID 匹配的输入，都能被 Name 匹配，且 Name 排在前面，ID 这条规则实质上永远不会被触发，等于写了一条死规则。

更麻烦的是 ID 的字符集要求至少两个字符，单字母标识符匹配不上，会掉到 Name 里去。这在测试阶段不容易发现，因为大家习惯用t1、user_name这种名字，长度都够；一旦有人写a，行为就变了。这种“只在特定输入下暴露”的问题，比直接报错难查得多。

要收口不难，把 Name 的字符集收窄成标准的标识符字符集，点号、括号、星号全部拿出来单独给规则：

[0-9]+ { return NUMBER; } [a-zA-Z_][a-zA-Z_0-9]* { return Name; } "." { return '.'; } "*" { return '*'; } "(" { return '('; }

改完之后table.field会变成 Name、.、Name 三个 token，语法层用table_field: table '.' field接住。看起来多了一层，但换来的是词法层可预测：任何一个 token 的长度和边界都能从字符集直接推出来，不用再猜哪条规则先命中。

3.4 用一段输入验证 token 流

规则写完别急着上完整语句，先用一段最小输入把 token 流打出来看。这一步花五分钟，能省掉后面几小时的文法排查。

# 把最小输入喂给生成出来的分析器，只看它吐出什么 echo "CREATE TABLE t1 (id INT);" > in.sql ./sqlparse < in.sql

期望的 token 序列大致是这样：

这张表里最值得盯的是t1和(两行。用原来的宽字符集，t1(会被整体吃成一个 Name，后面全部错位，报错点会落在INT上，看起来像是类型关键字没定义，实际是上一行的问题。先验证 token 流再看文法，就是避免这种错位背锅。

4. 语法分析那一层：产生式、优先级与语法树的落地

词法层把字符流切成 token，语法层负责把这些 token 组织成结构。这份报告的文法写得相当紧凑，三十条左右的产生式覆盖了八类语句，骨架清晰，但也有几处典型的写法问题，正好拿来当反面教材。

4.1 从 sts 开始符到八类语句的骨架

开始符是 sts，第一条产生式承担的是“语句序列”的角色：

sts: sts st { /* 每条语句解析完，这里打一行确认日志 */ } | /* empty */ ; st: create_st ';' | show_st ';' | drop_st ';' | use_st ';' | select_st ';' | delete_st ';' | update_st ';' | insert_st ';' ;

sts: sts st这个左递归写法，等价于正则表达式里的闭包，意思是一个语句序列由一条或多条语句组成，每条语句后面跟一个分号。左递归在这里是必须的，不是风格选择——yacc 这类自底向上的分析器处理左递归是常数栈，处理右递归sts: st sts会把整个输入压进栈里，输入一长就爆栈。

八条语句分支全部挂在 st 下面，每条后面统一跟分号，这个写法把“语句边界”这件事收敛到一处，后面要加分号可选之类的调整，只改这一层就行，不用动八条具体的语句规则。报告里这部分的骨架是对的，可以直接照搬。

4.2 左递归与优先级：AND/OR 必须 %left

conditions 这条产生式是整份文法里最容易出冲突的地方：

conditions: condition | '(' conditions ')' | conditions AND conditions | conditions OR conditions ;

问题出在后两条上。A AND B OR C这个输入，分析器读到 OR 的时候面临一个选择：是先把A AND B归约成一个 conditions，还是把 OR 移进栈里继续等。这个选择就是移进/归约冲突。不打优先级声明的话，yacc 默认选择移进，结果就是表达式变成右结合，A AND B OR C会被解析成A AND (B OR C)，和 SQL 的实际语义完全相反。

报告里给了%left AND OR，一行解决冲突。能跑，但这一行把 AND 和 OR 设成了同一优先级、都是左结合。SQL 里 AND 的优先级高于 OR，A OR B AND C应该是A OR (B AND C)。当年的测试用例大概没混用过 AND 和 OR，所以没暴露。要改对，拆成两行、按优先级从低到高排：

%left OR /* 先声明的优先级低 */ %left AND /* 后声明的优先级高 */ %left '=' NE '<' '>' %left '(' ')'

yacc 的规矩是后声明的优先级更高，所以把 OR 写在前面，AND 写在后面，比较运算符再往后，优先级就对了。这张优先级表值得单独记一下，换任何工具都是同一套逻辑：

4.3 条件表达式与表字段的递归写法

条件和字段这两组产生式值得单独拎出来看，因为它们是递归下降和自底向上都要处理的核心结构：

table_field: field | table '.' field ; table_fields: table_field | table_fields ',' table_field ; condition: comp_left comp_op comp_right ; comp_left: table_field ; comp_right: table_field | NUMBER ; comp_op: '<' | '>' | '=' | NE ;

table_fields这条是标准的左递归列表，逗号分隔的字段名，注意它在第二条分支里递归引用自己，这样a, b, c会一层层规约成列表。table_field这条分支处理带表名前缀的字段，WHERE t1.id = 1这种写法就靠它接住。

这里有个不对称的地方：comp_left 只允许 table_field，comp_right 允许 table_field 和 NUMBER。也就是说id = 1合法，1 = id不合法，id = other_id合法，1 = 1不合法。这不是有意设计，是漏了。要补的话把 comp_left 也改成table_field | NUMBER就行，代价是多一条二义性，NUMBER comp_op NUMBER这条会产生新的移进/归约冲突，得再压一次优先级。

还有个隐患藏在field: Name这条规则里。它不区分关键字和标识符，所以SELECT SELECT FROM t里的第二个 SELECT 会被当成字段名接住，不报错。要挡这个，得在 field 的规则里显式排除关键字，或者在语法分析之前加一步保留字检查。课程作业阶段这通常不是问题，真实场景里这是必补的一环。

4.4 语法树数据结构与三类语句的图形验证

报告里把语法树的数据结构描述了一番，列举了 CREATE TABLE、SELECT、INSERT 三类语句的树形。这部分内容本身没问题，问题在于它和代码没对上。看属性类型的声明：

%include { #ifndef YYSTYPE #define YYSTYPE int #endif }

YYSTYPE 定义成 int，意味着每条产生式的语义值只能是一个整数。这种配置下没法挂树节点指针，也没法挂字符串，语义动作基本只能干两件事：计数或者打日志。报告里画出来的那些树，是画在纸上和文档里的，不是运行时产出的。这是个很典型的状态——文法通了，语义还没开始。

要真正产树，属性类型至少得改成联合：

%union { int ival; /* NUMBER 这类整数常量 */ char *sval; /* Name 这类标识符文本 */ struct Node *node; /* 语法树节点 */ }

然后每个非终结符用%type <node>声明它产出的节点类型，终结符用<ival>或<sval>。改完之后，每条规则的动作里要自己分配节点、挂子节点、最后把根节点返回给调用方。这一步的工作量比词法加语法全加起来还大，但它是“能解析”和“能执行”之间的分水岭。报告止步在这条线之前，这一点写得很诚实。

5. 避坑记录：五个当年真翻车的位置

这段是从报告正文和附录里能反推出来的实际故障，不是事后编的。每一条都按“现象 → 原因 → 解决”走，顺序按踩到的先后排。

5.1 单引号规则不识别

现象：规则写进去之后，输入里只要出现单引号，词法分析器就报无法识别的字符，报错行号是对的，但看不出规则哪里写错了。

原因：规则文件里单引号本身是语法符号，直接把它当成要匹配的目标写，解析器会按自己的规则切分，最后得到的是一条语义不对的规则。

解决：改用双引号包裹"'"，或者加反斜线\'。改完先单独喂一个只含单引号的输入，确认它能出一个 token，再放回完整规则里。

5.2 Name 规则把括号和数字一起吃掉

现象：CREATE TABLE t1 (id INT)这种输入解析失败，报错点落在 INT 上，提示类型关键字位置不对。

原因：Name 的字符集里包含(、)、.、*，t1(被整体匹配成一个 Name，token 流变成 CREATE、TABLE、t1(、id……后面的括号和类型全错位。

解决：收窄 Name 的字符集到标准标识符，符号单独给规则。改完之后用 3.4 那张 token 表逐行核对，确认每个符号都单独出 token。

5.3 NUMBER 位置被 Name 截获

现象：INSERT INTO t VALUES (1)里的数字 1 识别不出来，或者被识别成标识符，报错位置在 VALUES 后面。

原因：数字规则和标识符规则的顺序、字符集没对齐。如果标识符规则允许数字开头，或者数字规则排在标识符规则之后，纯数字输入会优先命中标识符。这份报告里 Name 规则本身不允许数字开头，但宽字符集导致1)这种组合被前一条规则吃掉一半，表现和截获一样。

解决：数字规则放在所有标识符规则之前，标识符字符集不允许数字开头，两组规则之间的边界用输入验证，别靠推理。

5.4 YYSTYPE 定成 int，语义动作只能打日志

现象：文法跑通了，日志能打出来，但拿不到任何结构信息，语法树只能画在纸上。

原因：属性类型是 int，塞不进指针和字符串，语义动作没有可用的载体。

解决：改成%union，给每个非终结符声明%type，动作里手动建节点。这一步要在文法稳定之后做，文法还在改的时候建树是自找麻烦。

5.5 DBMS 部分只有设计没有实现

现象：报告里 DBMS 的物理结构和主要功能写了两节，但对应代码一行没有，评审时容易被追问。

原因：上机周期只够做词法加语法，DBMS 部分留在了设计阶段。

解决：把这两节明确标成“设计阶段”，写清楚哪些组件打算怎么实现、依赖哪个模块，别写得像已经跑通了。真要做，最小可跑版本是文件级的表存储加顺序扫描，别一上来就奔 B 树。

6. 从报告到可运行：四步验证流程与一个收尾习惯

把这份报告变成能跑的东西，我的做法是四步，每一步都有一个明确的验收点，任何一步不过就不往下走。

第一步，先把语句清单和 token 清单写成两张表，不碰工具。表里的每一行都要能对应到一条产生式或者一条词法规则，对不上的就是还没想清楚的部分。第二步，词法规则单独跑，只验证 token 流，用 3.4 那张表逐行对，确认关键字、标识符、数字、符号四类边界都清楚。第三步，文法规则单独跑，先喂最简单的CREATE DATABASE db1;，再一条条加到八类语句，每加一条看一次冲突数量，冲突不为零就停下来改文法，别靠%expect压。第四步，才动语义动作，把属性类型改成 union，建最简的语法树节点，打印出来和纸上的树对一遍。

# 词法与语法分别过生成器，再链接成一个可执行程序 lex mylexer.l # 产出词法分析器源码 yacc -d myparser.y # -d 额外产出 token 编号头文件，供词法层 include cc mylexer.c myparser.c -o sqlparse # 链接，-o 指定输出名 echo "SHOW TABLES;" | ./sqlparse # 用最小输入验证端到端能否走通

这里的-d是必须的，词法规则里引用的那些 token 常量要有地方定义，就是它生出来的那个头文件。cc换成 g++ 也行，但要注意生成器产出的代码如果是 C++ 类结构，就必须用 C++ 编译器链接，混用会在链接阶段报一堆找不到符号。

这套流程跑完，你会得到一份和这份报告结构相同、但每一层都验证过的东西。它未必比当年的版本功能多，但每个失败点都能定位到具体哪一层，这比多支持两条语句值钱得多。

回过头看，我后来每次碰文法类的东西，都会强制先写两张表、先验证 token 流，再碰产生式。这个习惯就是从这份报告里那几个“报错点落在下一行”的坑里长出来的。那份原始材料就放在那儿，词法规则、产生式、语法树结构都是现成的骨架，拿去对着改一遍，比自己从零摸索省太多时间。希望帮到你。

本文还有配套的精品资源，点击获取