基于 lex/yacc 的 DBMS SQL 词法语法分析与 AST 构建

简介面向计算机专业学生与编译原理课程学习者这份西安电子科技大学上机报告以“DBMS 的设计与实现”为主线记录从词法分析、语法分析到简单数据库管理系统落地的完整思路。内容涵盖项目概况、人员分工与完成情况lex/yacc 及 VC6.0 环境下的词法规则、语法规则设计DBMS 物理结构与建库建表、增删改查、索引和事务管理等核心功能并附上机心得与改进建议可用于课程报告撰写参考、实验方案复盘和编译原理知识梳理。压缩包仅含 1 个 doc 文件约 82KB篇幅集中、便于查阅。已有 1332 人学习适合需要了解上机报告结构、lex/yacc 实践路径及简易 DBMS 实现框架的读者参考。1. 从一份“只做了一半”的上机报告说起很多编译原理课设的通病是词法、语法分析器跑通了打印出一堆 token 和规约日志但问一句“这套东西到底解析了什么语言”答不上来。这份专做数据库管理系统DBMS前端的上机报告恰恰是另一种思路——它把 lex/yacc 定义为 SQL 的一个子集文法让分析器真正去吃CREATE TABLE、SELECT ... FROM ... WHERE这类语句再把语法树交给后面的执行模块。换句话说它要解决的是“给一门小型的、面向数据库的查询语言造一个可用的前端”而不是“造一个玩具计算器”。适合正在做编译原理课程设计、需要一份完整可参考方案的计算机专业学生也适合想理清前端到存储这条链路怎么拆的从业者。2. 需求与选型为什么用 lex/yacc 而不是手写递归下降先把这个项目的边界说清楚。DBMS 前端要做的事无非三件把字符流切成 token词法按文法判断 token 序列是否合法并构造语法树语法再把树交给执行层去操作物理文件。第三件事在这个方案里只做了结构设计和功能规划实际动手的是前两件。这个取舍不是偷懒而是课程设计的学时决定的——手写一个能覆盖 SQL 子集的递归下降解析器光调试左递归和运算符优先级就能耗掉大半时间。2.1 词法与语法分层的判断依据我一般会这样划分凡是能被正则表达式描述清楚的全部交给词法分析器凡是有嵌套、有递归结构、需要上下文才能判断的交给语法分析器。SQL 里关键字、标识符、数字、比较运算符、括号逗号分号都是典型的正则语言范畴而conditions: conditions AND conditions | ( conditions )这种可嵌套的条件表达式正则表达式根本表达不了必须上升到上下文无关文法。这个边界划错后面全是坑。最常见的是把!这种双字符运算符当成两个单字符处理或者让标识符的正则把数字前缀吃掉。报告里专门记了一条早期 Name 的规则把 NUMBER 截获了导致数字位置死活报错这就是词法优先级没排对。2.2 工具链与开发环境项目用的是 ParserWizard 生成 lex/yacc 骨架配 VC6.0 编译。ParserWizard 这类生成器的作用是帮你把yyparse的驱动循环、符号表管理、错误恢复的样板代码搭好你只填规则段。放到今天等价做法是 flex bison配 gcc/clang 或者任意现代 IDE思路完全一致规则文件的结构也几乎可以平移。这里给一段可复用的 flex 规则骨架把报告里那份mylexer.l的核心规则重新整理成带注释的版本%{ #include myparser.h /* 与 bison 生成的头文件对接拿到 token 定义 */ #include define.h %} %option noyywrap %% [ \t\r] { /* 跳过空白不产生 token */ } \n { /* 换行同样只做行号维护 */ } CREATE { return CREATE; } DATABASE { return DATABASE; } DATABASES { return DATABASES; } TABLE { return TABLE; } TABLES { return TABLES; } SHOW { return SHOW; } USE { return USE; } DROP { return DROP; } SELECT { return SELECT; } DELETE { return DELETE; } INSERT { return INSERT; } UPDATE { return UPDATE; } VALUES { return VALUES; } INTO { return INTO; } SET { return SET; } FROM { return FROM; } WHERE { return WHERE; } AND { return AND; } OR { return OR; } INT { return INT; } CHAR { return CHAR; } EXIT { return EXIT; } NULL { return NULLX; } /* 空值单独给一个 token */ ! { return NE; } /* 双字符运算符必须排在单字符 之前 */ [()*,;] { return yytext[0]; } /* 单字符运算符直接返回其 ASCII 码 */ [0-9] { return NUMBER; } [a-zA-Z_][a-zA-Z0-9_]* { return ID; } /* 标识符且必须放在关键字规则之后 */ %%几个关键点值得说明。第一关键字规则必须排在标识符规则之前因为 flex 遵循“最长匹配优先等长时先出现的规则优先”但如果你把ID写在CREATE前面虽然最长匹配仍能救回来可读性和可维护性都会变差。第二!必须显式写在[()*,;]之前否则!无处安放、会被单独吃掉语法层永远等不到NE。第三单字符运算符直接return yytext[0]这样 bison 里可以用、这种字面量写规则省去一堆 token 声明。提示%option noyywrap是给单文件编译用的如果你的项目要链接多个扫描器去掉它并自己实现yywrap()。2.3 语法分析从产生式到可运行的 parser语法部分的核心是那份 bison 规则。开始符号是sts第一条产生式sts: sts st | /* empty */完成的是“语句序列”的闭包功能——和正则里的*是同一个意思只不过这里靠左递归实现。st往下推出八类语句覆盖建库建表、展示、删除、切换、查询、删改插。把报告里的规则整理成可直接编译的版本重点看结构和优先级声明%{ #include mylexer.h #include define.h %} %union { int ival; char *sval; } %token sval ID %token ival NUMBER %token CREATE DATABASE DATABASES TABLE TABLES SHOW USE DROP EXIT %token SELECT DELETE INSERT UPDATE VALUES INTO SET FROM WHERE %token CHAR INT NULLX NE %left OR %left AND %nonassoc NE /* 比较运算不可连写abc 直接报错 */ %% 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 ID | CREATE TABLE ID ( create_field ) ; show_st : SHOW TABLE ID | SHOW TABLES | SHOW DATABASE ID | SHOW DATABASES ; drop_st : DROP TABLE ID | DROP DATABASE ID ; use_st : USE ID ; create_field : create_field , field_type | field_type ; field_type : ID type ; type : CHAR ( NUMBER ) | INT ; select_st : SELECT select_name FROM tables | SELECT select_name FROM tables WHERE conditions ; select_name : table_fields | * ; insert_st : INSERT INTO ID VALUES ( insert_atom_commalist ) ; insert_atom_commalist : insert_atom | insert_atom_commalist , insert_atom ; insert_atom : ID | NUMBER | NULLX ; delete_st : DELETE FROM tables WHERE conditions ; update_st : UPDATE ID SET set_fields WHERE conditions ; set_fields : set_field | set_field , set_field ; set_field : comp_left comp_op comp_right ; table_fields : table_field | table_fields , table_field ; table_field : ID | ID . ID ; tables : tables , ID | ID ; conditions : conditions AND conditions | conditions OR conditions | ( conditions ) | condition ; condition : comp_left comp_op comp_right ; comp_left : table_field ; comp_right : table_field | NUMBER ; comp_op : | | | NE ; %%这段规则里有三处是这份报告真正值钱的地方。一是%left OR写在%left AND之前bison 里越靠后声明的优先级越高所以 AND 高于 ORa 1 OR b 2 AND c 3会被解析成a1 OR (b2 AND c3)符合 SQL 直觉。二是%nonassoc用在比较运算符上写a b c会直接报语法错误而不是悄悄规约成(ab)c。这种“宁可报错不可错解”的取舍在做文法设计时应该成为默认习惯。三是table_field允许ID . ID两段式但comp_right里又允许直接跟NUMBER这两条规则的组合让WHERE t.id 100和WHERE id 5都能走通。代价是当你写WHERE id t.id这种右值是字段的等式时comp_right会在table_field和NUMBER之间产生一次移进-规约的抉择实际上因为ID已经由词法层统一成ID这里不会冲突但如果后续要给字段名加上表限定就得放大comp_right的产生式并重新验证冲突报告。2.4 语法树的数据结构设计光是printf(Operation is ok)只能证明文法通了真要对接执行层得让每条规约动作产出一个节点。报告里那几行“语法树图形说明”其实就是在讲这件事CREATE TABLE的树根挂表名、下面挂字段列表SELECT ... WHERE的树根挂投影列表、表名、条件子树INSERT挂表名和值列表。最小可用的节点结构我一般这么定义typedef enum { NODE_CREATE_TABLE, NODE_CREATE_DB, NODE_SELECT, NODE_INSERT, NODE_UPDATE, NODE_DELETE, NODE_DROP, NODE_SHOW, NODE_USE, NODE_FIELD_LIST, NODE_FIELD, NODE_SELECT_LIST, NODE_COND_AND, NODE_COND_OR, NODE_COND_CMP, NODE_VALUE_LIST, NODE_LITERAL } NodeKind; typedef struct AstNode { NodeKind kind; char *name; /* 表名、库名、字段名都放这里 */ char *op; /* 比较运算符只有一个字符或 NE */ int type; /* INT / CHAR(n)仅字段定义用 */ int ival; /* 字面量数值 */ struct AstNode *left; /* 条件左子树 / 字段列表 */ struct AstNode *right; struct AstNode *next; /* 兄弟链用于逗号分隔列表 */ } AstNode;next这条兄弟链是设计上的一个关键决定。SQL 里逗号列表特别多——字段列表、投影列表、值列表、多表连接——如果每样都定义一种链表节点结构体会膨胀到七八种。用next串起来一棵树就能表达“列表的列表”遍历时代码量少一半。代价是内存回收要写成递归释放别忘了这一步不然跑一百条语句就能看到内存曲线稳步上升。对应的规约动作长这样以create_field为例create_field : create_field , field_type { $$ append_sibling($1, $3); } | field_type { $$ $1; } ;append_sibling负责走到next链末尾挂上去。如果链已经很长又频繁插入可以改成头插再整体反转这是个小优化但不是必需。3. DBMS 部分物理结构与执行链路怎么设计前端只负责“听懂”听懂之后要“做到”。报告第三部分给出的物理结构和服务功能虽然只写到设计层面但骨架是对的我把它补到可实施的粒度。3.1 数据文件与元数据的组织方式一个最小 DBMS 需要两类持久化数据数据本身和描述数据的数据元数据。元数据包括有哪些库、每个库里有哪些表、每张表有哪些字段、字段类型是什么、字段占几个字节。数据则是按行存储的记录。物理结构上通常分三层层次存放内容实现方式库目录库名即目录名文件系统目录一库一目录表文件记录数据定长记录顺序文件一表一文件表定义字段名、类型、偏移与表同名的.def文本或二进制头选定长记录是最省事的做法。INT占 4 字节CHAR(n)占 n 字节一条记录的字节宽度在建表时就确定第 k 条记录的偏移就是k * record_size寻址是纯算术不需要扫描。变长字段比如不指定长度的 VARCHAR会直接把复杂度抬高一个量级你得维护槽位目录、处理记录迁移、考虑碎片整理。课程设计阶段老老实实定长就对了。建表时把字段布局算出来写进.def执行INSERT时按布局逐字段序列化执行SELECT时按布局反序列化再套上WHERE条件做过滤。这条链路一旦定死UPDATE和DELETE就退化成“定位记录 改写 落盘”的标准操作。3.2 语句执行流程与各模块职责从一条 SQL 字符串到数据落盘完整链路是这样的词法分析器把字符串切成 token 序列语法分析器按文法规约规约动作同步构造 AST语义检查表是否存在、字段是否匹配、类型是否兼容执行计划对SELECT决定是全表扫描还是走索引对INSERT决定目标文件与偏移存储引擎读页、改页、写回结果输出把记录集格式化成表格打印。报告里提到“已完成语句的执行过程、流程图、优缺点分析”这个流程图的节点就是上面六步。真要动手时第三、四步最容易被低估。语义检查漏了SELECT * FROM 不存在的表就会在存储层抛出一个空指针执行计划完全不做所有查询一律全表扫描十万条记录的表跑一个等值查询要好几百毫秒演示的时候很尴尬。一个成本极低但效果明显的优化在WHERE条件里识别“主键/首字段等值比较”这一种模式如果命中就直接算偏移、只读一条记录。代码不超过三十行演示速度却能差出一个数量级。3.3 已实现与未实现部分的边界报告里明确写了“完成了词法与语法分析已有设计思想但尚未实现的有若干语句”。这个边界要主动写清楚别含糊。已实现的八类语句的识别与 AST 构造语法错误能定位到出错 token。设计完成但未编码的语义检查、索引、事务、并发控制。把未实现的部分写成“设计已完成、编码待续”比含糊其辞地略过要专业得多。评审看的是你对系统的理解深度不是你代码行数。事务管理这种模块课程设计里能画出 undo 日志的结构、说清回滚时怎么按日志逆序撤销就已经到位了。4. 避坑与排查这份方案里最容易翻车的几个点4.1 词法规则顺序颠倒导致关键字被识别为标识符现象输入SELECT * FROM t;语法分析器报syntax error打印出的 token 序列里第一个是ID而不是SELECT。原因词法文件里[a-zA-Z_][a-zA-Z0-9_]*这条标识符规则写在了关键字规则前面且两条规则匹配长度相同时flex 选择先出现的。SELECT被当成标识符吃掉了。解决把所有关键字规则整体移到标识符规则之前并在规则文件顶部加注释说明“关键字必须优先于 ID”。改完重新生成扫描器别只重编译——生成器生成的代码不刷新改了规则文件也白改。4.2 双字符运算符被拆成两个单字符现象WHERE a ! 5解析失败报错位置指向!。原因词法里只写了、、这些单字符规则没有!!在规则表里无匹配扫描器走到默认的 ECHO 分支把它原样吐到标准输出同时语法层收到的下一个 token 是。解决显式加! { return NE; }且必须排在单字符符号类之前。排查时可以打开 flex 的调试输出或者临时在每条规则里打印匹配到的文本看!到底被谁吃掉了。4.3 移进-规约冲突被当成“警告”忽略现象bison 生成时报conflicts: 1 shift/reduce程序能跑但某些嵌套条件的解析结果和预期不一致比如a1 AND b2 OR c3的分组反了。原因没在文法里声明运算符优先级bison 遇到歧义时默认选择移进导致 AND 和 OR 结合方式由规则书写顺序决定而不是由语义决定。解决用%left/%nonassoc显式声明优先级低优先级写在前面。声明完重新生成确认冲突数归零。如果归零不了说明文法本身有真歧义得改产生式而不是继续加优先级。注意冲突数不为零不等于程序一定错但每一个冲突你都得能说清它为什么会安全地消解。说不清就是定时炸弹。4.4 规约动作里构造的 AST 节点没释放现象连续执行几百条语句后进程内存持续上涨长跑测试时被系统杀掉。原因规约动作里malloc出的节点执行完后没人管sts递归规约时中间结果也没有销毁路径。解决为每种语句写一个free_ast(AstNode*)递归释放left、right循环释放next链。在sts的规约动作里语句执行完立刻释放该语句子树。开发期可以加一个节点计数全局变量程序退出时打印不为零就是漏了。4.5 标识符规则把数字前缀吃进名字里现象CREATE TABLE t1 (c1 INT);报错说t1处的 token 类型不对。原因如果标识符规则误写成[a-zA-Z][a-zA-Z0-9]*而另一条NUMBER规则是[0-9]看起来没问题但若标识符规则写成[a-zA-Z][_0-9a-zA-Z()\.\*]*报告原文里就有这么一条奇怪的 Name 规则它会贪婪匹配超过需要的字符把后面的括号、点号都吞进去。解决把标识符的字符集收紧到[a-zA-Z_][a-zA-Z0-9_]*需要表限定名t.c时让词法返回ID、.、ID三个 token由语法层用ID . ID组合。词法层永远只做“最短的、无歧义的分割”组合逻辑交给文法这是分工原则。5. 验收与答辩怎么证明这套前端真的能用课程设计的验收评审不会逐行读你的代码他们看的是三件事文法覆盖了哪些语句、错误处理到什么程度、你能不能现场解释清楚一条语句的完整走位。所以准备验收时我建议倒着来——先设计测试用例再回头补文档。测试用例按四类准备每类至少五条类别示例期望结果正常建表建库CREATE TABLE stu (id INT, name CHAR(20));规约成功AST 含两字段正常查询SELECT id, name FROM stu WHERE id 100;AST 投影列表两项条件子树完整词法错误SELECT FROM stu;报错并指出的位置语法错误SELECT FROM stu;报错并指出缺少投影列表边界SELECT * FROM a, b WHERE a.id b.id;多表与字段限定都能解析答辩现场最容易被问住的两个问题提前想好答案。第一个是“你的文法有冲突吗”别答“没有”要答“声明优先级前有一个移进-规约冲突来自 AND/OR 的结合性用%left按低到高声明后归零”这体现你懂冲突的来源。第二个是“为什么!要单独处理”答“双字符运算符无法用单字符规则覆盖且必须排在单字符符号类之前否则!会走默认分支”这个答案能顺带展示你对 flex 最长匹配和规则顺序的理解。演示顺序也有讲究。先跑一条最简单的CREATE DATABASE让评审看到Operation is ok再跑一条带WHERE的查询展示 AST 打印最后故意输一条错语句展示错误定位。三分钟讲完比念十分钟 PPT 有效。至于报告里那份“上机心得”和“建议”别写成感想散文写具体的一条比如“词法规则顺序问题卡了两天后来靠逐条打印匹配文本来定位”这种细节评审一看就知道是真做过。从那以后我每次写规则文件第一件事就是把关键字规则整块挪到最前面并在文件头留一行注释提醒自己生成器生成的中间文件一律不手改改完规则必然重新生成一遍再编译。这套习惯救过我很多次也希望帮到你。本文还有配套的精品资源点击获取