编译原理课设：从词法DFA到四元式的全链路实现与排错-北京尧图网络

简介这份《北邮编译原理课程设计》面向学习编译原理、需要完成课程设计或自建小型编译器的读者以Pascal语言为示例覆盖词法分析、语法分析、语义检查、符号表管理、错误处理与代码生成等核心环节。压缩包为rar格式共83个文件、约123KB包含21个h头文件、19个cpp源文件、8个pas示例程序、8个asm汇编文件及8个bin可执行或二进制文件另有rez资源脚本等便于对照编译器各模块的实现。已有1196人学习说明其在校内课程与自学场景中具有一定参考价值。读者可据此梳理Pascal编译器的整体结构观察高级语言到汇编或机器指令的转换路径并借鉴虚拟执行、测试样例与界面资源组织方式为完成同类课程设计、理解编译流程和排查实现问题提供较完整的实践参照。1. 编译器课设的真相跑通只是及格线契约稳才是分数编译原理课程设计最反直觉的一点是把一段几十行的文法跑通通常只花掉总工期的三成剩下七成全耗在三层之间的数据契约上——词法给语法的是不是带着位置信息的 token语法给语义的是不是一棵能回溯到源码位置的语法树语义给后端的是不是已经消解了作用域的四元式。这些接口一旦含糊后面每加一条文法都要把旧代码重新翻一遍血泪经验基本都出在这儿。搞懂这条链路上的机制比背下 LL(1) 的构造算法有用得多它决定了编译器报错时你能不能看懂它在抱怨什么也决定了你半夜改文法时会不会把已经跑通的用例全弄翻。这套课设资料的价值正在于它把这条链路的每一环都摊开成了可读的实现而不是把结论糊在 PPT 上。2. 词法分析正则表达式为什么最终要落成一张 DFA 表几乎所有人第一次写词法分析器都是从一个巨型if-else链开始的先判断是不是数字再判断是不是字母然后判断是不是双字符运算符。这段代码跑起来没问题但它和课本上的正则表达式、NFA、DFA 之间隔着一层看不见的等价关系——手写的if-else链其实就是一个 DFA只不过状态被藏进了程序计数器里。理解这层等价关系是后面所有调试工作的前提。因为一旦你的扫描器在某个字符上报错你需要的不是加一个if而是问当前状态是什么这个字符属于哪个等价类转移表里为什么没有出边。这个问题只有把扫描器当成表来看才回答得清楚。2.1 子集构造到底在合并什么正则表达式到 DFA 的标准路径是三段Thompson 构造把正则变成带 ε 边的 NFA子集构造把 NFA 的状态集合压成 DFA 的单个状态最小化再去掉等价状态。课设里最容易被跳过、又最影响后续性能的是子集构造这一步。它的核心动作是「把一组 NFA 状态当成一个 DFA 状态」。因为 NFA 在同一时刻可以处在多个状态上而 DFA 只能有一个当前状态所以要让 DFA 模拟 NFA就必须把「可能同时处在的状态集合」整体打包。走一步ε-闭包读一个字符再求一次闭包得到的新集合如果没见过就分配一个新状态编号。状态爆炸的来源也在这里。一个含 k 个状态的 NFA理论上最多能炸出 2^k 个 DFA 状态实际工程里靠两件事压住一是把字符按等价类合并所有数字是同一类所有字母是同一类所有没被任何正则用到的字符统统归到「其它」类二是很多子集压根不可达。课设里的词法规则通常只有关键字、标识符、整数、浮点、运算符、界符这几类压缩之后转移表往往只有几十行。提示字符等价类不是可选的优化而是子集构造能落地的关键。不做等价类转移表的列数等于字符集大小可读性和体积都会失控。手写扫描器和表驱动扫描器的差别本质是「状态转移到代码里」还是「状态转移到数据里」。前者调试靠打断点后者调试靠打印一行表。2.2 最长匹配与回退一个字符的 lookahead 值多少钱词法分析里最容易翻车的一条规则叫最长匹配也叫 maximal munch扫描器必须吃掉尽可能多的字符再决定这是什么 token。if既是关键字也是合法标识符123abc里的123是整数但整个串非法不能被拆成和。这些判断都依赖同一件事——记住最后一次「处在一个接受状态」的位置。于是扫描器的主循环变成一直往前读每进入一个接受状态就记下当前位置一旦走进死状态就回退到最近一次接受点。这个回退动作在源码里通常只有一行赋值但它是所有「双字符运算符被误切成两个单字符」问题的根源。# 表驱动扫描器正则被编译成转移表运行期只做查表 # class_of 把字符映射成等价类等价类来自子集构造时的字符合并 def class_of(c): if c.isdigit(): return 0 # 数字类 if c.isalpha() or c _: return 1 # 标识符字符类 return 2 # 其它单字符运算符与界符 # TRANS[state][class] next_state负数表示该状态没有出边 TRANS [ [1, 3, 2], # 0 起始状态 [-1, -1, -1], # 1 接受整数不再有出边 [-1, -1, -1], # 2 接受单字符运算符/界符 [3, 3, -1], # 3 标识符中间态数字和字母都能继续吃 ] ACCEPT {1: INT, 2: OP, 3: ID} def scan(src, i): state, start 0, i accept_state, accept_end None, start while i len(src): to TRANS[state][class_of(src[i])] if to 0: break state to i 1 if state in ACCEPT: # 记录最长匹配的落点供后面回退使用 accept_state, accept_end state, i if accept_state is None: raise SyntaxError(f非法字符 {src[start]!r}位置 {start}) # 注意这里返回 accept_end 而不是 ii 可能已经越过接受点 return ACCEPT[accept_state], src[start:accept_end], accept_endTRANS的每一行对应一个 DFA 状态每一列对应一个字符等价类这是子集构造的直接产物ACCEPT把接受状态映射回 token 类型是「哪个状态算数」的声明。scan的返回值里第三个是新的读取位置调用方必须用它推进游标而不是自己1否则回退逻辑会被外部破坏。关键字识别的经典做法不在表里做扫描器先按标识符规则吃掉整个串再查一张关键字哈希表命中就改类型。这样TRANS不用为每个关键字开一条独立路径新增关键字只改表不改状态机。位置信息行号、列号必须在扫描阶段就算好别指望语法分析器回头去数换行。语法树节点的行列号是报错时唯一的坐标缺了它所有错误信息都只能写成「某处有语法错误」这种输出在验收现场基本等于没写。2.3 手写扫描器与生成器怎么选课设里两条路都有人走。手写扫描器代码短、调试直观、错误恢复好做可以直接跳过非法字符继续扫缺点是文法一变就得改代码。用生成器如 lex 系工具则把规则集中在一处改文法只改规则文件缺点是生成出来的表和源程序脱节出了错只能对着表猜。常见的实现思路是折中扫描器主体手写但把转移表抽成数据让TRANS和ACCEPT独立于主循环存在。这样既保留了手写的可读性又保留了「改规则只改表」的便利调试时把表打出来就能看出状态机长什么样。3. 语法分析递归下降和 LR 表驱动到底差在哪词法分析交付的是一串带位置的 token语法分析要做的是把这串线性输入还原成树。所有语法分析算法的本质都是同一个问题在只看到有限个 token 的前提下怎么确定该用哪条产生式。这个「有限」就是 lookahead它决定了你的分析器能处理多复杂的文法也决定了你会在什么时候撞上冲突。课设里最常见的两种选择是递归下降配 LL(1)和表驱动 LRSLR/LALR。它们的分歧点不在算法难度而在「冲突暴露给谁」——递归下降把冲突暴露给写文法的人LR 把冲突暴露给构造分析表的人。3.1 LL(1) 的确定性边界递归下降之所以能一句话对上一条产生式靠的是 FIRST 集和 FOLLOW 集。当非终结符 A 有两条候选A - α和A - β时只要 FIRST(α) 和 FIRST(β) 不相交看一个 token 就能决定走哪条如果某条候选能推出空串还得保证 FIRST(α) 和 FOLLOW(A) 也不相交。这条边界非常硬。if E then S else S这种文法能过因为then和else是显式终结符但经典的悬空 else 文法在 LL(1) 下直接冲突因为else既可能启动内层 if 的 else 分支也可能是外层 if 的 else 部分。这不是实现 bug是 lookahead 长度不够导致的本质信息缺失。课程设计里撞上 FIRST/FOLLOW 冲突一般三条路改写文法提左公因子、消除左递归、增加 lookaheadLL(2) 或回溯、改用 LR。被讲得最多的是消除左递归因为它顺带把「表达式左结合」这件事从算法层面变成了文法层面。3.2 LR(1) 项目集族与 LALR 合并的代价LR 分析器的能力来自「已经看过的东西」——它用状态栈记录到目前为止匹配过的句型用分析表决定移进还是归约。LR(1) 项目形如[A - α·β, a]点表示当前解析位置a是向前看符号它比 SLR 强的地方在于归约只看该状态真正允许的 follow 符号而不是全局 FOLLOW 集。代价是状态数。带向前看符号的项目集族规模通常比 LR(0) 大好几倍LALR(1) 的应对办法是把「同心项目集」合并——所有核心项目相同、只有向前看符号不同的状态合并成一个。合并之后状态数降到和 LR(0) 一致但会引入一类新冲突归约-归约冲突。原本在两个状态里各自合法的归约合并后挤在同一个状态里向前看符号重叠了。这就是「LALR 比 LR(1) 弱一点」的具体含义。对课设规模的文法表达式、语句、声明来说LALR 几乎总能压住所以大多数教学实现走到 LALR 就够了。真正的难点不在构造算法而在冲突报告怎么读。3.3 冲突消解优先级写进文法还是写进分析表表达式文法是冲突高发区。E - E E | E * E | id这条文法用任何分析法都会冲突因为a b * c有两个合法的语法树。消解方式有两种选哪种直接决定了后面怎么加新运算符。第一种是在文法层面分层。把表达式拆成E - T (|-) T、T - F (*|/) F、F - id | (E)这样的层级优先级由层级的深浅表达结合性由左递归或循环表达。第二种是把优先级和结合性作为元信息挂在运算符表上让分析器在冲突时查表决定。递归下降天然适合第一种因为每层优先级就是一个函数# 每一层函数对应一级优先级优先级低的函数在调用链上层 # 文法已消除左递归E - T {(|-) T} def parse_expr(self): node self.parse_term() while self.peek().kind OP and self.peek().text in (, -): op self.advance().text right self.parse_term() # 左结合新节点包住已建好的左子树再挂右子树 node Node(BinOp, opop, leftnode, rightright) return node def parse_term(self): node self.parse_factor() while self.peek().kind OP and self.peek().text in (*, /): op self.advance().text node Node(BinOp, opop, leftnode, rightself.parse_factor()) return nodeparse_expr调用parse_termparse_term再调用parse_factor调用链的深度就是优先级的高低不需要额外的优先级表。while循环实现左结合a - b - c第一次循环建出(a-b)第二次循环把它当成新的左子树得到((a-b)-c)。如果要右结合比如赋值运算符把循环改成递归让右子树先建完再回来挂左子树。表驱动 LR 则倾向第二种做法文法保持自然形态冲突用%left、%right、%nonassoc这类声明消解。好处是文法可读性高加运算符只加一行声明坏处是分析器的行为被藏进了生成器出错时只能看冲突报告。注意优先级表里同级运算符必须声明为左结合或右结合不能只给优先级。a - b - c的两种结合方式在语法上都能建树只有结合性声明能选出其中一个。4. 语义分析到中间代码符号表为什么必须和作用域一起设计语法树只是结构它是没有「意思」的。a b里的a到底是一个整数变量、一个数组、还是一个未声明的名字语法树自己不知道。语义分析要做的事就是给每个名字找到绑定检查类型是否自洽然后把树翻译成一种不再依赖语法细节的形式——四元式。这三件事必须一起设计。符号表的生命周期决定了作用域规则作用域规则决定了类型检查在哪个时刻能看到哪些名字而四元式的生成顺序又必须和作用域的进出严格对齐否则临时变量的作用域会串味。4.1 作用域链为什么不是一张大哈希表加撤销栈最省事的符号表实现是一张全局哈希表进入语句块时插入离开时删除。这个方案在简单语言里能跑但一遇到「同一名字在内层遮蔽外层」就出问题你删掉的是内层的那个还是外层的那个如果内层没定义过这个名字你在清理时会把外层的错误删掉。作用域链把这个问题从「删不删」变成「在哪一层找」class Scope: def __init__(self, parentNone): self.table {} self.parent parent def define(self, name, sym): # 同一作用域内重复定义才是错误跨作用域遮蔽是合法的 if name in self.table: raise SemanticError(f符号 {name} 重复定义于本作用域) self.table[name] sym def lookup(self, name): s self while s is not None: if name in s.table: return s.table[name] s s.parent return None # 一路走到最外层都没找到才算未声明parent指针构成链define只写当前层lookup由内向外逐层找。退出作用域时不需要任何删除动作把当前指针指回parent就行——内层那个Scope对象被丢弃外层的表从未被碰过这正是「遮蔽」应有的语义。这套结构还有一个隐性好处离开作用域时天然支持一次性回收。函数有几十个局部变量时不需要逐个撤销整个Scope对象直接释放。作用域进出的时机必须和语法制导翻译的时机严格对应。进入一个{就push一层离开}就pop函数参数属于函数体那一层不属于外层for循环里声明的循环变量属于循环体那一层循环结束就该消失。这些规则在语法树上看起来都很清楚但在自底向上的分析器里实际触发点是归约动作稍不留神就会晚一步或者早一步。4.2 类型检查的求值顺序属性依赖不能靠猜语法制导翻译把每个节点看成带属性的对象综合属性从子节点往上传继承属性从父节点往下传。类型检查是典型的综合属性一个BinOp节点的类型由左右子树的类型和运算符决定子树不先算完父节点无从下手。问题出在继承属性上。像int a[10]这种声明数组维度的合法范围、变量实际类型既要看父节点给的上下文这是不是一个类型声明又要看子节点维度和初值。这类属性没法靠一次遍历算完要么多遍扫描要么在构造节点时把上下文显式传下去。课设里比较稳的做法是给每个节点一个check(ctx)方法ctx装着当前作用域和当前函数返回类型父节点调用子节点的check时把ctx传下去子节点的返回值是它自己的类型。这样综合属性和继承属性共用一条调用链顺序由调用关系自然保证不需要额外做拓扑排序。类型规则本身不需要写得多完备但必须写清楚。隐式类型转换整型提升、数值类型混算是最容易出隐蔽 bug 的地方int float到底转成什么赋值时窄类型往宽类型转是否合法这些规则的每一条都应该有一个对应的测试用例否则等到代码生成阶段再发现错误会以「指令选择失败」的面目出现完全看不出根因。4.3 四元式为什么中间表示要「最小」四元式的形式是(op, arg1, arg2, result)每条只做一件事一次运算、一次赋值、一次跳转。a b c * 2会被拆成三条# 四元式生成每条指令只有一个运算符临时变量按序编号 # a b c * 2 # (*, c, 2, t1) # (, b, t1, t2) # (, t2, , a) def emit(self, op, arg1, arg2, result): self.quads.append((op, arg1, arg2, result)) def new_temp(self): self.temp_id 1 return ft{self.temp_id}拆成三条看起来啰嗦价值在于每一条都是「无歧义、无嵌套」的。语法树是有层次的四元式是线性的树上的每个父子关系都被临时变量显式化了。后面做控制流分析、活跃变量分析、常量折叠处理的都是这条线性序列不需要在树上递归。临时变量的编号策略也值得想一下。全局递增最简单但会生成大量永不复用的名字按作用域重置编号能压缩数量代价是要保证不同作用域的临时变量不会在同一段代码里互相覆盖。课设规模下全局递增完全够用只要在生成目标代码时把临时变量正确映射到寄存器或栈槽。从四元式到目标代码最朴素的映射是「一个四元式一段汇编」(, a, b, t1)翻成LOAD r1, a; ADD r1, b; STORE t1, r1。这个版本能跑但寄存器压力大改进方向是表达式树求值——按 Sethi-Ullman 编号决定先算哪棵子树用最少的寄存器完成整棵树的求值。这一步是从「能跑」到「像编译器」的分水岭。5. 排查清单课设里最容易翻车的五个地方调试编译器有个特点错误现象出现的位置往往离真正的原因隔了好几层。一个「代码生成结果不对」的问题根因可能是词法阶段少记了一个位置导致语法树的节点全错位。下面五条是按实际踩坑频率排的每条都按现象、原因、解决写清楚。5.1 前端词法与语法阶段的三个坑坑一双字符运算符被切成两个单字符。现象是a b被解析成a b语法分析器报「意外的」。原因是扫描器在读到之后没有继续往前看直接按单字符接受返回了。解决的关键是落实最长匹配主循环必须持续读到死状态并且用accept_end而不是当前游标做切片只要最后一处接受点是那个状态返回的就是完整的两字符 token。这类 bug 的隐蔽之处在于单运算符测试全部通过只有复合运算符的用例才会暴露。坑二关键字被当成标识符。现象是if (a) ...里if被识别成变量名语义分析报「未声明的标识符 if」。原因是扫描器把关键字和标识符混在同一条正则里或者关键字表在标识符识别之后才查。解决方式是在标识符接受之后立刻查关键字表并改写 token 类型同时保证关键字表是大小写敏感的完全匹配不做前缀匹配——否则iff会被误判成if。坑三错误信息定位到错误的行。现象是报错说第 42 行有问题实际错误在第 40 行。原因是行号统计放在语法分析阶段按语法树节点的位置反推而空行和注释里的换行没被计入。解决办法是把换行计数放在扫描器里读到一个\n就自增每个 token 出发前把当前的(line, col)存进 token语法树节点直接继承子节点的位置。这条改动成本很低收益是之后所有报错都可信。5.2 后端语义与代码生成阶段的两个坑坑四内层作用域的变量退出后仍然可见。现象是{ int x; } x 1;这种代码通过了语义检查。原因是作用域退出时只把符号表指针指回父层但某个缓存或者闭包里还留着指向内层Scope的引用查找时绕过了链式回溯。解决是把查找路径统一收敛到lookup一个入口禁止任何代码直接访问scope.table退出作用域时只改指针不保留任何对内层表的引用。坑五四元式顺序和执行顺序不一致。现象是短路求值a b在a为假时仍然计算了b导致除零或者空指针。原因是语法制导翻译在遍历子树时先递归生成了右子树的四元式再插入跳转指令顺序彻底颠倒。解决是把控制流的生成拆成两段先申请标号、生成左子树、发射条件跳转再生成右子树、回填标号。回填backpatch机制就是为这个场景准备的——跳转指令先写一个占位标号等目标位置确定后再统一改写。注意回填列表一定要在函数或语句结束时检查是否全部回填完毕。漏回填的跳转指令在最终输出里会指向一个不存在的标号这种错误在汇编阶段才报排查成本极高。6. 取舍把编译器写成「能改的」比写成「能跑的」难课设结束时回头看真正拉开差距的不是谁实现了更多文法特性而是谁的代码在最后一刻还能改。递归下降和 LR 表驱动在这件事上的表现完全不同维度手写递归下降表驱动 LR实现成本低每个非终结符一个函数高需要项目集族构造与表压缩文法改动成本改文法就要改函数改文法只需重新生成表错误恢复容易可直接跳过 token 继续较难需要在状态栈上做弹出可读性高调用链就是文法结构低行为藏在表里冲突暴露时机写代码时构造表时我的取舍是前端用递归下降把优先级和结合性写成函数层级让文法结构在代码里一眼可见语义分析和中间代码生成做成独立的两遍中间用四元式解耦。这样即使语法分析器重写后端一行都不用动。验证方法上最有效的一条是给每个阶段做「单阶段可测」。扫描器能单独喂字符串输出 token 流语法分析器能单独喂 token 流输出语法树用 S-表达式打印语义分析能单独喂树输出符号表和四元式。任何一层出问题都能在它的边界上定位而不是从头跑一遍再靠猜。这套习惯让我在后来的项目里少走了很多弯路。那次课设我最后悔的一件事是为了赶进度跳过了错误恢复把所有非法输入都直接raise掉。验收时老师输入了一个少写分号的程序编译器吐了一个空白的异常栈我在旁边站了半分钟不知道说什么。从那以后我每次写解析器都强制先实现一条「至少能报告行列号和期望 token 集合」的错误路径再回去补功能。这份课设资料里把错误处理和各阶段边界都写得很细值得拿去对着源码走一遍。希望帮到你。本文还有配套的精品资源点击获取

编译原理课设：从词法DFA到四元式的全链路实现与排错

相关推荐

Calico v3.20.6 离线部署实战：镜像导入、yaml 调参与避坑指南

CTF比赛入门指南：从零基础到实战精进

JavaWeb运动健康管理系统源码：Servlet+JSP+JDBC全栈实战

更多资讯

Struts 2学习笔记：OGNL

Maven 依赖导入失败

Nginx安装方法和反向代理配置

Windows Mysql 版本更新

【前端】移动端布局基础

一键开关机电源管理芯片选型四大核心维度

今日更新

GUI自动化测试中的ScreenLayout：从硬编码坐标到声明式画面地图

LLC谐振变换器12V25A 300W开关电源设计与调试全攻略

ESP32多应用Flash数据隔离：分区表与NVS namespace实战

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？