★ FEATURED ARTICLE 简介这是一份关于简单文法编译器前端设计与实现的课程设计报告适合正在学习编译原理、需要完成课程设计或理解词法/语法分析流程的本科生。报告从扫描器生成Token讲起完整演示递归下降子程序法如何同时完成语法分析与语义分析并生成四元式中间代码其中对词法分析模块、语法语义分析模块、目标代码生成模块的功能、数据结构与算法均有详细说明内容覆盖常量、数组、if-else、while等文法扩展以及递归子程序栈设计能够帮助读者把从源码到目标代码的完整编译过程串起来。资源为单体docx文档约381KB正文包含摘要、设计任务、算法与数据结构、程序流程图、实验结果、结论、参考文献与收获体会还附有小组分工说明结构清晰便于直接参考。目前已有693人学习适合零基础到进阶的编译原理实践者查阅。1. 这一份能跑通全流程的编译器前端词法、语法语义、四元式都在里面2014 年 12 月的一份课程设计报告里面完成了一个相当完整的编译器前端词法分析切 Token、递归下降做语法语义分析、边分析边生成四元式最后还给后端留好了目标代码生成的接口。这份资源最值钱的地方不是它把编译原理的某个知识点做深了而是把整个前端从头到尾串了一遍——文法怎么定义、状态转换图怎么落地、递归子程序怎么跟文法一一对应、四元式在哪个语义动作产生每一步都有据可查。适合正在做编译原理课程设计的学生也适合想找一份可复现模板、快速搞懂「词法 语法 语义」三者如何协作的从业者。2. 词法分析文件驱动的状态转换关键字表和界符表分离设计2.1 先读懂那张状态转换图d、l、b、E/e 到底切出什么词法分析模块的输入是源程序字符流输出是 Token 序列。报告里给了一张核心状态转换图图的语义用符号缩写表达d 表示数字l 表示字母b 表示界符E/e 表示字母 E 或 e科学计数法的指数标志。整个图按终结状态分成五类单词数字常量、标识符或关键字、界符、字符常量、字符串常量。这张图里最值得研究的是数字常量的路径。它允许可选的符号/-开头然后走数字、小数点、数字再到 E/e 指数部分指数部分又可以带符号最后仍以数字结尾。这里面有个隐藏细节E/e 之后如果没有数字整个输入就不能归约为合法的数字常量状态机应该进入非法状态或回退重切。我在实现时习惯在状态转移表里给 E/e 单独列一列因为它在数字常量子图里是一个分叉点——接了数字继续走接了字母就得把 E/e 回退回去重新当标识符切。2.2 为什么把关键字表、界符表、状态转换关系放到文件里这个设计决策在今天看是常规操作但在课程设计里算很有工程意识的新增关键字不用改代码直接往文件里加一行。报告里的关键字表一共 14 个我列出来方便核对关键字编码关键字编码program0real8var1bool9integer2char10begin3arr11end4con12if5of13else6while7界符表一共 21 个编码从 0 到 20、*、-、/、:、,、[、]、{、}、;、、、(、)、:、.、、、、。注意这里的 没有独立编码赋值用 : 表达等于比较在文法里根本没出现这是这个简单语言的一个边界——想扩展 运算符就得先往界符表文件里追加新编码。两处都是纯粹的「读文件 → 建表 → 查表」逻辑。词法分析器每切出一个单词先去关键字表里查是不是保留字查到就直接输出关键字 Token查不到再按标识符处理。界符表同理原则是「最长匹配优先」比如读到 时先看下一个字符是不是 或 是就拼成 或 不是再回退。2.3 扫描器主循环状态转移表的查表实现下面这段我用伪代码描述扫描器的主循环实际工程里换成 C 或 Java 的数组合哈希表实现即可。def scan_token(): state 0 buf while True: ch get_char() # 从源文件读一个字符 next_state trans_table[state][ch] # 查状态转换表 if next_state DEAD_STATE: # 死状态当前单词结束 push_back(ch) # 把多读的字符回退给输入流 break state next_state buf ch if state in FINAL_STATES: # 记录最近一次终态 last_final state last_buf buf # 用 last_buf 切出单词再用关键字表/界符表分类 return classify_token(last_buf)这里有两个关键参数trans_table是二维数组行是状态编号列是输入字符类别数字、字母、界符、小数点、引号等值是下一状态编号DEAD_STATE表示当前路径无法继续匹配任何合法单词此时必须把最后一个字符回退到输入流否则下一个单词的第一个字符就丢了。这个回退操作是最容易出错的地方我见过不少实现直接用下标回退而不是真正放回缓冲区导致源程序末尾多切出空 Token。词法分析器的输出是一个 Token 序列单词编码、单词文本、所在行号这个序列喂给下一阶段的递归下降分析器。3. 递归下降语法语义分析边配语法边出四元式的实现套路3.1 文法产生式和递归子程序的一一对应关系语法分析选型上报告用递归下降子程序法而不是 LL(1) 表驱动理由很实际手写递归下降直观、便于在产生式右部任意位置插入语义动作而且课程设计规模下不需要处理复杂的冲突消除。文法在报告里写得很完整核心骨架如下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 } ; | ε 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 → EXPRESSION TERM | TERM TERM → TERM * FACTOR | FACTOR FACTOR → id | cons | ( EXPRESSION )递归下降的规矩是「一个非终结符对应一个子程序」所以这里大概要写十几个函数program()、sub_program()、variable()、declare_sequence()、type()、com_sentence()、sentence_sequence()、assignment()、expression()、term()、factor()。每个函数几乎照抄产生式右部遇到终结符就调用match()比对当前 Token遇到非终结符就调用对应的子函数。这里有个很多人忽略的选型理由文法里 EXPRESSION 和 TERM 用了左递归形式这在递归下降里会直接死循环——expression()调用自己而不消耗任何 Token。报告里的做法是把左递归写成循环等价形式我一般会在代码里用while去迭代处理和*每个运算符走一次right term()这样既避免了无限递归又让四元式的生成顺序和运算顺序保持一致。3.2 四元式生成语义动作的插入位置决定中间代码质量语法分析和语义分析同时进行是这份报告实现上的一个核心技巧。每识别出一个产生式就在代码里插入语义动作产出四元式(op, arg1, arg2, result)。用表达式a b * c举例生成的中间代码长这样序号四元式含义1(*, b, c, t1)先算 b * c结果存 t12(, a, t1, t2)再算 a t1结果存 t23(, t2, _, a)把 t2 赋值给 a实现里我习惯用变量和中间结果表的计数器每生成一个新临时变量就把下标加一def emit(op, arg1, arg2, result): quads.append((op, arg1, arg2, result)) def new_temp(): global temp_count temp_count 1 return ft{temp_count} def expression(): left term() while lookahead Token.PLUS: advance() right term() result new_temp() emit(, left, right, result) left result return left注意new_temp()里的temp_count是全局状态它决定了临时变量不会重名。这个计数器如果作用域搞错了生成的t1可能被后面的子表达式覆盖四元式看起来逻辑对但执行起来结果错。赋值语句id : EXPRESSION的语义动作最简单先递归分析 EXPRESSION 得到它的存放位置然后生成(, 结果, _, id)一份四元式。3.3 递归子程序栈每一步都能看到调用现场报告里专门设计了一个递归子程序栈这是很多教材代码里没有的调试功能。进入每个子程序时压入一条记录记录当前的非终结符、当前正在分析的 Token、当前已生成的四元式序号子程序返回时弹出一条记录。这样在每一步语法语义分析之后栈里保存的就是完整的调用链——比如分析a : b c时栈顶到栈底依次是factor → term → expression → assignment → sentence_sequence → …。我实际调试时发现这个栈最大的价值不是看「现在在哪个函数」而是看「当前 Token 是在哪一层被消费的」。递归下降里经常出现某个子程序提前预读了一个 Token 导致回溯困难有调用栈就能准确判断是哪一层多读了。实现上用一个全局栈数组加栈顶指针就能搞定课程设计里不必写成通用数据结构。4. 文法扩展常量、数组、if-else、while 的插入方式4.1 常量声明和数组声明扩展声明部分不影响语句分析基础文法只支持var声明变量扩展后加入con和arr。常量声明的文法产生式是VARIABLE → con ID_SEQUENCE : cons ; VARIABLEcons在报告里代表常数这里的意思是说常量声明里类型字段直接写常量值。处理时的语义动作比变量声明多一步把常量名和值登记到常量表里后续 FACTOR 分析到id时先查常量表查到就按常量处理而不是按变量处理。这个小改动直接影响中间代码——x : 2 * 3会在语法分析阶段就把2 * 3算出来生成的三地址码里直接是t1 : 6省掉一次运行时乘法。我一般建议在常量表里顺便记录常量的数据类型否则后面目标代码生成时无法确定该用整数指令还是浮点指令。数组声明的产生式是arr id cons { of cons }这个写法看起来有点绕实际上是想表达arr a 10 of 5这样的形式。数组扩展的语义动作核心是把数组的起始地址、元素个数、元素类型记录到符号表里数组元素的访问通过下标计算生成辅助四元式def array_access(arr_name, index_expr): base sym_table[arr_name].base_addr idx expression() addr new_temp() offset new_temp() emit(*, idx, elem_size, offset) emit(, base, offset, addr) return addr # 数组元素的地址4.2 if-else 与 while控制流的四元式跳转回填控制流扩展是这份设计里逻辑最密集的地方。if-else 的文法在报告里没有完整展开但按分支语句的常规扩展方式可以写成IF_STMT → if EXPRESSION then SENTENCE else SENTENCE。递归下降子程序在处理 if 时先生成条件判断的四元式(j, a, b, label)但这个 label 当时还不知道必须留空回头再填。这就是编译原理书里的「回填」概念。实现上我习惯用一个backpatch_list数组每生成一个待回填的四元式就把它的下标记下来。等分析完 then 分支、拿到 else 分支的入口四元式编号后再回头把之前留空的 label 填成实际值def if_statement(): cond expression() jump_false emit(jfalse, cond, None, None) # 先留空 sentence() # then 分支 else_start len(quads) jump_end emit(jump, None, None, None) quads[jump_false].result else_start # 回填 jfalse 的跳转目标 sentence() # else 分支 quads[jump_end].result len(quads) # 回填 jump 的跳转目标while 比 if 多一个「循环头回退」逻辑循环开始的位置要在进入判断之前记下来条件为真的跳转目标要填回循环头这样生成的中间代码才能在执行到时跳回去重复执行。4.3 扩展时最容易破坏原有递归链的地方往递归下降框架里塞新产生式最忌讳的是改了文法却忘了改lookahead的预读逻辑。比如在statement()里增加 if、while 分支就必须在函数开头根据当前 Token 决定走哪个分支如果预读的 Token 已经被之前的子程序消费分析就会串线。我踩过的坑是在 if 的条件分析完成后顺手把then关键字匹配掉了等分析完 then 分支回头比对else时发现else已经被下一层的sentence()当作新的语句开头预读了。解决办法是严格控制match()的调用时机每个终结符只匹配一次不要为了省代码提前消费。另一个容易翻车的地方是扩展文法后原有的递归下降函数签名要跟着改。比如 FACTER 原来只返回id或cons的存放位置加了数组后得返回「是普通变量还是数组元素」的结构体。不改签名硬塞的后果是数组下标计算生成的临时变量没人管理符号表里的记录和四元式里的引用对不上。5. 高频踩坑与排查五类翻车现场和解决路径5.1 科学计数法识别到 E/e 后跟了字母整个 Token 被切废现象源程序写3.14e2词法分析把e2切成了标识符数字常量变成3.14语法分析报错。原因状态转换图里 E/e 之后只允许数字但实现时没检查 E/e 的下一个字符直接把e也拼进了数字 Token。解决在扫描器里把 E/e 单独做一次预读判断下一个字符不是数字就立即回退。我处理时是把这个分叉点在转换表里显式建一行状态 6 遇数字进状态 7遇字母进死状态回退。5.2 关键字表文件漏了 program程序开头永远过不了现象语法分析报错「期望 program实际得到 id」但源程序第一行明明写着program test。原因关键字表是从文件读的文件里没有 program 这一行词法分析器把program按普通标识符切出来了。解决先确认关键字表文件内容是否齐全再确认词法分类函数查表逻辑是否正确。排查时我一共对照了 14 个关键字发现program的编码 0 被漏掉了补上后立刻通过。5.3 else 悬空递归下降里 else 被归进了错误的 if现象if a then if b then c : 1 else c : 2这段代码else 被匹配给了内层 if语义正好反了。原因递归下降过程里每一个if分支处理完后立即去找else导致内层 if 把 else 抢走了。解决在if_statement()里不要无条件匹配 else而是遇到 else 先回填当前未闭合的 if这儿最保险的做法是把「当前是否允许吸收 else」做成参数往下传只有最内层未闭合的 if 才有权消费 else。5.4 临时变量编号冲突四元式看着全对执行结果就是错现象两个不相干的表达式a : b c和d : e f生成的临时变量都叫t1目标代码执行时相互覆盖。原因new_temp()的计数器在表达式子程序里被重置了或者每个子程序各自维护了局部计数变量。解决把临时变量计数器提成全局唯一变量整个编译过程只在一个地方递增。我在验收时用一段包含十几个表达式的测试程序打印全部四元式逐个检查t的下标是否严格递增。5.5 单词结束后没有清空缓冲区最后一个 Token 被重复输出现象程序末尾连续输出了两遍 end 的 Token或者 Token 序列里多了一个空字符串。原因扫描器在普通字符循环结束后直接返回buf内容没有判断缓冲区是否为空文件末尾的特殊字符被当成一个单词切了出来。解决在scan_token()返回前加一个空缓冲区判断buf 为空直接返回结束标记同时把字符回退逻辑放在死状态分支的最前面避免多读的字符丢进下一个单词。6. 后端与调试技巧四元式到目标代码的查表映射和递归子程序栈观察法6.1 四元式到目标代码的查表映射后端生成目标代码是本设计里最实在的部分。四元式是平台无关的中间表示翻译成目标代码时查表映射即可。我习惯准备一张映射表按四元式操作符分别处理四元式目标代码简化指令序列(, a, b, t1)LOAD a; LOAD b; ADD; STORE t1(*, a, b, t1)LOAD a; LOAD b; MUL; STORE t1(, a, _, t1)LOAD a; STORE t1(j, _, _, L)JMP L(jfalse, cond, _, L)LOAD cond; JZ L翻译器的主循环是从四元式数组第一条开始往下逐条处理遇到操作符就去映射表里找对应的指令模板替换参数。注意四元式里的arg1、arg2、result可能是变量名、常量名或临时变量名翻译时必须分别查符号表拿地址常量要直接作为立即数嵌入指令。这里的坑是数组元素的地址是计算出来的不能直接查表翻译时要判断操作数是简单变量还是「地址四元式的结果」。6.2 递归子程序栈的观察法报告里设计了这个栈调试时最有效的用法是配合单步执行看三个东西当前 Token、栈顶子程序、最近生成的四元式。三个信息对齐后绝大多数语法错误都能一眼定位。我一般的观察顺序是先看当前 Token 是不是预期中的合法开头不是的话往回看栈里的调用链找到第一个不合理预读的位置问题通常出在那附近的match()调用上。这个习惯来源很直接——第一次看到四元式回填失败时我靠这个栈把问题定位到了if_statement()里第 27 行少写了一次advance()。从那以后我只要接触递归下降的编译器代码第一件事就是先看它的临时变量命名和跳转回填表这两处才是真正藏坑的地方。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
