编译器前端设计：表驱动词法与递归下降四元式生成

简介面向计算机专业学生与编译原理课程设计学习者这份文档围绕一个简单文法的编译器前端展开兼顾后端目标代码生成可用于课程设计选题参考、方案撰写与模块实现对照。压缩包仅含1个docx文件约381KB以课程设计报告形式组织涵盖任务要求、总体流程、数据结构、算法设计、程序实现与实验结果等章节。内容具体包括基于文件配置状态转换关系的词法分析、递归下降的语法与语义分析、四元式中间代码生成以及常量、数组、if-else和while等文法扩展并设计递归子程序栈观察调用过程。已有694人学习适合需要理解编译前端完整链路、整理报告结构或准备答辩的读者参考。1. 编译器设计的分水岭不在算法而在“表能不能动”多数人第一次接触编译器设计注意力会全部压在递归下降、四元式、LL(1) 这些名词上默认难的地方是算法。真正完整跑一遍前端之后才会发现容易出问题的地方常常是“可变性”关键字表、界符表、状态转换关系只要有一项固定在代码里后面每加一条扩展文法就要重新编译一遍扫描器改一层连带崩掉一层。一个简单文法要不要做成文件驱动直接决定了这个前端最后能长成小语言还是只够在验收现场跑通一次。下面要拆的这份设计里把状态机、关键字、界符全部落成外部文件用同一份扫描器吃不同的表这才是它最值得细看的地方。2. 词法分析状态转换表为什么要落成文件而不是写进 switch编译课第一段手写代码通常是while套switch的扫描器。识别数字时读到一个字符就case一次碰到字母就跳进标识符分支。这段代码写起来最顺手也最容易在文法扩展时出问题。问题不在于写得不对而在于它把“规则”和“执行”绑死了加一个关键字、改一个双字符运算符都要动代码、重编译、重新跑一遍所有测试用例。2.1 扫描器做的其实是字符流上的最长匹配把扫描过程讲透比贴一个状态图更有用。扫描器从源程序开头逐字前进每读一个字符就切换到一个新状态一个状态代表“已经读到的这段前缀属于什么类型”。比如从初始状态读到第一个数字时进入“已读到一个数字”的状态接着读到一个字母就转入“标识符或关键字”的状态读到E/e再转入“科学计数法指数”的状态。每进入一个可接受状态就记下当前位置这样便能完成最长匹配即最终吐出的词素是能接受的最长前缀。数字、标识符、字符常量、字符串常量、界符各自会走一段状态路径。设计稿里的状态图从0出发按d / l / b / E等字符类别给出分支本质上就是一个 DFA。很多初学者只记住了状态图的样子没有记住它为什么要拆成“字符类别 → 下一状态”这种表示。一旦理解这一步表驱动就是顺理成章的。2.2 三张表各管一件事别混在一起设计稿把配置拆成三份文件不是故弄玄虚而是把三件本来互相独立的事分开状态转换表怎么切出词素关键字表切出来的标识符串是不是保留字界符表单字符和双字符运算符、分隔符各自的词法编码关键字是标识符的子集所以扫描器先统一按标识符规则切出来再去关键字表里查一次命中就换成关键字编码否则按普通标识符处理。这条规则在实现里非常轻但在可扩展性上很关键加一个关键字只需要改文件不用动状态机也不用动扫描循环。文件格式可以直接取设计稿里最朴素的“键 空格 值”一行一条# keywords.txt —— 关键字表左边是单词右边是编码 program 0 var 1 integer 2 begin 3 end 4 if 5 else 6 while 7 real 8 bool 9 char 10 arr 11 con 12 of 13# delims.txt —— 界符表双字符运算符也算一条 0 * 1 - 2 / 3 : 4 , 5 [ 6 ] 7 { 8 } 9 ; 10 : 15 . 16 17 18 19 20# dfa.txt —— 每行给出 当前状态 字符类别 下一状态 0 digit 1 0 letter 8 1 digit 1 1 dot 2 2 digit 3 3 eE 4 4 sign 5 5 digit 6 ... 8 letter 8 8 digit 8三张文件各管一段出问题的时候可以直接diff两份配置而不是在几百行switch里靠肉眼找分支差异。这种可解释性对于一个需要边写边改文法的课程设计来说价值远大于性能那一点点损失。2.3 表驱动的扫描循环把三张表装进内存之后扫描器只剩一个循环。下面这段是压缩过的核心逻辑伪代码级别用来讲清“表怎么用”不追求工程完备# 伪代码读三张表装配成一个表驱动扫描器 def load_tables(prefix): keywords read_kv_file(f{prefix}/keywords.txt) # dict: 单词 - 编码 delims read_kv_file(f{prefix}/delims.txt) # dict: 界符 - 编码 trans {} with open(f{prefix}/dfa.txt, encodingutf-8) as f: for line in f: line line.strip() if not line or line.startswith(#): # 允许注释方便维护 continue cur, cls, nxt line.split() trans[(int(cur), cls)] int(nxt) # (状态, 字符类别) - 新状态 return keywords, delims, trans def scan(src, tables): keywords, delims, trans tables tokens, i, n [], 0, len(src) while i n: if src[i].isspace(): i 1 continue state, start, last_accept 0, i, None while i n: cls char_class(src[i]) # digit / letter / delim / other key (state, cls) if key not in trans: break # 当前状态吃不进这个字符 state trans[key] i 1 if state in ACCEPT_STATES: # 记录最后一次“可以接受”的位置 last_accept (state, i) if last_accept is None: raise SyntaxError(f非法字符 {src[start]!r} 位置 {start}) state, i last_accept # 关键一步把指针回退到最长可接受点 lexeme src[start:i] tokens.append(classify(lexeme, state, keywords, delims)) return tokens这段代码有三处需要留意。第一处是char_class它把每个字符映射成有限的几个字符类别DFA 表用类别而不是具体字符作为键能把表规模压缩一个数量级否则 26 个字母加 10 个数字会让转换表膨胀。第二处是last_accept扫描推进和接受判断是两件事指针会一直向前走但只有落在可接受状态的那一刻才算是“一个合法词素的终点”扫描退出时让指针回退到那一刻才是最长匹配。第三处是classify它把切出来的词素再送去关键字表和界符表查一次做词法类别的最终归类。ACCEPT_STATES是哪些状态设计稿里没有明写编号但按状态图理解就是“标识符结束”“数字常量结束”“字符常量结束”“字符串常量结束”“界符结束”这几类。把它做成一个集合而不是写死在条件判断里改文法时一样只改配置。2.4 把表展开之后换来了什么表驱动扫描器最直接的收益是可配置、可解释。加一个关键字时只改keywords.txt编译器的二进制文件一个字都不用动调试时打印当前 DFA 状态、当前指针和last_accept一眼就能看出为什么某个词素被切成了两段。代价也很明确每个字符多一次字典查找扫描速度必然慢于手写switch。但在一个简单文法的课设规模里源程序普遍只有几百行这点开销可以被完全忽略换来的是“改规则不重编译”的可解释性。这也是理解现代词法分析器生成器的一条捷径它们做的事情本质相同把规则写进文件再根据规则生成状态表或状态代码。区别在于本设计是“读表执行”生成器则是“生成执行代码”。前者直观、适合教学和调试后者快、适合产出。选择哪一边取决于规则是否经常改动以及规模是否够大。提示表驱动扫描器的性能瓶颈通常在字符类别映射如果字符集是 ASCII可以预先把 128 个字符的类别查表展开成数组避免每字符一次dict查找。3. 递归下降子程序语法和语义凭什么能在同一遍下降里跑完语法分析这一段最容易记成“按文法写几个函数就完了”。真写起来才会注意到一个更本质的问题语法分析本质上是在源程序的 token 序列上做一次递归对比每对比成功一次其实就掌握了一段输入的结构而这段结构要变成四元式最省事的时机恰恰就是刚刚对比成功的那一刻。语法分析和语义分析能一起跑是因为递归下降的调用栈和文法的产生式之间有一种天然的对应关系。3.1 一个非终结符对应一个函数这是递归下降的物理形态把文法写成递归下降能直接实现的形式第一件事往往不是写代码而是改写产生式。算术表达式最爱的写法是EXPRESSION → EXPRESSION TERM教科书里看着漂亮直接翻译成函数却会无限递归函数第一件事就是调用自己一个 token 都没吃掉。所以实际实现里要把左递归等价地改写成用循环表达的右递归形状PROGRAM → program id SUB_PROGRAM . SUB_PROGRAM → VARIABLE COM_SENTENCE VARIABLE → var ID_SEQUENCE : TYPE ; VARIABLE | con ID_SEQUENCE : cons ; VARIABLE | arr id cons { of cons } ; VARIABLE | ε ID_SEQUENCE → id { , id } TYPE → integer | real | char | bool COM_SENTENCE → begin SEN_SEQUENCE end SEN_SEQUENCE → EVA_SENTENCE { ; EVA_SENTENCE } EVA_SENTENCE → id : EXPRESSION EXPRESSION → TERM { TERM } TERM → FACTOR { * FACTOR } FACTOR → id | cons | ( EXPRESSION )改写完之后函数体和产生式右部就是一一对应的形状def parse_statement_seq(): parse_assignment() # EVA_SENTENCE while cur_token_is(;): # 对应 { ; EVA_SENTENCE } match(;) parse_assignment()match负责“吃掉一个当前 token并把指针指向下一个”。函数里语句的先后顺序就是产生式右部符号的从左到右的顺序。不需要构造显式的预测分析表也不需要回溯因为每条产生式右部第一个终结符是否匹配在进入函数时就能根据当前 token 判断出来。3.2 语义动作为什么能挂在下降路径上递归下降是深度优先的。当一个函数返回时它对应的整段子树已经处理完了。这一点很重要因为它意味着四元式的生成可以就地完成parse_term()返回的时候它对应子表达式的四元式已经全部生成了返回值就是该子表达式的“结果名”。这个结果名可能是一个临时变量也可能直接就是变量名或常数本身。所以不需要像“先建 AST 再遍历 AST”那样分两遍走。单遍下降加就地生成是这份设计能把语法语义合在一起做的根本原因。AST 当然有 AST 的好处比如后续做变换、做优化更灵活但在一个以“产生中间代码”为目标的编译器设计里单遍生成省掉了 AST 那一层内存和一次遍历代价是语义动作和文法耦合得更紧改文法时动作也要跟着改。3.3 四元式从叶子往上长把表达式生成四元式这件事落到代码上核心是三个函数加一张全局四元式表。下面的代码按“从底向上”的顺序给出方便对照文法看生成顺序tmp_counter 0 quads [] # 每条四元式是 (op, arg1, arg2, result) def new_temp(): global tmp_counter tmp_counter 1 return fT{tmp_counter} # 全局单调递增避免跨层重名 def gen(op, a1, a2, result): quads.append((op, a1, a2, result)) # 函数调用顺序就是四元式的生成顺序 return result def parse_expression(): left parse_term() # 先递归到最左叶子 while cur_token_is(): match() right parse_term() # 右子树的四元式在此时已经全部生成 left gen(, left, right, new_temp()) return left def parse_term(): left parse_factor() while cur_token_is(*): match(*) right parse_factor() left gen(*, left, right, new_temp()) return left def parse_factor(): if cur_token_is_id(): name cur_token.value match_id() return name # 变量名直接作为操作数不占临时量 if cur_token_is_cons(): v cur_token.value match_cons() return str(v) # 常数直接内联到四元式里 match(() t parse_expression() match()) return t参数含义需要提前说明。op是运算符arg1和arg2是两个操作数result是存放结果的位置。源码里a b * c会先进入parse_expression它调用parse_term拿到leftparse_term内部又先拿到b发现后面是*于是产生一条乘法四元式结果存进T1parse_term返回后parse_expression发现后面是再调一次parse_term拿到c作为右操作数接着产生加法四元式。最终的四元式序列是(*, b, c, T1) (, a, T1, T2)乘法在加法之前出现不是巧合而是因为parse_term比parse_expression先返回。四元式的顺序天然就是表达式的求值顺序这也是单遍下降生成中间代码能成立的关键。3.4 单遍下降留下的其他副作用除了四元式下降过程还会顺带维护一张符号表。变量声明语句var x : integer ;在parse_variable里执行到match(;)之前应该已经完成“把x和它的类型登记到符号表”的动作。赋值语句x : ...在parse_assignment里处理:之后要先查一次符号表确认x声明过否则给出语义错误。临时变量用全局计数器tmp_counter而不是函数内局部变量是一个容易忽略的细节。如果按函数作用域重置计数器外层表达式和内层表达式可能生成同名的临时变量后一条四元式就会覆盖前一条的语义。全局单调递增虽然不够省空间但不会出错在课程设计这个规模上是最稳的做法。4. 文法扩展与递归子程序栈加语法时怎么不打乱主干扩展到常量、数组、if-else、while 这几类语法时最容易犯的错是“先写新分支再补语义动作”结果是新语法在语法树上对了四元式却漏生成或者顺序错位。更可靠的做法是每一步先确定产生式分支再确定对应的符号表条目或跳转四元式最后才把控件、界面接上。4.1 常量与数组符号表多一个字段声明部分的扩展主要落在VARIABLE上VARIABLE → var ID_SEQUENCE : TYPE ; VARIABLE | con ID_SEQUENCE : cons ; VARIABLE | arr id cons { of cons } ; VARIABLE | εcon分支处理常量声明arr分支处理一维数组声明。两者对符号表的影响不同def parse_variable(): if cur_token_is(var): match(var) names parse_id_sequence() match(:) ty parse_type() match(;) for name in names: symbol_table[name] {kind: var, type: ty} elif cur_token_is(con): match(con) names parse_id_sequence() match(:) value expect_cons() match(;) for name in names: symbol_table[name] {kind: const, type: integer, value: value} elif cur_token_is(arr): match(arr) name expect_id() length expect_cons() match(of) base expect_cons() match(;) symbol_table[name] {kind: array, len: length, base: base}参数上names是逗号分隔的标识符序列结果逐个登记value是常量值后续在parse_factor里可以直接替换成字面量省掉一次变量读取len和base分别是数组长度和元素基准值后续处理下标时用来算偏移。这里做的是声明登记和约束保存没有生成四元式因为声明本身在运行期不产生动作。数组下标在parse_factor里处理时要先查符号表确认它确实是数组再按下标 * 元素宽度 基址生成一组四元式。设计稿里没有展开实现细节按常见的实现思路是走“先算下标再算地址”的两步式因为一维数组不需要像多维数组那样做乘法展开两步就够了。4.2 if-else 与 while跳转四元式靠回填控制流扩展的关键是“先生成跳转再回填目标”。if-else要求条件为假时跳过 then 分支while要求每次循环结束跳回条件判断。两者的共同点是目标标签在生成跳转的那一刻往往还没算出来只能先占位、后回填。def next_quad_index(): return len(quads) # 下一条四元式的下标就是回填的目标 def backpatch(idx, target): op, a1, a2, _ quads[idx] quads[idx] (op, a1, a2, target) # 覆盖第四元填上跳转目标 def parse_if(): match(if) cond parse_expression() jf_idx len(quads) gen(jf, cond, None, None) # 条件为假跳到 else 或 if 之后 match(then) parse_statement() if cur_token_is(else): j_idx len(quads) gen(j, None, None, None) # then 分支结束跳过 else backpatch(jf_idx, next_quad_index()) match(else) parse_statement() backpatch(j_idx, next_quad_index()) else: backpatch(jf_idx, next_quad_index())jf是 conditional jump 的反面jump if false第四元是条件为假时跳转的目标四元式下标。backpatch做的事就是把当时留空的第四元补上。if-then-else会产生两条跳转一条在条件判断之后一条在 then 分支末尾if-then只产生一条。while更简单只在条件判断前打一个入口标签循环体末尾再加一条无条件跳回入口L1: (jf, cond, _, L2) ...循环体... (j, _, _, L1) L2:控制流四元式是中间代码里最需要保证顺序正确的部分四元式表的下标就相当于地址一旦顺序打乱跳转目标全部错位。4.3 递归子程序栈把“正在下降”做成一块可见面板设计稿里的递归子程序栈是为了把“某一时刻的调用路径”可视化。做法简单但很有用每进入一个parse_xxx函数就把函数名压栈退出时弹栈每次入栈出栈都刷新界面同时把当前 token 和刚生成的四元式一并显示。from contextlib import contextmanager call_stack [] contextmanager def descending(name): call_stack.append(name) ui.refresh(stacklist(call_stack), tokencur_token.text, last_quadquads[-1] if quads else None) try: yield finally: call_stack.pop() # 异常路径也保证弹栈 ui.refresh(stacklist(call_stack), tokencur_token.text, last_quadquads[-1] if quads else None)用上下文管理器包住而不是手动在函数开头push、结尾pop是为了让异常路径也走finally。这一点在调度栈面板的调试场景里特别重要语法报错的时候用户最想看到的就是出错那一刻栈的形状而那一刻恰恰是异常抛出的路径手动 pop 很容易漏。参数上stacklist(call_stack)传一份快照而不是引用避免面板拿到列表之后被后续的 push、pop 修改token是当前正在看的 tokenlast_quad是最近生成的一条四元式让观察面板能同时呈现“在哪一层下降”和“刚生成了什么中间代码”。4.4 栈的形状本身就是诊断信号这块面板不只是一个显示功能它的形状可以直接当作判断文法是否正确的信号。正常的下降过程栈会随表达式嵌套深度起落如果栈长时间停在EXPRESSION → TERM → FACTOR → …这样的循环里不动十有八九是文法里存在左递归或者括号没有配对如果栈早早地卡在PROGRAM不动说明扫描出来的 token 里缺少begin或声明部分提前结束。用这块面板核对四元式生成时机也很方便。当栈里出现EVA_SENTENCE而四元式表里还没看到赋值四元式说明语义动作挂在了函数返回之后而不是:被匹配之后反过来当栈里已经退出EXPRESSION而四元式表里多出三条乘法则可能是循环写成了“每次匹配一个 token 就建一条四元式”影响求值顺序。5. 前端实现排查四类只在真实输入下暴露的问题课堂讲原理的时候容易遗漏下面这些情况它们几乎都不在算法教材里出现却会在真拿源程序敲进去的那一刻冒出来。5.1 程序卡在 parse_expression 里不再推进左递归的典型死法现象输入1 2 ;词法扫描正常进入语法分析后界面不再刷新栈面板停在EXPRESSION不动CPU 占用上升但没有任何报错。原因原始文法写的是EXPRESSION → EXPRESSION TERM直接照抄成函数parse_expression的第一件事就是再调用parse_expression一个 token 都没吃掉就无限递归。解决把左递归等价改写成用循环表达的右递归形式即EXPRESSION → TERM { TERM }TERM → FACTOR { * FACTOR }。改写之后再按函数体里“先调parse_term再在while里循环匹配运算符”的顺序实现。判断依据很直接只要递归下降函数的第一个动作是调用自己就说明文法里有左递归必须先改写。5.2 标识符被切成两个 token最长匹配的回退点没有记对现象输入a1 : 10 ;扫描结果里a1被拆成a和1两个 token或者:被拆成:和两个界符后面的语法分析报“缺少标识符”。原因状态机在每个可接受状态都接受但输入指针i已经多走了一到两位扫描循环退出时没有让i回退到“最近一次接受”的位置导致接受点之前的字符被重复扫描或者漏掉。解决维护一个last_accept (state, i)每进入一个可接受状态就更新扫描循环因“吃不进下一个字符”退出时把state和i一起恢复到last_accept。注意回退的是指针位置不是只回退状态两者分开处理是常见错误。判据也很明确凡是字符串长度大于 1 的词素都应该检查它的结束位置是不是最后一次接受的位置。5.3 program 偶尔被判成非法 token关键字编码 0 撞了哨兵现象源程序以program开头时有时候能正常进PROGRAM分支有时候报“非法 token”换成另一个测试用例program又通过。重启程序之后有时又正常。原因关键字表里program的编码是 0而代码里“不是关键字”的哨兵默认值也是 0或者扫描器返回None之后被.get(0)的默认值兜底成 0。任何把这个 0 当成“无关键字”的地方都会把program误判成非法。解决两种改法都行要么关键字编码从 1 起把 0 显式保留给“不是关键字”要么把 token 的类别和编码拆成两个字段类别字段用KEYWORD / IDENT / CONST区分编码字段才表示关键字序号。前一种改文法小、后一种结构更清晰。出现“同一个词有时候合法、有时候非法”这种带随机性的现象时优先怀疑默认值撞车。5.4 语法错误之后栈越堆越高异常路径没有弹栈现象故意去掉一个分号再跑程序报语法错误但栈面板一直停在出错那一层不降下来。重新载入另一段源程序后栈上还残留着上一次的帧。原因压栈写在了parse_xxx开头弹栈只写在正常返回路径。异常抛出时pop根本没执行下一次扫描又叠上去。解决用try/finally或者上下文管理器把弹栈包住重新扫描之前显式清空call_stack不要指望残留的栈能自愈。判断依据是报错之后再给一段干净输入如果栈的层数比第一次运行时更深就说明有异常路径漏了清理。注意错误路径的清理逻辑和正常路径分开写是递归下降实现里最常见的隐患之一。状态面板越复杂这个隐患越容易被隐藏因为面板看起来总是“有东西在跑”。6. 设计取舍前端为什么愿赌递归下降后端为什么只认四元式把这份设计的前端和后端拆开看会看到一组对立的选择前端压上递归下降赌的是文法简单、能单遍生成后端只认四元式赌的是前后端解耦、优化和换目标架构不必回头动前端。这两条路都不是“通用最优”而是对项目规模做了判断本文还有配套的精品资源点击获取