简介面向编译原理课程设计与实验的综合资源包适合高校计算机专业学生与自学编译器基础知识的开发者。内容覆盖从词法分析到语法分析、中间代码生成直至汇编代码生成的完整环节包含LL(1)分析、LR(0)与SLR(1)分析等经典方法并提供了可直接运行的C/C源代码、相关文法定义与说明文本以及一份小型编译器课程设计报告便于对照实验要求进行调试与扩展。包体共14个文件以C/C源文件cpp、c、h为主配合txt文法说明和doc实验报告文档整体仅557KB结构紧凑便于快速下载查阅。目前已吸引2342人学习下载验证了其在同类课程设计中的参考价值。读者可通过这些代码理解简单语句如ii*i的分析过程与四元式生成思路并借助报告梳理从设计到实现的整体流程适合作为课程设计或期末实验的速查模板。 盯着“编译原理课程设计”这几个字发呆可能是不少同学拿到题目后的第一状态。更别说什么词法分析、语法分析、小型编译器、实验报告一串名词堆在一起好像每一项都认识但真要动手做完全不知道从哪下笔。我当年也走过这条路最后用Python手写了一个能完成四则运算赋值、变量存储、print输出的小型编译器顺带把实验报告整理得明明白白答辩一次通过。这篇文章就把我当时的设计思路、代码核心、踩过的坑、报告写法全部摊开来讲希望能帮你少走弯路。1. 整体设计与思路拆解1.1 先搞清楚课设的验收底线很多同学一上来就想着“我要写一个能编译C语言的编译器”这完全是在给自己挖坑。编译原理课程设计的重点并不是做一个工业级产品而是让你把理论课上的词法分析、语法分析、语义分析、代码生成这几个阶段亲手实现一遍。验收老师的核心关注点通常是三个你的分析器能不能正确处理规定范围内的输入、你知不知道每一步在做什么、实验报告能不能把你的思路讲清楚。所以我在动手前先圈定了一个“小而全”的范围词法方面支持关键字let、print、标识符、整数、四则运算符、赋值号、括号、分号语法方面支持表达式、赋值语句和打印语句代码生成方面不生成真正的机器码而是生成三地址码并解释执行。这样一来理论课上的重点全部覆盖到代码量控制在几百行以内调试起来也相对简单。做课设最忌讳的是贪大范围定得越小越容易把每个阶段做扎实。1.2 开发语言怎么选别在工具上内耗我见过很多人为了课设去自学Flex、Bison或者用Java严格按书上的写法搞一个巨复杂的框架结果浪费了大量时间在环境配置和工具使用上。当时我选择Python理由很简单写起来快、正则表达式用着顺手、调试时不用管编译和内存问题。最关键的是手写的递归下降分析器在Python里体现得非常直观每个非终结符对应一个函数逻辑和文法几乎一一对应实验报告里讲原理的时候可以“照着代码说”特别省事。如果你的课程要求必须用C/C那也不用慌核心算法和Python版本完全一致只是字符串处理和动态数组需要自己多写一点。我个人建议优先用Python除非老师明确强制指定语言。原因就一条课设的重点在“分析器怎么写”不在“语言特性怎么用”用最顺手的语言把原理吃透比用高难度语言写出一个跑不起来的代码好得多。1.3 三阶段流水线先看清整体框架主流的编译器结构分好几个阶段但课设里我们只要做清楚三件事词法分析、语法分析、代码生成。我当时把所有代码组织成一个管道源代码字符串经过词法分析器变成Token列表Token列表经过语法分析器变成抽象语法树ASTAST经过遍历生成三地址码最后再对三地址码做简单解释执行。这样做的好处是每一层只做一件事出了问题容易定位。比如报错时如果语法层出问题你只要看Token列表是否正常如果运行结果不对直接看AST是否长得合理。整个程序结构划分成三个模块实验报告里“概要设计”那一章也就有了现成的图输入-词法分析-语法分析-代码生成-输出。这里的“图”其实可以画成简单的矩形框图不用画到什么高深的工具Word画就够了。2. 词法分析把字符流变成Token流2.1 先定义Token的类型和属性词法分析的工作就是把源代码拆成一个个有意义的“单词”Token。第一个要做的就是确定语言里有哪些Token类型。我当时设计了一张表放在代码注释里后来也直接搬进实验报告类型名含义例子KEYWORD关键字let, printID标识符x, totalINT整数常量1, 42OP运算符 - * / LPAREN/RPAREN括号( )SEMI分号;EOF文件结束--Token本身用什么存储我用了Python的namedtuple每个Token包含三个字段类型字符串、实际值、行号。行号特别重要实验报告里必须写出“当语法错误时能定位到第几行”所以我在词法阶段就顺手把行号记下来。实际代码大概长这样from collections import namedtuple Token namedtuple(Token, [type, value, line])有的同学会在这一步就做符号表把标识符存起来我建议先不要急。符号表放语义分析阶段做更合理词法层只要保证每个ID都能被正确识别出来就行否则耦合在一起会非常难调试。2.2 手写扫描器不用正则也能写明白词法分析有两种常见做法一是手写状态机二是基于正则表达式匹配。在课设里很多老师希望看到“手写逐字符扫描”因为这样更能体现状态机思想。我当时也选择手写用一个index指针从头往后扫遇到字母开头就一直读直到非字母数字判断为关键字或标识符遇到数字就一直读到非数字判断为整数遇到符号就匹配对应的运算符。核心逻辑并不复杂但有一个坑必须注意等号“”和字符串结束判断、减号“-”与负号的区别。我当时限定所有数字都是非负整数负号被当作减法运算符这样表达式“-3”就必须写成“0 - 3”虽然别扭但文法简单课设足够。如果你后续想扩展负数就需要在语法分析阶段处理一元运算符复杂度会上升不少。扫描代码的骨架大约是这样的def tokenize(code): tokens [] i 0 n len(code) while i n: ch code[i] if ch.isspace(): i 1 continue if ch.isalpha(): start i while i n and (code[i].isalnum() or code[i] _): i 1 word code[start:i] if word in {let, print}: tokens.append(Token(KEYWORD, word, line)) else: tokens.append(Token(ID, word, line)) continue if ch.isdigit(): # 连续读数字 ... if ch in -*/: tokens.append(Token(OP, ch, line)) ...这样写完以后输入“let x 10 5;”输出的Token列表理想情况下是[let, ID(x), , INT(10), , INT(5), ;]。我当时为了演示效果在main里加了一个debug参数可以直接输出这个列表答辩时展示“看词法分析成功把源码拆成了Token流”老师一眼就明白你确实做了东西。2.3 错误恢复别让一个错字符卡死整个程序初版代码最常见的毛病是遇到一个无法识别的字符就立即抛异常程序直接退出。比如用户多打了一个“#”整个分析就中断了这样的用户体验非常糟糕而且实验报告里“错误处理”部分没东西可写。我当时的做法是遇到无法识别的字符记录一条“第几行发现非法字符”的报错信息然后直接跳过这个字符继续往后扫。这样词法分析阶段可以一次性列出所有非法字符而不是报一个就停。同理如果字符串里出现非法数字比如“12a”我暂且把它识别为一个ID还是报错这里要定义清楚我选择先识别“12”为INT再让“a”作为ID这样在语法层会因为两个相邻Token不符合文法而报“语法错误”。其实这样也能接受。当然如果你希望更严谨可以在数字后面紧随字母时报“数字标识符不合法”。这部分属于加分项实验报告里写清楚你的规则即可。词法错误恢复的验收点通常是“错误信息有没有行号”只要把这个细节做到老师就会觉得你考虑很周全。3. 语法分析递归下降构造AST3.1 文法设计先写产生式再写代码语法分析不能凭空写代码得先把文法规则写出来。当时我选的文法支持以分号分隔的语句序列每个语句要么是“let 变量 表达式;”要么是“print 表达式;”。因为递归下降分析法对应LL文法所以一开始我就避免直接写出左递归的表达式文法而是采用“优先级分层法”来天然消除左递归。我设置的文法如下E代表表达式程序 - 语句列表 语句列表 - 语句 | 语句列表 语句 语句 - 赋值语句 | 打印语句 | 空 赋值语句 - let ID 表达式 ; 打印语句 - print 表达式 ; 表达式 - 项 ( ( | - ) 项 )* 项 - 因子 ( ( * | / ) 因子 )* 因子 - INT | ID | ( 表达式 )这里“*”表示循环所以实际上已经不会产生左递归了。很多课程理论里会先写“E - E T | T”再教你消除左递归我在实验报告里就专门写了一段为了避免LL(1)分析中的无限递归我直接将文法改写成上面这种迭代形式。这一步在答辩时特别容易被问“为什么不用E-ET”你回答“因为递归下降的递归调用会无限循环所以采用循环右递归等价形式”基本就稳了。3.2 递归下降函数一个非终结符一个函数递归下降的名称听起来高级其实思路很简单为每个非终结符写一个解析函数函数里根据当前Token类型决定下一步怎么走。其中“表达式”和“项”这种带循环的函数是核心。以“项”的函数为例流程是先调用“因子”函数解析第一个因子然后循环判断当前Token是不是乘号或除号是就消费这个运算符再调用“因子”解析右操作数如此反复。这里有一个坑循环的退出条件必须判断“当前Token不是运算符”时break否则会一直死循环。我当时写过一个bug循环里忘了在匹配失败时break结果一旦遇到分号就无限卡在“项”的函数里。“因子”函数相对简单如果当前Token是INT就创建一个数字节点如果是ID就创建变量节点如果是左括号就递归调用“表达式”函数然后期望下一个Token是右括号。这里必须做完整检测“下一个Token如果不是右括号就报错”我当时偷懒没有做导致“((12)”这种输入居然被接受了后来补上以后测试才严谨。为了满足老师“报告里必须有语法树”的要求我写了一个AST节点树形打印函数调试时可以直接把解析结果打印成类似如下的形式Program Assign: x BinOp() Int(10) Int(5)这个功能写起来很简单就是递归打印AST但对理解程序和执行流程特别有用。3.3 AST节点怎么存用dict和class二选一AST既可以用类占位也可以用字典。我当时用了很朴素的Python类每个节点有一个type字段比如int、id、binop、assign、print然后根据类型附带不同属性比如binop节点有left、op、right字段assign节点有name和expr字段。用类的好处是访问属性方便缺点是定义几个类代码看起来更“正式”。如果你不想写太长也可以直接用tuple或list但那样代码可读性会变差报告里解释起来也费劲。我建议用最简形式的类别整一堆继承够用就行class Node: def __init__(self, type, **kwargs): self.type type self.__dict__.update(kwargs)这样一个Node就能装下所有节点类型唯一的缺点是属性名字写错了不会报错需要自己小心。站在课设角度这种“半动态”结构压力不大。3.4 语法分析调试实录最常见的三个错第一次跑通语法分析后我开始故意输入各种非法程序来测试。最常出现的三种错误情境基本覆盖了课设中大多数人的困难。第一个是没有及时消费Token。比如在“表达式”解析里刚吃完一个数字忘了调用advance()移动到下一个Token结果下次循环又处理同一个Token导致AST长得极其奇怪甚至死循环。排查方法很简单在关键函数入口打印当前Token看它有没有向后走。第二个是括号匹配没有做“缺右括号”判断。我当时只检查“如果有右括号就吃掉”完全不看“是不是真的有右括号”。后来输入“let x (12; ”发现它居然顺利通过了差点以为出现了灵异事件。检查之后才发现代码逻辑写反了应该先检查当前Token是否为右括号不是就报错。第三个是关键字和标识符区分时机不对。词法层已经把“let”识别成了KEYWORD但语法层的语句入口只认“ID”开头。正确的做法是在语句判断时收到KEYWORD类型然后根据值是let或print来决定进入哪个分支。如果你在语法层还去判断Token的value而不是类型就会漏判很多情况。记住语法分析阶段只看Token.type不要过分检查Token.valuevalue的具体意义留给上层。4. 小型编译器从AST到三地址码4.1 语义分析与符号表变量的记录和检查语法分析之后我们有了AST但还没有“变量存储”的概念。小型编译器至少要能处理“变量必须先定义再使用”所以我在这个阶段做了一次AST遍历完成两件事把所有let语句里的变量名记录进符号表在print表达式和赋值表达式里遇到ID时检查该变量是否存在不存在就报“未定义变量”。符号表我用了一个非常简单的Python字典变量名到值。因为课设不需要作用域所有变量都在一个全局空间。如果你希望更复杂一点可以给每个变量加类型、初始值、使用次数等但那些不是硬性要求只会增加报告篇幅。这里的核心技巧是语义检查最好在代码生成之前独立做一遍不要边生成边检查。否则代码生成到一半才发现变量未定义整个流程就会很乱。我当时把语义分析写成了对AST的check(env)函数它会返回一个新的符号表给后续代码生成用这样各个阶段边界非常清楚。4.2 三地址码生成比想想中还要简单很多同学看到“三地址码”就害怕其实它就是“每条指令最多三个地址”的中间代码比如t1 10 5。我需要的指令类型很少赋值、二元运算、打印、标号跳转这门课里用不到跳转所以直接省略。生成逻辑就是遍历AST遇到BinOp先生成左操作数的代码、再生成右操作数的代码然后生成一条运算指令。比如let x (10 5) * 2;最终生成的三地址码就是t1 10 5 t2 t1 * 2 x t2如果表达式里出现变量ID就直接用变量名作为操作数不需要临时变量。实现时用了一个new_temp()函数每调用一次返回t 序号同时序号加一。这个序号在实验报告里最好写清楚不然答辩时老师问“为什么t后面要加数字”你可能一时想不起来。三地址码生成完后我把它保存成一个列表每一条指令要么是一个tuple要么是字符串。我当时用字符串列表因为打印出来特别直观便于验收。实际代码大约是这样def gen(node): if node.type int: return node.value if node.type id: return node.name if node.type binop: left gen(node.left) right gen(node.right) t new_temp() code.append(f{t} {left} {node.op} {right}) return t if node.type assign: expr gen(node.expr) code.append(f{node.name} {expr}) ...4.3 解释执行三地址码最后一公里生成三地址码之后理论上已经完成“编译器”的主要任务了。但课程设计要求能运行结果所以我选择再写一个简单的解释器去执行三地址码输出print结果。这其实是绕过真实机器码的讨巧方法但对课设完全成立。解释器逻辑很简单顺序遍历指令列表遇到x y op z就把对应变量的值取出来做运算结果存回x遇到x y就是普通赋值遇到print x就打印变量x的值。这里有一个需要注意的点三地址码里t1 10 5的右操作数可能是数字也可能是变量名怎么判断可以维护一个value_of函数如果字符串全是数字就转成int否则在符号表里查变量值。这正好复用了之前语义分析阶段生成的符号表。至此从源代码到最终打印结果一个完整的小型编译器就闭环了。我当时在main函数里敲入let a 2; let b a * 3 1; print b;程序输出7。那一刻的成就感真的是别提了也是后来答辩时最有底气的部分。5. 实验报告把过程变成分数5.1 测试用例怎么设计才不是凑数实验报告里最容易被忽视的是“测试与分析”章节很多同学就放两三个正常用例老师一眼看穿没好好测。我当时把测试用例分成四类写了一个完整的测试表测试类别输入程序期望输出验证点正常表达式print 10 5 * 2;20优先级处理变量赋值let x 3; let y x 4; print y;7变量存储与读取括号嵌套print (1 2) * (3 4);21括号递归解析错误处理let x ;第1行报语法错误错误信息与定位错误处理print a;第1行报未定义变量符号表检查每个用例我都写了“输入、输出、结论”三行并且在测试代码里用断言验证期望输出。这样报告里可以写“全部测试用例自动通过”比手写截图更有说服力。另外建议至少放一个错误处理的用例这是最能体现你考虑了健壮性。5.2 实验报告结构模板照着填就行虽然不同学校格式要求略有差异但核心章节基本是固定的。我当时的报告包含六个大块需求分析、总体设计、详细设计、测试与分析、结论与心得、参考文献。每一块都有一些可以“从代码中直接迁移”的内容写起来并不难。需求分析里写明“我们要做什么、输入输出是什么、功能列表”。总体设计里画一个简单的模块关系图并说明三个模块的调用关系。详细设计是重头戏我会把Token定义表、文法产生式、关键数据结构、核心函数接口全部列出来再配上少量关键代码。测试与分析就用上一节的表格和截图。结论与心得里我写了自己踩的坑和学到的“先设计再写代码”的思维这部分不用太长真实最重要。注意不要大段抄代码堆在报告里老师更想看到的是“为什么这样设计”。比如我写递归下降时专门解释“为什么要用循环消除左递归”就是那句“防止递归调用无限循环”。这种一句话的原理比贴一百行代码更能拿分。5.3 演示材料准备细节决定印象如果有答辩环节演示时不要把源码从头到尾翻给老师看那既看不出重点又容易显得没准备。我当时的策略是先演示一个最简单的print 1 2;输出3再演示变量和括号最后故意输入一句话法错误展示错误定位。整个演示控制在3分钟以内。期间老师问得最多的往往是“你的这个运算符优先级是怎么实现的”。你要能回答因为语法分析时分为表达式和项两层乘除在项层加减在表达式层所以乘除会先被解析优先级自然就高了。这个解释甚至不需要看代码只要理解了分层就能答上来。6. 常见问题与避坑清单6.1 词法层和语法层各有什么最容易翻车的点词法层最常见的问题是不能区分“abc123”这类标识符如果规则开放了下划线就要让字母、数字、下划线都能出现在标识符中间。语法层最大的坑我刚才说过就是没有对“当前Token和期望Token不匹配”做出统一报错。如果你在每个函数里各写各的报错逻辑很容易出现“一处报错、程序崩溃”的尴尬。我建议做一个统一的错误告警函数error(msg, token)任何语法错误都调用它并携带当前Token的行号。这样既统一了格式也为报告里的错误处理亮点提供了依据。另外解析循环语句时一定要有步进机制绝不允许一个Token被连续消费两次或永远不被消费。6.2 代码实现里别犯的三个低级错误第一个是新建临时变量时忘记初始化计数器导致第一次生成的临时变量是t1但下一次还是t1最终代码互相覆盖。第二个是AST节点生成后忘记挂载子节点比如生成binop节点时只设置了left忘记设置right导致解释执行时访问right属性报错。第三个是表达式求值和代码生成混在一起中间栈乱了到了末尾甚至分不清谁是谁。解决方法就是坚持“一步一个中间表示”的原则不让任何阶段跨越。6.3 报告和答辩中怎么讲才能拿高分一个小经验是答辩前准备一个“三个为什么”。问自己为什么选择手写词法分析器为什么选择递归下降而不是LR为什么生成三地址码而不是直接输出汇编把这三个问题想透就能应付大多数老师的追问。还有一点报告里不要只写成功适当写一点“在设计过程中遇到的问题以及如何解决”。老师非常喜欢看到这种真实的数据。比如我写“第一版没有处理括号不匹配导致表达式错误被错误接受后来在因子解析函数中增加右括号检查后解决”比通篇吹自己完美更打动人。最后分享一个小技巧写编译原理课设时如果卡在了某个地方先把阶段边界捋一遍。词法出问题就去检查Token流语法出问题就去打印AST生成结果不对就去单步走一遍代码生成。只要阶段清晰任何bug都能被快速定位。整个过程下来你会发现自己对“一个程序是怎么运行起来”的理解真的会完全不一样。本文还有配套的精品资源点击获取
手写小型编译器：Python实现词法分析到三地址码
简介面向编译原理课程设计与实验的综合资源包适合高校计算机专业学生与自学编译器基础知识的开发者。内容覆盖从词法分析到语法分析、中间代码生成直至汇编代码生成的完整环节包含LL(1)分析、LR(0)与SLR(1)分析等经典方法并提供了可直接运行的C/C源代码、相关文法定义与说明文本以及一份小型编译器课程设计报告便于对照实验要求进行调试与扩展。包体共14个文件以C/C源文件cpp、c、h为主配合txt文法说明和doc实验报告文档整体仅557KB结构紧凑便于快速下载查阅。目前已吸引2342人学习下载验证了其在同类课程设计中的参考价值。读者可通过这些代码理解简单语句如ii*i的分析过程与四元式生成思路并借助报告梳理从设计到实现的整体流程适合作为课程设计或期末实验的速查模板。 盯着“编译原理课程设计”这几个字发呆可能是不少同学拿到题目后的第一状态。更别说什么词法分析、语法分析、小型编译器、实验报告一串名词堆在一起好像每一项都认识但真要动手做完全不知道从哪下笔。我当年也走过这条路最后用Python手写了一个能完成四则运算赋值、变量存储、print输出的小型编译器顺带把实验报告整理得明明白白答辩一次通过。这篇文章就把我当时的设计思路、代码核心、踩过的坑、报告写法全部摊开来讲希望能帮你少走弯路。1. 整体设计与思路拆解1.1 先搞清楚课设的验收底线很多同学一上来就想着“我要写一个能编译C语言的编译器”这完全是在给自己挖坑。编译原理课程设计的重点并不是做一个工业级产品而是让你把理论课上的词法分析、语法分析、语义分析、代码生成这几个阶段亲手实现一遍。验收老师的核心关注点通常是三个你的分析器能不能正确处理规定范围内的输入、你知不知道每一步在做什么、实验报告能不能把你的思路讲清楚。所以我在动手前先圈定了一个“小而全”的范围词法方面支持关键字let、print、标识符、整数、四则运算符、赋值号、括号、分号语法方面支持表达式、赋值语句和打印语句代码生成方面不生成真正的机器码而是生成三地址码并解释执行。这样一来理论课上的重点全部覆盖到代码量控制在几百行以内调试起来也相对简单。做课设最忌讳的是贪大范围定得越小越容易把每个阶段做扎实。1.2 开发语言怎么选别在工具上内耗我见过很多人为了课设去自学Flex、Bison或者用Java严格按书上的写法搞一个巨复杂的框架结果浪费了大量时间在环境配置和工具使用上。当时我选择Python理由很简单写起来快、正则表达式用着顺手、调试时不用管编译和内存问题。最关键的是手写的递归下降分析器在Python里体现得非常直观每个非终结符对应一个函数逻辑和文法几乎一一对应实验报告里讲原理的时候可以“照着代码说”特别省事。如果你的课程要求必须用C/C那也不用慌核心算法和Python版本完全一致只是字符串处理和动态数组需要自己多写一点。我个人建议优先用Python除非老师明确强制指定语言。原因就一条课设的重点在“分析器怎么写”不在“语言特性怎么用”用最顺手的语言把原理吃透比用高难度语言写出一个跑不起来的代码好得多。1.3 三阶段流水线先看清整体框架主流的编译器结构分好几个阶段但课设里我们只要做清楚三件事词法分析、语法分析、代码生成。我当时把所有代码组织成一个管道源代码字符串经过词法分析器变成Token列表Token列表经过语法分析器变成抽象语法树ASTAST经过遍历生成三地址码最后再对三地址码做简单解释执行。这样做的好处是每一层只做一件事出了问题容易定位。比如报错时如果语法层出问题你只要看Token列表是否正常如果运行结果不对直接看AST是否长得合理。整个程序结构划分成三个模块实验报告里“概要设计”那一章也就有了现成的图输入-词法分析-语法分析-代码生成-输出。这里的“图”其实可以画成简单的矩形框图不用画到什么高深的工具Word画就够了。2. 词法分析把字符流变成Token流2.1 先定义Token的类型和属性词法分析的工作就是把源代码拆成一个个有意义的“单词”Token。第一个要做的就是确定语言里有哪些Token类型。我当时设计了一张表放在代码注释里后来也直接搬进实验报告类型名含义例子KEYWORD关键字let, printID标识符x, totalINT整数常量1, 42OP运算符 - * / LPAREN/RPAREN括号( )SEMI分号;EOF文件结束--Token本身用什么存储我用了Python的namedtuple每个Token包含三个字段类型字符串、实际值、行号。行号特别重要实验报告里必须写出“当语法错误时能定位到第几行”所以我在词法阶段就顺手把行号记下来。实际代码大概长这样from collections import namedtuple Token namedtuple(Token, [type, value, line])有的同学会在这一步就做符号表把标识符存起来我建议先不要急。符号表放语义分析阶段做更合理词法层只要保证每个ID都能被正确识别出来就行否则耦合在一起会非常难调试。2.2 手写扫描器不用正则也能写明白词法分析有两种常见做法一是手写状态机二是基于正则表达式匹配。在课设里很多老师希望看到“手写逐字符扫描”因为这样更能体现状态机思想。我当时也选择手写用一个index指针从头往后扫遇到字母开头就一直读直到非字母数字判断为关键字或标识符遇到数字就一直读到非数字判断为整数遇到符号就匹配对应的运算符。核心逻辑并不复杂但有一个坑必须注意等号“”和字符串结束判断、减号“-”与负号的区别。我当时限定所有数字都是非负整数负号被当作减法运算符这样表达式“-3”就必须写成“0 - 3”虽然别扭但文法简单课设足够。如果你后续想扩展负数就需要在语法分析阶段处理一元运算符复杂度会上升不少。扫描代码的骨架大约是这样的def tokenize(code): tokens [] i 0 n len(code) while i n: ch code[i] if ch.isspace(): i 1 continue if ch.isalpha(): start i while i n and (code[i].isalnum() or code[i] _): i 1 word code[start:i] if word in {let, print}: tokens.append(Token(KEYWORD, word, line)) else: tokens.append(Token(ID, word, line)) continue if ch.isdigit(): # 连续读数字 ... if ch in -*/: tokens.append(Token(OP, ch, line)) ...这样写完以后输入“let x 10 5;”输出的Token列表理想情况下是[let, ID(x), , INT(10), , INT(5), ;]。我当时为了演示效果在main里加了一个debug参数可以直接输出这个列表答辩时展示“看词法分析成功把源码拆成了Token流”老师一眼就明白你确实做了东西。2.3 错误恢复别让一个错字符卡死整个程序初版代码最常见的毛病是遇到一个无法识别的字符就立即抛异常程序直接退出。比如用户多打了一个“#”整个分析就中断了这样的用户体验非常糟糕而且实验报告里“错误处理”部分没东西可写。我当时的做法是遇到无法识别的字符记录一条“第几行发现非法字符”的报错信息然后直接跳过这个字符继续往后扫。这样词法分析阶段可以一次性列出所有非法字符而不是报一个就停。同理如果字符串里出现非法数字比如“12a”我暂且把它识别为一个ID还是报错这里要定义清楚我选择先识别“12”为INT再让“a”作为ID这样在语法层会因为两个相邻Token不符合文法而报“语法错误”。其实这样也能接受。当然如果你希望更严谨可以在数字后面紧随字母时报“数字标识符不合法”。这部分属于加分项实验报告里写清楚你的规则即可。词法错误恢复的验收点通常是“错误信息有没有行号”只要把这个细节做到老师就会觉得你考虑很周全。3. 语法分析递归下降构造AST3.1 文法设计先写产生式再写代码语法分析不能凭空写代码得先把文法规则写出来。当时我选的文法支持以分号分隔的语句序列每个语句要么是“let 变量 表达式;”要么是“print 表达式;”。因为递归下降分析法对应LL文法所以一开始我就避免直接写出左递归的表达式文法而是采用“优先级分层法”来天然消除左递归。我设置的文法如下E代表表达式程序 - 语句列表 语句列表 - 语句 | 语句列表 语句 语句 - 赋值语句 | 打印语句 | 空 赋值语句 - let ID 表达式 ; 打印语句 - print 表达式 ; 表达式 - 项 ( ( | - ) 项 )* 项 - 因子 ( ( * | / ) 因子 )* 因子 - INT | ID | ( 表达式 )这里“*”表示循环所以实际上已经不会产生左递归了。很多课程理论里会先写“E - E T | T”再教你消除左递归我在实验报告里就专门写了一段为了避免LL(1)分析中的无限递归我直接将文法改写成上面这种迭代形式。这一步在答辩时特别容易被问“为什么不用E-ET”你回答“因为递归下降的递归调用会无限循环所以采用循环右递归等价形式”基本就稳了。3.2 递归下降函数一个非终结符一个函数递归下降的名称听起来高级其实思路很简单为每个非终结符写一个解析函数函数里根据当前Token类型决定下一步怎么走。其中“表达式”和“项”这种带循环的函数是核心。以“项”的函数为例流程是先调用“因子”函数解析第一个因子然后循环判断当前Token是不是乘号或除号是就消费这个运算符再调用“因子”解析右操作数如此反复。这里有一个坑循环的退出条件必须判断“当前Token不是运算符”时break否则会一直死循环。我当时写过一个bug循环里忘了在匹配失败时break结果一旦遇到分号就无限卡在“项”的函数里。“因子”函数相对简单如果当前Token是INT就创建一个数字节点如果是ID就创建变量节点如果是左括号就递归调用“表达式”函数然后期望下一个Token是右括号。这里必须做完整检测“下一个Token如果不是右括号就报错”我当时偷懒没有做导致“((12)”这种输入居然被接受了后来补上以后测试才严谨。为了满足老师“报告里必须有语法树”的要求我写了一个AST节点树形打印函数调试时可以直接把解析结果打印成类似如下的形式Program Assign: x BinOp() Int(10) Int(5)这个功能写起来很简单就是递归打印AST但对理解程序和执行流程特别有用。3.3 AST节点怎么存用dict和class二选一AST既可以用类占位也可以用字典。我当时用了很朴素的Python类每个节点有一个type字段比如int、id、binop、assign、print然后根据类型附带不同属性比如binop节点有left、op、right字段assign节点有name和expr字段。用类的好处是访问属性方便缺点是定义几个类代码看起来更“正式”。如果你不想写太长也可以直接用tuple或list但那样代码可读性会变差报告里解释起来也费劲。我建议用最简形式的类别整一堆继承够用就行class Node: def __init__(self, type, **kwargs): self.type type self.__dict__.update(kwargs)这样一个Node就能装下所有节点类型唯一的缺点是属性名字写错了不会报错需要自己小心。站在课设角度这种“半动态”结构压力不大。3.4 语法分析调试实录最常见的三个错第一次跑通语法分析后我开始故意输入各种非法程序来测试。最常出现的三种错误情境基本覆盖了课设中大多数人的困难。第一个是没有及时消费Token。比如在“表达式”解析里刚吃完一个数字忘了调用advance()移动到下一个Token结果下次循环又处理同一个Token导致AST长得极其奇怪甚至死循环。排查方法很简单在关键函数入口打印当前Token看它有没有向后走。第二个是括号匹配没有做“缺右括号”判断。我当时只检查“如果有右括号就吃掉”完全不看“是不是真的有右括号”。后来输入“let x (12; ”发现它居然顺利通过了差点以为出现了灵异事件。检查之后才发现代码逻辑写反了应该先检查当前Token是否为右括号不是就报错。第三个是关键字和标识符区分时机不对。词法层已经把“let”识别成了KEYWORD但语法层的语句入口只认“ID”开头。正确的做法是在语句判断时收到KEYWORD类型然后根据值是let或print来决定进入哪个分支。如果你在语法层还去判断Token的value而不是类型就会漏判很多情况。记住语法分析阶段只看Token.type不要过分检查Token.valuevalue的具体意义留给上层。4. 小型编译器从AST到三地址码4.1 语义分析与符号表变量的记录和检查语法分析之后我们有了AST但还没有“变量存储”的概念。小型编译器至少要能处理“变量必须先定义再使用”所以我在这个阶段做了一次AST遍历完成两件事把所有let语句里的变量名记录进符号表在print表达式和赋值表达式里遇到ID时检查该变量是否存在不存在就报“未定义变量”。符号表我用了一个非常简单的Python字典变量名到值。因为课设不需要作用域所有变量都在一个全局空间。如果你希望更复杂一点可以给每个变量加类型、初始值、使用次数等但那些不是硬性要求只会增加报告篇幅。这里的核心技巧是语义检查最好在代码生成之前独立做一遍不要边生成边检查。否则代码生成到一半才发现变量未定义整个流程就会很乱。我当时把语义分析写成了对AST的check(env)函数它会返回一个新的符号表给后续代码生成用这样各个阶段边界非常清楚。4.2 三地址码生成比想想中还要简单很多同学看到“三地址码”就害怕其实它就是“每条指令最多三个地址”的中间代码比如t1 10 5。我需要的指令类型很少赋值、二元运算、打印、标号跳转这门课里用不到跳转所以直接省略。生成逻辑就是遍历AST遇到BinOp先生成左操作数的代码、再生成右操作数的代码然后生成一条运算指令。比如let x (10 5) * 2;最终生成的三地址码就是t1 10 5 t2 t1 * 2 x t2如果表达式里出现变量ID就直接用变量名作为操作数不需要临时变量。实现时用了一个new_temp()函数每调用一次返回t 序号同时序号加一。这个序号在实验报告里最好写清楚不然答辩时老师问“为什么t后面要加数字”你可能一时想不起来。三地址码生成完后我把它保存成一个列表每一条指令要么是一个tuple要么是字符串。我当时用字符串列表因为打印出来特别直观便于验收。实际代码大约是这样def gen(node): if node.type int: return node.value if node.type id: return node.name if node.type binop: left gen(node.left) right gen(node.right) t new_temp() code.append(f{t} {left} {node.op} {right}) return t if node.type assign: expr gen(node.expr) code.append(f{node.name} {expr}) ...4.3 解释执行三地址码最后一公里生成三地址码之后理论上已经完成“编译器”的主要任务了。但课程设计要求能运行结果所以我选择再写一个简单的解释器去执行三地址码输出print结果。这其实是绕过真实机器码的讨巧方法但对课设完全成立。解释器逻辑很简单顺序遍历指令列表遇到x y op z就把对应变量的值取出来做运算结果存回x遇到x y就是普通赋值遇到print x就打印变量x的值。这里有一个需要注意的点三地址码里t1 10 5的右操作数可能是数字也可能是变量名怎么判断可以维护一个value_of函数如果字符串全是数字就转成int否则在符号表里查变量值。这正好复用了之前语义分析阶段生成的符号表。至此从源代码到最终打印结果一个完整的小型编译器就闭环了。我当时在main函数里敲入let a 2; let b a * 3 1; print b;程序输出7。那一刻的成就感真的是别提了也是后来答辩时最有底气的部分。5. 实验报告把过程变成分数5.1 测试用例怎么设计才不是凑数实验报告里最容易被忽视的是“测试与分析”章节很多同学就放两三个正常用例老师一眼看穿没好好测。我当时把测试用例分成四类写了一个完整的测试表测试类别输入程序期望输出验证点正常表达式print 10 5 * 2;20优先级处理变量赋值let x 3; let y x 4; print y;7变量存储与读取括号嵌套print (1 2) * (3 4);21括号递归解析错误处理let x ;第1行报语法错误错误信息与定位错误处理print a;第1行报未定义变量符号表检查每个用例我都写了“输入、输出、结论”三行并且在测试代码里用断言验证期望输出。这样报告里可以写“全部测试用例自动通过”比手写截图更有说服力。另外建议至少放一个错误处理的用例这是最能体现你考虑了健壮性。5.2 实验报告结构模板照着填就行虽然不同学校格式要求略有差异但核心章节基本是固定的。我当时的报告包含六个大块需求分析、总体设计、详细设计、测试与分析、结论与心得、参考文献。每一块都有一些可以“从代码中直接迁移”的内容写起来并不难。需求分析里写明“我们要做什么、输入输出是什么、功能列表”。总体设计里画一个简单的模块关系图并说明三个模块的调用关系。详细设计是重头戏我会把Token定义表、文法产生式、关键数据结构、核心函数接口全部列出来再配上少量关键代码。测试与分析就用上一节的表格和截图。结论与心得里我写了自己踩的坑和学到的“先设计再写代码”的思维这部分不用太长真实最重要。注意不要大段抄代码堆在报告里老师更想看到的是“为什么这样设计”。比如我写递归下降时专门解释“为什么要用循环消除左递归”就是那句“防止递归调用无限循环”。这种一句话的原理比贴一百行代码更能拿分。5.3 演示材料准备细节决定印象如果有答辩环节演示时不要把源码从头到尾翻给老师看那既看不出重点又容易显得没准备。我当时的策略是先演示一个最简单的print 1 2;输出3再演示变量和括号最后故意输入一句话法错误展示错误定位。整个演示控制在3分钟以内。期间老师问得最多的往往是“你的这个运算符优先级是怎么实现的”。你要能回答因为语法分析时分为表达式和项两层乘除在项层加减在表达式层所以乘除会先被解析优先级自然就高了。这个解释甚至不需要看代码只要理解了分层就能答上来。6. 常见问题与避坑清单6.1 词法层和语法层各有什么最容易翻车的点词法层最常见的问题是不能区分“abc123”这类标识符如果规则开放了下划线就要让字母、数字、下划线都能出现在标识符中间。语法层最大的坑我刚才说过就是没有对“当前Token和期望Token不匹配”做出统一报错。如果你在每个函数里各写各的报错逻辑很容易出现“一处报错、程序崩溃”的尴尬。我建议做一个统一的错误告警函数error(msg, token)任何语法错误都调用它并携带当前Token的行号。这样既统一了格式也为报告里的错误处理亮点提供了依据。另外解析循环语句时一定要有步进机制绝不允许一个Token被连续消费两次或永远不被消费。6.2 代码实现里别犯的三个低级错误第一个是新建临时变量时忘记初始化计数器导致第一次生成的临时变量是t1但下一次还是t1最终代码互相覆盖。第二个是AST节点生成后忘记挂载子节点比如生成binop节点时只设置了left忘记设置right导致解释执行时访问right属性报错。第三个是表达式求值和代码生成混在一起中间栈乱了到了末尾甚至分不清谁是谁。解决方法就是坚持“一步一个中间表示”的原则不让任何阶段跨越。6.3 报告和答辩中怎么讲才能拿高分一个小经验是答辩前准备一个“三个为什么”。问自己为什么选择手写词法分析器为什么选择递归下降而不是LR为什么生成三地址码而不是直接输出汇编把这三个问题想透就能应付大多数老师的追问。还有一点报告里不要只写成功适当写一点“在设计过程中遇到的问题以及如何解决”。老师非常喜欢看到这种真实的数据。比如我写“第一版没有处理括号不匹配导致表达式错误被错误接受后来在因子解析函数中增加右括号检查后解决”比通篇吹自己完美更打动人。最后分享一个小技巧写编译原理课设时如果卡在了某个地方先把阶段边界捋一遍。词法出问题就去检查Token流语法出问题就去打印AST生成结果不对就去单步走一遍代码生成。只要阶段清晰任何bug都能被快速定位。整个过程下来你会发现自己对“一个程序是怎么运行起来”的理解真的会完全不一样。本文还有配套的精品资源点击获取
