简介这份编译原理上机报告面向计算机科学与技术等专业学生聚焦编译原理课程设计与上机实验场景解决从词法、语法分析到简易数据库管理系统落地的完整方案参考问题。报告以《DBMS 的设计与实现》为主线依次覆盖项目概况与分工、基于 lex 与 yacc 的词法分析与语法分析实现、DBMS 的物理结构与核心功能设计并附上机心得与改进建议目录层级清晰便于按模块对照学习。压缩包内共 1 个 doc 文档约 82KB属于轻量级文字报告适合直接查阅实现思路与报告写作框架。该资源已有 1332 人学习说明其在课程报告参考场景中具有一定认可度。读者可从中获取词法规则与语法规则的组织方式、编译前端与数据管理模块的衔接思路以及表创建、增删改查、索引与事务等功能的规划要点也可借鉴报告章节编排与心得总结的写法用于自己的上机实践与文档整理。1. 一份 2011 年的编译原理上机报告值得现在翻出来看什么2011 年 5 月某高校一份编译原理上机报告题目叫《DBMS 的设计与实现》全程一个人做完。词法分析用 Lex 系的代码生成器写语法分析用 Yacc 系的生成器写编译环境是 VC6.0报告里老老实实写了「完成的语句」和「只有设计思想、尚未实现的语句」两栏。这份编译原理上机报告最值钱的地方恰恰不是它做完了多少功能而是它把翻车现场原样留在了纸面上单引号没转义导致字符常量识别不了标识符规则把数字截走导致报错报到怀疑人生。这篇东西写给三类人正在做课程设计、不知道怎么从正规式走到 Token 流的已经把语法跑通、卡在「语法树怎么接到执行层」的还有带别人做上机、想找一份能直接照着讲的踩坑清单的。下面按词法、语法、执行层、避坑、验证五段拆能抄的直接抄抄之前先看判断依据。2. 词法分析怎么拆从正规式到 Token 流的三层结构词法分析看着简单实际上手才知道坑都在细节里。一条SELECT * FROM t WHERE id 100;丢进去好的词法器吐出来的是一串带类型的 Token差一点的是能过但后面语法分析天天报错最差的是 Token 勉强对了、位置信息全丢出错时你根本不知道错在第几个字符。这份报告的 lex 部分走的是「关键字枚举 标识符 数字 运算符」四类切分结构不复杂但顺序和字符集两处稍不注意就会连锁反应。2.1 先把 Token 表定死再动手写规则我一般建议先列一张 Token 表别急着打开生成器写正则。表定下来了正则就是照着表填空表没定写到一半发现TABLES和TABLE混了回头改一遍规则、再改一遍文法、再改一遍语法树节点一天就没了。这份报告里的 Token 集合是围绕 SQL 子集设计的整理出来大致是这样Token 名匹配内容类别说明CREATE / DATABASE / DATABASES库级操作关键字保留字大小写写死不做大小写折叠TABLE / TABLES / SHOW / USE / DROP表级操作关键字保留字单复数各占一个 Token别合并SELECT / INSERT / VALUES / UPDATE / DELETEDML 关键字保留字VALUES 只在 INSERT 后出现WHERE / FROM / INTO / SET / AND / OR子句关键字保留字AND、OR 参与优先级声明INT / CHAR / NULLX类型与空值关键字NULLX 是为了避开 C 头文件里的 NULL 宏ID库名、表名、字段名标识符首字符必须是字母或下划线NUMBER列宽、比较常量字面量纯数字本层不处理正负号!不等比较运算符必须排在单字符前面( ) , ; * 分隔与比较符号单字符直接返回字符本身即可表里有两处很容易被忽略的判断依据。一处是单复数拆成两个 TokenSHOW TABLE t和SHOW TABLES是两条语义不同的语句如果你用一条SHOWID硬凑语义分析阶段就得靠字符串比较来区分等于把词法该干的活推给了后面。另一处是NULLX这个命名看着别扭其实是被迫的——C 语言里NULL是宏你在%token里写NULL预处理阶段就被替换掉了编译报错你都找不到源头。这种名字上的将就恰恰是做过一遍的人才写得出来的。提示Token 表里凡是「单复数」「近义词」成对出现的先在表阶段决定是拆是合别留到文法阶段临时想办法。2.2 规则顺序与实际匹配关键字必须跑在标识符前面词法生成器的匹配规则通常是「最长匹配优先同等长度按规则出现顺序」。很多人只记住了前半句结果把标识符规则写在关键字前面跑SELECT这种恰好也能被标识符正则吃下的词出现「有时候对有时候错」的玄学现象。原因是长度相同时先出现的规则赢。这份报告里关键字规则是集中写在标识符规则之前的顺序没出问题主体片段大约长这样/* mylexer.l 关键片段规则顺序即优先级先吃特殊再吃通用 */ %{ #include myparser.h #include define.h %} %option noyywrap %% [ \t\r] { /* 空白直接吞掉不产生 token但要保留行号 */ } CREATE { return CREATE; } DATABASE { return DATABASE; } DATABASES { return DATABASES; } TABLE { return TABLE; } TABLES { return TABLES; } SELECT { return SELECT; } INSERT { return INSERT; } VALUES { return VALUES; } WHERE { return WHERE; } FROM { return FROM; } ! { return NE; } /* 双字符运算符必须在单字符之前 */ | | | * { return yytext[0]; } /* 单字符直接回传 ASCII */ [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z_0-9]* { yylval strdup(yytext); return ID; } %%这段规则里关键字写在标识符前面是「防御性写法」哪怕生成器改成了其他匹配策略你也不会突然翻车。!排在前面也是同一个道理如果先匹配!就会被切成!未定义直接报错和两个 Token语法分析那边拿到的是一堆对不上的东西。代码之后要补一句参数说明yylval是给语法分析器传值用的联合体atoi把数字串转成intstrdup把标识符拷进堆内存——注意这里必须拷贝因为yytext是复用的缓冲区你不拷贝下一个 Token 一进来内容就被覆盖了语法树里所有名字最后都变成最后一个标识符。这个坑比前面几个更隐蔽因为它在小用例上根本不发作只有一条语句里出现两个以上标识符时才会暴露。还有一点报告里标识符规则后面跟了一句printf(%s, yytext);做调试输出。我理解调试期想看匹配结果的心情但这行必须在上交前删掉或者在编译开关里关掉否则你跑一条INSERT INTO t VALUES (1);屏幕上会糊出一串粘在一起的标识符出错了根本分不清是词法打印的还是语法打印的。2.3 三条标识符类规则怎么分工Name、ID、NUMBER这份报告最典型的一处设计是把「名字」拆成了Name和ID两条规则再加上NUMBER一共三条能吞字符的规则。原稿的做法是让Name的字符集放宽到能带().*这些字符本意是想一把兜住t.id、t.*这类带点号的字段引用结果埋了两个雷。第一个雷是字符集重叠[a-zA-Z][_0-9a-zA-Z()\.\*]*和[a-zA-Z][_a-zA-Z0-9]都能匹配普通标识符前者因为更长而经常胜出于是正常的表名也走了Name分支语法分析里期望ID的地方拿到Name归约直接失败。第二个雷更严重宽字符集让Name有能力把后面跟着的数字也吃进同一个 TokenWHERE id 100里的100在某些上下文下变成了一整块Name而文法里comp_right期望的是NUMBER于是报错信息全落在数字位置上你会误以为是数字规则本身写错了。我的处理方式是拆干净NUMBER只认纯数字ID只认「字母或下划线开头 字母数字下划线」点号这种字段引用交给文法去处理写成table . field让点号本身作为一个单字符 Token 走文法归约。多写一条产生式换掉一堆玄学问题非常划算。同理*也不要塞进标识符字符集它本来就是select_name的一个分支。注意词法层每多放一个字符进标识符字符集文法层就少一个可以拿来做错误定位的锚点。字符集从宽是省事但省的是写规则的时间赔的是调试的时间。2.4 词法阶段先自己造脏输入写完规则别急着往语法层走先拿十几条脏输入过一遍比什么评审都管用。我的习惯清单是关键字和标识符连写的SELECTt、运算符紧跟数字的id100、多条语句压在一行的CREATE DATABASE a; USE a;、空语句只有一个分号、缺分号的、带多余空白的、大小写混写的select、以及最关键的——字符常量a。最后这条命中率极高。报告里就明确记了一笔单引号规则没有做转义写成了一串裸单引号结果字符常量根本进不了 Token 流。正确写法是\或者放进方括号里写[]两种都行重点是别在正则里裸奔。这种错的迷惑之处在于它不报错只是在遇到x时悄悄匹配失败然后被兜底规则吃掉或者直接退出你看到的现象是「跑到这里就停了没有报错信息」也就是所谓的黑匣子。3. 语法分析怎么搭从产生式到语法树的实操路径词法跑通只是拿到了原料语法才决定这些原料能不能拼成一条合法语句。这份报告用的是 Yacc 系的生成器文法直接写在规则段里起始符是sts。整套规则覆盖了建库建表、展示、删除、使用、查询、插入、更新、删除八类语句其中相当一部分只写了产生式、没接执行动作。下面按我实际复现时的顺序把判断依据和可抄的部分一起给出。3.1 起始符 sts用闭包模式接住多条语句最上面那条产生式决定了整个分析器的入口形态。报告用的是/* myparser.y 关键片段起始符吸收「任意多条语句」 */ %% sts : /* empty */ { $$ NULL; } | sts st { $$ ast_link($1, $2); } ; st : create_st ; { $$ $1; } | show_st ; { $$ $1; } | drop_st ; { $$ $1; } | use_st ; { $$ $1; } | select_st ; { $$ $1; } | insert_st ; { $$ $1; } | update_st ; { $$ $1; } | delete_st ; { $$ $1; } ; %%sts : sts st | empty是标准的左递归闭包写法作用相当于正则里的st*一条输入里能连续塞多条语句每条以分号收尾。为什么用左递归不用右递归因为 LR 类分析器天生喜欢左递归栈深度是常数级的你换成右递归sts : st sts分析器照样能处理但语法树的构造方向反了——你得在归约到最里层时才开始建树链接顺序和书写顺序相反多写几行翻转代码还容易把语句顺序搞乱。分号的处理也值得说一句。报告把分号放在st层而不是各条语句内部好处是统一所有语句都必须以分号结束检查点只有一个。坏处是少写一个分号时分析器会一直把后面的内容往后吞直到遇到下一个能收尾的东西报错位置往往落后真实位置好几行。这是 LR 分析器的通病不是写法问题靠后面的错误恢复来缓解。$$和$1$2是语义值的传递写法$$是左侧非终结符要产出的结果$1$2是右侧第几个符号带过来的值。要用它们必须先在文件头用%union声明值类型再用%type给非终结符指定具体成员否则所有值都是默认的int语法树指针一传就变成野指针。3.2 比较运算符与 AND/OR%left 只解决一半问题优先级是这个项目里最容易想当然的地方。报告的声明段写了%left AND OR只能说明 AND 和 OR 左结合但没有区分两者的优先级。结果就是a 1 AND b 2 OR c 3这种条件分析器可能先按AND结合出一个复合条件也可能先把OR收掉具体怎么归约取决于分析表属于典型的「跑十次对九次」的诡异问题。正确的做法是分层声明把优先级从低到高排好比较运算符单独一层并声明为非结合/* 优先级从低到高越靠后越先结合 */ %left OR %left AND %nonassoc NE /* 条件产生式不写歧义结构交给优先级解决 */ conditions : condition | ( conditions ) | conditions AND conditions | conditions OR conditions ; condition : comp_left comp_op comp_right ; comp_op : | | | NE ;这样写之后a 1 AND b 2 OR c 3会被正确解析成(a 1 AND b 2) OR c 3因为AND的优先级高于OR比较运算符又高于两者。用%nonassoc而不是%left是为了挡住a b c这种写法——它在你这个语言里没有语义与其让它悄悄归约成(ab)c不如直接报语法错误越早发现越好。还有一处值得改报告里comp_left只能推出table_field也就是说100 id这种常量在左边、字段在右边的写法会被拒掉。严格来说这是合理的限制大多数 SQL 也这么要求但如果你的文法是给学生做演示用的接不住这种写法会让人以为是 bug。要么放宽comp_left让它也能推常量要么在文档里写清限制别让人瞎猜。3.3 左递归还是右递归递归下降与 LR 的取舍生成器选型这件事很多报告一带而过其实是个真判断点。Yacc/Bison 是 LALR(1) 分析器生成器天生偏爱左递归能处理的文法范围比手写递归下降宽手写递归下降写起来直观、好断点、错误信息自己控制但对左递归文法必须改成右递归或者加循环改的时候很容易把优先级搞丢。我的判断标准是三条文法规模超过三十条产生式、需要处理优先级和结合性、需要后期加语句——选 LALR 生成器文法只有十几条、以教学演示为主、要精确控制报错文案——手写递归下降更省心。这个项目显然属于前者八类语句加上字段列表、条件列表、值列表产生式数量早就过了三十条用生成器是合适的。真正让人后悔的是没在第一天把分析器的返回值约定清楚。报告里的main大致是这么写的int main(void) { int n 1; mylexer lexer; myparser parser; if (parser.yycreate(lexer)) { if (lexer.yycreate(parser)) { n parser.yyparse(); /* 0 表示整条输入被完整归约 */ } } return n; }yyparse()返回 0 才算成功非 0 就是语法错误。这个约定必须写进头文件注释因为后面接执行层的时候你的主流程要靠这个返回值决定「要不要执行语法树」。见过太多人在这一步偷懒语法出错也照样把半棵语法树丢给执行层然后数据莫名其妙写坏一半回头查的时候怀疑是文件读写的问题。3.4 语法树节点结构一次定义别返工报告里对语法树只给了图示说明没给结构体定义这是典型的「只可意会」写法。实际动手时这里必须先落定否则后面接执行层要返工。/* 语法树节点kind 决定用哪个字段child 管下层next 管同级 */ typedef enum { N_CREATE_DB, N_CREATE_TB, N_USE, N_SHOW, N_INSERT, N_SELECT, N_DELETE, N_UPDATE, N_FIELD, N_VALUE, N_COND } NodeKind; typedef struct AstNode { NodeKind kind; char *name; /* 库名 / 表名 / 字段名 */ int ival; /* 列宽、常量值 */ struct AstNode *child; /* 字段列表、VALUES 列表、条件子树 */ struct AstNode *next; /* 同级链表用于 a,b,c 这种逗号列表 */ } AstNode;三个字段的分工是child走纵向next走横向。CREATE TABLE t (a INT, b CHAR(10))里两个字段是横向关系挂在child的next链上INSERT INTO t VALUES (1, x)里值列表同理。用一条链把同级元素串起来比开固定长度数组灵活得多也不会因为字段数超过某个上限就崩。判断是否该拆新 kind 的依据是「执行层会不会用不同的函数处理它」。建库和执行是两套逻辑所以拆INT和CHAR(10)都是字段类型执行层在同一个建表函数里处理就不用拆 kind用ival存长度、用name存类型名即可。拆太细会让执行层的 switch 长得没法看拆太粗又得在执行层里做二次判断两头都不讨好。4. 从 AST 到 DBMS执行层怎么接住语法树语法树建出来那一刻编译前端的工作其实只完成了一半。真正决定这个项目能不能叫「DBMS」的是后面那层执行。报告里第三部分写了物理结构和主要功能但内容和前两部分的密度差了一大截篇幅也短这基本是时间不够的典型症状。下面按我复现时补全的思路写。4.1 物理结构一表一文件定长记录教学项目别上 B 树真的。一表一文件、定长记录、行号即偏移这套结构足够撑起除索引外的全部功能而且调试的时候可以用十六进制编辑器直接看数据出问题一眼定位。报告里提到的物理结构就是这个路子只是没把头部定义写出来我补一版/* 表文件头放在文件开头后面紧跟记录区 */ typedef struct { char table_name[32]; int field_cnt; struct { char name[32]; int type; /* 0 INT, 1 CHAR */ int len; /* CHAR 的长度INT 固定为 sizeof(int) */ } fields[16]; int rec_size; /* 一条记录占多少字节建表时算死 */ int rec_cnt; /* 已写入记录数也是下一条记录的槽位号 */ } TableHeader;rec_size在建表那一刻算死之后所有读写都按它做偏移计算第 n 条记录的起始位置是sizeof(TableHeader) n * rec_size。这个设计的好处是随机访问是常数时间的改某一行不用重写整个文件坏处是 CHAR 字段必须定长写不满要补空格。教学项目里这不是问题反而让你必须想清楚「变长和定长各付什么代价」。注意文件头里的rec_cnt是唯一可信的行数来源。别用文件大小反推行数一旦中间有空洞删除留下的空槽算出来的数就是错的。这套结构还有个隐性优势换机器、换编译器都不影响。sizeof(TableHeader)里没有指针全是定长数组和整数拷到另一台机器上照样能读。如果你在表头里塞了char *那这个文件就只能在本进程里用一存盘就废。4.2 三条语句跑通最小闭环CREATE、INSERT、SELECT时间有限的时候优先做这三条。理由很实在建表是所有操作的前提插数据是让表里有东西查询是让你能验证前两步确实生效了。这三条跑通你就有了一个可以自证的闭环答辩或者写报告的时候有东西演示比十条半成品语句有说服力得多。执行层的分发函数建议长这样一个 switch 到底/* 语句分发语法树根节点进来按 kind 走不同执行函数 */ int exec_stmt(AstNode *n) { if (n NULL) return 0; /* 空语句不算错 */ switch (n-kind) { case N_CREATE_DB: return db_create(n-name); case N_CREATE_TB: return tb_create(n-name, n-child); case N_INSERT: return tb_insert(n-name, n-child); case N_SELECT: return tb_select(n-name, n-child); case N_USE: return db_use(n-name); default: return ERR_UNSUPPORTED; /* 未实现统一走这里不崩 */ } }n-child在不同 kind 下语义不同建表时是字段定义链插入时是值链查询时是字段选择链。这种「一个字段多种含义」的做法在小型项目里完全可以接受前提是每个执行函数开头都断言一下child的结构别让错位的树悄悄跑进去。返回值统一用 0 表示成功、负数表示错误码调用方只关心正负具体错误码在函数内部打日志。值得单独提醒的是db_use切库不是改个全局变量就完事你得让后续所有路径拼接都带上当前库名否则CREATE TABLE t到底建在哪个库就成了悬案。最简单的办法是维护一个当前工作目录字符串所有文件操作前做一次拼路径退出时再清掉。4.3 没实现的语句怎么留接口报告里明确写了「已有设计思想但尚未实现的语句」这个态度比硬凑功能诚实得多。留接口的关键是让未实现的部分明确失败而不是静默跳过。default: return ERR_UNSUPPORTED;这一行的价值就在这里——用户输入DROP TABLE t;你会回一句「暂不支持」而不是什么都不做让人以为删掉了。前后差别巨大前者是可用的半成品后者是会吃数据的黑匣子。接口预留上还有一个细节即使不实现DROP、UPDATE、DELETE的语法树节点也应该建出来。理由是你不知道后面什么时候会补如果文法里压根没有它们的位置补的时候要动文法、动%token、动语法树定义、动分发四个地方一起改如果只是分发里少一个 case补起来就是十分钟的事。5. 避坑与排查五个当年真翻车的地方这一节是整篇里最该先看的。下面五条都来自实际跑代码时踩出来的坑按「现象 → 原因 → 解决」写能对号入座就别自己再撞一遍。5.1 单引号没转义字符常量直接消失现象测试INSERT INTO t VALUES (abc);程序跑到一半停了没有任何报错也没有任何输出像被吞掉一样。原因词法规则里写的是裸单引号没有做转义生成器把它当成了字符串边界或者直接匹配失败导致这条规则形同虚设字符常量进不了 Token 流分析器在期望常量的位置等不到东西就卡在那里。解决规则里写\或者用字符类[]两种都能让单引号变成一个普通字符。改完立刻跑一条最短用例验证只输入a;看能不能吐出常量 Token。这类「不报错只是卡住」的问题一定要用最小用例定位别在长语句里猜。5.2 标识符规则把数字截走报错位置全错现象SELECT * FROM t WHERE id 100;报语法错误错误位置指向100但NUMBER规则明明写了。原因标识符的字符集里带上了数字和括号点号匹配时比数字规则更「长」优先把整块吃成了标识符。分析器在comp_right位置期望NUMBER却拿到标识符归约失败。报告里对这条的记录是「Name 会把 NUMBER 截获」本质就是字符集太宽。解决三条规则拆干净数字只认[0-9]标识符只认字母下划线开头点号留给文法处理。改完跑WHERE id 100和WHERE id t.id两条用例确认两条路径都能通。5.3 条件产生式有歧义跑十次对九次现象WHERE a 1 AND b 2 OR c 3有时候结果对有时候不对换个顺序写又好了。原因优先级声明只写了%left AND OR没区分两者高低文法里conditions又是直接递归分析表在冲突点上的选择不确定。解决按 3.2 节那样分层声明优先级OR低、AND高、比较运算符最高且非结合。改完用生成器的冲突报告验证规则冲突应该清零或者只剩预期内的移进—归约冲突。5.4 关键字重叠规则写得越全错得越隐蔽现象SHOW TABLES;被解析成SHOW 标识符TABLES语法报错说后面缺表名。原因TABLE和TABLES、DATABASE和DATABASES是前缀关系如果只写了短的那条、或者长的那条排在短的后面的且字符集允许长词就会被切开。解决单复数各占一个 Token且长词规则写在短词前面。这不是理论问题是最长匹配的实际表现——生成器选最长的那条你只要保证长的那条存在且完整短词就不会误吃。5.5 没有错误恢复一处错就一路错到底现象输入里少一个分号程序把后面十行内容全部吞进去最后报一个跟真实位置差了很远的错误。原因st层以分号收尾缺分号时分析器会一直往后找能收尾的符号错误检测点被推到很后面加上文法里没有错误产生式遇到非法 Token 直接终止不给任何恢复机会。解决在st层加一条错误恢复产生式遇到非法符号时跳到下一个分号重新同步同时把出错位置记进错误列表而不是直接退出。教学项目里加这一条的成本很低但对调试体验的提升是数量级的。6. 把这份报告变成能跑的东西一条最小验证路径拿到这套代码之后别急着整体编译。按下面这个顺序走每步都有明确的通过标准卡住了就知道问题在哪一层。步骤动作通过标准1单独编译词法器喂CREATE DATABASE a;输出 Token 序列关键字和标识符各就各位2喂a;和!两类边界输入常量与双字符运算符都能正确切分3加语法规则只跑st : create_st ;单条建库语句归约成功返回 04逐条放开 show、use、create table每放开一条就跑一条对应用例别一次全开5接执行层先只做建库建表磁盘上能看到文件文件头字段数与输入一致6补 insert 和 select插进去的数据能原样查出来工具链有个必须注意的差异报告里的mylexer、myparser是代码生成向导产出的 C 类接口是yycreate和yyparse挂在对象上原生 flex/bison 生成的是全局函数yylex和yyparse没有这些包装。直接拿现在的工具链去编这份代码第一关就会在yycreate未定义上卡住。要么沿用当年那套生成器要么把main改写成全局函数调用两条路都行但别指望代码原样能编过——这一点报告里没写属于时代差异。回过头看这个项目最值钱的不是那几条跑通的语句而是它把「没做完」和「哪里翻了车」都写进了文档。我后来带别人做类似的上机都会强制先跑三张脏输入用例一条带字符常量的、一条带数字比较的、一条缺分号的。三张全过再谈功能扩展。这个习惯是从当年盯着屏幕找不到报错原因的那几个小时里长出来的比任何教程都管用。希望帮到你。本文还有配套的精品资源点击获取
简介这份编译原理上机报告面向计算机科学与技术等专业学生聚焦编译原理课程设计与上机实验场景解决从词法、语法分析到简易数据库管理系统落地的完整方案参考问题。报告以《DBMS 的设计与实现》为主线依次覆盖项目概况与分工、基于 lex 与 yacc 的词法分析与语法分析实现、DBMS 的物理结构与核心功能设计并附上机心得与改进建议目录层级清晰便于按模块对照学习。压缩包内共 1 个 doc 文档约 82KB属于轻量级文字报告适合直接查阅实现思路与报告写作框架。该资源已有 1332 人学习说明其在课程报告参考场景中具有一定认可度。读者可从中获取词法规则与语法规则的组织方式、编译前端与数据管理模块的衔接思路以及表创建、增删改查、索引与事务等功能的规划要点也可借鉴报告章节编排与心得总结的写法用于自己的上机实践与文档整理。1. 一份 2011 年的编译原理上机报告值得现在翻出来看什么2011 年 5 月某高校一份编译原理上机报告题目叫《DBMS 的设计与实现》全程一个人做完。词法分析用 Lex 系的代码生成器写语法分析用 Yacc 系的生成器写编译环境是 VC6.0报告里老老实实写了「完成的语句」和「只有设计思想、尚未实现的语句」两栏。这份编译原理上机报告最值钱的地方恰恰不是它做完了多少功能而是它把翻车现场原样留在了纸面上单引号没转义导致字符常量识别不了标识符规则把数字截走导致报错报到怀疑人生。这篇东西写给三类人正在做课程设计、不知道怎么从正规式走到 Token 流的已经把语法跑通、卡在「语法树怎么接到执行层」的还有带别人做上机、想找一份能直接照着讲的踩坑清单的。下面按词法、语法、执行层、避坑、验证五段拆能抄的直接抄抄之前先看判断依据。2. 词法分析怎么拆从正规式到 Token 流的三层结构词法分析看着简单实际上手才知道坑都在细节里。一条SELECT * FROM t WHERE id 100;丢进去好的词法器吐出来的是一串带类型的 Token差一点的是能过但后面语法分析天天报错最差的是 Token 勉强对了、位置信息全丢出错时你根本不知道错在第几个字符。这份报告的 lex 部分走的是「关键字枚举 标识符 数字 运算符」四类切分结构不复杂但顺序和字符集两处稍不注意就会连锁反应。2.1 先把 Token 表定死再动手写规则我一般建议先列一张 Token 表别急着打开生成器写正则。表定下来了正则就是照着表填空表没定写到一半发现TABLES和TABLE混了回头改一遍规则、再改一遍文法、再改一遍语法树节点一天就没了。这份报告里的 Token 集合是围绕 SQL 子集设计的整理出来大致是这样Token 名匹配内容类别说明CREATE / DATABASE / DATABASES库级操作关键字保留字大小写写死不做大小写折叠TABLE / TABLES / SHOW / USE / DROP表级操作关键字保留字单复数各占一个 Token别合并SELECT / INSERT / VALUES / UPDATE / DELETEDML 关键字保留字VALUES 只在 INSERT 后出现WHERE / FROM / INTO / SET / AND / OR子句关键字保留字AND、OR 参与优先级声明INT / CHAR / NULLX类型与空值关键字NULLX 是为了避开 C 头文件里的 NULL 宏ID库名、表名、字段名标识符首字符必须是字母或下划线NUMBER列宽、比较常量字面量纯数字本层不处理正负号!不等比较运算符必须排在单字符前面( ) , ; * 分隔与比较符号单字符直接返回字符本身即可表里有两处很容易被忽略的判断依据。一处是单复数拆成两个 TokenSHOW TABLE t和SHOW TABLES是两条语义不同的语句如果你用一条SHOWID硬凑语义分析阶段就得靠字符串比较来区分等于把词法该干的活推给了后面。另一处是NULLX这个命名看着别扭其实是被迫的——C 语言里NULL是宏你在%token里写NULL预处理阶段就被替换掉了编译报错你都找不到源头。这种名字上的将就恰恰是做过一遍的人才写得出来的。提示Token 表里凡是「单复数」「近义词」成对出现的先在表阶段决定是拆是合别留到文法阶段临时想办法。2.2 规则顺序与实际匹配关键字必须跑在标识符前面词法生成器的匹配规则通常是「最长匹配优先同等长度按规则出现顺序」。很多人只记住了前半句结果把标识符规则写在关键字前面跑SELECT这种恰好也能被标识符正则吃下的词出现「有时候对有时候错」的玄学现象。原因是长度相同时先出现的规则赢。这份报告里关键字规则是集中写在标识符规则之前的顺序没出问题主体片段大约长这样/* mylexer.l 关键片段规则顺序即优先级先吃特殊再吃通用 */ %{ #include myparser.h #include define.h %} %option noyywrap %% [ \t\r] { /* 空白直接吞掉不产生 token但要保留行号 */ } CREATE { return CREATE; } DATABASE { return DATABASE; } DATABASES { return DATABASES; } TABLE { return TABLE; } TABLES { return TABLES; } SELECT { return SELECT; } INSERT { return INSERT; } VALUES { return VALUES; } WHERE { return WHERE; } FROM { return FROM; } ! { return NE; } /* 双字符运算符必须在单字符之前 */ | | | * { return yytext[0]; } /* 单字符直接回传 ASCII */ [0-9] { yylval atoi(yytext); return NUMBER; } [a-zA-Z_][a-zA-Z_0-9]* { yylval strdup(yytext); return ID; } %%这段规则里关键字写在标识符前面是「防御性写法」哪怕生成器改成了其他匹配策略你也不会突然翻车。!排在前面也是同一个道理如果先匹配!就会被切成!未定义直接报错和两个 Token语法分析那边拿到的是一堆对不上的东西。代码之后要补一句参数说明yylval是给语法分析器传值用的联合体atoi把数字串转成intstrdup把标识符拷进堆内存——注意这里必须拷贝因为yytext是复用的缓冲区你不拷贝下一个 Token 一进来内容就被覆盖了语法树里所有名字最后都变成最后一个标识符。这个坑比前面几个更隐蔽因为它在小用例上根本不发作只有一条语句里出现两个以上标识符时才会暴露。还有一点报告里标识符规则后面跟了一句printf(%s, yytext);做调试输出。我理解调试期想看匹配结果的心情但这行必须在上交前删掉或者在编译开关里关掉否则你跑一条INSERT INTO t VALUES (1);屏幕上会糊出一串粘在一起的标识符出错了根本分不清是词法打印的还是语法打印的。2.3 三条标识符类规则怎么分工Name、ID、NUMBER这份报告最典型的一处设计是把「名字」拆成了Name和ID两条规则再加上NUMBER一共三条能吞字符的规则。原稿的做法是让Name的字符集放宽到能带().*这些字符本意是想一把兜住t.id、t.*这类带点号的字段引用结果埋了两个雷。第一个雷是字符集重叠[a-zA-Z][_0-9a-zA-Z()\.\*]*和[a-zA-Z][_a-zA-Z0-9]都能匹配普通标识符前者因为更长而经常胜出于是正常的表名也走了Name分支语法分析里期望ID的地方拿到Name归约直接失败。第二个雷更严重宽字符集让Name有能力把后面跟着的数字也吃进同一个 TokenWHERE id 100里的100在某些上下文下变成了一整块Name而文法里comp_right期望的是NUMBER于是报错信息全落在数字位置上你会误以为是数字规则本身写错了。我的处理方式是拆干净NUMBER只认纯数字ID只认「字母或下划线开头 字母数字下划线」点号这种字段引用交给文法去处理写成table . field让点号本身作为一个单字符 Token 走文法归约。多写一条产生式换掉一堆玄学问题非常划算。同理*也不要塞进标识符字符集它本来就是select_name的一个分支。注意词法层每多放一个字符进标识符字符集文法层就少一个可以拿来做错误定位的锚点。字符集从宽是省事但省的是写规则的时间赔的是调试的时间。2.4 词法阶段先自己造脏输入写完规则别急着往语法层走先拿十几条脏输入过一遍比什么评审都管用。我的习惯清单是关键字和标识符连写的SELECTt、运算符紧跟数字的id100、多条语句压在一行的CREATE DATABASE a; USE a;、空语句只有一个分号、缺分号的、带多余空白的、大小写混写的select、以及最关键的——字符常量a。最后这条命中率极高。报告里就明确记了一笔单引号规则没有做转义写成了一串裸单引号结果字符常量根本进不了 Token 流。正确写法是\或者放进方括号里写[]两种都行重点是别在正则里裸奔。这种错的迷惑之处在于它不报错只是在遇到x时悄悄匹配失败然后被兜底规则吃掉或者直接退出你看到的现象是「跑到这里就停了没有报错信息」也就是所谓的黑匣子。3. 语法分析怎么搭从产生式到语法树的实操路径词法跑通只是拿到了原料语法才决定这些原料能不能拼成一条合法语句。这份报告用的是 Yacc 系的生成器文法直接写在规则段里起始符是sts。整套规则覆盖了建库建表、展示、删除、使用、查询、插入、更新、删除八类语句其中相当一部分只写了产生式、没接执行动作。下面按我实际复现时的顺序把判断依据和可抄的部分一起给出。3.1 起始符 sts用闭包模式接住多条语句最上面那条产生式决定了整个分析器的入口形态。报告用的是/* myparser.y 关键片段起始符吸收「任意多条语句」 */ %% sts : /* empty */ { $$ NULL; } | sts st { $$ ast_link($1, $2); } ; st : create_st ; { $$ $1; } | show_st ; { $$ $1; } | drop_st ; { $$ $1; } | use_st ; { $$ $1; } | select_st ; { $$ $1; } | insert_st ; { $$ $1; } | update_st ; { $$ $1; } | delete_st ; { $$ $1; } ; %%sts : sts st | empty是标准的左递归闭包写法作用相当于正则里的st*一条输入里能连续塞多条语句每条以分号收尾。为什么用左递归不用右递归因为 LR 类分析器天生喜欢左递归栈深度是常数级的你换成右递归sts : st sts分析器照样能处理但语法树的构造方向反了——你得在归约到最里层时才开始建树链接顺序和书写顺序相反多写几行翻转代码还容易把语句顺序搞乱。分号的处理也值得说一句。报告把分号放在st层而不是各条语句内部好处是统一所有语句都必须以分号结束检查点只有一个。坏处是少写一个分号时分析器会一直把后面的内容往后吞直到遇到下一个能收尾的东西报错位置往往落后真实位置好几行。这是 LR 分析器的通病不是写法问题靠后面的错误恢复来缓解。$$和$1$2是语义值的传递写法$$是左侧非终结符要产出的结果$1$2是右侧第几个符号带过来的值。要用它们必须先在文件头用%union声明值类型再用%type给非终结符指定具体成员否则所有值都是默认的int语法树指针一传就变成野指针。3.2 比较运算符与 AND/OR%left 只解决一半问题优先级是这个项目里最容易想当然的地方。报告的声明段写了%left AND OR只能说明 AND 和 OR 左结合但没有区分两者的优先级。结果就是a 1 AND b 2 OR c 3这种条件分析器可能先按AND结合出一个复合条件也可能先把OR收掉具体怎么归约取决于分析表属于典型的「跑十次对九次」的诡异问题。正确的做法是分层声明把优先级从低到高排好比较运算符单独一层并声明为非结合/* 优先级从低到高越靠后越先结合 */ %left OR %left AND %nonassoc NE /* 条件产生式不写歧义结构交给优先级解决 */ conditions : condition | ( conditions ) | conditions AND conditions | conditions OR conditions ; condition : comp_left comp_op comp_right ; comp_op : | | | NE ;这样写之后a 1 AND b 2 OR c 3会被正确解析成(a 1 AND b 2) OR c 3因为AND的优先级高于OR比较运算符又高于两者。用%nonassoc而不是%left是为了挡住a b c这种写法——它在你这个语言里没有语义与其让它悄悄归约成(ab)c不如直接报语法错误越早发现越好。还有一处值得改报告里comp_left只能推出table_field也就是说100 id这种常量在左边、字段在右边的写法会被拒掉。严格来说这是合理的限制大多数 SQL 也这么要求但如果你的文法是给学生做演示用的接不住这种写法会让人以为是 bug。要么放宽comp_left让它也能推常量要么在文档里写清限制别让人瞎猜。3.3 左递归还是右递归递归下降与 LR 的取舍生成器选型这件事很多报告一带而过其实是个真判断点。Yacc/Bison 是 LALR(1) 分析器生成器天生偏爱左递归能处理的文法范围比手写递归下降宽手写递归下降写起来直观、好断点、错误信息自己控制但对左递归文法必须改成右递归或者加循环改的时候很容易把优先级搞丢。我的判断标准是三条文法规模超过三十条产生式、需要处理优先级和结合性、需要后期加语句——选 LALR 生成器文法只有十几条、以教学演示为主、要精确控制报错文案——手写递归下降更省心。这个项目显然属于前者八类语句加上字段列表、条件列表、值列表产生式数量早就过了三十条用生成器是合适的。真正让人后悔的是没在第一天把分析器的返回值约定清楚。报告里的main大致是这么写的int main(void) { int n 1; mylexer lexer; myparser parser; if (parser.yycreate(lexer)) { if (lexer.yycreate(parser)) { n parser.yyparse(); /* 0 表示整条输入被完整归约 */ } } return n; }yyparse()返回 0 才算成功非 0 就是语法错误。这个约定必须写进头文件注释因为后面接执行层的时候你的主流程要靠这个返回值决定「要不要执行语法树」。见过太多人在这一步偷懒语法出错也照样把半棵语法树丢给执行层然后数据莫名其妙写坏一半回头查的时候怀疑是文件读写的问题。3.4 语法树节点结构一次定义别返工报告里对语法树只给了图示说明没给结构体定义这是典型的「只可意会」写法。实际动手时这里必须先落定否则后面接执行层要返工。/* 语法树节点kind 决定用哪个字段child 管下层next 管同级 */ typedef enum { N_CREATE_DB, N_CREATE_TB, N_USE, N_SHOW, N_INSERT, N_SELECT, N_DELETE, N_UPDATE, N_FIELD, N_VALUE, N_COND } NodeKind; typedef struct AstNode { NodeKind kind; char *name; /* 库名 / 表名 / 字段名 */ int ival; /* 列宽、常量值 */ struct AstNode *child; /* 字段列表、VALUES 列表、条件子树 */ struct AstNode *next; /* 同级链表用于 a,b,c 这种逗号列表 */ } AstNode;三个字段的分工是child走纵向next走横向。CREATE TABLE t (a INT, b CHAR(10))里两个字段是横向关系挂在child的next链上INSERT INTO t VALUES (1, x)里值列表同理。用一条链把同级元素串起来比开固定长度数组灵活得多也不会因为字段数超过某个上限就崩。判断是否该拆新 kind 的依据是「执行层会不会用不同的函数处理它」。建库和执行是两套逻辑所以拆INT和CHAR(10)都是字段类型执行层在同一个建表函数里处理就不用拆 kind用ival存长度、用name存类型名即可。拆太细会让执行层的 switch 长得没法看拆太粗又得在执行层里做二次判断两头都不讨好。4. 从 AST 到 DBMS执行层怎么接住语法树语法树建出来那一刻编译前端的工作其实只完成了一半。真正决定这个项目能不能叫「DBMS」的是后面那层执行。报告里第三部分写了物理结构和主要功能但内容和前两部分的密度差了一大截篇幅也短这基本是时间不够的典型症状。下面按我复现时补全的思路写。4.1 物理结构一表一文件定长记录教学项目别上 B 树真的。一表一文件、定长记录、行号即偏移这套结构足够撑起除索引外的全部功能而且调试的时候可以用十六进制编辑器直接看数据出问题一眼定位。报告里提到的物理结构就是这个路子只是没把头部定义写出来我补一版/* 表文件头放在文件开头后面紧跟记录区 */ typedef struct { char table_name[32]; int field_cnt; struct { char name[32]; int type; /* 0 INT, 1 CHAR */ int len; /* CHAR 的长度INT 固定为 sizeof(int) */ } fields[16]; int rec_size; /* 一条记录占多少字节建表时算死 */ int rec_cnt; /* 已写入记录数也是下一条记录的槽位号 */ } TableHeader;rec_size在建表那一刻算死之后所有读写都按它做偏移计算第 n 条记录的起始位置是sizeof(TableHeader) n * rec_size。这个设计的好处是随机访问是常数时间的改某一行不用重写整个文件坏处是 CHAR 字段必须定长写不满要补空格。教学项目里这不是问题反而让你必须想清楚「变长和定长各付什么代价」。注意文件头里的rec_cnt是唯一可信的行数来源。别用文件大小反推行数一旦中间有空洞删除留下的空槽算出来的数就是错的。这套结构还有个隐性优势换机器、换编译器都不影响。sizeof(TableHeader)里没有指针全是定长数组和整数拷到另一台机器上照样能读。如果你在表头里塞了char *那这个文件就只能在本进程里用一存盘就废。4.2 三条语句跑通最小闭环CREATE、INSERT、SELECT时间有限的时候优先做这三条。理由很实在建表是所有操作的前提插数据是让表里有东西查询是让你能验证前两步确实生效了。这三条跑通你就有了一个可以自证的闭环答辩或者写报告的时候有东西演示比十条半成品语句有说服力得多。执行层的分发函数建议长这样一个 switch 到底/* 语句分发语法树根节点进来按 kind 走不同执行函数 */ int exec_stmt(AstNode *n) { if (n NULL) return 0; /* 空语句不算错 */ switch (n-kind) { case N_CREATE_DB: return db_create(n-name); case N_CREATE_TB: return tb_create(n-name, n-child); case N_INSERT: return tb_insert(n-name, n-child); case N_SELECT: return tb_select(n-name, n-child); case N_USE: return db_use(n-name); default: return ERR_UNSUPPORTED; /* 未实现统一走这里不崩 */ } }n-child在不同 kind 下语义不同建表时是字段定义链插入时是值链查询时是字段选择链。这种「一个字段多种含义」的做法在小型项目里完全可以接受前提是每个执行函数开头都断言一下child的结构别让错位的树悄悄跑进去。返回值统一用 0 表示成功、负数表示错误码调用方只关心正负具体错误码在函数内部打日志。值得单独提醒的是db_use切库不是改个全局变量就完事你得让后续所有路径拼接都带上当前库名否则CREATE TABLE t到底建在哪个库就成了悬案。最简单的办法是维护一个当前工作目录字符串所有文件操作前做一次拼路径退出时再清掉。4.3 没实现的语句怎么留接口报告里明确写了「已有设计思想但尚未实现的语句」这个态度比硬凑功能诚实得多。留接口的关键是让未实现的部分明确失败而不是静默跳过。default: return ERR_UNSUPPORTED;这一行的价值就在这里——用户输入DROP TABLE t;你会回一句「暂不支持」而不是什么都不做让人以为删掉了。前后差别巨大前者是可用的半成品后者是会吃数据的黑匣子。接口预留上还有一个细节即使不实现DROP、UPDATE、DELETE的语法树节点也应该建出来。理由是你不知道后面什么时候会补如果文法里压根没有它们的位置补的时候要动文法、动%token、动语法树定义、动分发四个地方一起改如果只是分发里少一个 case补起来就是十分钟的事。5. 避坑与排查五个当年真翻车的地方这一节是整篇里最该先看的。下面五条都来自实际跑代码时踩出来的坑按「现象 → 原因 → 解决」写能对号入座就别自己再撞一遍。5.1 单引号没转义字符常量直接消失现象测试INSERT INTO t VALUES (abc);程序跑到一半停了没有任何报错也没有任何输出像被吞掉一样。原因词法规则里写的是裸单引号没有做转义生成器把它当成了字符串边界或者直接匹配失败导致这条规则形同虚设字符常量进不了 Token 流分析器在期望常量的位置等不到东西就卡在那里。解决规则里写\或者用字符类[]两种都能让单引号变成一个普通字符。改完立刻跑一条最短用例验证只输入a;看能不能吐出常量 Token。这类「不报错只是卡住」的问题一定要用最小用例定位别在长语句里猜。5.2 标识符规则把数字截走报错位置全错现象SELECT * FROM t WHERE id 100;报语法错误错误位置指向100但NUMBER规则明明写了。原因标识符的字符集里带上了数字和括号点号匹配时比数字规则更「长」优先把整块吃成了标识符。分析器在comp_right位置期望NUMBER却拿到标识符归约失败。报告里对这条的记录是「Name 会把 NUMBER 截获」本质就是字符集太宽。解决三条规则拆干净数字只认[0-9]标识符只认字母下划线开头点号留给文法处理。改完跑WHERE id 100和WHERE id t.id两条用例确认两条路径都能通。5.3 条件产生式有歧义跑十次对九次现象WHERE a 1 AND b 2 OR c 3有时候结果对有时候不对换个顺序写又好了。原因优先级声明只写了%left AND OR没区分两者高低文法里conditions又是直接递归分析表在冲突点上的选择不确定。解决按 3.2 节那样分层声明优先级OR低、AND高、比较运算符最高且非结合。改完用生成器的冲突报告验证规则冲突应该清零或者只剩预期内的移进—归约冲突。5.4 关键字重叠规则写得越全错得越隐蔽现象SHOW TABLES;被解析成SHOW 标识符TABLES语法报错说后面缺表名。原因TABLE和TABLES、DATABASE和DATABASES是前缀关系如果只写了短的那条、或者长的那条排在短的后面的且字符集允许长词就会被切开。解决单复数各占一个 Token且长词规则写在短词前面。这不是理论问题是最长匹配的实际表现——生成器选最长的那条你只要保证长的那条存在且完整短词就不会误吃。5.5 没有错误恢复一处错就一路错到底现象输入里少一个分号程序把后面十行内容全部吞进去最后报一个跟真实位置差了很远的错误。原因st层以分号收尾缺分号时分析器会一直往后找能收尾的符号错误检测点被推到很后面加上文法里没有错误产生式遇到非法 Token 直接终止不给任何恢复机会。解决在st层加一条错误恢复产生式遇到非法符号时跳到下一个分号重新同步同时把出错位置记进错误列表而不是直接退出。教学项目里加这一条的成本很低但对调试体验的提升是数量级的。6. 把这份报告变成能跑的东西一条最小验证路径拿到这套代码之后别急着整体编译。按下面这个顺序走每步都有明确的通过标准卡住了就知道问题在哪一层。步骤动作通过标准1单独编译词法器喂CREATE DATABASE a;输出 Token 序列关键字和标识符各就各位2喂a;和!两类边界输入常量与双字符运算符都能正确切分3加语法规则只跑st : create_st ;单条建库语句归约成功返回 04逐条放开 show、use、create table每放开一条就跑一条对应用例别一次全开5接执行层先只做建库建表磁盘上能看到文件文件头字段数与输入一致6补 insert 和 select插进去的数据能原样查出来工具链有个必须注意的差异报告里的mylexer、myparser是代码生成向导产出的 C 类接口是yycreate和yyparse挂在对象上原生 flex/bison 生成的是全局函数yylex和yyparse没有这些包装。直接拿现在的工具链去编这份代码第一关就会在yycreate未定义上卡住。要么沿用当年那套生成器要么把main改写成全局函数调用两条路都行但别指望代码原样能编过——这一点报告里没写属于时代差异。回过头看这个项目最值钱的不是那几条跑通的语句而是它把「没做完」和「哪里翻了车」都写进了文档。我后来带别人做类似的上机都会强制先跑三张脏输入用例一条带字符常量的、一条带数字比较的、一条缺分号的。三张全过再谈功能扩展。这个习惯是从当年盯着屏幕找不到报错原因的那几个小时里长出来的比任何教程都管用。希望帮到你。本文还有配套的精品资源点击获取
