简介这份资源是北京交通大学2021—2022学年第二学期《编译原理》期末试卷A卷的PDF文档面向正在备考该课程的高校学生与需要复习编译核心知识的自学者。试卷覆盖文法分析、正则表达式与有限自动机、消除左递归与回溯、算符优先文法、LR(0)与SLR(1)分析、语法制导翻译及四元式序列优化等模块题型从简答到综合计算层层递进适合用于考前自测与知识点查漏补缺。资源包共1个PDF文件大小约396KB轻量易存便于打印或移动端随时翻阅。目前已有355人浏览学习说明其在校内复习场景中具有一定参考价值。通过逐题演练读者可系统梳理上下文无关文法推导、FIRSTVT/LASTVT集合求解、活前缀与可归前缀判定、拉链回填及DAG重构等关键方法为编译器设计与系统级编程打下扎实基础。1. 一份期末试卷为什么值得当成编译原理的“逆向工程样本”如果你正在准备《编译原理》期末或者刚学完词法分析、语法分析、语义分析却总觉得知识点是散的这份“北京交通大学2021-2022(2)《编译原理》期末试卷(A)-0620.pdf”其实是一个被低估的复习入口。它不只是一套题而是一份把整门课压缩成若干道大题的“知识地图”。很多人复习时习惯从头翻教材结果时间花在已经会的地方真正的薄弱点反而没暴露。试卷的价值在于它用有限题量逼你面对最核心的几类问题——正则表达式到NFA再到DFA的转换、LL(1)和LR分析表的构造、语法制导翻译、运行时存储分配。这些恰好也是编译原理实验里最容易翻车的地方。适合谁适合已经学过一遍、想用最短时间定位漏洞的本科生也适合想用Java或Python手写小型编译器来巩固理论的开发者。接下来我不谈空泛的复习方法而是把这份试卷拆成可复现的技术动作从题型反推考点从考点反推你必须会写的代码和必须会填的表。2. 从试卷题型反推词法、语法、语义到底考什么2.1 词法分析题正则表达式到DFA的手工推导链试卷里词法分析通常不会只让你写一个正则表达式就结束而是给出一段语言描述要求你写出正则式、构造NFA、确定化得到DFA、最后最小化。这条链每一步都有固定套路但手工推导时最容易在子集构造法里漏状态。我一般会先写正则式再用Thompson算法构造NFA然后画状态转移表做子集构造。下面用Python演示一个最小化的DFA模拟帮你验证手工结果。# DFA模拟器验证你手工构造的DFA是否接受给定字符串 # 状态转移表用字典表示transitions[state][symbol] next_state def dfa_accepts(s, transitions, start, accepts): state start for ch in s: if ch not in transitions.get(state, {}): return False state transitions[state][ch] return state in accepts # 示例识别以ab结尾的字符串a,b字母表 transitions { 0: {a: 1, b: 0}, 1: {a: 1, b: 2}, 2: {a: 1, b: 0} } print(dfa_accepts(aab, transitions, 0, {2})) # True print(dfa_accepts(aba, transitions, 0, {2})) # False这段代码的关键参数是transitions它对应你手画的DFA状态图。start是初态accepts是终态集合。逻辑说明每读一个字符就查表跳转如果某个状态没有对应字符的转移就拒绝。参数怎么改如果你的字母表包含数字就在每个状态的字典里加数字键。失败时看什么如果模拟结果和手工推导不一致先检查子集构造时是否漏了空集状态再检查最小化时是否把可区分状态合并了。常见误用是直接把NFA当DFA用导致一个状态对同一字符有多个转移模拟器会静默取最后一个结果全错。2.2 语法分析题LL(1)分析表的构造与冲突排查LL(1)是试卷里出现频率最高的语法分析考点。题目通常给一个文法要求判断是否为LL(1)求FIRST集、FOLLOW集构造预测分析表。很多人在求FOLLOW集时忘记处理ε产生式导致表里出现多重入口。我一般会按三步走先消除左递归和提取左公因子再求FIRST和FOLLOW最后填表。下面用Python计算FIRST和FOLLOW你可以直接套用。# 计算FIRST和FOLLOW集文法用产生式列表表示 # 非终结符用大写字母终结符用小写字母ε用eps表示 grammar { E: [[T, E]], E: [[, T, E], [eps]], T: [[F, T]], T: [[*, F, T], [eps]], F: [[(, E, )], [id]] } nonterms set(grammar.keys()) terms set() for prods in grammar.values(): for p in prods: for s in p: if s not in nonterms and s ! eps: terms.add(s) FIRST {nt: set() for nt in nonterms} FOLLOW {nt: set() for nt in nonterms} FOLLOW[E] {$} def first_of_seq(seq): result set() for s in seq: if s in terms: result.add(s) return result result | (FIRST[s] - {eps}) if eps not in FIRST[s]: return result result.add(eps) return result changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: f first_of_seq(p) if not f FIRST[nt]: FIRST[nt] | f changed True changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: for i, s in enumerate(p): if s in nonterms: rest p[i1:] f first_of_seq(rest) if rest else {eps} add f - {eps} if eps in f: add | FOLLOW[nt] if not add FOLLOW[s]: FOLLOW[s] | add changed True print(FIRST:, {k: sorted(v) for k, v in FIRST.items()}) print(FOLLOW:, {k: sorted(v) for k, v in FOLLOW.items()})逻辑说明第一段循环不断合并每个产生式右部的FIRST集直到不再变化。第二段处理FOLLOW对于产生式A→αBβ把FIRST(β)-{ε}加入FOLLOW(B)如果β能推出ε把FOLLOW(A)也加入FOLLOW(B)。参数怎么改如果你的文法有多个字符的非终结符把nonterms改成从产生式左部自动提取即可。失败时看什么如果FOLLOW集为空检查是否忘了把开始符号的FOLLOW设为$。常见坑是ε产生式处理不干净导致FIRST集里混入ε但FOLLOW没跟上。2.3 语义分析与中间代码语法制导翻译的落地写法试卷里语义分析通常结合语法制导定义要求写出翻译方案或画出注释分析树。常见题型是给表达式文法配语义动作生成三地址码。我一般用递归下降的框架来模拟每个非终结符对应一个函数返回值携带综合属性。下面用Python演示如何把算术表达式翻译成三地址码。# 语法制导翻译表达式到三地址码 # 文法E - E T | T; T - T * F | F; F - (E) | id temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def parse_E(tokens, pos): # 简化版只处理左结合加法和乘法返回(代码列表, 结果地址, 新位置) code, addr, pos parse_T(tokens, pos) while pos len(tokens) and tokens[pos] : pos 1 code2, addr2, pos parse_T(tokens, pos) t new_temp() code code2 [f{t} {addr} {addr2}] addr t return code, addr, pos def parse_T(tokens, pos): code, addr, pos parse_F(tokens, pos) while pos len(tokens) and tokens[pos] *: pos 1 code2, addr2, pos parse_F(tokens, pos) t new_temp() code code2 [f{t} {addr} * {addr2}] addr t return code, addr, pos def parse_F(tokens, pos): if tokens[pos] (: pos 1 code, addr, pos parse_E(tokens, pos) assert tokens[pos] ) return code, addr, pos 1 else: return [], tokens[pos], pos 1 tokens [id, , id, *, id] code, addr, _ parse_E(tokens, 0) for line in code: print(line) print(结果地址:, addr)逻辑说明每个非终结符函数返回三样东西——已生成的代码列表、当前结果存放的地址、下一个待读token位置。new_temp()生成临时变量名。参数怎么改如果要支持减法和除法在parse_E和parse_T的while条件里加对应符号并修改生成的指令。失败时看什么如果临时变量编号混乱检查temp_count是否被重复初始化。常见坑是左递归未消除就直接写递归下降导致无限递归——试卷里如果要求写递归下降必须先消除左递归。3. 把试卷当项目做用Java或Python复现一个最小编译器3.1 实验环境与工具链选择为什么我不建议一上来就写完整编译器编译原理实验最常见的翻车方式是试图从零写一个能编译完整语言的编译器。试卷里的题目都是片段化的但实验往往要求端到端跑通。我的建议是先选一个极小子集比如只支持整数四则运算和变量赋值用Java或Python实现词法、语法、语义三个阶段。工具链上Java可以用JFlex和CUPPython可以用PLY或手写递归下降。但试卷考的是手工推导能力所以实验里我一般手写词法分析器和递归下降分析器不依赖生成器这样能真正理解每个状态转移。环境准备很简单Java 8以上或Python 3.8以上一个文本编辑器即可。不需要复杂IDE因为你要看清每个字符的处理过程。3.2 手写词法分析器从正则到Token流的完整代码下面是一个支持整数、标识符、运算符和括号的词法分析器用Python实现。它对应试卷里词法分析题的手工推导结果。# 手写词法分析器输入源字符串输出Token列表 import re token_spec [ (NUMBER, r\d), (ID, r[a-zA-Z_]\w*), (ASSIGN, r), (PLUS, r\), (MINUS, r-), (TIMES, r\*), (DIV, r/), (LPAREN, r\(), (RPAREN, r\)), (SEMI, r;), (SKIP, r[ \t\n]), (MISMATCH, r.) ] def tokenize(code): tokens [] tok_regex |.join(f(?P{name}{pattern}) for name, pattern in token_spec) for mo in re.finditer(tok_regex, code): kind mo.lastgroup value mo.group() if kind SKIP: continue elif kind MISMATCH: raise RuntimeError(f非法字符: {value}) elif kind NUMBER: value int(value) tokens.append((kind, value)) return tokens source x 3 4 * (y - 1); for tok in tokenize(source): print(tok)逻辑说明token_spec按优先级排列re.finditer从左到右扫描每个匹配对应一个Token。SKIP跳过空白MISMATCH捕获非法字符。参数怎么改如果要支持浮点数把NUMBER的正则改成\d(\.\d)?并在转换时用float。失败时看什么如果报非法字符检查源串里是否有未定义的符号。常见坑是正则顺序放错比如把ID放在NUMBER前面导致数字被识别成标识符。3.3 递归下降语法分析把试卷里的LL(1)表变成可执行代码试卷里构造的LL(1)分析表在实验里可以直接转成递归下降函数。下面接着上面的Token流实现一个简单的赋值语句和表达式分析器。# 递归下降语法分析器消费Token列表生成三地址码 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.temp_count 0 self.code [] def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (None, None) def match(self, kind): tok self.peek() if tok[0] kind: self.pos 1 return tok raise RuntimeError(f期望 {kind}实际 {tok}) def new_temp(self): self.temp_count 1 return ft{self.temp_count} def parse(self): while self.pos len(self.tokens): self.statement() return self.code def statement(self): name self.match(ID)[1] self.match(ASSIGN) addr self.expr() self.match(SEMI) self.code.append(f{name} {addr}) def expr(self): addr self.term() while self.peek()[0] in (PLUS, MINUS): op self.match(self.peek()[0])[0] addr2 self.term() t self.new_temp() self.code.append(f{t} {addr} { if op PLUS else -} {addr2}) addr t return addr def term(self): addr self.factor() while self.peek()[0] in (TIMES, DIV): op self.match(self.peek()[0])[0] addr2 self.factor() t self.new_temp() self.code.append(f{t} {addr} {* if op TIMES else /} {addr2}) addr t return addr def factor(self): tok self.peek() if tok[0] NUMBER: self.pos 1 return str(tok[1]) elif tok[0] LPAREN: self.match(LPAREN) addr self.expr() self.match(RPAREN) return addr elif tok[0] ID: self.pos 1 return tok[1] raise RuntimeError(f意外的Token: {tok}) tokens tokenize(x 3 4 * (y - 1);) parser Parser(tokens) for line in parser.parse(): print(line)逻辑说明Parser类维护Token列表和当前位置。statement处理赋值语句expr处理加减term处理乘除factor处理数字、括号和标识符。每个函数返回结果地址并生成三地址码。参数怎么改如果要支持更多语句类型在parse里根据peek的Token类型分派。失败时看什么如果报“期望SEMI”检查源串末尾是否漏了分号。常见坑是peek在越界时返回(None, None)导致match报错信息不明确建议在match里加位置信息。4. 避坑与排查期末复习和实验里最容易翻车的5件事4.1 现象子集构造法得到的DFA状态数比答案多原因在计算ε闭包时只对单个状态求闭包没有对状态集合求闭包。解决子集构造的每一步先对当前状态集合求ε闭包再对每个输入符号求转移后的集合再求一次ε闭包。手工推导时用表格逐列填写每列写清楚闭包结果。4.2 现象LL(1)分析表出现多重入口但文法看起来没有左递归原因提取左公因子不彻底或者FOLLOW集计算时遗漏了ε产生式。解决先检查所有产生式右部是否有公共前缀如果有就提取。再检查每个非终结符的FOLLOW集是否包含了所有该出现的位置。可以用第2.2节的Python脚本验证。4.3 现象递归下降分析器遇到左递归文法直接栈溢出原因递归下降不能处理左递归必须改写为右递归或迭代。解决对于E→ET|T改写成E→T EE→T E|ε。试卷里如果要求写递归下降先做这一步改写。4.4 现象语法制导翻译生成的临时变量名重复原因临时变量计数器在递归调用中被局部变量覆盖或者多个函数各自维护计数器。解决把计数器放在全局或类属性里确保所有生成临时变量的地方共用同一个计数器。第3.3节的Parser类用self.temp_count就是正确做法。4.5 现象实验里词法分析器把关键字识别成标识符原因关键字和标识符的正则模式相同但关键字优先级更高。解决在词法分析器里先匹配关键字表如果匹配到关键字就返回关键字Token否则再按标识符处理。常见做法是在token_spec里把关键字放在ID前面或者单独维护一个关键字集合。5. 用试卷反推复习优先级一个可复用的自测脚本最后一章我想给你一个具体技巧把试卷里的每道题映射到一个可执行的自测脚本用代码验证你的手工答案。比如词法分析题你可以把手工构造的DFA输入到第2.1节的模拟器用试卷里可能出现的字符串测试。语法分析题把FIRST和FOLLOW集输入到第2.2节的脚本对比输出。语义分析题把翻译方案写成第3.3节的递归下降函数看生成的三地址码是否和手工推导一致。这个自测脚本不需要多复杂关键是形成“手工推导→代码验证→修正”的闭环。我一般会建一个exam_check.py把每道题的验证函数放进去复习时跑一遍哪个函数报错就重点看哪个知识点。参数上你只需要把试卷里的文法、正则、输入串替换成实际题目内容。失败时看什么如果脚本输出和手工答案不一致先检查脚本里的文法是否抄错再检查手工推导的每一步。这个习惯帮我省了很多后悔药——考试时最怕的不是不会而是以为自己会了。希望帮到你。本文还有配套的精品资源点击获取 编译原理期末试卷逆向工程：从DFA到递归下降的实战复习指南
简介这份资源是北京交通大学2021—2022学年第二学期《编译原理》期末试卷A卷的PDF文档面向正在备考该课程的高校学生与需要复习编译核心知识的自学者。试卷覆盖文法分析、正则表达式与有限自动机、消除左递归与回溯、算符优先文法、LR(0)与SLR(1)分析、语法制导翻译及四元式序列优化等模块题型从简答到综合计算层层递进适合用于考前自测与知识点查漏补缺。资源包共1个PDF文件大小约396KB轻量易存便于打印或移动端随时翻阅。目前已有355人浏览学习说明其在校内复习场景中具有一定参考价值。通过逐题演练读者可系统梳理上下文无关文法推导、FIRSTVT/LASTVT集合求解、活前缀与可归前缀判定、拉链回填及DAG重构等关键方法为编译器设计与系统级编程打下扎实基础。1. 一份期末试卷为什么值得当成编译原理的“逆向工程样本”如果你正在准备《编译原理》期末或者刚学完词法分析、语法分析、语义分析却总觉得知识点是散的这份“北京交通大学2021-2022(2)《编译原理》期末试卷(A)-0620.pdf”其实是一个被低估的复习入口。它不只是一套题而是一份把整门课压缩成若干道大题的“知识地图”。很多人复习时习惯从头翻教材结果时间花在已经会的地方真正的薄弱点反而没暴露。试卷的价值在于它用有限题量逼你面对最核心的几类问题——正则表达式到NFA再到DFA的转换、LL(1)和LR分析表的构造、语法制导翻译、运行时存储分配。这些恰好也是编译原理实验里最容易翻车的地方。适合谁适合已经学过一遍、想用最短时间定位漏洞的本科生也适合想用Java或Python手写小型编译器来巩固理论的开发者。接下来我不谈空泛的复习方法而是把这份试卷拆成可复现的技术动作从题型反推考点从考点反推你必须会写的代码和必须会填的表。2. 从试卷题型反推词法、语法、语义到底考什么2.1 词法分析题正则表达式到DFA的手工推导链试卷里词法分析通常不会只让你写一个正则表达式就结束而是给出一段语言描述要求你写出正则式、构造NFA、确定化得到DFA、最后最小化。这条链每一步都有固定套路但手工推导时最容易在子集构造法里漏状态。我一般会先写正则式再用Thompson算法构造NFA然后画状态转移表做子集构造。下面用Python演示一个最小化的DFA模拟帮你验证手工结果。# DFA模拟器验证你手工构造的DFA是否接受给定字符串 # 状态转移表用字典表示transitions[state][symbol] next_state def dfa_accepts(s, transitions, start, accepts): state start for ch in s: if ch not in transitions.get(state, {}): return False state transitions[state][ch] return state in accepts # 示例识别以ab结尾的字符串a,b字母表 transitions { 0: {a: 1, b: 0}, 1: {a: 1, b: 2}, 2: {a: 1, b: 0} } print(dfa_accepts(aab, transitions, 0, {2})) # True print(dfa_accepts(aba, transitions, 0, {2})) # False这段代码的关键参数是transitions它对应你手画的DFA状态图。start是初态accepts是终态集合。逻辑说明每读一个字符就查表跳转如果某个状态没有对应字符的转移就拒绝。参数怎么改如果你的字母表包含数字就在每个状态的字典里加数字键。失败时看什么如果模拟结果和手工推导不一致先检查子集构造时是否漏了空集状态再检查最小化时是否把可区分状态合并了。常见误用是直接把NFA当DFA用导致一个状态对同一字符有多个转移模拟器会静默取最后一个结果全错。2.2 语法分析题LL(1)分析表的构造与冲突排查LL(1)是试卷里出现频率最高的语法分析考点。题目通常给一个文法要求判断是否为LL(1)求FIRST集、FOLLOW集构造预测分析表。很多人在求FOLLOW集时忘记处理ε产生式导致表里出现多重入口。我一般会按三步走先消除左递归和提取左公因子再求FIRST和FOLLOW最后填表。下面用Python计算FIRST和FOLLOW你可以直接套用。# 计算FIRST和FOLLOW集文法用产生式列表表示 # 非终结符用大写字母终结符用小写字母ε用eps表示 grammar { E: [[T, E]], E: [[, T, E], [eps]], T: [[F, T]], T: [[*, F, T], [eps]], F: [[(, E, )], [id]] } nonterms set(grammar.keys()) terms set() for prods in grammar.values(): for p in prods: for s in p: if s not in nonterms and s ! eps: terms.add(s) FIRST {nt: set() for nt in nonterms} FOLLOW {nt: set() for nt in nonterms} FOLLOW[E] {$} def first_of_seq(seq): result set() for s in seq: if s in terms: result.add(s) return result result | (FIRST[s] - {eps}) if eps not in FIRST[s]: return result result.add(eps) return result changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: f first_of_seq(p) if not f FIRST[nt]: FIRST[nt] | f changed True changed True while changed: changed False for nt, prods in grammar.items(): for p in prods: for i, s in enumerate(p): if s in nonterms: rest p[i1:] f first_of_seq(rest) if rest else {eps} add f - {eps} if eps in f: add | FOLLOW[nt] if not add FOLLOW[s]: FOLLOW[s] | add changed True print(FIRST:, {k: sorted(v) for k, v in FIRST.items()}) print(FOLLOW:, {k: sorted(v) for k, v in FOLLOW.items()})逻辑说明第一段循环不断合并每个产生式右部的FIRST集直到不再变化。第二段处理FOLLOW对于产生式A→αBβ把FIRST(β)-{ε}加入FOLLOW(B)如果β能推出ε把FOLLOW(A)也加入FOLLOW(B)。参数怎么改如果你的文法有多个字符的非终结符把nonterms改成从产生式左部自动提取即可。失败时看什么如果FOLLOW集为空检查是否忘了把开始符号的FOLLOW设为$。常见坑是ε产生式处理不干净导致FIRST集里混入ε但FOLLOW没跟上。2.3 语义分析与中间代码语法制导翻译的落地写法试卷里语义分析通常结合语法制导定义要求写出翻译方案或画出注释分析树。常见题型是给表达式文法配语义动作生成三地址码。我一般用递归下降的框架来模拟每个非终结符对应一个函数返回值携带综合属性。下面用Python演示如何把算术表达式翻译成三地址码。# 语法制导翻译表达式到三地址码 # 文法E - E T | T; T - T * F | F; F - (E) | id temp_count 0 def new_temp(): global temp_count temp_count 1 return ft{temp_count} def parse_E(tokens, pos): # 简化版只处理左结合加法和乘法返回(代码列表, 结果地址, 新位置) code, addr, pos parse_T(tokens, pos) while pos len(tokens) and tokens[pos] : pos 1 code2, addr2, pos parse_T(tokens, pos) t new_temp() code code2 [f{t} {addr} {addr2}] addr t return code, addr, pos def parse_T(tokens, pos): code, addr, pos parse_F(tokens, pos) while pos len(tokens) and tokens[pos] *: pos 1 code2, addr2, pos parse_F(tokens, pos) t new_temp() code code2 [f{t} {addr} * {addr2}] addr t return code, addr, pos def parse_F(tokens, pos): if tokens[pos] (: pos 1 code, addr, pos parse_E(tokens, pos) assert tokens[pos] ) return code, addr, pos 1 else: return [], tokens[pos], pos 1 tokens [id, , id, *, id] code, addr, _ parse_E(tokens, 0) for line in code: print(line) print(结果地址:, addr)逻辑说明每个非终结符函数返回三样东西——已生成的代码列表、当前结果存放的地址、下一个待读token位置。new_temp()生成临时变量名。参数怎么改如果要支持减法和除法在parse_E和parse_T的while条件里加对应符号并修改生成的指令。失败时看什么如果临时变量编号混乱检查temp_count是否被重复初始化。常见坑是左递归未消除就直接写递归下降导致无限递归——试卷里如果要求写递归下降必须先消除左递归。3. 把试卷当项目做用Java或Python复现一个最小编译器3.1 实验环境与工具链选择为什么我不建议一上来就写完整编译器编译原理实验最常见的翻车方式是试图从零写一个能编译完整语言的编译器。试卷里的题目都是片段化的但实验往往要求端到端跑通。我的建议是先选一个极小子集比如只支持整数四则运算和变量赋值用Java或Python实现词法、语法、语义三个阶段。工具链上Java可以用JFlex和CUPPython可以用PLY或手写递归下降。但试卷考的是手工推导能力所以实验里我一般手写词法分析器和递归下降分析器不依赖生成器这样能真正理解每个状态转移。环境准备很简单Java 8以上或Python 3.8以上一个文本编辑器即可。不需要复杂IDE因为你要看清每个字符的处理过程。3.2 手写词法分析器从正则到Token流的完整代码下面是一个支持整数、标识符、运算符和括号的词法分析器用Python实现。它对应试卷里词法分析题的手工推导结果。# 手写词法分析器输入源字符串输出Token列表 import re token_spec [ (NUMBER, r\d), (ID, r[a-zA-Z_]\w*), (ASSIGN, r), (PLUS, r\), (MINUS, r-), (TIMES, r\*), (DIV, r/), (LPAREN, r\(), (RPAREN, r\)), (SEMI, r;), (SKIP, r[ \t\n]), (MISMATCH, r.) ] def tokenize(code): tokens [] tok_regex |.join(f(?P{name}{pattern}) for name, pattern in token_spec) for mo in re.finditer(tok_regex, code): kind mo.lastgroup value mo.group() if kind SKIP: continue elif kind MISMATCH: raise RuntimeError(f非法字符: {value}) elif kind NUMBER: value int(value) tokens.append((kind, value)) return tokens source x 3 4 * (y - 1); for tok in tokenize(source): print(tok)逻辑说明token_spec按优先级排列re.finditer从左到右扫描每个匹配对应一个Token。SKIP跳过空白MISMATCH捕获非法字符。参数怎么改如果要支持浮点数把NUMBER的正则改成\d(\.\d)?并在转换时用float。失败时看什么如果报非法字符检查源串里是否有未定义的符号。常见坑是正则顺序放错比如把ID放在NUMBER前面导致数字被识别成标识符。3.3 递归下降语法分析把试卷里的LL(1)表变成可执行代码试卷里构造的LL(1)分析表在实验里可以直接转成递归下降函数。下面接着上面的Token流实现一个简单的赋值语句和表达式分析器。# 递归下降语法分析器消费Token列表生成三地址码 class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.temp_count 0 self.code [] def peek(self): return self.tokens[self.pos] if self.pos len(self.tokens) else (None, None) def match(self, kind): tok self.peek() if tok[0] kind: self.pos 1 return tok raise RuntimeError(f期望 {kind}实际 {tok}) def new_temp(self): self.temp_count 1 return ft{self.temp_count} def parse(self): while self.pos len(self.tokens): self.statement() return self.code def statement(self): name self.match(ID)[1] self.match(ASSIGN) addr self.expr() self.match(SEMI) self.code.append(f{name} {addr}) def expr(self): addr self.term() while self.peek()[0] in (PLUS, MINUS): op self.match(self.peek()[0])[0] addr2 self.term() t self.new_temp() self.code.append(f{t} {addr} { if op PLUS else -} {addr2}) addr t return addr def term(self): addr self.factor() while self.peek()[0] in (TIMES, DIV): op self.match(self.peek()[0])[0] addr2 self.factor() t self.new_temp() self.code.append(f{t} {addr} {* if op TIMES else /} {addr2}) addr t return addr def factor(self): tok self.peek() if tok[0] NUMBER: self.pos 1 return str(tok[1]) elif tok[0] LPAREN: self.match(LPAREN) addr self.expr() self.match(RPAREN) return addr elif tok[0] ID: self.pos 1 return tok[1] raise RuntimeError(f意外的Token: {tok}) tokens tokenize(x 3 4 * (y - 1);) parser Parser(tokens) for line in parser.parse(): print(line)逻辑说明Parser类维护Token列表和当前位置。statement处理赋值语句expr处理加减term处理乘除factor处理数字、括号和标识符。每个函数返回结果地址并生成三地址码。参数怎么改如果要支持更多语句类型在parse里根据peek的Token类型分派。失败时看什么如果报“期望SEMI”检查源串末尾是否漏了分号。常见坑是peek在越界时返回(None, None)导致match报错信息不明确建议在match里加位置信息。4. 避坑与排查期末复习和实验里最容易翻车的5件事4.1 现象子集构造法得到的DFA状态数比答案多原因在计算ε闭包时只对单个状态求闭包没有对状态集合求闭包。解决子集构造的每一步先对当前状态集合求ε闭包再对每个输入符号求转移后的集合再求一次ε闭包。手工推导时用表格逐列填写每列写清楚闭包结果。4.2 现象LL(1)分析表出现多重入口但文法看起来没有左递归原因提取左公因子不彻底或者FOLLOW集计算时遗漏了ε产生式。解决先检查所有产生式右部是否有公共前缀如果有就提取。再检查每个非终结符的FOLLOW集是否包含了所有该出现的位置。可以用第2.2节的Python脚本验证。4.3 现象递归下降分析器遇到左递归文法直接栈溢出原因递归下降不能处理左递归必须改写为右递归或迭代。解决对于E→ET|T改写成E→T EE→T E|ε。试卷里如果要求写递归下降先做这一步改写。4.4 现象语法制导翻译生成的临时变量名重复原因临时变量计数器在递归调用中被局部变量覆盖或者多个函数各自维护计数器。解决把计数器放在全局或类属性里确保所有生成临时变量的地方共用同一个计数器。第3.3节的Parser类用self.temp_count就是正确做法。4.5 现象实验里词法分析器把关键字识别成标识符原因关键字和标识符的正则模式相同但关键字优先级更高。解决在词法分析器里先匹配关键字表如果匹配到关键字就返回关键字Token否则再按标识符处理。常见做法是在token_spec里把关键字放在ID前面或者单独维护一个关键字集合。5. 用试卷反推复习优先级一个可复用的自测脚本最后一章我想给你一个具体技巧把试卷里的每道题映射到一个可执行的自测脚本用代码验证你的手工答案。比如词法分析题你可以把手工构造的DFA输入到第2.1节的模拟器用试卷里可能出现的字符串测试。语法分析题把FIRST和FOLLOW集输入到第2.2节的脚本对比输出。语义分析题把翻译方案写成第3.3节的递归下降函数看生成的三地址码是否和手工推导一致。这个自测脚本不需要多复杂关键是形成“手工推导→代码验证→修正”的闭环。我一般会建一个exam_check.py把每道题的验证函数放进去复习时跑一遍哪个函数报错就重点看哪个知识点。参数上你只需要把试卷里的文法、正则、输入串替换成实际题目内容。失败时看什么如果脚本输出和手工答案不一致先检查脚本里的文法是否抄错再检查手工推导的每一步。这个习惯帮我省了很多后悔药——考试时最怕的不是不会而是以为自己会了。希望帮到你。本文还有配套的精品资源点击获取