简介这份编译原理上机报告来自西安电子科技大学计算机科学与技术专业面向正在学习编译原理、需要完成课程上机或课程设计的高校学生。报告以“DBMS的设计与实现”为题完整记录了从词法分析、语法分析到数据库管理系统物理结构与核心功能的实现思路适合作为课程报告的参考模板与项目实践指南。资源包内共1个doc文档约82KB内容涵盖项目概况与分工、基于lex与yacc的编译部分实现方案、DBMS的存储与索引结构设计以及建库建表、增删改查、索引使用和事务管理等主要功能说明并附有上机心得与建议。目前已有1330人浏览学习读者可借此了解编译原理技术如何落地到一个简易DBMS中获取词法与语法分析器的构建方法、模块划分思路及报告撰写框架适合作为课程设计参考与知识梳理材料。1. 词法与语法分析为什么一个 SQL 解析器能撑起整个 DBMS 的骨架很多人第一次接触编译原理上机都会觉得词法分析和语法分析只是“把字符串切开再拼回去”的机械操作。但真正动手写一个能识别CREATE TABLE、SELECT ... FROM ... WHERE的解析器时才会发现一个反直觉的事实DBMS 的前端本质上就是一个编译器。SQL 语句是源语言执行计划是目标语言而词法分析和语法分析就是这座桥梁的两座桥墩。这份上机报告的核心价值不在于它实现了一个多么完整的数据库而在于它用 lex 和 yacc 把“编译器如何理解结构化查询”这件事拆到了源码级——从正则式到产生式从 token 流到语法树每一步都能看到编译原理在真实系统里的投影。搞懂这套机制你再看任何 SQL 解析器、ORM 框架甚至配置语言解析器都不会再觉得它们是黑匣子。2. 词法分析正则式怎么把一串字符变成有类型的 token2.1 从mylexer.l看 lex 的工作方式词法分析器的输入是原始字符流输出是带类型标记的 token 序列。这份报告里的mylexer.l文件用的是 ParserWizard 生成的 lex 骨架核心逻辑集中在%%之后的规则区。每条规则左边是正则式右边是匹配后执行的动作——通常是return一个 token 类型给语法分析器。%% \n {} {} [ \t] { /* do nothing */ } 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; } NULLX { return NULLX; } 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; } %%这段规则区里藏着几个值得细看的机制点。第一关键字匹配用的是带引号的字面量lex 会为每个关键字生成一个精确匹配的 DFA 分支匹配优先级高于后面的通用标识符规则。第二[0-9]匹配数字并返回NUMBER但注意它没有处理负数和小数——这是上机报告里刻意简化的部分真实 DBMS 的词法分析器需要处理-、.、e等符号。第三Name和ID两条规则的区别很微妙Name允许出现()、.、*这些字符而ID只允许字母数字下划线。这种设计通常是为了区分“表名/字段名”和“普通标识符”但代价是Name的正则式会贪婪匹配可能把后续的运算符也吞进去。2.2 单引号识别翻车一个斜线引发的血泪经验报告里明确记录了一个踩坑点“在识别单引号时由于没有使用斜线标示导致无法识别”。这个问题的根源在于 lex 的正则式语法里单引号本身是普通字符但如果你写试图匹配一个单引号lex 会把它解析成“空字符串 空字符串 空字符串”而不是“一个单引号字符”。正确的写法应该是\或者用双引号包裹。/* 错误写法lex 无法正确解析 */ {} /* 正确写法用转义或双引号 */ { return \; }这个坑之所以典型是因为它暴露了 lex 正则式解析的一个底层规则单引号在 lex 里不是特殊字符但连续三个单引号会被词法分析器自身误读。很多初学者会在这里卡住因为报错信息往往指向“无法识别的规则”而不是“你的引号写错了”。我一般会建议在写 lex 规则时所有标点符号都用双引号包裹这样能避开大部分转义问题。2.3 token 类型定义与yylval的传递机制词法分析器不仅要返回 token 类型还要把 token 的语义值传给语法分析器。这份报告里用了一个Token结构体struct Token { int type; char *yych; int value; };但在 lex 规则区里真正起作用的是yylval这个全局变量。YYSTYPE被定义为int所以yylval只能传整数。这意味着Name和ID匹配到的字符串实际上没有被传给语法分析器——语法分析器只知道“这是一个 Name”但不知道“这个 Name 具体叫什么”。这是上机报告里一个隐藏的简化它只做了语法层面的识别没有做语义层面的值传递。真实的 DBMS 解析器需要把表名、字段名、常量值都存到语法树节点里否则后续无法生成执行计划。3. 语法分析产生式怎么把 token 流组织成语法树3.1myparser.y的产生式结构语法分析器的输入是词法分析器返回的 token 流输出是语法树。这份报告里的myparser.y用 yacc 定义了 SQL 语句的上下文无关文法。开始符号是sts第一条产生式sts: sts st | /* empty */实现了类似正则式闭包的功能——它可以匹配任意多条语句。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 ) ; select_st: SELECT select_name FROM tables | SELECT select_name FROM tables WHERE conditions ; conditions: condition | ( conditions ) | conditions AND conditions | conditions OR conditions ;这套产生式覆盖了 DBMS 最核心的几类语句建库建表、查询、插入、删除、更新。conditions的递归定义支持括号嵌套和AND/OR组合这是布尔表达式解析的标准做法。但注意comp_op只支持、、、!四种比较运算符没有、也没有LIKE、IN这些 SQL 里常见的谓词。3.2 语法树的数据结构从产生式到树节点yacc 在解析过程中会自动构建语法树但这份报告没有显式定义树节点结构。从产生式的形状可以反推语法树的形态sts是根节点每个st是子节点create_st、select_st等是st的子节点以此类推。报告里用文字描述了典型语句的语法树CREATE TABLE Name ( Name INT )对应的树结构是create_st ├── CREATE ├── TABLE ├── Name └── create_field └── field_type ├── field │ └── Name └── type └── INT这种树结构的好处是每个节点对应一个语法单位后续的语义分析可以自底向上遍历先处理叶子节点字段名、类型再处理父节点表定义。但报告里没有实现语义动作所以这棵树实际上只存在于解析器的栈里没有被持久化成数据结构。3.3 冲突与优先级%left AND OR解决了什么问题yacc 在生成解析表时如果遇到移进-归约冲突或归约-归约冲突会报错。这份报告里用了%left AND OR来声明运算符的结合性和优先级。%left表示左结合优先级按声明顺序从低到高。%left AND OR如果没有这行声明conditions: conditions AND conditions | conditions OR conditions会产生歧义A AND B OR C可以被解析成(A AND B) OR C或者A AND (B OR C)。%left告诉 yacc 在遇到冲突时优先归约左边的运算符从而消除歧义。但注意AND和OR被声明为同一优先级这意味着A OR B AND C会被解析成(A OR B) AND C而不是 SQL 标准的A OR (B AND C)。这是一个设计上的取舍报告选择了简化优先级处理代价是语义与标准 SQL 不完全一致。3.4 数字被 Name 截获一个正则式贪婪匹配的经典翻车报告里记录了第二个踩坑点“开始时没有考虑 Name 会将 NUMBER 截获导致数字对应的位置无法识别”。这个问题的根源在于 lex 的规则匹配顺序[a-zA-Z][_0-9a-zA-Z()\.\*]*这条规则虽然以字母开头但它的字符集里包含了0-9所以像123abc这样的输入会被Name规则匹配而不是被NUMBER规则匹配。更隐蔽的是如果Name规则写在NUMBER规则前面lex 会优先尝试匹配Name即使输入是纯数字也可能因为后续字符而误判。/* 有问题的顺序Name 在 NUMBER 之前 */ [a-zA-Z][_0-9a-zA-Z()\.\*]* { return Name; } [0-9] { return NUMBER; } /* 修正后的顺序NUMBER 在 Name 之前 */ [0-9] { return NUMBER; } [a-zA-Z][_0-9a-zA-Z()\.\*]* { return Name; }但仅仅调整顺序还不够。如果输入是123NUMBER规则会匹配如果输入是123abcNUMBER规则匹配123然后Name规则匹配abc这可能导致语法错误。更稳妥的做法是把Name的字符集限制为不以数字开头并且确保NUMBER规则在Name之前。这个坑的教训是lex 的规则匹配是“最长匹配优先同长度时先定义的规则优先”理解这一点才能避免类似的翻车。4. 避坑与排查词法语法分析里最容易翻车的几个点4.1 现象关键字被识别成标识符原因关键字规则写在标识符规则后面或者关键字没有用双引号包裹。lex 在匹配时如果两条规则都能匹配同一个字符串会优先选择先定义的那条。如果[a-zA-Z][_a-zA-Z0-9]写在CREATE前面那么CREATE会被当成普通标识符。解决把所有关键字规则放在标识符规则之前并且用双引号包裹关键字。如果关键字很多可以用一个单独的规则区段来管理。4.2 现象语法分析器报“syntax error”但 token 流看起来正常原因通常是产生式缺少某个分支或者 token 类型不匹配。比如select_st只定义了SELECT select_name FROM tables但输入是SELECT * FROM table WHERE id 1而conditions里没有处理NUMBER和Name的比较。解决用 yacc 的-v选项生成y.output文件查看解析表的状态机。找到报错时所在的状检查该状态下期望的 token 类型和实际输入的 token 类型是否一致。4.3 现象Name规则吞掉了运算符原因Name的字符集里包含了()、.、*这些字符在 SQL 里也可能是运算符或分隔符。比如table.field会被Name整体匹配但table . field会被拆成三个 token。解决把Name的字符集收窄只允许字母、数字、下划线。如果需要支持table.field这种限定名可以在语法分析层面用table . field的产生式来处理而不是在词法层面合并。4.4 现象yylval传值丢失原因YYSTYPE被定义为int但Name和ID匹配到的是字符串。如果语法动作里试图用$1获取字符串值会得到错误的结果。解决把YYSTYPE定义为一个联合体包含int、char*等类型。在 lex 规则里用yylval.str strdup(yytext)保存字符串在 yacc 动作里用$1.str获取。4.5 现象递归产生式导致栈溢出原因conditions: conditions AND conditions是左递归yacc 可以处理但如果写成conditions: AND conditions conditions就是右递归可能导致解析栈无限增长。解决优先使用左递归产生式yacc 对左递归的解析效率更高且不会导致栈溢出。如果必须用右递归确保有终止条件。5. 从词法语法到 DBMS解析器只是前端的开始这份上机报告的价值在于它展示了一个完整的“SQL 解析器”的最小实现用 lex 做词法分析用 yacc 做语法分析用产生式定义 SQL 语句的结构。但它也暴露了一个关键问题解析器只是 DBMS 的前端真正的挑战在语义分析和执行引擎。报告里提到“已经实现语句的执行过程”但从产生式来看它只做了语法层面的识别没有做语义检查比如表是否存在、字段类型是否匹配、没有生成执行计划、没有实现存储引擎。这意味着它离一个可用的 DBMS 还有很长的距离。但正是这种“不完整”让它成为一个极好的学习材料你可以清楚地看到编译原理的每个阶段在 DBMS 里对应什么也可以自己动手补全缺失的部分。我一般会建议在读完这份报告后尝试做三件事第一把YYSTYPE改成联合体让Name和NUMBER的值能真正传到语法树节点里第二给conditions加上AND/OR的优先级处理让它符合标准 SQL 的语义第三实现一个简单的语义检查器在解析完成后遍历语法树检查表名和字段名是否存在。做完这三步你对“DBMS 前端”的理解就不再停留在纸面上了。从那以后我每次写解析器都会先把 token 类型和语法树节点结构定义清楚再写词法规则和产生式——这个顺序能避免大部分返工。希望帮到你。本文还有配套的精品资源点击获取