从 lex/yacc 到 SQL 执行：编译原理前端与 AST 落地

简介面向编译原理课程设计与上机实践场景的《DBMS 的设计与实现》报告适合计算机科学与技术等专业学生参考编译器构建与数据库管理系统入门实现的完整思路。报告围绕项目概况、编译部分、DBMS 部分和总结展开涵盖开发环境与工具、词法分析、语法分析、物理结构及主要功能等内容并结合 lex/yacc 的使用说明语句解析流程。压缩包内共 1 个 doc 文件约 82KB以课程报告文档形式呈现便于直接查阅和整理报告结构。已有 1332 人学习内容预览可见其包含人员分工、完成情况、正规式与词法分析代码片段、上机心得等能帮助读者了解从词法/语法分析到简单 DBMS 功能设计的组织方式也可作为撰写上机报告、梳理实验步骤和复盘实现难点的参考。1. 手写一个 SQL 子集的编译器比读十页龙书更管用有个朋友接了个课设辅导的活学生交上来的东西是“能识别 CREATE TABLE、SELECT、INSERT 这些语句但一句也不会执行”。听起来像半成品其实这恰恰是编译原理上机最有价值的那一段词法分析和语法分析占到了整个工作量的大头也是最容易出错、最能看出功底的地方。这份报告做的事情就是拿一个 DBMS 的 SQL 子集当靶子用 lex/yacc 把词法、语法前端搭起来再往 DBMS 的物理结构和执行流程上对接。它适合两类人看一类是要交编译原理课设、需要一份能跑通的参考骨架的人另一类是已经工作、想回头补一遍“正则式怎么落到 token、产生式怎么落到语法树”的人。工具链很老思路不老——报告里对 Token 结构、关键字匹配顺序、Name 与 ID 抢字符这些细节的记录放到今天手写递归下降或者补 flex/bison 都还能直接用上。2. 工程骨架与工具链Generator VC6.0 里那份报告的三层结构2.1 报告拆开是三块词法前端、语法前端、DBMS 执行把目录翻一遍能看出来整份东西不是一篇“讲编译原理”的文章而是一个三段式的工程第一段是词法分析用 lex 风格的规则文件把 SQL 文本切成 token第二段是语法分析用 yacc 风格的产生式把 token 流归约成语句结构第三段是 DBMS负责建库建表、字段定义、记录的物理存放和语句的执行。这三段在代码组织上是解耦的。词法部分只对外暴露一个“给我下一个 token”的接口语法部分只依赖 token 类型和值不关心字符是怎么被吃掉的DBMS 部分只关心“来了一条什么样的语句”不关心这条语句是手敲的还是解析出来的。这种切法在 2011 年的上机作业里算是比较规矩的做法常见做法是把三块全塞进一个 main 函数改一个关键字要全文搜索那才是真正的血泪经验。报告里给出的完成度也很诚实词法和语法部分完成DBMS 部分只写到物理结构设计和功能描述尚未落地。所以读这份材料时要有个心理预期——前面两段可以直接抄作业后面那段得自己补。2.2 lex/yacc 的代码生成链路.l 和 .y 怎么变成 .cpp报告里写的环境是 Generator 加 VC6.0。这里的 Generator 指的是那类 Parser Generator 工具它的特点是直接产出 C 类——词法器叫mylexer、语法器叫myparser各自带构造函数、析构函数和yycreate/yyparse成员函数和 Unix 下裸 flex/bison 产出的 C 数组风格不一样。文件头那句注释已经说明了来源%{ /**************************************************************************** mylexer.l ParserWizard generated Lex file. Date: 2011年4月12日 ****************************************************************************/ #include myparser.h #include define.h %} %name mylexer %%这段是 lex 文件的第一段声明段%{ %}之间的内容会被原样抄进生成的.cpp文件顶部所以头文件包含、宏定义、全局变量都写在这里。%name mylexer指定生成类的名字后面{ }包起来的部分是类成员、构造函数、析构函数这份报告里全是空的说明作者没用到额外状态。第二段%%之后是规则段第三段%%之后是用户代码段。这种三段式是 lex 的固定骨架换成 flex 也一样只是%name没有对应物得靠%option prefixmy之类的选项去改符号前缀。真正要理解的是生成链路.l文件不是 C 源码得先过一遍 Generator产出mylexer.cpp和mylexer.h.y文件同样过一遍产出myparser.cpp和myparser.h。然后才是 VC6.0 把它们和define.h、main.cpp一起编译链接。顺序错了就会看到一堆“找不到 myparser.h”的报错。2.3 生成产物清单与编译顺序把工程文件摊开大致是这么几类文件来源作用是否手写mylexer.l手写词法规则、关键字表是myparser.y手写产生式、token 声明是define.h手写token 编号、公共结构是mylexer.cpp/.hGenerator 生成词法器实现否myparser.cpp/.hGenerator 生成语法器实现否main.cpp手写创建两个对象并启动解析是main.cpp在报告里也贴出来了短得有点反直觉int main(void) { int n 1; mylexer lexer; myparser parser; if (parser.yycreate(lexer)) { if (lexer.yycreate(parser)) { n parser.yyparse(); } } return n; }这里的关键是yycreate的双向绑定parser.yycreate(lexer)把词法器指针挂到语法器上lexer.yycreate(parser)反过来把语法器挂到词法器上。为什么要互相挂因为语法器需要“取下一个 token”而词法器在动作里需要拿到yylval的引用规则段开头那行YYSTYPE YYFAR yylval *(YYSTYPE YYFAR*)yyparserptr-yylvalptr;就是在干这事。单向绑定也能跑但语义值传不回去。参数说明yycreate返回非零表示初始化成功两个都成功才调yyparse()返回值n就是解析结果通常 0 表示语法分析正常结束。这种“层层嵌套 if”的写法在 C 里不好看但胜在不用处理异常。2.4 搬到现代工具链flex/bison 的等价命令如果不想折腾 VC6.0把这套东西搬到 Linux 上其实很快。工具换名字流程不变# 1. 生成词法器与语法器 C 源码 flex -o mylexer.c mylexer.l bison -d -o myparser.c myparser.y # 2. 编译链接注意 -d 生成的 myparser.h 要先被包含 gcc -c mylexer.c myparser.c main.c gcc -o sqldemo mylexer.o myparser.o main.o-d的作用是让 bison 额外生成头文件把 token 编号用enum yytokentype导出来替代原来手写的define.h。-o指定输出文件名不指定的话 flex 默认产出lex.yy.c、bison 产出y.tab.c混在一起很难管。这套命令我一般放在 Makefile 里改.l就make一下比在 IDE 里点半天菜单省事。需要注意的差异bison 生成的解析器是yyparse()全局函数不是类语义值叫yylval类型用%union定义词法器里返回 token 的写法return CREATE;可以直接沿用。改造成本主要在把yycreate那套对象化的初始化换成全局变量半小时的活。3. 词法分析mylexer.l 里的 Token 定义与关键字规则3.1 Token 结构与 define.h 的约定词法器的产出物是一个个 tokentoken 至少要有两样东西它是什么类型、它的值是什么。报告里定义的struct Token有三字段struct Token { int type; /* token 类型对应 define.h 里的宏 */ char *yych; /* 词素原文比如表名、字段名 */ int value; /* 数值型 token 的值 */ };type是语法器唯一认的东西语法产生式里写的CREATE、Name、NUMBER全部是type的取值。yych存原始字符串建表语句里的表名、字段名都靠它往下传因为语法器不知道“users”这个词长什么样它只收到一个Name和一段字符串。value只在数字场景用得上CHAR(20)里的 20 就得从这里取。这种“类型 原文 数值”的三件套几乎是所有教学型词法器的标配。实际工程里更常见的是一个union加一个kind字段省内存但教学代码用结构体更直观调试时printf一下就能看到全部信息属于可接受的浪费。3.2 mylexer.l 的三段式结构规则段是整份词法文件的核心把关键字全列了一遍%% \n { /* 换行直接丢弃 */ } { /* 单引号原报告这里写法有问题见第 5 章 */ } [ \t] { /* 空白字符跳过 */ } CREATE { return CREATE; } DATABASE { return DATABASE; } DATABASES { return DATABASES; } USE { return USE; } SHOW { return SHOW; } TABLE { return TABLE; } TABLES { return TABLES; } SELECT { return SELECT; } DELETE { return DELETE; } INSERT { return INSERT; } VALUES { return VALUES; } UPDATE { return UPDATE; } DROP { return DROP; } EXIT { return EXIT; } INT { return INT; } CHAR { return CHAR; } AND { return AND; } OR { return OR; } WHERE { return WHERE; } INTO { return INTO; } SET { return SET; } FROM { return FROM; } ( { return (; } ) { return ); } ; { return ;; } , { return ,; } * { return *; } { return ; } { return ; } { return ; } ! { return NE; } [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; } %%规则的读法是“左边模式右边动作”。带双引号的模式是字面量匹配匹配上就把对应的 token 编号返回给语法器[0-9]是正则匹配一串数字。单字符运算符直接返回字符本身因为 yacc 允许产生式里写(这样的字符字面量省去一堆 token 定义。yytext是 flex/lex 内置的指针指向本次匹配到的原始文本。printf(%s, yytext)那行其实是调试残留正式版应该删掉或者改成写yylval.yych否则每识别到一个名字就往屏幕上吐一次输出会乱成一锅粥。3.3 关键字表与最长匹配为什么 Name 规则放在 ID 前面看最后两条规则的顺序很有讲究[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; }lex 的匹配原则是“最长匹配优先长度相同则靠前的规则优先”。Name那条允许字符里出现括号、点号和星号是为了兼容db.tbl这种带库名前缀的写法以及t.*这种通配ID那条只允许下划线和字母数字是标准的标识符形态。两条都能匹配users这个串长度一样谁在前面谁赢所以Name被放在了前面。这个顺序直接决定了语法器收到的 token 种类所有裸标识符都变成NameID实际上很难被触发。这在当时的测试用例里没出问题但埋了个坑——第 5 章会专门说NUMBER被Name抢走的那次翻车。顺带说一句关键字用CREATE这种字面量规则、标识符用正则规则两者不会打架CREATE匹配长度 6但Name规则也能匹配CREATE且长度相同靠前的字面量规则赢所以关键字优先级天然高于标识符。这是 lex 最省心的一点不需要像手写词法器那样维护一张哈希表再判断“这个词是不是关键字”。3.4 单引号与空白处理的那点事空白处理用的是[ \t] { }动作体是空的意思是匹配到空格或制表符就什么也不返回词法器继续找下一个能返回 token 的模式。换行同理。这种“吞掉不返回”的规则必须写在前面否则空格会被当成未识别字符触发默认动作一般是回显到标准输出看着像程序出了玄学问题。单引号那条规则是整份文件里唯一明显写错的在 lex 里不是一个合法的单引号匹配。要在规则里匹配一个单引号字符得写成\或者用双引号包起来。报告作者在“存在问题及解决方法”里也承认了这一点说“在识别单引号时由于没有使用斜线标示导致无法识别”后来翻了课本才改对。这条记录挺真实的因为单引号在 SQL 里是字符串常量的边界一旦识别不了INSERT INTO t VALUES (abc)这种语句从词法层就断了。修法很简单把规则改成 { return \; } /* 字符串常量起始/结束 */ [ \t\n] { /* 统一吞掉所有空白 */ }\是 C 里的转义单引号字符常量作为 token 编号返回给语法器语法器那边用\接住配对逻辑就通了。这一步看着小但不修的话后面所有带字符串的 INSERT 都过不了属于“卡在最前面”的那类问题。4. 语法分析myparser.y 产生式与语法树落地4.1 声明段%token 与优先级声明.y文件和.l的结构对称也是三段。声明段先解决“有哪些 token”%include { #ifndef YYSTYPE #define YYSTYPE int #endif } %token ID NUMBER Name %token CREATE USE SHOW DROP %token SELECT INSERT VALUES DELETE UPDATE %token TABLE DATABASE TABLES DATABASES %token CHAR INT NULLX %token EXIT %token WHERE INTO SET FROM %token ( ) * %token NE %left AND OR %token , ; %%%token是告诉语法器“这个词法层会送过来”名字和.l里return的一致。单字符的(、)也声明了一遍其实 yacc 允许直接用字符字面量而不声明写上去纯粹是为了读着清楚。%left AND OR是唯一一条优先级声明含义是AND和OR左结合、优先级相同。这条声明直接影响WHERE a 1 AND b 2 OR c 3这种条件串的解析树形状。严格说AND的优先级应该高于OR写成两行%left OR在前、%left AND在后才对报告里合并成一行等于把两者当同级别处理条件表达式会出现结合性歧义。这是教学代码常见的简化功能上不影响跑通但语义上是错的。YYSTYPE在这里被定义成int说明语义值只传整数。这对教学够用但一旦要在归约动作里传字符串表名、字段名就得改成union或者结构体指针。报告里没做这一步语法树是“打出来看的”不是“存下来用的”这也是为什么它只能验证语法正确、不能真正执行。4.2 sts 与 st语句列表的闭包写法规则段开头两条产生式决定了整个程序的骨架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 ; ;sts是开始符第一个产生式sts st是标准的左递归写法作用等价于正则里的st*——允许一个程序里连续写多条语句每条以分号结尾。第二条空产生式让“空输入”也能合法归约否则空文件会直接报语法错误。左递归在这里不是随便写的yacc 是 LALR(1) 解析器左递归产生式消耗栈空间恒定右递归写多了反而容易栈溢出而且左递归配%left声明消除冲突更自然。st是语句分派点八条产生式对应八种顶层语句每条都强制以;结尾。这个设计把“语句之间怎么分隔”这件事收敛到了一处后面加新语句类型只要在st上加一条分支sts完全不用动。我更倾向于把;放进各个子产生式里比如create_st: CREATE DATABASE Name ;好处是报错位置更准——现在如果漏了分号错误会报在st这个非终结符上不告诉你到底哪条语句缺了。4.3 各语句产生式的拆解建表这条最能看出“用产生式描述结构”的写法create_st : CREATE DATABASE Name | CREATE TABLE Name ( create_field ) ; create_field: create_field , field_type | field_type ; field_type : field type ; type : CHAR ( NUMBER ) | INT ;读法是自上而下递归。CREATE TABLE后面跟表名然后一对括号括号里是字段列表字段列表用左递归展开成字段, 字段, 字段最少一个字段每个字段是“名字 类型”类型要么是INT要么是CHAR(n)其中 n 是数字 token。这里的嵌套层次是create_st → create_field → field_type → type四层。层数多不是坏事每一层对应一个语义单位字段列表、字段定义、类型后面写语义动作的时候正好一层挂一个动作。挤成一条产生式也能解析但动作就没地方挂了。查询和更新这两条稍微复杂些select_st : SELECT select_name FROM tables | SELECT select_name FROM tables WHERE conditions ; select_name : table_fields | * ; update_st : UPDATE table SET set_fields WHERE conditions ; set_fields : set_field | set_field , set_field ; set_field : comp_left comp_op comp_right ; conditions : condition | ( conditions ) | conditions AND conditions | conditions OR conditions ; condition : comp_left comp_op comp_right ; comp_left : table_field ; comp_right : table_field | NUMBER ; comp_op : | | | NE ;conditions是标准的二元表达式文法带括号、带AND/OR递归。conditions AND conditions和%left AND OR配合能正确消掉二义性——没有优先级声明的话这种产生式会产生移进-归约冲突yacc 会警告“conflicts: 1 shift/reduce”然后按默认策略移进处理结果可能和你想的不一样。comp_right只允许table_field或NUMBER也就是说WHERE a b和WHERE a 1都能解析但WHERE a abc不行因为词法层的字符串 token 没接进来。这个限制在报告当时的完成度下是合理的补的话在comp_right上加一条| literal、literal里加Name | NUMBER | STRING即可。4.4 语法树的数据结构与从归约到执行的衔接报告里用图形描述了典型语句的语法树比如CREATE TABLE那棵树的形状是根节点CREATE TABLE、两个子节点分别是表名和字段定义SELECT * FROM t WHERE a 1的树根是SELECT下面挂字段列表、表名、条件子树。图形是给人看的代码要落地得有一个结构体/* 语法树节点教学版够用工程版要加链表挂兄弟节点 */ typedef enum { N_STMT_LIST, N_CREATE_DB, N_CREATE_TABLE, N_SELECT, N_INSERT, N_UPDATE, N_DELETE, N_DROP } NodeKind; typedef struct AstNode { NodeKind kind; /* 节点类型决定怎么解释后续字段 */ struct AstNode *child; /* 第一个子节点 */ struct AstNode *next; /* 兄弟节点构成列表 */ char *name; /* 表名/字段名/库名 */ int ival; /* 类型长度、数字常量 */ char op; /* 比较运算符 或 NE */ } AstNode;字段说明一下child和next这套“左孩子右兄弟”的表示法是为了让create_field这种列表型产生式能挂成链不用给每种节点写不同的结构体name存yych里那份原文用完要strdup不能直接指yytext因为yytext指向的缓冲区下一轮就被覆盖了这是新手最容易翻车的地方ival同时承担CHAR(20)的长度和WHERE a 1里的常量靠kind区分场景。有了这个结构归约动作就从printf变成建节点create_st : CREATE TABLE Name ( create_field ) { $$ mk_node(N_CREATE_TABLE); $$-name strdup($3); /* 表名 */ $$-child $5; /* 字段链表 */ } ;$$是归约结果的语义值$3、$5是产生式右部第 3、5 个符号的语义值。mk_node是自己写的分配函数负责把child/next置空。这样一条CREATE TABLE语句解析完根节点就握在sts的语义值里交给 DBMS 层去执行——执行层只需要按kind做 switch取name建表、遍历child建字段完全不用回头碰词法和语法。这条“语法树 → 执行”的边界就是编译器前端的终点。报告里 DBMS 部分描述的物理结构数据文件、表定义、记录布局之所以没写代码卡的就是这一步没有 AST执行层拿不到结构化的语句只能靠全局变量传参写出来必然一团乱。先把 AST 定下来DBMS 部分才有得谈。5. 避坑与排查这几个问题我当年也踩过5.1 数字被 Name 规则截获NUMBER 永远不出现现象写CHAR(20)或WHERE a 1时语法器一直报 syntax error打日志发现词法器返回的全是NameNUMBER一次都没出现过。原因Name那条规则是[a-zA-Z][_0-9a-zA-Z()\.\*]*首字符要求是字母理论上不该匹配纯数字。但如果规则顺序被调整过、或者Name的正则里首字符被放宽成[a-zA-Z0-9]数字就会先被Name吃掉。报告作者在“存在问题及解决方法”里写的正是这件事“开始时没有考虑 Name 会将 NUMBER 截获导致数字对应的位置无法识别”。解决把[0-9]这条规则放在所有标识符规则之前并且严格保证标识符正则的首字符集合不含数字。lex 的最长匹配会优先选长度更长的同长度才看顺序所以顺序和首字符约束两个都要对。5.2 改了 .l 文件跑起来还是旧行为现象把单引号规则改对了重新编译程序行为一点没变甚至报错信息都和改之前一模一样。原因只编译了mylexer.cpp没重新跑 Generator 生成它。.l是源.cpp是产物改了源不重新生成编译器看到的还是旧产物。VC6.0 的项目文件里如果没有把.l配成自定义生成步骤就得手动跑一遍工具再编译。解决把生成命令挂到构建流程里。VC6.0 时代是在 Project Settings 的 Custom Build 里加命令行现代工具链写进 Makefilemylexer.c: mylexer.l flex -o mylexer.c mylexer.l myparser.c myparser.h: myparser.y bison -d -o myparser.c myparser.y这样make会根据时间戳判断要不要重新生成改.l一定触发重生成后悔药就省了。5.3 语法冲突只警告不报错跑起来结果诡异现象bison 编译时打出一行conflicts: 2 shift/reduce没当回事结果WHERE a 1 AND b 2 OR c 3解析出来的树形状和预期不一致。原因shift/reduce 冲突说明文法有二义性bison 的默认策略是“移进优先”这个默认值在某些场景下会把AND和OR绑成一样优先级或者在conditions AND conditions和conditions OR conditions之间选错分支。警告不阻止生成所以很容易被忽略。解决先用bison -v生成.output文件里面会列出每个冲突状态的具体项看清楚是哪两条产生式在抢然后要么补优先级声明%left OR在前、%left AND在后要么重写文法消除二义性。零冲突不是目标但每条冲突都得知道它为什么存在。5.4 语义值用 yytext 指针日志全是乱码现象printf打表名的时候有时候正常有时候打出来是后面几个 token 拼起来的乱码。原因规则里printf(%s, yytext)能用但把yytext直接赋给yylval.yych再往下传就不行。yytext指向的是词法器内部的扫描缓冲区下一轮匹配会往里写新内容之前存下的指针就悬空了。解决存进去之前先拷贝一份yylval.yych strdup(yytext);用完记得在 AST 销毁时free。教学代码里为了省事经常不释放跑一次就退出无所谓但如果你要在一个进程里连续解析多条语句内存会一直涨。5.5 报 syntax error 却不知道错在哪现象输入SELECT * FROM程序只回一句syntax error没有行号、没有出错 token、没有上下文。原因yyerror用的是默认实现只打固定字符串。yacc 允许你自己实现yyerror(char *msg)但报告里没写等于把诊断信息全丢了。解决自己实现一个把当前行号和出错 token 打出来void yyerror(const char *msg) { extern int yylineno; /* flex 里加 %option yylineno */ extern char *yytext; fprintf(stderr, 第 %d 行附近: %s出错 token %s\n, yylineno, msg, yytext ? yytext : (空)); }yylineno需要词法器开%option yylineno才会自动维护否则一直是 0。yytext在语法错误发生时指向的是刚被读进来、还没归约的那个 token用它基本能定位到出错位置。这一条改完调试效率的提升比前面几条加起来都明显。6. 二次开发从“能识别”到“能执行”的改造路线这份材料的价值在词法和语法这两段缺的是执行。真要往上加我建议按这个顺序推别一上来就写存储引擎。第一步把printf换成 AST。所有归约动作用mk_node建节点sts的语义值最终是一棵语句链表的头指针。这一步做完程序行为不变但你手里有了结构化数据后面所有事都好办。验证方法很简单写个dump_ast(node, 0)递归打缩进树输入三条语句看输出和报告里画的语法树图形是否一致。第二步给每条语句挂一个执行函数。按kind分发N_CREATE_TABLE走建表、N_INSERT走插记录、N_SELECT走全表扫。表结构可以先做成内存里的哈希表加vector字段定义存name/type/len三元组记录存vectorstring先把语义跑通再考虑落盘。这一步是改造量最大的也是最容易失控的建议先只做CREATE TABLEINSERTSELECT *三条跑通了再补WHERE。第三步补错误处理和事务边界。语法层通过不代表语义层合法CREATE TABLE t (id INT, id CHAR(10))重复字段名、SELECT * FROM 不存在的表都得在执行层拦下来报错信息要带上表名。这条不做二次开发出来的东西只能自己玩交给别人一用就崩。有个地方值得单独说条件表达式WHERE a 1 AND b 2的执行。AST 里它是conditions节点左孩子一个condition、右孩子另一个condition、中间挂着AND。求值的时候写一个递归的eval_cond(node, record)遇到AND就两边同时为真遇到比较节点就按op取字段值和常量比。这套逻辑和编译原理的关系就不大了属于解释器写法但它是把前端成果用起来的唯一路径。从那以后我每次改这类前端工程都强制先跑一遍 AST dump 再往下接执行层——语法树对了执行错了是逻辑问题语法树都不对往下写的每一行都是浪费。希望这份材料能被你改成真正跑得起来的东西也希望帮到你。本文还有配套的精品资源点击获取