简介2022年华东理工大学编译原理实验资料包包含词法分析与语法分析两份实验报告及配套源码面向高校编译原理课程学习者尤其是需要完成PL/0词法分析实验的学生。资源共5个文件包括2个Word实验报告、2个C源程序词法分析器PL0Compiler.cpp与语法分析yufa2.cpp和1个PL/0测试用例Test1.pl整体仅274KB小巧便于对照阅读。内容围绕PL/0编译器展开先编写测试用例再开发词法分析程序逐个输出单词序号、字符串、类型和值在此基础上将PL/0标识符规则修改为C语言风格定义新语言PL/1并编写用例实验记录中解释了数据与变量变化原因及输出结果。语法分析报告则覆盖语法分析设计与实现思路可帮助读者理解编译前端核心流程。已有722人学习下载适合需要实验报告参考、源码复现或快速入门词法/语法分析的在校学生。1. 编译原理词法分析加语法分析实验为什么这是编译器课程第一道真坎编译原理词法分析加语法分析实验是编译器课程里第一道必须动手过的坎。前面学正则表达式、DFA、文法、LL(1) 的时候还能在纸上推到这一步得把一段类 C 源程序先切成 token再按文法还原出结构每一条规则都会在你面前变成真实的逻辑。华东理工大学 2022 年这个实验考察的就是完整链路词法分析器能不能干净识别关键字、标识符、运算符语法分析器能不能按文法给出正确的推导过程以及报告能不能把设计取舍和测试证据讲清楚。这篇文章适合两类人正在实验周里赶进度、想照着一套可靠流程把项目写完的学生以及工作后想补编译器前端基础的工程师。我按自己做过的方案把实验拆成六段来讲代码给到能直接跑通坑给到能绕开。2. 词法分析从正则式到可落地的 token 识别词法分析是整个实验的第一层很多人一上来就写一个巨大的 switch 分支堆字符结果改一个运算符就得动五处。更常见的思路是先把语言里所有词法单元列成一张表再写一个统一的扫描循环按表匹配。下面先讲清楚为什么我推荐手写 DFA 而不是直接调正则库再给一份能直接跑的最小实现。2.1 识别器选型手写 DFA还是直接调正则引擎词法分析器有两种写法一种是基于正则表达式用re模块或者 flex 生成识别器另一种是手动模拟 DFA把每个 token 的识别状态画出来。课程实验里我一般会选手写原因有三。第一多数实验明确要求“不得直接调用正则库”判分时会看你对 DFA 的理解第二手写代码虽然长一点但每个字符该怎么消费、什么时候回退都是可控的调试起来不用跟黑匣子较劲第三手写方案后面接语法分析的时候错误信息能把 token 类型、原文和行号全都带出来正则库很难给到这种精度。选型上可以这样判断如果实验文档里写了“建议使用 flex”那只表示允许并不代表加分如果写了“手工构造”那就完全没有悬念直接用 DFA。即使你最后想偷懒用正则库也至少要把状态转换图先画出来报告的方案设计部分才站得住。下面这份表是我常用的对比口径。方案优点缺点适用场景直接调正则库代码量小匹配写法直观容易被判定不符合实验要求回退与错误定位难控制自测辅助脚本不上交flex 自动生成支持复杂正则生成代码稳定输出代码可读性差报告里讲不清状态转换实验允许且要求生成代码手写 DFA 扫描器结构透明错误定位准确最容易讲设计首次编写稍慢运算符一多要细心维护课程实验主流做法2.2 最小可运行的词法分析器完整代码与参数说明下面这份代码不依赖任何第三方库用 Python 写核心逻辑是“一个 while 扫描 多字符优先匹配”。如果你交的是 java编译原理方向的实验把 dict 换成 HashMap、把 list 换成 ArrayList 就行结构完全不用变。# lexer.py不依赖正则库的最小词法分析器 # 支持关键字 int void if else while return # 支持运算符 - * / ! ; , ( ) { } KEYWORDS {int, void, if, else, while, return} # 运算符统一放在一张表里保证“取两个字符”和“取一个字符”走同一套逻辑 OPS { : PLUS, -: MINUS, *: STAR, /: SLASH, : LT, : LE, : GT, : GE, : EQ, !: NE, : ASSIGN, ;: SEMI, ,: COMMA, (: LPAREN, ): RPAREN, {: LBRACE, }: RBRACE, } class Token: __slots__ (kind, text, line) def __init__(self, kind, text, line): self.kind kind self.text text self.line line def __repr__(self): return f{self.kind}({self.text!r}){self.line} def tokenize(src): tokens [] i, n, line 0, len(src), 1 while i n: c src[i] if c in \t\r: i 1 continue if c \n: line 1 i 1 continue # 注释 // 优先处理遇到注释直接跳到行尾避免把注释里的运算符当代码 if c / and i 1 n and src[i 1] /: while i n and src[i] ! \n: i 1 continue # 标识符和关键字统一按标识符拼出来再查关键字表 if c.isalpha() or c _: start i while i n and (src[i].isalnum() or src[i] _): i 1 text src[start:i] kind KEYWORD if text in KEYWORDS else ID tokens.append(Token(kind, text, line)) continue # 整数字面量 if c.isdigit(): start i while i n and src[i].isdigit(): i 1 # 数字后面紧跟字母属于非法标识符形式这里直接暴露问题 if i n and (src[i].isalpha() or src[i] _): raise SyntaxError(fline {line}: invalid number {src[start:i]}{src[i]}) tokens.append(Token(INT, src[start:i], line)) continue # 运算符匹配先试两个字符再退回单字符 two src[i:i 2] if two in OPS: tokens.append(Token(OPS[two], two, line)) i 2 continue if c in OPS: tokens.append(Token(OPS[c], c, line)) i 1 continue raise SyntaxError(fline {line}: unexpected char {c!r}) tokens.append(Token(EOF, , line)) return tokens if __name__ __main__: import sys source open(sys.argv[1], encodingutf-8).read() for tok in tokenize(source): print(tok)这段代码的关键点有两个。第一个是运算符匹配顺序必须先查src[i:i2]再查单字符因为、这类两字符运算符优先级更高如果反了a b会被拆成a b语法分析器直接拒绝。第二个是换行计数\n分支里必须先line 1再i 1顺序不能反否则所有报错行号都会偏小。数字后面跟字母我直接抛了异常这是刻意为之宁可在这里报错也不能让123abc被静默切分成两个 token否则语法阶段会给出很误导的错误。2.3 标识符与关键字先拼完整词再查表关键字和标识符的区分是词法分析最容易写错的地方。新手常犯的错误是先对第一个字符判断它是不是关键字比如看到i就以为一定是if结果把合法的变量名intx给拆了。正确做法是不管是什么词先按“字母或下划线开头后续允许字母数字下划线”的规则拼出完整词再去查 KEYWORDS 集合。这样if和iffy自然落进不同的桶不需要额外处理。这套方案里还存在一个优先级问题注释//必须在运算符判断之前处理。如果你把//放进运算符表就会先把/匹配成 SLASH再把第二个/匹配成另一个 SLASH注释内容从此全部被当成源码。所以我单开了一个分支跳到行尾。同理字符串字面量如果实验支持也要放在运算符之前不做字符串的话遇到直接报错比假装支持更稳。3. 语法分析递归下降法如何接手 token 流词法分析把字符流变成 token 流之后语法分析器要做的事情就是按照文法规则逐步匹配 token。这个实验里最稳妥、最容易在报告里讲清楚的方法是递归下降它本质上是把文法的每个非终结符写成一个函数函数之间互相调用。下面先解决文法改写的问题再给一份和上一章 lexer 配套的 parser 代码。3.1 文法改写左递归为什么会让递归下降死循环递归下降要求文法不能有左递归否则函数会无限调用。典型例子是表达式文法E - E T | T如果直接照抄成parse_E()函数函数第一行就调用自己永远走不到第二个分支。标准做法是把左递归改写成右递归E - T E E - T E | ε这样parse_E先调parse_T再调parse_E而parse_E只有在看到的时候才继续递归不会空转。课程实验里真正需要这种改写的通常只有表达式部分语句级文法像if、while、赋值大多天然就是 LL(1) 结构。如果你在报告里能写清楚“左递归会导致递归下降栈溢出或死循环因此改写成右递归”这一节的设计分基本就稳了。提取公因子也是个常见操作。比如if (E) S和if (E) S else S两个产生式共享前缀if (E) S直接写两个分支会让 parser 不知道选哪个。解决方法是先匹配公共前缀再看后面是不是else决定走哪个分支。代码里我会用peek().text else做这个二选一这就是提取公因子后的结果。3.2 递归下降语法分析器完整代码与运行方式下面这份 parser 完整接住上一章的 token 流解析一个迷你语言的函数定义、语句、赋值和表达式。每个函数对应一个非终结符我用缩进把推导过程打印出来方便实验报告里直接贴输出。# parser.py递归下降语法分析器输入为 lexer.tokenize 产生的 token 流 from lexer import tokenize, Token class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.depth 0 def peek(self): if self.pos len(self.tokens): return Token(EOF, , -1) return self.tokens[self.pos] def advance(self): tok self.peek() self.pos 1 return tok def expect(self, kind): tok self.peek() if tok.kind ! kind: raise SyntaxError(fline {tok.line}: expect {kind}, got {tok.kind}({tok.text})) return self.advance() def expect_text(self, text): tok self.peek() if tok.text ! text: raise SyntaxError(fline {tok.line}: expect {text}, got {tok.text}) return self.advance() def show(self, tag, text): print( * self.depth tag ( text if text else )) # program - function* def parse_program(self): while self.peek().kind ! EOF: self.parse_function() # function - type ID ( ) block def parse_function(self): self.show(FUNCTION) self.depth 1 self.expect(KEYWORD) # int 或 void self.expect(ID) self.expect(LPAREN) self.expect(RPAREN) self.parse_block() self.depth - 1 # block - { statement* } def parse_block(self): self.show(BLOCK) self.depth 1 self.expect(LBRACE) while self.peek().text ! }: if self.peek().kind EOF: raise SyntaxError(unclosed block) self.parse_statement() self.expect(RBRACE) self.depth - 1 # statement 的分发逻辑 def parse_statement(self): tok self.peek() if tok.kind KEYWORD and tok.text in (int, void): self.parse_decl() elif tok.text if: self.parse_if() elif tok.text while: self.parse_while() elif tok.text return: self.parse_return() elif tok.kind ID: self.parse_assign() else: raise SyntaxError(fline {tok.line}: unexpected statement start {tok.text}) def parse_decl(self): self.show(DECL) self.depth 1 self.advance() # 类型 self.expect(ID) # 变量名 if self.peek().text : self.advance() self.parse_expr() self.expect(SEMI) self.depth - 1 def parse_if(self): self.show(IF) self.depth 1 self.advance() self.expect(LPAREN) self.parse_expr() self.expect(RPAREN) self.parse_statement() if self.peek().text else: self.advance() self.parse_statement() self.depth - 1 def parse_while(self): self.show(WHILE) self.depth 1 self.advance() self.expect(LPAREN) self.parse_expr() self.expect(RPAREN) self.parse_statement() self.depth - 1 def parse_return(self): self.show(RETURN) self.depth 1 self.advance() self.parse_expr() self.expect(SEMI) self.depth - 1 def parse_assign(self): self.show(ASSIGN) self.depth 1 self.advance() # ID self.expect(ASSIGN) # 一定不能是 self.parse_expr() self.expect(SEMI) self.depth - 1 # 表达式入口按优先级分成三层 def parse_expr(self): self.parse_additive() def parse_additive(self): self.parse_mul() while self.peek().text in (, -): self.show(OP, self.peek().text) self.advance() self.parse_mul() def parse_mul(self): self.parse_primary() while self.peek().text in (*, /): self.show(OP, self.peek().text) self.advance() self.parse_primary() def parse_primary(self): tok self.peek() if tok.kind INT: self.show(INT, tok.text) self.advance() elif tok.kind ID: self.show(ID, tok.text) self.advance() elif tok.text (: self.advance() self.parse_expr() self.expect(RPAREN) else: raise SyntaxError(fline {tok.line}: unexpected expression token {tok.text}) if __name__ __main__: import sys source open(sys.argv[1], encodingutf-8).read() tokens tokenize(source) Parser(tokens).parse_program()运行方式很简单python3 lexer.py test.c python3 parser.py test.cparser 的每个parse_xxx函数就是文法里的一个非终结符expect负责消费指定类型的 tokenpeek只往前看一个 token 不消费。parse_if里明显体现了提取公因子的结果先匹配if (expr)再匹配语句最后用peek().text else判断是不是要走 else 分支。参数层面你只需要维护 KEYWORDS 集合和 OPS 表文法扩展语句时加一个新分支函数即可。3.3 表达式优先级函数的嵌套深度就是优先级如果把表达式直接写成parse_expr一个函数那2 3 * 4会被算成(2 3) * 4这在语法层面就错了。解决手段就是分层递归加法层调用乘法层乘法层调用基本单元层。优先级越高函数调用的层次越深所以*会被更早匹配也就更靠近操作数。expr - additive additive - mul (( | -) mul)* mul - primary ((* | /) primary)* primary - INT | ID | ( expr )这套结构还有一个额外好处想加一元负号只需要在 primary 里加- primary分支想加取模%只需要在 mul 里加一个 token 判断。报告里你甚至可以放一张“层数和优先级对照表”说明每一层对应哪一级运算符老师一眼就能看出你理解了运算符优先级的本质。4. 词法与语法联调避坑输入缓冲、回退和错误行号词法分析单独跑没问题语法分析单独跑也没问题一联调就翻车这是这条实验线路上最常见的现象。下面五个坑是我自己踩过、也看身边人反复踩过的每一条都按“现象、原因、解决”给清楚。4.1 多字符运算符被拆成两个 token现象a b被识别成ID(a) GT() ASSIGN() ID(b)语法分析器直接报错但词法单测是过的。原因词法扫描只看了当前字符发现在运算符表里就直接返回完全没有看下一个字符是不是。解决在取 token 前先检查src[i:i2]是否在两字符运算符表里命中则整体消费两个字符。这就是 2.2 代码里two src[i:i 2]那两行的作用。实验里最容易漏的是、、、!这四个其中漏!的隐蔽性最强因为单字符!往往不在你的运算符表里结果是直接报“unexpected char”反而比拆成! 更容易发现。4.2 数字后面跟字母导致静默切分现象输入int 123abc;词法分析器输出KEYWORD(int)、INT(123)、ID(abc)语法分析器居然通过了程序行为完全错误。原因数字循环只认数字字符循环结束就提交 token没有检查下一个字符是不是字母或下划线。解决在数字循环结束后补一个判断如果下一个字符是字母或下划线就抛异常把问题暴露在词法阶段。这也是 2.2 代码里特意加那个if的原因。很多人觉得这是罕见输入可以不管但实验报告的负数测试用例里一旦出现老师就会认为边界意识不够。4.3 语法分析死循环错误 token 没有被消费现象输入if (a { }parser 卡住不退出或者无限打印同一个错误。原因某个 parse 函数在匹配失败时没有调用advance()self.pos永远停在同一个位置外层 while 循环判断条件不变于是反复进入同一分支。解决在每个parse_xxx里保证“要么抛异常要么至少消费一个 token”。调试时可以临时在 parser 的__init__里加一个self.step 0每次advance()后递增超过 10000 就抛异常用这种保险绳定位是哪个分支在空转。我实际见过最多的死循环在parse_blockwhile self.peek().text ! }这个条件一旦 token 流里根本没有}指针走到 EOF 也不满足终止条件就会死循环。所以代码里我加了 EOF 检查这一行就是血泪经验换来的。4.4 报错行号永远差一行现象明明在文件第 10 行写错了报错却指向第 9 行。原因词法扫描器在遇到\n时先i 1再line 1或者干脆跳过换行忘了计数。由于代码里多个分支共享i 1新人在重构时很容易把line 1一起删掉。解决换行分支单独写顺序固定为“先 line 1 再 i 1”。验证方法也简单写一个每行只有一个小 token 的文件比如一行一个数字词法输出如果行号序列是 1,2,3,4 就正确如果中间断了说明某个空白字符分支吃掉了换行。4.5 注释里的运算符被当成代码处理现象输入// a b词法分析器在//处没有跳行而是把识别成了 GE 运算符。原因注释判断写在了运算符分支之后扫描器先看到/匹配成了 SLASH完全没有机会进入注释逻辑。解决注释跳过、空白跳过、换行计数这三类“不可见 token”处理必须放在所有有效 token 识别之前优先级最高。另一个常见版本是/* */块注释跨越换行时要在注释内部也做行号计数否则行号会再次失准。课程实验通常只要求//但报告里如果能主动说明“我把注释优先级提到最高并维护了行号”是一个很便宜的加分点。5. 实验报告评分点与容易漏掉的证据代码能跑只是实验的一半另一半是报告。编译原理实验报告不是代码贴图集老师要看的是你“为什么这样设计”和“怎么证明它是对的”。下面按我写课程报告的习惯拆开讲照着这个骨架写基本不会漏评分点。5.1 报告骨架先给表格再给代码一份能拿高分的报告结构上通常是这样需求描述、总体设计、详细设计、测试与结果、问题与反思。需求描述要写清楚你实现了语言子集的哪些部分比如“支持 int/void 函数定义、if/while/return、四则运算与关系比较”这样老师不用读代码就知道覆盖范围。总体设计放一张模块图不必画得多精致但要明确词法分析器和语法分析器的数据流方向字符流进词法、token 流进语法、推导或语法树出结果。详细设计里最忌讳整段贴源码应该贴关键数据结构比如 token 表、文法规则表、运算符优先级表。你贴一棵 200 行的函数树不如一张 token 类型表值钱。5.2 三个决定印象分的细节第一个细节是 token 表完整列出来。词的种类、示例、正则形式三列一张表就能看出你对词法单元有没有完整认识。第二个细节是错误处理单独写一节。哪怕只实现了最简单的“遇错即停”也要写清楚错误信息里包含了行号和期望 token 类型这比任何设计图都能体现工程感。第三个细节是运行截图不要只截成功案例。至少一张正常输出、一张错误输出附上命令行输入错误输出的信息越具体越好。很多人只截一段结果老师根本看不出输入是什么等于没截图。5.3 测试结果用测试矩阵不要用聊天式描述我建议测试部分放一张矩阵表横轴是测试用例编号纵轴是检查点。例如用例输入片段期望行为实际行为备注01int main() { return 0; }正常解析一致基础流程02a 1 2 * 3;乘法优先一致运算符优先级03a b;EQ 而非两个 ASSIGN一致多字符运算符04if (a) { } else { }两个分支均识别一致else 可选性05int 123abc;词法报错一致非法标识符06while ( { }语法报错行号一致错误定位注意“备注”这一列要写清测的是哪个设计点而不是写“跑通了”。老师看测试矩阵第一眼是看覆盖第二眼是看有没有针对自己的薄弱点设计用例。能把错误路径的用例放在前面说明你对“程序是会出错的”这件事有充分认知。5.4 反思部分避免空话“通过本次实验我深入理解了编译原理”这句话等于没写。合格的反思要能看出设计假设与实际结果之间的碰撞。我习惯用三个问题驱动第一我最初的设计和最终实现差在哪里第二哪个 bug 花的时间最长根因是什么第三如果再给我一周我会加什么功能。比如你可以写“最初把运算符匹配放在注释处理之前导致 // 后内容全部被解析为代码后来把注释优先级提到最高这让我意识到词法扫描的分支顺序也是一种设计”。这种具体的错误记录比任何总结都有说服力而且老师明显能看出来是不是自己做的。6. 验证与进阶答辩前靠这三招把实验从能跑做到能讲6.1 构造一个自动回归验证脚本实验临近答辩时最怕改一处运算符、坏一片功能。我习惯把测试用例放进tests/目录用一段 shell 批量跑比对实际输出和期望文件# run_tests.sh对每个 .c 样例执行 parser并与 .out 期望文件比对 for f in tests/*.c; do base${f%.c} python3 parser.py $f ${base}.result if diff -u ${base}.out ${base}.result /dev/null; then echo PASS $f else echo FAIL $f fi donetests目录里每个样例配套一个.out期望文件改动代码后跑一遍失败的用例立刻暴露。这比答辩现场手敲输入要稳得多也方便老师看你准备了多完备的验证。我的习惯是每次修复一个 bug就把它对应的错误输入保存成新用例这样同一个坑不会再踩第二次测试样例就是你的后悔药。6.2 panic mode 错误恢复一个低成本加分项如果只想加一个功能来拉开差距我推荐做 panic mode 错误恢复。思路是给语法分析器定义一组同步 token出错后不断丢 token直到遇到同步点再继续解析而不是直接终止。常见同步点包括分号、右花括号和 EOF。def synchronize(self): while self.pos len(self.tokens): tok self.peek() if tok.text in (;, }, EOF): return self.advance()把这个方法插到parse_statement的异常处理里一条语句出错后还能继续解析下一条错误报告也能一次给出多个问题。报告里只要写明“我设置了分号和右花括号作为同步 tokenpanic mode 恢复后从下一条语句继续”这就从基础正确性迈向了容错性很多实验的评分表里会有这一步的加分项。我这么多年的习惯是先保证错误定位准再做错误恢复顺序反了会连正确的报错都搞丢。希望这段思路能帮你在同样的实验里少绕几个弯。本文还有配套的精品资源点击获取
编译原理词法分析加语法分析实验：手写DFA与递归下降实现
简介2022年华东理工大学编译原理实验资料包包含词法分析与语法分析两份实验报告及配套源码面向高校编译原理课程学习者尤其是需要完成PL/0词法分析实验的学生。资源共5个文件包括2个Word实验报告、2个C源程序词法分析器PL0Compiler.cpp与语法分析yufa2.cpp和1个PL/0测试用例Test1.pl整体仅274KB小巧便于对照阅读。内容围绕PL/0编译器展开先编写测试用例再开发词法分析程序逐个输出单词序号、字符串、类型和值在此基础上将PL/0标识符规则修改为C语言风格定义新语言PL/1并编写用例实验记录中解释了数据与变量变化原因及输出结果。语法分析报告则覆盖语法分析设计与实现思路可帮助读者理解编译前端核心流程。已有722人学习下载适合需要实验报告参考、源码复现或快速入门词法/语法分析的在校学生。1. 编译原理词法分析加语法分析实验为什么这是编译器课程第一道真坎编译原理词法分析加语法分析实验是编译器课程里第一道必须动手过的坎。前面学正则表达式、DFA、文法、LL(1) 的时候还能在纸上推到这一步得把一段类 C 源程序先切成 token再按文法还原出结构每一条规则都会在你面前变成真实的逻辑。华东理工大学 2022 年这个实验考察的就是完整链路词法分析器能不能干净识别关键字、标识符、运算符语法分析器能不能按文法给出正确的推导过程以及报告能不能把设计取舍和测试证据讲清楚。这篇文章适合两类人正在实验周里赶进度、想照着一套可靠流程把项目写完的学生以及工作后想补编译器前端基础的工程师。我按自己做过的方案把实验拆成六段来讲代码给到能直接跑通坑给到能绕开。2. 词法分析从正则式到可落地的 token 识别词法分析是整个实验的第一层很多人一上来就写一个巨大的 switch 分支堆字符结果改一个运算符就得动五处。更常见的思路是先把语言里所有词法单元列成一张表再写一个统一的扫描循环按表匹配。下面先讲清楚为什么我推荐手写 DFA 而不是直接调正则库再给一份能直接跑的最小实现。2.1 识别器选型手写 DFA还是直接调正则引擎词法分析器有两种写法一种是基于正则表达式用re模块或者 flex 生成识别器另一种是手动模拟 DFA把每个 token 的识别状态画出来。课程实验里我一般会选手写原因有三。第一多数实验明确要求“不得直接调用正则库”判分时会看你对 DFA 的理解第二手写代码虽然长一点但每个字符该怎么消费、什么时候回退都是可控的调试起来不用跟黑匣子较劲第三手写方案后面接语法分析的时候错误信息能把 token 类型、原文和行号全都带出来正则库很难给到这种精度。选型上可以这样判断如果实验文档里写了“建议使用 flex”那只表示允许并不代表加分如果写了“手工构造”那就完全没有悬念直接用 DFA。即使你最后想偷懒用正则库也至少要把状态转换图先画出来报告的方案设计部分才站得住。下面这份表是我常用的对比口径。方案优点缺点适用场景直接调正则库代码量小匹配写法直观容易被判定不符合实验要求回退与错误定位难控制自测辅助脚本不上交flex 自动生成支持复杂正则生成代码稳定输出代码可读性差报告里讲不清状态转换实验允许且要求生成代码手写 DFA 扫描器结构透明错误定位准确最容易讲设计首次编写稍慢运算符一多要细心维护课程实验主流做法2.2 最小可运行的词法分析器完整代码与参数说明下面这份代码不依赖任何第三方库用 Python 写核心逻辑是“一个 while 扫描 多字符优先匹配”。如果你交的是 java编译原理方向的实验把 dict 换成 HashMap、把 list 换成 ArrayList 就行结构完全不用变。# lexer.py不依赖正则库的最小词法分析器 # 支持关键字 int void if else while return # 支持运算符 - * / ! ; , ( ) { } KEYWORDS {int, void, if, else, while, return} # 运算符统一放在一张表里保证“取两个字符”和“取一个字符”走同一套逻辑 OPS { : PLUS, -: MINUS, *: STAR, /: SLASH, : LT, : LE, : GT, : GE, : EQ, !: NE, : ASSIGN, ;: SEMI, ,: COMMA, (: LPAREN, ): RPAREN, {: LBRACE, }: RBRACE, } class Token: __slots__ (kind, text, line) def __init__(self, kind, text, line): self.kind kind self.text text self.line line def __repr__(self): return f{self.kind}({self.text!r}){self.line} def tokenize(src): tokens [] i, n, line 0, len(src), 1 while i n: c src[i] if c in \t\r: i 1 continue if c \n: line 1 i 1 continue # 注释 // 优先处理遇到注释直接跳到行尾避免把注释里的运算符当代码 if c / and i 1 n and src[i 1] /: while i n and src[i] ! \n: i 1 continue # 标识符和关键字统一按标识符拼出来再查关键字表 if c.isalpha() or c _: start i while i n and (src[i].isalnum() or src[i] _): i 1 text src[start:i] kind KEYWORD if text in KEYWORDS else ID tokens.append(Token(kind, text, line)) continue # 整数字面量 if c.isdigit(): start i while i n and src[i].isdigit(): i 1 # 数字后面紧跟字母属于非法标识符形式这里直接暴露问题 if i n and (src[i].isalpha() or src[i] _): raise SyntaxError(fline {line}: invalid number {src[start:i]}{src[i]}) tokens.append(Token(INT, src[start:i], line)) continue # 运算符匹配先试两个字符再退回单字符 two src[i:i 2] if two in OPS: tokens.append(Token(OPS[two], two, line)) i 2 continue if c in OPS: tokens.append(Token(OPS[c], c, line)) i 1 continue raise SyntaxError(fline {line}: unexpected char {c!r}) tokens.append(Token(EOF, , line)) return tokens if __name__ __main__: import sys source open(sys.argv[1], encodingutf-8).read() for tok in tokenize(source): print(tok)这段代码的关键点有两个。第一个是运算符匹配顺序必须先查src[i:i2]再查单字符因为、这类两字符运算符优先级更高如果反了a b会被拆成a b语法分析器直接拒绝。第二个是换行计数\n分支里必须先line 1再i 1顺序不能反否则所有报错行号都会偏小。数字后面跟字母我直接抛了异常这是刻意为之宁可在这里报错也不能让123abc被静默切分成两个 token否则语法阶段会给出很误导的错误。2.3 标识符与关键字先拼完整词再查表关键字和标识符的区分是词法分析最容易写错的地方。新手常犯的错误是先对第一个字符判断它是不是关键字比如看到i就以为一定是if结果把合法的变量名intx给拆了。正确做法是不管是什么词先按“字母或下划线开头后续允许字母数字下划线”的规则拼出完整词再去查 KEYWORDS 集合。这样if和iffy自然落进不同的桶不需要额外处理。这套方案里还存在一个优先级问题注释//必须在运算符判断之前处理。如果你把//放进运算符表就会先把/匹配成 SLASH再把第二个/匹配成另一个 SLASH注释内容从此全部被当成源码。所以我单开了一个分支跳到行尾。同理字符串字面量如果实验支持也要放在运算符之前不做字符串的话遇到直接报错比假装支持更稳。3. 语法分析递归下降法如何接手 token 流词法分析把字符流变成 token 流之后语法分析器要做的事情就是按照文法规则逐步匹配 token。这个实验里最稳妥、最容易在报告里讲清楚的方法是递归下降它本质上是把文法的每个非终结符写成一个函数函数之间互相调用。下面先解决文法改写的问题再给一份和上一章 lexer 配套的 parser 代码。3.1 文法改写左递归为什么会让递归下降死循环递归下降要求文法不能有左递归否则函数会无限调用。典型例子是表达式文法E - E T | T如果直接照抄成parse_E()函数函数第一行就调用自己永远走不到第二个分支。标准做法是把左递归改写成右递归E - T E E - T E | ε这样parse_E先调parse_T再调parse_E而parse_E只有在看到的时候才继续递归不会空转。课程实验里真正需要这种改写的通常只有表达式部分语句级文法像if、while、赋值大多天然就是 LL(1) 结构。如果你在报告里能写清楚“左递归会导致递归下降栈溢出或死循环因此改写成右递归”这一节的设计分基本就稳了。提取公因子也是个常见操作。比如if (E) S和if (E) S else S两个产生式共享前缀if (E) S直接写两个分支会让 parser 不知道选哪个。解决方法是先匹配公共前缀再看后面是不是else决定走哪个分支。代码里我会用peek().text else做这个二选一这就是提取公因子后的结果。3.2 递归下降语法分析器完整代码与运行方式下面这份 parser 完整接住上一章的 token 流解析一个迷你语言的函数定义、语句、赋值和表达式。每个函数对应一个非终结符我用缩进把推导过程打印出来方便实验报告里直接贴输出。# parser.py递归下降语法分析器输入为 lexer.tokenize 产生的 token 流 from lexer import tokenize, Token class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.depth 0 def peek(self): if self.pos len(self.tokens): return Token(EOF, , -1) return self.tokens[self.pos] def advance(self): tok self.peek() self.pos 1 return tok def expect(self, kind): tok self.peek() if tok.kind ! kind: raise SyntaxError(fline {tok.line}: expect {kind}, got {tok.kind}({tok.text})) return self.advance() def expect_text(self, text): tok self.peek() if tok.text ! text: raise SyntaxError(fline {tok.line}: expect {text}, got {tok.text}) return self.advance() def show(self, tag, text): print( * self.depth tag ( text if text else )) # program - function* def parse_program(self): while self.peek().kind ! EOF: self.parse_function() # function - type ID ( ) block def parse_function(self): self.show(FUNCTION) self.depth 1 self.expect(KEYWORD) # int 或 void self.expect(ID) self.expect(LPAREN) self.expect(RPAREN) self.parse_block() self.depth - 1 # block - { statement* } def parse_block(self): self.show(BLOCK) self.depth 1 self.expect(LBRACE) while self.peek().text ! }: if self.peek().kind EOF: raise SyntaxError(unclosed block) self.parse_statement() self.expect(RBRACE) self.depth - 1 # statement 的分发逻辑 def parse_statement(self): tok self.peek() if tok.kind KEYWORD and tok.text in (int, void): self.parse_decl() elif tok.text if: self.parse_if() elif tok.text while: self.parse_while() elif tok.text return: self.parse_return() elif tok.kind ID: self.parse_assign() else: raise SyntaxError(fline {tok.line}: unexpected statement start {tok.text}) def parse_decl(self): self.show(DECL) self.depth 1 self.advance() # 类型 self.expect(ID) # 变量名 if self.peek().text : self.advance() self.parse_expr() self.expect(SEMI) self.depth - 1 def parse_if(self): self.show(IF) self.depth 1 self.advance() self.expect(LPAREN) self.parse_expr() self.expect(RPAREN) self.parse_statement() if self.peek().text else: self.advance() self.parse_statement() self.depth - 1 def parse_while(self): self.show(WHILE) self.depth 1 self.advance() self.expect(LPAREN) self.parse_expr() self.expect(RPAREN) self.parse_statement() self.depth - 1 def parse_return(self): self.show(RETURN) self.depth 1 self.advance() self.parse_expr() self.expect(SEMI) self.depth - 1 def parse_assign(self): self.show(ASSIGN) self.depth 1 self.advance() # ID self.expect(ASSIGN) # 一定不能是 self.parse_expr() self.expect(SEMI) self.depth - 1 # 表达式入口按优先级分成三层 def parse_expr(self): self.parse_additive() def parse_additive(self): self.parse_mul() while self.peek().text in (, -): self.show(OP, self.peek().text) self.advance() self.parse_mul() def parse_mul(self): self.parse_primary() while self.peek().text in (*, /): self.show(OP, self.peek().text) self.advance() self.parse_primary() def parse_primary(self): tok self.peek() if tok.kind INT: self.show(INT, tok.text) self.advance() elif tok.kind ID: self.show(ID, tok.text) self.advance() elif tok.text (: self.advance() self.parse_expr() self.expect(RPAREN) else: raise SyntaxError(fline {tok.line}: unexpected expression token {tok.text}) if __name__ __main__: import sys source open(sys.argv[1], encodingutf-8).read() tokens tokenize(source) Parser(tokens).parse_program()运行方式很简单python3 lexer.py test.c python3 parser.py test.cparser 的每个parse_xxx函数就是文法里的一个非终结符expect负责消费指定类型的 tokenpeek只往前看一个 token 不消费。parse_if里明显体现了提取公因子的结果先匹配if (expr)再匹配语句最后用peek().text else判断是不是要走 else 分支。参数层面你只需要维护 KEYWORDS 集合和 OPS 表文法扩展语句时加一个新分支函数即可。3.3 表达式优先级函数的嵌套深度就是优先级如果把表达式直接写成parse_expr一个函数那2 3 * 4会被算成(2 3) * 4这在语法层面就错了。解决手段就是分层递归加法层调用乘法层乘法层调用基本单元层。优先级越高函数调用的层次越深所以*会被更早匹配也就更靠近操作数。expr - additive additive - mul (( | -) mul)* mul - primary ((* | /) primary)* primary - INT | ID | ( expr )这套结构还有一个额外好处想加一元负号只需要在 primary 里加- primary分支想加取模%只需要在 mul 里加一个 token 判断。报告里你甚至可以放一张“层数和优先级对照表”说明每一层对应哪一级运算符老师一眼就能看出你理解了运算符优先级的本质。4. 词法与语法联调避坑输入缓冲、回退和错误行号词法分析单独跑没问题语法分析单独跑也没问题一联调就翻车这是这条实验线路上最常见的现象。下面五个坑是我自己踩过、也看身边人反复踩过的每一条都按“现象、原因、解决”给清楚。4.1 多字符运算符被拆成两个 token现象a b被识别成ID(a) GT() ASSIGN() ID(b)语法分析器直接报错但词法单测是过的。原因词法扫描只看了当前字符发现在运算符表里就直接返回完全没有看下一个字符是不是。解决在取 token 前先检查src[i:i2]是否在两字符运算符表里命中则整体消费两个字符。这就是 2.2 代码里two src[i:i 2]那两行的作用。实验里最容易漏的是、、、!这四个其中漏!的隐蔽性最强因为单字符!往往不在你的运算符表里结果是直接报“unexpected char”反而比拆成! 更容易发现。4.2 数字后面跟字母导致静默切分现象输入int 123abc;词法分析器输出KEYWORD(int)、INT(123)、ID(abc)语法分析器居然通过了程序行为完全错误。原因数字循环只认数字字符循环结束就提交 token没有检查下一个字符是不是字母或下划线。解决在数字循环结束后补一个判断如果下一个字符是字母或下划线就抛异常把问题暴露在词法阶段。这也是 2.2 代码里特意加那个if的原因。很多人觉得这是罕见输入可以不管但实验报告的负数测试用例里一旦出现老师就会认为边界意识不够。4.3 语法分析死循环错误 token 没有被消费现象输入if (a { }parser 卡住不退出或者无限打印同一个错误。原因某个 parse 函数在匹配失败时没有调用advance()self.pos永远停在同一个位置外层 while 循环判断条件不变于是反复进入同一分支。解决在每个parse_xxx里保证“要么抛异常要么至少消费一个 token”。调试时可以临时在 parser 的__init__里加一个self.step 0每次advance()后递增超过 10000 就抛异常用这种保险绳定位是哪个分支在空转。我实际见过最多的死循环在parse_blockwhile self.peek().text ! }这个条件一旦 token 流里根本没有}指针走到 EOF 也不满足终止条件就会死循环。所以代码里我加了 EOF 检查这一行就是血泪经验换来的。4.4 报错行号永远差一行现象明明在文件第 10 行写错了报错却指向第 9 行。原因词法扫描器在遇到\n时先i 1再line 1或者干脆跳过换行忘了计数。由于代码里多个分支共享i 1新人在重构时很容易把line 1一起删掉。解决换行分支单独写顺序固定为“先 line 1 再 i 1”。验证方法也简单写一个每行只有一个小 token 的文件比如一行一个数字词法输出如果行号序列是 1,2,3,4 就正确如果中间断了说明某个空白字符分支吃掉了换行。4.5 注释里的运算符被当成代码处理现象输入// a b词法分析器在//处没有跳行而是把识别成了 GE 运算符。原因注释判断写在了运算符分支之后扫描器先看到/匹配成了 SLASH完全没有机会进入注释逻辑。解决注释跳过、空白跳过、换行计数这三类“不可见 token”处理必须放在所有有效 token 识别之前优先级最高。另一个常见版本是/* */块注释跨越换行时要在注释内部也做行号计数否则行号会再次失准。课程实验通常只要求//但报告里如果能主动说明“我把注释优先级提到最高并维护了行号”是一个很便宜的加分点。5. 实验报告评分点与容易漏掉的证据代码能跑只是实验的一半另一半是报告。编译原理实验报告不是代码贴图集老师要看的是你“为什么这样设计”和“怎么证明它是对的”。下面按我写课程报告的习惯拆开讲照着这个骨架写基本不会漏评分点。5.1 报告骨架先给表格再给代码一份能拿高分的报告结构上通常是这样需求描述、总体设计、详细设计、测试与结果、问题与反思。需求描述要写清楚你实现了语言子集的哪些部分比如“支持 int/void 函数定义、if/while/return、四则运算与关系比较”这样老师不用读代码就知道覆盖范围。总体设计放一张模块图不必画得多精致但要明确词法分析器和语法分析器的数据流方向字符流进词法、token 流进语法、推导或语法树出结果。详细设计里最忌讳整段贴源码应该贴关键数据结构比如 token 表、文法规则表、运算符优先级表。你贴一棵 200 行的函数树不如一张 token 类型表值钱。5.2 三个决定印象分的细节第一个细节是 token 表完整列出来。词的种类、示例、正则形式三列一张表就能看出你对词法单元有没有完整认识。第二个细节是错误处理单独写一节。哪怕只实现了最简单的“遇错即停”也要写清楚错误信息里包含了行号和期望 token 类型这比任何设计图都能体现工程感。第三个细节是运行截图不要只截成功案例。至少一张正常输出、一张错误输出附上命令行输入错误输出的信息越具体越好。很多人只截一段结果老师根本看不出输入是什么等于没截图。5.3 测试结果用测试矩阵不要用聊天式描述我建议测试部分放一张矩阵表横轴是测试用例编号纵轴是检查点。例如用例输入片段期望行为实际行为备注01int main() { return 0; }正常解析一致基础流程02a 1 2 * 3;乘法优先一致运算符优先级03a b;EQ 而非两个 ASSIGN一致多字符运算符04if (a) { } else { }两个分支均识别一致else 可选性05int 123abc;词法报错一致非法标识符06while ( { }语法报错行号一致错误定位注意“备注”这一列要写清测的是哪个设计点而不是写“跑通了”。老师看测试矩阵第一眼是看覆盖第二眼是看有没有针对自己的薄弱点设计用例。能把错误路径的用例放在前面说明你对“程序是会出错的”这件事有充分认知。5.4 反思部分避免空话“通过本次实验我深入理解了编译原理”这句话等于没写。合格的反思要能看出设计假设与实际结果之间的碰撞。我习惯用三个问题驱动第一我最初的设计和最终实现差在哪里第二哪个 bug 花的时间最长根因是什么第三如果再给我一周我会加什么功能。比如你可以写“最初把运算符匹配放在注释处理之前导致 // 后内容全部被解析为代码后来把注释优先级提到最高这让我意识到词法扫描的分支顺序也是一种设计”。这种具体的错误记录比任何总结都有说服力而且老师明显能看出来是不是自己做的。6. 验证与进阶答辩前靠这三招把实验从能跑做到能讲6.1 构造一个自动回归验证脚本实验临近答辩时最怕改一处运算符、坏一片功能。我习惯把测试用例放进tests/目录用一段 shell 批量跑比对实际输出和期望文件# run_tests.sh对每个 .c 样例执行 parser并与 .out 期望文件比对 for f in tests/*.c; do base${f%.c} python3 parser.py $f ${base}.result if diff -u ${base}.out ${base}.result /dev/null; then echo PASS $f else echo FAIL $f fi donetests目录里每个样例配套一个.out期望文件改动代码后跑一遍失败的用例立刻暴露。这比答辩现场手敲输入要稳得多也方便老师看你准备了多完备的验证。我的习惯是每次修复一个 bug就把它对应的错误输入保存成新用例这样同一个坑不会再踩第二次测试样例就是你的后悔药。6.2 panic mode 错误恢复一个低成本加分项如果只想加一个功能来拉开差距我推荐做 panic mode 错误恢复。思路是给语法分析器定义一组同步 token出错后不断丢 token直到遇到同步点再继续解析而不是直接终止。常见同步点包括分号、右花括号和 EOF。def synchronize(self): while self.pos len(self.tokens): tok self.peek() if tok.text in (;, }, EOF): return self.advance()把这个方法插到parse_statement的异常处理里一条语句出错后还能继续解析下一条错误报告也能一次给出多个问题。报告里只要写明“我设置了分号和右花括号作为同步 tokenpanic mode 恢复后从下一条语句继续”这就从基础正确性迈向了容错性很多实验的评分表里会有这一步的加分项。我这么多年的习惯是先保证错误定位准再做错误恢复顺序反了会连正确的报错都搞丢。希望这段思路能帮你在同样的实验里少绕几个弯。本文还有配套的精品资源点击获取
