从lex/yacc到LR分析：SQL词法语法解析核心机制与避坑

简介这份编译原理上机报告面向正在完成课程设计、需要参考编译器与小型 DBMS 实现思路的计算机专业学生选题为“DBMS 的设计与实现”。报告以单份 doc 文档交付压缩包共 1 个文件、约 82KB正文按项目概况、编译部分、DBMS 部分与总结展开记录了基于 lex 和 yacc 的词法、语法分析方案Token 结构、正规式定义、VC6.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时既可以解析成(a1 AND b2) OR c3也可以解析成a1 AND (b2 OR c3)语法树形状不同求值结果就不同。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 ANDyacc 里越靠后声明的优先级越高。这是个很典型的翻车点测试用例恰好都只覆盖了前一种顺序程序跑起来一切正常。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 流和归约序列打出来跑一遍最小样例哪怕它能跑通——因为能跑通和按你以为的方式跑通是两件事。希望帮到你。本文还有配套的精品资源点击获取