简介本资源是西安电子科技大学计算机科学与技术专业《编译原理》课程的上机实践报告面向高校相关专业学生及编译技术初学者聚焦编译器核心组件与数据库管理系统DBMS的协同设计问题。报告完整呈现了基于Lex/Yacc或Flex/Bison实现词法分析、语法分析并在此基础上构建简易DBMS的全过程涵盖环境配置、正规式定义、抽象语法树构建、数据文件存储结构、基础CRUD与事务管理等关键环节兼具理论深度与工程实操性。压缩包为单个82KB的Word文档.doc内容结构清晰含项目概况、编译与DBMS双模块实现方案、上机心得与改进建议等章节便于对照学习与复现。目前已有1329人下载学习适合用于课程设计参考、编译原理综合实践复盘及DBMS底层机制入门理解。1. 编译原理上机报告西安电子科技大学一份能跑通的 Lex/Yacc 实战 DBMS 编译器骨架这不是一份交差用的 PDF 报告而是一份真正在 VC6.0 下编译通过、能识别 CREATE TABLE / SELECT * FROM / INSERT INTO 等语句、并输出“Operation is ok”提示的可执行编译器原型。它把《编译原理》课里抽象的“词法→语法→AST”链条焊死在 DOS 窗口里——输入CREATE DATABASE test;回车就打印 OK输错CREAT DATABASE;就报错停住。整套流程不依赖 Java、Python 或现代 IDE纯 C Lex/Yacc VC6.0连#include string.h都得手动加是 2011 年真实课堂环境的硬核复刻。适合三类人1正被编译原理实验卡在 Lex 规则写不对、Yacc 冲突报错、VC6.0 找不到yacc.exe的本科生2想用最小成本验证“自己写的 SQL 解析器到底能不能动”的课程设计者3需要快速搭建一个可调试、可扩展的 DBMS 前端解析框架的毕设同学。它不实现磁盘存储、不搞事务日志、不写 B 树索引——但词法状态机、语法推导栈、冲突消解逻辑、VC6.0 工程配置全在源码里且每一行都有血泪注释。2. 从 Lex 规则到 Token 流词法分析器的四个关键锚点与实操配置2.1 为什么必须用 Lex而非手写状态机——规则优先级与空格吞吐的底层逻辑Lex 不是语法糖它是确定性有限自动机DFA的声明式封装。本项目中mylexer.l的核心价值在于用正则表达式直接映射语言原子单元避免手写 switch-case 时因顺序错误导致INT被ID吞掉的玄学翻车。比如[0-9] {return NUMBER;} [a-zA-Z][_a-zA-Z0-9] {return ID;}这两条规则看似简单但 Lex 的匹配原则是“最长前缀匹配 规则定义顺序优先”。若把ID规则写在NUMBER前面123abc就会被识别为ID因为123abc满足[a-zA-Z][...]的开头a而非NUMBERID。而本报告中NUMBER在前确保数字字面量被精准捕获。更关键的是空格处理[ \t] {/* do nothing */} \n {}这两行不是摆设——它们让词法分析器主动丢弃空白符使后续语法分析器收到的 token 流是干净的[CREATE, DATABASE, test, ;]而非夹杂\n和\t的脏流。这是 Yacc 能稳定工作的前提。若漏掉此项Yacc 会因意外 token 报syntax error且错误位置飘忽不定排查成本陡增。2.2 关键 Token 类型定义与define.h的联动机制Token 类型不是随便起名的字符串而是整数常量必须与 Yacc 的%token声明严格一致。本项目在define.h中集中定义// define.h #define CREATE 256 #define DATABASE 257 #define TABLE 258 #define SELECT 259 #define NUMBER 260 #define ID 261 #define Name 262 // 注意Name 是独立 token非 ID 的别名为什么要有Name看 Lex 规则[a-zA-Z][_0-9a-zA-Z()\.\*]* {printf(%s,yytext);return Name;}它匹配带括号/点号/星号的标识符如test(10)、user.name而ID规则[a-zA-Z][_a-zA-Z0-9]只匹配纯字母数字下划线。这种拆分是为支持CREATE TABLE t1(id INT, name CHAR(20));中的CHAR(20)——CHAR是关键字(20)是括号包裹的数字但CHAR(20)整体作为类型名需被识别为Name。若统一用IDYacc 无法区分CHAR关键字和CHAR(20)类型名导致语法分析失败。define.h是 Lex 和 Yacc 的契约文件修改任一端另一端必须同步否则编译时undefined symbol或运行时 token 错位。2.3 VC6.0 下 Lex/Yacc 工具链的硬核集成步骤VC6.0 本身不带 Lex/Yacc需手动集成 Flex/Bison本报告用的是 ParserWizard 生成的兼容版本但配置逻辑相同。关键四步下载工具获取flex.exe、bison.exe或本报告配套的yacc.exe、lex.exe放入C:\Program Files\Microsoft Visual Studio\VC98\Bin\VC6.0 默认 bin 目录注册自定义构建工具在 VC6.0 中右键mylexer.l→ Properties → Custom Build → SettingsCommand line:flex -o mylexer.cpp mylexer.lOutputs:mylexer.cpp同理为myparser.y设置bison -d -o myparser.cpp myparser.yOutputs 为myparser.cpp、myparser.h头文件路径Project → Settings → C/C → Preprocessor → Additional include directories 添加.当前目录确保#include mylexer.h可找到链接库Project → Settings → Link → Object/library modules 添加libfl.libFlex 运行库否则yywrap未定义报错。提示若flex报unrecognized option -o说明你用了老版本 Flex如 2.5.4需改用flex -t mylexer.l mylexer.cppbison若报conflicts: 1 shift/reduce先别慌——这是本报告语法的正常现象见后文避坑章节。2.4 词法分析器的调试技巧yydebug与yytext日志注入Lex 默认不输出匹配过程调试时需主动埋点。在mylexer.l的%{...%}区域添加int yydebug 1; // 启用 debug 模式并在规则动作中插入日志CREATE { printf(LEX: matched CREATE - %s\n, yytext); return CREATE; } [0-9] { printf(LEX: matched NUMBER - %s\n, yytext); return NUMBER; }编译运行后控制台将逐行打印匹配详情例如LEX: matched CREATE - CREATE LEX: matched DATABASE - DATABASE LEX: matched NUMBER - 10这比单纯看Operation is ok有用十倍——它能立刻暴露CREATE被识别成ID说明关键字规则位置错了、或数字被截断说明[0-9]规则被更长的规则覆盖。yytext是当前匹配文本的指针yyleng是长度二者组合可做精准校验比如检查Name是否含非法字符。3. 从产生式到语法树Yacc 语法分析器的冲突消解与 AST 构建逻辑3.1 为什么选 LR(1) 而非递归下降——SQL 语句嵌套深度的刚性需求本项目语法SELECT ... FROM ... WHERE ... AND ... OR ...存在深层嵌套WHERE (ab AND cd) OR ef递归下降分析器需手动管理调用栈易栈溢出且难以处理左递归。而 Yacc 生成的 LR(1) 分析器用状态栈 GOTO 表自动处理任意深度嵌套且对左递归如conditions: conditions AND conditions天然友好。看核心产生式conditions: condition | ( conditions ) | conditions AND conditions | conditions OR conditions ;这是典型的左递归写法Yacc 会将其转换为右结合的移进/归约序列保证(a AND b) OR c正确解析为(a AND b)先算再OR c。若强行改成右递归conditions: condition | condition AND conditions虽能编译但会导致a AND b AND c解析为a AND (b AND c)语义错误。LR(1) 的优势在此刻凸显——它不靠程序员脑补结合性而靠分析表驱动。3.2yyparse()的返回值与错误恢复机制yyparse()返回0表示成功1或2表示失败。但本报告main()中int n parser.yyparse(); return n;这不够健壮。真实场景需捕获错误并尝试恢复int main(void) { mylexer lexer; myparser parser; if (parser.yycreate(lexer)) { if (lexer.yycreate(parser)) { int result parser.yyparse(); if (result ! 0) { fprintf(stderr, Parse failed with code %d\n, result); // 可在此处清空 lexer 状态继续读下一条语句 } } } return 0; }Yacc 默认错误恢复策略是遇到syntax error时丢弃输入直到找到同步符号如;、}然后重启分析。本报告中st: ... ;的分号就是同步点确保SELECT * FROM t1 WHERE a1; DROP TABLE t2;即使第一句错第二句仍能解析。若删掉分号规则错误会蔓延至整个输入流。3.3 抽象语法树AST的极简实现用printf替代指针结构的工程权衡本报告未显式构建 AST 结构体如struct Node { int type; Node* left; Node* right; }而是在归约动作中直接printfsts: sts st {printf(Operation is ok\n);} | /* empty */ ; st: create_st ; { printf(CREATE statement parsed\n); } | select_st ; { printf(SELECT statement parsed\n); } ;这是教学项目的合理妥协AST 的本质是语义动作的载体而非必须存在的内存结构。printf语句即语义动作它验证了语法结构被正确识别。若需真正执行如生成中间代码只需将printf替换为new CreateNode(...)即可。本报告的CREATE TABLE t1(id INT);语法树图形说明中CREATE、TABLE、t1、id、INT五个节点的父子关系已由产生式create_st : CREATE TABLE Name ( create_field )的归约顺序隐式定义——Yacc 归约时CREATE和TABLE是终结符叶子Name是非终结符子树create_field是递归子树。理解这点就抓住了 AST 的灵魂。3.4 语法冲突的定位与解决Shift/Reduce 冲突的三步诊断法Yacc 编译时若报conflict: 1 shift/reduce不是 bug而是文法二义性的信号。本报告conditions规则必然触发此冲突a AND b OR c可理解为(a AND b) OR c或a AND (b OR c)。诊断三步查冲突报告运行bison -v myparser.y生成myparser.output搜索state 123数字随文法变找到类似state 123 conditions : conditions . AND conditions conditions : conditions . OR conditions AND shift, and go to state 45 OR shift, and go to state 46 OR reduce using rule 5 (conditions - conditions OR conditions)这说明在 state 123看到OR时既可移进期待conditions OR conditions也可归约按conditions - conditions OR conditions处理已读部分。设优先级在%{...%}后添加%left AND %left OR告诉 YaccAND和OR同级左结合AND优先级高于OR因AND在OR上方故a AND b OR c必先归约a AND b。验证重编译conflicts消失且测试SELECT * FROM t1 WHERE a1 OR b2 AND c3;输出Operation is ok证明结合性生效。提示%nonassoc用于禁止结合如%right用于右结合如赋值选错会导致abc解析为a(bc)右结合或(ab)c左结合语义天壤之别。4. 编译器与 DBMS 的耦合点物理结构如何承接语法分析结果4.1 “CREATE TABLE” 到磁盘文件的映射create_field规则的语义延伸语法分析器只负责确认CREATE TABLE t1(id INT, name CHAR(20));符合文法但真正的 DBMS 功能始于语义动作。本报告虽未实现但create_field规则已预留接口create_field: create_field , field_type { /* 此处可调用 create_column(t1, $3.type, $3.length) */ } | field_type ; field_type: field type { $$ $2; } // $2 是 type 的值INT 或 CHAR type : CHAR ( NUMBER ) { $$ make_char_type($3); } // $3 是 NUMBER 的值 | INT { $$ make_int_type(); } ;$3是第三个符号的语义值NUMBER的整数值$$是当前非终结符的语义值。若make_char_type(20)返回一个struct ColumnType { int type; int length; }则create_field归约时就能收集所有列定义最终传给create_table(t1, column_list)。本报告物理结构图中“数据文件存储”模块其文件格式如每行 CSV 或固定长度二进制就由此决定——CHAR(20)意味着该字段占 20 字节INT占 4 字节这就是语法到物理的桥梁。4.2 查询语句的执行流程select_st如何驱动缓冲区与索引select_st: SELECT select_name FROM tables WHERE conditions;的归约应触发查询执行引擎。典型流程步骤模块输入输出本报告对应点1. 语法解析YaccSELECT * FROM t1 WHERE id5;AST 节点SelectNode{fields:*, table:t1, condition:EqNode{id,5}}select_st归约动作2. 语义检查符号表AST 数据字典无错误则继续否则报table t1 not exists报告中“尚未实现”部分3. 查询优化简单优化器AST优化后 AST如WHERE id5→ 使用主键索引物理结构图中“索引”模块4. 执行缓冲区管理器优化后 AST从磁盘读取 t1 的数据页到内存缓冲区“缓冲区管理”文字说明5. 返回结果结果集缓冲区数据控制台打印5, Aliceprintf(Operation is ok)的升级版本报告的“物理结构”描述虽简略但SELECT语句的语法树图形中*、Name、、NUMBER的节点布局已暗示了执行器需提取的字段、表名、条件谓词——这是 DBMS 功能落地的起点。4.3 “DROP DATABASE” 的危险操作防护语法树中的安全钩子drop_st: DROP DATABASE Name ;看似简单但生产 DBMS 必须加防护。本报告可在归约动作中植入钩子drop_st: DROP DATABASE Name { if (is_system_database($3)) { // $3 是 Name 的值 fprintf(stderr, ERROR: Cannot drop system database %s\n, $3); YYERROR; // 强制报错退出 } else { drop_database($3); } }is_system_database()查询内置系统表如sys_databasesYYERROR是 Yacc 内置宏触发错误恢复。这比在 C 代码里if (strcmp(name,master)0)更优雅——语法层就拦截不进入执行层。本报告虽未实现但DROP规则的存在正是为这类安全控制预留的语法锚点。4.4 符号表的构建时机从ID到SymbolEntry的生命周期符号表不是全局变量而是随作用域动态创建销毁的结构。本报告中IDtoken 的语义值应携带作用域信息field: ID { $$ enter_symbol($1, SCOPE_TABLE); } // 在 CREATE TABLE 中ID 是列名 table: ID { $$ enter_symbol($1, SCOPE_DATABASE); } // 在 USE db1; 中ID 是数据库名enter_symbol()返回符号表项指针存入struct SymbolTable { char* name; int type; int scope; SymbolTable* next; }。当CREATE TABLE t1(id INT);解析完成符号表应有t1SCOPE_DATABASE和idSCOPE_TABLE两项。后续SELECT id FROM t1中的id需在t1的子作用域中查找否则报column id not found in table t1。本报告“符号表”热词指向的正是此机制——它是连接语法分析与语义检查的枢纽没有它SELECT * FROM non_exist_table;就无法报错。5. 避坑指南VC6.0 Lex/Yacc 开发中踩过的五个真实深坑5.1 现象Lex 编译报错undefined reference to yywrap原因Flex 默认期望用户实现yywrap()函数来处理文件结束VC6.0 链接时找不到该函数。解决在mylexer.l的%{...%}外即最后添加int yywrap() { return 1; }或更规范地在%{...%}内添加#define YY_NO_UNISTD_H并链接libfl.lib见 2.3 节。5.2 现象Yacc 编译报conflicts: 1 shift/reduce但程序仍能运行原因Yacc 默认采用“移进优先”策略解决冲突a AND b OR c会被解析为a AND (b OR c)违背 SQL 标准。解决明确声明运算符优先级见 3.4 节%left AND OR确保左结合且AND优先级更高。5.3 现象输入CREATE DATABASE test;后无输出程序卡死原因main()中parser.yyparse()未处理 EOFLex 的yywrap()返回 0 导致无限循环读取。解决确保yywrap()返回 1并在main()中检查yyparse()返回值if (n 0) printf(OK\n);。5.4 现象CHAR(20)被识别为ID而非Name导致CREATE TABLE t1(name CHAR(20));语法错误原因Lex 规则顺序错误[a-zA-Z][_a-zA-Z0-9]ID写在[a-zA-Z][_0-9a-zA-Z()\.\*]*Name之前CHAR(20)的CHAR部分先匹配 ID 规则。解决调换两条规则顺序让更具体的Name规则在前ID规则在后。5.5 现象VC6.0 编译mylexer.cpp报error C2065: yytext : undeclared identifier原因yytext是 Lex 内部变量需在%{...%}中声明为 extern或启用--yytext选项。解决在%{...%}中添加extern char *yytext;或在 Flex 命令中加-y参数flex -y -o mylexer.cpp mylexer.l。6. 进阶技巧用yacc -v生成状态机图谱把黑匣子变成可调试白盒Yacc 的最大黑匣子不是语法而是它生成的 LALR(1) 状态机——你写的产生式最终变成几百个状态、上千条转移边的 DFA。yacc -v myparser.y生成的myparser.output文件就是这个黑匣子的 X 光片。它不只告诉你冲突在哪更能让你像调试汇编一样调试语法分析过程。6.1 解读myparser.output的核心三要素打开myparser.output重点看三块State 定义每个state N是一个 DFA 状态包含items当前状态下的 LR(0) 项目集如st: . create_st ;表示等待create_stshift遇到某 token 时转移到哪个 statereduce遇到某 token 时按哪条产生式归约。Grammar Rules列出所有产生式编号Rule 1, Rule 2...$1、$2对应符号位置。Conflicts明确标出 shift/reduce 或 reduce/reduce 冲突的状态和 token。例如state 15中st: create_st . ; ; shift, and go to state 20 ; reduce using rule 3 (st - create_st ;)这说明在create_st解析完后看到;时既可移进去 state 20 继续也可归约完成st。此时若没设优先级Yacc 默认移进可能造成归约延迟。6.2 用状态机反向定位语法缺陷假设SELECT * FROM t1 WHERE id5 AND nameabc;总是报错但SELECT * FROM t1;正常。步骤运行yacc -v myparser.y得到myparser.output搜索WHERE相关状态找到where_st对应的 state如 state 42查看 state 42 的shift行确认id、、5是否都能正确转移重点看ANDtoken 的处理若AND在 state 42 中只有shift无reduce说明conditions规则未覆盖AND后的condition需检查conditions: conditions AND conditions是否遗漏。这比盲目改产生式高效十倍——状态机是语法的终极真相。6.3 构建可复现的测试用例矩阵基于状态机设计最小化测试集测试用例目的对应状态CREATE TABLE t1(id INT);验证create_field递归state 10, 12SELECT * FROM t1 WHERE a1;验证conditions单条件state 35SELECT * FROM t1 WHERE a1 AND b2;验证AND左结合state 35 → state 40SELECT * FROM t1 WHERE (a1);验证括号嵌套state 35 → state 50每个用例执行时加#define YYDEBUG 1Yacc 会打印state 10, reading a token等日志与myparser.output的 state 描述一一对照瞬间定位问题在 Lexertoken 错还是 Parserstate 错。从那以后我每次写完新产生式都强制走一遍yacc -vyacc -d 编译 最小测试用例绝不凭感觉提交。状态机图谱是编译器工程师的后悔药也是唯一能穿透 Lex/Yacc 黑匣子的探针。希望帮到你。本文还有配套的精品资源点击获取
