编译原理上机：lex与yacc构建SQL词法语法分析器

简介《编译原理上机报告西安电子科技大学》面向计算机专业学习编译原理、需要完成课程上机或课程设计的学生围绕“DBMS 的设计与实现”展开重点说明如何借助 lex 与 yacc 完成词法分析、语法分析并延伸到数据库管理系统的物理结构与基本功能设计。压缩包内含 1 个 doc 文档约 82KB内容包含项目概况、分工与完成情况、编译部分实现方案、词法/语法分析、DBMS 物理结构与主要功能以及上机心得等章节结构完整适合作为报告撰写框架、实验实现思路和课程项目复盘参考。现有 1332 人学习便于读者了解西电编译原理上机报告的常见组织方式、技术路线与文档呈现重点。1. 一份“半成品”上机报告为什么反而更值得读很多编译原理上机报告的问题是把 lex 和 yacc 写得像配置文件的抄写练习——规则列出来、生成器跑通、控制台打印“Operation is ok”就算完成任务。但真正能说明问题的恰恰是那种只做了一半的系统词法和语法分析能跑语义动作还没接上数据库的物理结构画了草图却没来得及实现。这种“半成品”状态暴露了编译器构建过程中最真实的分界线——前端到底在做什么、它凭什么能被验证、以及它和后面要接的存储引擎之间到底隔了什么东西。这份报告用 Genareator 配合 VC6.0 环境把 SQL 子集拆成词法规约和产生式两套描述交给 lex 和 yacc 生成分析器。它没有把 DBMS 完整做出来但恰好把“正则匹配如何变成记号流”“上下文无关文法如何变成归约动作”这两块底层机制完整铺开了。搞懂这两块比通读一本教科书更接近编译器前端的真实运转方式。2. 词法分析为什么规则顺序比规则本身更重要2.1 lex 内部不是逐条 if-else而是一张吃字符的自动机lex 拿到.l文件后不是生成一个从上到下遍历规则的函数。它先把所有规则转成等价的非确定有限自动机再合并成一台确定有限自动机DFA。输入字符流从起始状态出发每读一个字符跳一次状态只有走到终态才吐出一个记号。这解释了为什么 lex 的匹配速度不随规则数量线性变慢规则被烧进状态转移表了运行时只做表驱动跳转。这份报告里写的规则一眼看过去是“模式和动作”的列表比如CREATE {return CREATE;}、[0-9] {return NUMBER;}但在生成器的处理顺序里它们的物理顺序影响的是 DFA 的接受优先级。常见的实现思路是当多条规则都能匹配当前前缀时lex 选择匹配长度最长的那条长度相同时选择书写位置更靠前的那条。这份实现里特意把CREATE放在[a-zA-Z][_0-9a-zA-Z()\.\*]*前面就是这个机制在起作用否则CREATE会被更长的标识符规则吃掉。词法分析这一层不讲逻辑推导讲的是“谁先到达终态、谁匹配得更远”。2.2 那几行规则里藏着三个关键设计选择第一处是把关键字和标识符分开处理所有 SQL 保留字单独列规则、直接return对应记号而普通名字走Name规则。这样做的代价是关键字规则数量随保留字表膨胀好处是词法层就完成了关键字消歧语法层的产生式不需要写ID(CREATE)这种丑东西。第二处是标识符字符集刻意放宽[a-zA-Z][_0-9a-zA-Z()\.\*]*允许名字里面带括号、点、星号。这看起来不像正经 SQL 的标识符定义但考虑到这是个上机作业后续语法里又出现了table.field这种表名点字段名的写法宽松匹配能把a.b整段先当一个Name吃进去把拆解工作留给语法层和语义动作。常见的实现思路是词法层尽量“贪吃”、语法层负责切分这样词法规则简洁但需要后续补解析逻辑。第三处是NULLX的规则直接写在保留字堆里靠字面量NULLX匹配。这意味着源码里如果出现NULLX三个字母不会走标识符路径而是被当成空值记号。这条把“空值”从标识符空间里硬挖了出来代价是用户不能再用NULLX当列名。%{ YYSTYPE YYFAR yylval *(YYSTYPE YYFAR*)yyparserptr-yylvalptr; %} \n {} {} [ \t] {/* do nothing */ } CREATE {return CREATE;} INT {return INT;} [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;}这段代码里有几处值得停下来看。yylval那行是从解析器上下文里抠出语义值指针意思是词法动作不仅能return记号类型还能往外挂载附加数据比如数字值、字符串内容。两条标识符规则——Name和ID——匹配模式几乎重叠前者字符集更宽。这种“规则近似重复”的写法是真正的危险信号如果输入abc两条规则都能匹配长度相同必须依靠书写顺序让前者生效意味着所有普通标识符都会被Name规则抢走ID规则很有可能永远走不到。这一点在后续语法层引发的冲突才能被真正暴露出来。最后printf那行属于调试痕迹正规的写法应该是在动作里给yylval赋值把原始文本挂到语法树上。2.3 单引号那处“翻车”暴露了 lex 的模式转义语义报告里专门提到“识别单引号时由于没有使用斜线标示导致无法识别”。这个坑的成因是lex 的模式区不是普通字符串单引号在某些 lex 实现里被当作引用定界符使用直接裸写可能让生成器把后续内容当成引用区匹配逻辑不按预期生效。血泪经验是在.l文件里匹配任何元字符单引号、反斜杠、点号、括号先加反斜杠再谈别的。这是词法阶段最容易被忽略的一类 bug因为生成器不报错跑起来只是某些输入流派不出记号。3. 语法分析yacc 不是在“理解语句”而是在自动做移进和归约3.1 移进-归约的本质是一台带栈的状态机yacc 生成的分析器维护一个状态栈每次从词法层取一个记号查表决定“移进”把记号压栈、跳新状态还是“归约”把栈顶若干符号按某条产生式折叠成一个非终结符。归约发生的时候挂在该产生式后面的动作代码才会执行。这意味着报告里看到的| create_st ;这些规则运行时就是一段“弹出右侧符号、压入左侧符号”的机械操作。状态表和归约动作表在生成阶段就算好了运行时不需要回头“理解”文法只需要查表。这是 LALR(1) 的核心设计取舍把复杂度推到编译期换取运行时的确定性。文法里sts那条产生式写着sts st | /* empty */形成了一个左递归加空串的经典结构。左递归让分析器能循环着把多条语句叠成一串空串给整串语句一个退出条件。这属于“语法树根节点可以零语句”的设计直接对应 SQL 脚本可以完全为空的情况。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 ; ; create_st : CREATE DATABASE Name | CREATE TABLE Name( create_field ) ;从st往下拆出八条语句分支每条都必须以分号收尾这相当于在文法层面强制了简单 SQL 脚本“一句一结束”的纪律。create_st的第二个分支值得注意建表语句在语法层只检查“表名 左括号 字段定义列表 右括号”这个骨架字段名和字段类型的组合方式被扔给了create_field和field_type两条产生式去递归展开。语法分析管的是符号之间的嵌套关系是否合法不负责检查字段名重不重复、类型长度合不合理这类检查属于语义阶段报告里明确说“不要写语义部分”把边界划得很清楚。3.2 优先级冲突用 %left 声明而不是改文法conditions的产生式里同时出现了 AND 和 OR如果不声明优先级yacc 会遇到移进-归约冲突读到一个 AND 时是先把前面的条件归约成一个conditions还是继续移进等右边的条件报告里用%left AND OR声明了结合性和优先级含义是“两者都左结合同一优先级”冲突时按先来后到归约。这等于告诉分析器“先把左边的条件折起来别贪心地往右边吃”。同样的手法出现在comp_op上 NE被定义成比较运算符但报告没有给它们声明优先级。这会在conditions里同时出现比较和逻辑运算时留下潜在隐患——a 1 AND b 2的分析树形状依赖于归约顺序如果比较运算的优先级没被声明得比 AND 高解析结果可能变成a (1 AND b) 2这种诡异结构。常见的做法是给所有运算符组都声明优先级层次避免分析器在默认规则下“猜”。3.3 语法树的数据结构其实藏在语义值类型里报告有一段“语法树主要数据结构说明”用的是示意图描述而不是代码。从%include {#define YYSTYPE int}这个声明能看出语义值被简化成了一个整数真实工程里通常会用 union 把数字、字符串、子树指针打包在一起。如果要把这份实验推到能构造 AST 的程度每个非终结符的语义值需要携带指向子节点的指针归约动作负责分配节点并按固定字段把子节点串起来。这是从“能识别语句”跨到“能表示语句”的关键一步报告没展开实现但结构上已经预留了位置。4. 语法分析里的坑为什么“看起来对”的规则会互相吃4.1 Name 和 NUMBER 的抢夺战报告里明确写了一个 bug“开始时没有考虑 Name 会将 NUMBER 截获导致数字对应的位置无法识别老实报错经过和同学讨论后进行了纠正”。这个现象是典型的词法层顺序问题但表现出来的症状在语法层插入语句INSERT INTO t VALUES (1)里的1本该是NUMBER如果[0-9]规则排在标识符规则后面又或者标识符规则允许数字开头数字就会被当成Name喂给语法分析器产生式insert_atom期待数字却收到名字直接触发语法错误。从这份实现的规则看标识符规则都要求首字符为字母理论上不该截获数字。真正的隐患在于[0-9]这条规则本身的动作只写了return NUMBER;没有把数字值挂到yylval上语法层拿到的NUMBER记号背后是空的。如果后续动作尝试读取数字值就会拿到脏数据。这在“能解析”层面不报错在“能执行”层面才是一颗雷。排查这类问题的通用手法是在词法动作里打印记号类型和原文报告里Name规则确实带了一句printf然后对比语法分析器实际收到的记号流。如果发现期待数字的位置收到了名字就回头看词法规则的书写顺序如果发现数字后面跟了错误内容就检查标识符的字符集是否包含了数字开头。4.2 左递归和空产生式一起出现的分析表风险sts: sts st | /* empty */这个结构在书上是标准写法但放到工具里跑容易遇到“空产生式归约时机”的问题。空串归约意味着分析器可以在还没看到任何记号时就先折出一个sts紧接着读入第一条语句的第一个记号移进后试图归约如果文法设计的引导符号集没覆盖全就可能报“冲突”。报告里单靠%left解决不了所有冲突最终能跑通说明实际生成的表恰好落在了可行的解析路径上换一个文法扩展方向可能就需要用%expect或者改写文法来压冲突。4.3 名字里的点号让表字段拆不开table_field: field | table.field这条产生式依赖于词法层把a.b整体当作一个记号。如果Name规则放宽了字符集分析器拿到的是单个Nametable.field这条就用不上如果词法层不放宽a.b会被拆成Name、点、Name这条产生式才有意义。一份作业里同时容忍两种写法会导致同一类输入产生两条不同的分析路径增加冲突。更干净的做法是在词法层就决定点号是独立记号还是被吞进名字里而不是两边模糊。5. DBMS 物理结构编译器前端和存储引擎之间的接缝5.1 语句被分析完之后真正的工作才开始词法和语法分析只完成了一件事把文本变成结构合法的语句表示。CREATE TABLE t (id INT)通过语法检查之后后面需要回答一系列问题——表定义存哪里、字段的偏移怎么算、插入一行时往文件哪个位置写、查询时怎么在块之间找。报告在 DBMS 部分提到了物理结构这是一个刻意留白的章节语法树负责表达“要做什么”存储层负责决定“数据放在哪、读的时候按什么路径找”。典型的简单 DBMS 物理结构分三层。最底层是定长页或数据块一页通常对应固定字节数页内按行存储记录块之间用链表或索引串联。中间层是表定义和字段目录记录表名、字段名、字段类型、字段在行内的偏移量。最上层是执行层把分析后的语句翻译成“打开哪个文件、读到第几页、从哪个偏移开始解释多少字节”。这套结构和编译器后端里的目标文件格式、段表、符号表是同一类思路语义动作知道要什么东西物理结构负责把东西放在可寻址的位置上。5.2 语法树到存储操作的映射决定了哪些语句能先被支持这份报告的语法覆盖了 CREATE、SHOW、DROP、USE、SELECT、INSERT、DELETE、UPDATE 八类语句但按执行难度分档很清楚。CREATE DATABASE和USE只需要一个目录和一个当前数据库指针映射到物理层最简单CREATE TABLE需要在元数据文件里追加一条表定义字段类型定长的情况下直接算行宽INSERT需要按行宽在数据页里找空槽位SELECT带 WHERE 条件时需要逐行读取并比较DELETE和UPDATE在页内做标记或覆盖。从简易到困难CREATE 先跑通、SELECT 随后、WHERE 条件再往上加这条顺序基本是教学型 DBMS 的共识。值得注意的是SELECT * FROM t里的*被语法规则select_name: table_fields | *处理成单独分支。物理层不需要知道星号具体展开成哪些字段它只需要从表定义里读出全部字段列表然后按行序整块返回。把“展开”这一步放在执行层而不是语法层可以让语法树保持和用户输入一一对应调试时更容易回溯是哪条语句触发了哪次读取。6. 为什么这份作业值得当成一个完整案例来读这份报告最值得看的地方不是它完成了什么而是它把“编译器前端可以独立验证”这件事做成了可运行的最小闭环。词法规则能生成记号流语法产生式能把记号流折叠成语句结构中间打印出的 “Operation is ok” 表明归约动作被执行到了。这意味着即便后面的存储层一行没写前端部分的正确性已经能被单独检查——喂一条CREATE TABLE t (id INT);看它是否走到create_st的归约分支哪怕动作里只打印一个字符串。这个分离本身是一种设计取舍。把语义动作全部写进语法产生式里、一边解析一边执行写起来快但每加一条语句都要同时改语法和执行逻辑分析器跟存储层耦合死。更可控的做法是语法归约时只构造 AST 节点执行层再遍历 AST 去调存储接口。这样词法和语法可以独立于 DBMS 的物理结构被测试调试时也能把“解析错”和“执行错”分开定位。省下来的是排查时间付出的是多一层节点分配和释放的管理成本。另一个值得注意的取舍是Name规则的宽松字符集。放宽到能吞下点号和括号让词法分析器对写法更宽容代价是语法层要靠额外产生式去拆解。换一种做法是把点号留成独立记号词法规则收紧语法层的table.field就变成自然匹配。前一种写法词法简单语法复杂后一种写法词法严格语法干净教学项目里通常偏向前者因为改.l文件比补产生式容易工程里偏向后者因为文法越干净、自动生成的冲突越少后面加新语句时越不容易踩到归约顺序的玄学。验证前端是否正确我一般会固定做三件事给一批合法语句检查每条都走到预期的归约分支给一批边界输入比如空语句串、缺分号、名字里带数字检查报错点是否停在正确层次在归约动作里打印被折叠的产生式名对比语法树的实际形状和纸上画的形状是否一致。这三步不需要存储层就能完成却能提前拦掉大部分“看起来对、跑起来错”的问题。从那以后我每次写文法都会先让归约动作只打印、不干活等树上形状确认无误再往里填语义省掉不少回头查冲突的时间。希望这份思路对你有用。本文还有配套的精品资源点击获取