拓冰网站定制 、LR(1)选型指南)
简介面向编译原理课程设计与语法分析器开发学习者资源内包含一份用C实现的语法分析器源码覆盖输入扫描、语法树构造与错误处理等关键环节帮助理解从源代码到语法结构的解析过程适用于高校编译原理实验、课设以及collegevm5等课程实践场景。资源为zip压缩包共1个文件核心为cpp源码文件整体仅2KB代码精简便于阅读和二次修改。已有177人学习浏览适合正在实现递归下降、LL或LR分析等任务的读者参考。通过这份代码学习者可以直接查看C如何组织词法扫描、语法判断与错误处理流程对照BNF/EBNF形式文法与解析表构建思路快速把握一个基础语法分析器的骨架。虽然包体很小但作为单一源码示例其逻辑完整可作为课程报告分析对象或扩展开发起点帮助加深对编译原理中语法分析阶段的理解。1. 语法分析器是什么从Token流到语法树的必经关卡做编译原理实验的人十个里有八个卡在语法分析器这一关。词法分析好歹是线性扫描正则表达式一匹配就出Token到了语法分析器面对的是嵌套结构、运算符优先级、左递归这些反直觉的东西代码写着写着就栈溢出了。语法分析器要解决的问题很直接拿到词法分析器吐出来的一串Token按照文法规则判断这段代码是否符合语法并把符合的部分组织成一棵语法树。它上接词法、下接语义分析是编译器里最难糊弄过去的一个模块。适合谁读正在做collegevm5这类编译课程虚拟机实验、需要自己写或借助工具生成语法分析器的同学以及要把表达式解析、配置文件解析做扎实的工程从业者。读完你能确定一件事选择手写递归下降还是用生成器从此不再凭感觉。2. 自顶向下与自底向上LL(1)和LR(1)怎么选才不返工2.1 两种路线的核心差异谁在决定下一步看什么语法分析器分两大流派自顶向下和自底向上。自顶向下从开始符号出发试图推导出整个Token序列自底向上从Token序列出发试图归约回开始符号。教科书上这一句带过但实际写代码时它直接决定了你手里的控制流长什么样也决定了你后面排错看的是调用栈还是状态栈。自顶向下最典型的实现是递归下降分析。思路是给每个非终结符写一个函数函数里看一眼当前Token决定走哪条产生式然后递归调用其他非终结符对应的函数。比如解析表达式进入expr()之后当前Token是数字还是左括号决定了是先走term还是直接进括号分支。这种方式的代码和文法几乎一一对应出错时调试栈就是函数的调用栈哪一步错了一目了然。自底向上的代表是LR分析器。它维护一个状态栈根据当前状态和下一个Token决定移进还是归约。移进是把Token压栈归约是把栈顶若干符号按产生式还原成一个非终结符。LR能处理的文法范围比LL宽几乎所有手写文法都能找到对应的LR(1)形式但状态表动辄几十上百个状态手写等于给自己挖坑通常要靠Yacc/Bison自动生成。这里有一个容易混淆的概念LL里的第一个L表示从左到右扫描输入第二个L表示最左推导LR同理第一个L是扫描方向R是最右推导。考试和面试爱考这个但工程上你只需要记住一个判断标准如果文法改写后每个非终结符的每个分支都能靠当前Token唯一确定就用递归下降如果产生式之间有重叠、靠一个Token分不开要么改文法要么上LR生成器。FIRST集和FOLLOW集是判断能不能靠当前Token唯一确定的工具。FIRST集是一个非终结符能推导出的所有首Token的集合FOLLOW集是所有可能跟在其后的Token的集合。求这两个集合很机械手算几个简单文法就能明白但到了十几个非终结符的文法手算容易漏。在实际项目中我一般会在纸上列出每个非终结符的FIRST集和FOLLOW集或者写个小脚本算一遍作为写递归下降前的体检报告。2.2 文法改造消除左递归与提取左公因子递归下降最怕两类文法问题左递归和左公因子。这两件事不解决代码写出来不是无限递归就是逻辑全错。在大多数教材里比如清华大学出版社第三版的编译原理教材第二章的习题就是围绕FIRST集、FOLLOW集和预测分析表展开的把这部分练透递归下降基本不会出预测冲突。左递归就是产生式左边第一个符号还是自己例如 E - E T。递归下降遇到它expr()会无限调用自己读不到任何Token栈直接爆炸。解决办法是把左递归改写成右递归。经典表达式文法的改造过程是这样的原始文法E - E T | E - T | TT - T * F | T / F | FF - NUMBER | ( E )改造后E - T EE - T E | - T E | εT - F TT - * F T | / F T | εF - NUMBER | ( E )这里ε表示空串也就是E可以什么都不匹配直接结束。这个改造在纸上是一套固定替换规则但在实际手写代码时我更推荐直接用EBNF的循环写法也就是把 E - T ((|-) T)* 这样的形式直接翻译成while循环。它和右递归是等价的但代码可读性好得多学生作业里两种写法都常见我一般建议用循环少一层递归少一次栈压力。左公因子问题出现在同一非终结符的两条产生式开头相同。比如 IF_STMT - if (expr) stmt | if (expr) stmt else stmt两条都以if开头递归下降的决策点在看到if那一刻根本不知道后面跟的是else还是没有。解决办法是延迟决策提取公共前缀IF_STMT - if (expr) stmt TAILTAIL - else stmt | ε。这样先统一进if分支读到else再决定TAIL怎么走。这个延迟决策的思路在更复杂的文法里也适用。判断是否需要提取公因子我有个土办法把每个非终结符所有产生式的首符号列出来但凡有重复的就说明这个地方存在预测冲突先提取再往下写。别等到代码跑挂了再回头改那会儿改的是函数逻辑比改文法难多了。2.3 选型对照手写递归下降还是上生成器选型没有绝对标准我按自己做过的几个项目给一个参考。如果你的目标语言是几十行到几百行的规模语法以表达式和简单语句为主手写递归下降是最快的路径代码量小、报错位置精确、不依赖外部工具链。如果你要解析的是完整的C或Java语法或者语法还在频繁迭代直接用Yacc/Bison或ANTLR省下的时间够你多调试两轮生成器的冲突。生成器也不是零成本。Yacc/Bison意味着你要接受它的冲突报告是英文缩写、语义动作里写$$和$1这套约定、生成的C代码可读性差这些现实。ANTLR则要面对Java运行时依赖和语法文件版本匹配问题。对collegevm5这类课程虚拟机来说老师多半会限定解析范围比如只解析赋值、表达式、if和while。先看懂实验要求是手写parser还是允许工具生成这决定了后面几周的工作量方向。我的建议是实验要求不明确时能手写就手写因为生成器的产物在你的虚拟机里接起来调试成本往往比手写还要高。维度手写递归下降Yacc/Bison/LR文法范围需改造为LL(1)接受LR(1)及部分二义文法代码可控性高报错可精确到函数低纠错逻辑难定制学习成本低递归加匹配高状态机与冲突报告调试方式栈调用即解析路径看状态机文件与冲突位置适用规模小型语言原型中型以上完整语言这张表的结论不是手写优于生成器而是规模决定工具。我见过有人用Bison解析一个只需要支持加减乘除的小语言结果花在配置环境和处理冲突上的时间比手写整个parser还长也见过纯手写去解析类C语法写到两千行之后维护成本爆炸。先量规模再选路线。3. 手写递归下降语法分析器从表达式文法到可运行代码3.1 词法接口与Token流最小约定写语法分析器之前先和词法器把接口谈清楚。我的惯例是词法器暴露一个next_token()方法返回二元组(type, value)type是Token类型value是具体值。语法分析器只依赖type做决策value留到AST构建时用。再往下有一个约定容易被忽略语法分析器需要偷看当前Token做决策但不该消耗它。所以我不把Token流当成队列去pop而是维护一个current指针只有match成功时才移动。这样决策逻辑始终只盯着一个Token不会出现读掉了结果发现不对的尴尬。import re from enum import Enum class TokenType(Enum): NUMBER 1 PLUS 2 MINUS 3 STAR 4 SLASH 5 LPAREN 6 RPAREN 7 END 8 class Token: def __init__(self, type_, value, line, col): self.type type_ self.value value self.line line self.col col def __repr__(self): return f{self.type.name}({self.value}){self.line}:{self.col} def tokenize(text): tokens [] i 0 line, col 1, 1 token_spec [ (TokenType.NUMBER, r\d), (TokenType.PLUS, r\), (TokenType.MINUS, r-), (TokenType.STAR, r\*), (TokenType.SLASH, r/), (TokenType.LPAREN, r\(), (TokenType.RPAREN, r\)), ] while i len(text): if text[i] in \t: i 1 col 1 continue if text[i] \n: line 1 col 1 i 1 continue matched False for ttype, pattern in token_spec: m re.match(pattern, text[i:]) if m: tokens.append(Token(ttype, m.group(), line, col)) col len(m.group()) i len(m.group()) matched True break if not matched: raise SyntaxError(f未知字符 {text[i]!r} at {line}:{col}) tokens.append(Token(TokenType.END, None, line, col)) return tokens逻辑说明tokenize把输入字符串切成一串Token并在末尾追加END标记表示输入耗尽。每个Token记录行号和列号这一步看似多余实际上语法分析器报错时全靠它定位后面避坑章节会专门讲。空白字符被跳过数字用正则\d匹配。参数说明token_spec里正则的顺序有讲究NUMBER在最前面然后是单字符运算符。如果以后要支持标识符、关键字、赋值号往这个列表里追加即可注意长的模式要放在短模式前面比如 必须在 前面否则先匹配到就错了。这个顺序问题是最常见的词法翻车点改之前先想清楚匹配优先级。另外这里为了可读性用了text[i:]切片每次都会新建字符串工程上应该用带pos参数的编译后正则但语义完全一样。3.2 递归下降四件套match、expr、term、factor表达式文法在消除左递归之后用EBNF写就是三行 expr - term (( | -) term)* term - factor (( | /) factor)factor - NUMBER | ( expr )我直接用循环实现因为循环天然处理了右递归展开后的那几层调用省栈空间不说代码还短。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.current tokens[0] def advance(self): if self.pos len(self.tokens) - 1: self.pos 1 self.current self.tokens[self.pos] def match(self, type_): if self.current.type type_: self.advance() else: raise SyntaxError( f期望 {type_.name}实际 {self.current.type.name} fat {self.current.line}:{self.current.col} ) def parse(self): node self.expr() self.match(TokenType.END) return node def expr(self): left self.term() while self.current.type in (TokenType.PLUS, TokenType.MINUS): op self.current.type self.advance() right self.term() left Node(binop, valueop, leftleft, rightright) return left def term(self): left self.factor() while self.current.type in (TokenType.STAR, TokenType.SLASH): op self.current.type self.advance() right self.factor() left Node(binop, valueop, leftleft, rightright) return left def factor(self): t self.current if t.type TokenType.NUMBER: self.advance() return Node(number, valueint(t.value)) if t.type TokenType.LPAREN: self.advance() node self.expr() self.match(TokenType.RPAREN) return node raise SyntaxError(f意外的Token {t.type.name} at {t.line}:{t.col})逻辑说明expr先调用term拿到左操作数再进入while循环。循环里看一下当前Token是加号还是减号是就消耗掉再解析右操作数把左右拼成一个binop节点。注意while条件用元组加in可以同时支持两个运算符比写两个if简洁。term对乘除做同样的事factor处理数字和括号括号内递归调用expr。参数说明这个结构里优先级完全由调用层级体现expr调termterm调factor所以乘除先绑定括号最优先。如果要加入一元负号在factor里新增一个MINUS分支先消耗负号再递归factor而不是在expr里处理否则 -23 会被解析成 -(23)。这个一元运算放因子层的规律在扩展文法时一定要记住放错层优先级就反了。补一个单测习惯写完这个Parser之后第一件事不是跑大用例而是跑边界用例。空输入应该报END期望错误单独一个数字应该能解析成功(12这种缺右括号的输入报错位置应该指向缺失的右括号附近。这三个用例过了parser的骨架才算稳。3.3 建AST而不是只判对错节点设计与遍历验证很多初学版本只做布尔判断输入合法返回True非法抛异常。这在验证语法阶段能应付但到了collegevm5这类要生成指令或中间代码的项目阶段你会发现自己得从头重构。所以第一版就把AST建起来后面每一步都省事。class Node: __slots__ (kind, value, left, right) def __init__(self, kind, valueNone, leftNone, rightNone): self.kind kind self.value value self.left left self.right right def dump(self, level0): pad * level if self.kind number: return f{pad}{self.value}\n op_name { TokenType.PLUS: , TokenType.MINUS: -, TokenType.STAR: *, TokenType.SLASH: /, }.get(self.value, str(self.value)) return (f{pad}{op_name}\n f{self.left.dump(level 1)} f{self.right.dump(level 1)})逻辑说明Node只有四个字段kind区分节点类型value在number节点存数值、在binop节点存运算符的TokenTypeleft和right连接子节点。dump方法做先序遍历打印number直接输出数值binop输出运算符并递归打印左右子树。用__slots__是为了少占内存在parser这种高频构造节点的场景省一点是一点。参数说明节点命名跟文法走。我没有用泛化的node而是用kindbinop加value存具体运算符这样后面做代码生成时遍历一次node.dump()就能看清整个表达式绑定的结构。验证AST对不对有一个好办法把 (23)4 和 234 两个表达式分别打印出来前者根节点是*后者根节点是如果打印结果反了说明term和expr之间的调用层级接错排查范围就锁定在expr和term两个函数里。4. 语法分析器避坑5条踩坑记录与排查思路4.1 左递归造成无限递归现象、原因、解决现象运行语法分析器输入一个简单表达式程序直接RecursionError甚至不需要输入任何内容初始化Parser那一刻就崩。原因文法保留了左递归产生式。常见于从教科书抄了原始文法没做改造或者用递归调用代替了while循环。expr()在读取任何Token之前先调用自己栈帧无限累加Python默认递归深度限制约1000层几毫秒就触顶。有些人会去调sys.setrecursionlimit那只是把爆炸时间往后推并不能解决问题。解决把左递归产生式改写成循环。用 E - T ((|-) T)* 这种EBNF形式让消耗Token的动作发生在循环体内。判断是否改干净的标准是每个非终结符函数的第一行代码必须读取或判断current而不是递归调用自己。如果看到函数开头就 self.expr()那一定是左递归没消除。4.2 回溯爆炸同一段输入被反复扫描现象输入一长就明显卡顿。短表达式毫秒级返回几十个Token的表达式肉眼可感知的延迟再长直接等不下去。原因递归下降里用了保存位置再回退的策略。比如factor里先尝试按NUMBER解析失败后把pos存回退到原地再尝试按括号解析。遇到多个可选分支时同一段Token流被反复扫描复杂度呈指数上升。这种实现思路在Prolog风格的逻辑编程里很常见但不适合手写parser。解决把文法往LL(1)方向改造让每个分支只依赖当前Token即可唯一决定。我的做法是绝不在Parser里保存pos做回退如果发现非回退不可先回去提取左公因子或者把产生式改写得更短。一个实用的检查方法是给每个非终结符算FIRST集如果两条产生式FIRST集有交集就是潜在回溯点。宁可花半小时改文法也不要留一个会在长输入上卡死的parser。4.3 优先级写反乘除比加减后执行现象输入23*4如果你期望的语义是左结合且乘除优先得到20就说明乘除没先绑定更明显的翻车是 (23)4 被解析成 2(34)AST形状完全反了。原因expr函数直接调用factor跳过了term这一层。调用层级只有两级乘除和加减在同层处理先到先结合优先级消失。还有一种是循环条件里把加减和乘除写在同一个集合里也会出现同层处理。解决恢复三层调用结构。expr调termterm调factorfactor管括号和数字。验证方法解析234后打印AST根节点必须是右子树是解析(23)4时根节点必须是。两个用例一对优先级有没有接对立刻知道。这是语法分析器里最便宜的一个验证手段比拿十个测试用例跑结果还有用。4.4 报错位置漂移错误信息指向行尾而不是出错点现象输入12报错信息说第1行第7列出问题实际号在第1行第3列。用户对着行尾找半天根本不知道错在哪。原因match抛出异常时没有携带Token位置或者异常被外层循环吞掉。如果parse入口抛错时current已经advance到了END那么错误位置自然落在末尾。另一个常见原因是把异常捕获放在parse外层try块里continue循环把错误状态冲掉了。解决每个抛出的SyntaxError都带上self.current.line和self.current.col报错信息里同时打印期望类型和实际类型。同时把异常处理放在parse的入口处只做一层捕获打印完整错误后退出不要在循环内吞异常。这样12会准确报在号的位置期望NUMBER实际STAR一看就知道是乘号后面缺了操作数。调试时可以临时在match里加一行print(fconsumed {self.current})看Token消耗到哪一步开始偏离预期。4.5 生成器冲突报告看不懂规则被静默解决现象用Bison生成的parser跑小用例全对跑大用例时某个if语句行为诡异。编译时其实有冲突报告输出但你是后来才注意到的warning级别信息被静默忽略了。原因文法有二义性最常见的悬空else——if (a) if (b) s1 else s2里的else到底匹配哪个if。Bison默认偏向移进else就近匹配这个决策对你可能不是想要的。运算符优先级没写%left声明时expr和expr之间也存在大量shift/reduce冲突全部被默认规则静默消化。解决文法里声明运算符优先级用%left和%right把运算符从低到高排列。悬空else如果不满意默认行为可以借助%prec或者改写文法分支。冲突还是看不懂时用bison -v输出以.output结尾的状态描述文件里面逐状态标明了冲突位置和参与符号是排错唯一靠谱的入口。别靠猜猜三次错三次的教训我经历过。5. 从手写验证到自动生成用Yacc/Bison做文法正确性的后悔药手写递归下降有个让人头疼的问题你很难证明自己的文法没有歧义。等写完三四个非终结符发现某个表达式存在两条解析路径时前面的代码可能得推翻重来。我后来养成的习惯是文法稍微复杂一点先用Yacc/Bison把文法描述跑一遍让它告诉我有没有冲突再动手手写。Bison这时候不是最终交付物而是一颗后悔药把问题拦截在动手之前。一个常见的Bison描述片段长这样%token NUMBER %left - %left * / %% expr: expr term { $$ make_node(, $1, $3); } | expr - term { $$ make_node(-, $1, $3); } | term { $$ $1; } ; term: term * factor { $$ make_node(*, $1, $3); } | term / factor { $$ make_node(/, $1, $3); } | factor { $$ $1; } ; factor: NUMBER { $$ make_node(number, $1); } | ( expr ) { $$ $2; } ; %%逻辑说明%left声明运算符优先级越靠后的行优先级越高所以乘法比加法先归约。产生式左边是左部非终结符右边是符号序列竖线分隔同一非终结符的多个选择。语义动作里$1是右部第一个符号的结果$3是第三个$$是当前产生式要返回的结果。这里expr仍保留左递归写法因为LR分析器能处理不需要像LL那样改写。参数说明如果只拿来做验证语义动作可以全部省略只保留%token、%left和产生式规则。Bison依然会做冲突检测并输出报告而不会因为省略$$而报错。拿到一份无冲突报告之后再按照同一套文法结构手写递归下降等于先有一张经过验证的图纸。手写时把expr这条左递归产生式换成循环写法就行。注意如果实验要求里明确写了不允许使用生成器Bison产出的parser只能用来对照验证不能作为最终提交。先问清楚规则再决定时间投入。我自己的流程是草稿纸上写出文法 → 消除左递归和左公因子 → 用Bison验证一份同样的文法 → 确认无冲突 → 才是写Parser代码。验证阶段的耗时通常不超过半小时但能省掉后面至少两天的重构时间。文法层面的错是最贵的错因为它会让到处的语义动作、AST节点全部跟着返工。希望帮到你至少别像我第一版那样写完了才发现乘除和加减优先级接反连夜重排调用层次。本文还有配套的精品资源点击获取 语法分析器从入门到实践：递归下降与LL(1)、LR(1)选型指南
简介面向编译原理课程设计与语法分析器开发学习者资源内包含一份用C实现的语法分析器源码覆盖输入扫描、语法树构造与错误处理等关键环节帮助理解从源代码到语法结构的解析过程适用于高校编译原理实验、课设以及collegevm5等课程实践场景。资源为zip压缩包共1个文件核心为cpp源码文件整体仅2KB代码精简便于阅读和二次修改。已有177人学习浏览适合正在实现递归下降、LL或LR分析等任务的读者参考。通过这份代码学习者可以直接查看C如何组织词法扫描、语法判断与错误处理流程对照BNF/EBNF形式文法与解析表构建思路快速把握一个基础语法分析器的骨架。虽然包体很小但作为单一源码示例其逻辑完整可作为课程报告分析对象或扩展开发起点帮助加深对编译原理中语法分析阶段的理解。1. 语法分析器是什么从Token流到语法树的必经关卡做编译原理实验的人十个里有八个卡在语法分析器这一关。词法分析好歹是线性扫描正则表达式一匹配就出Token到了语法分析器面对的是嵌套结构、运算符优先级、左递归这些反直觉的东西代码写着写着就栈溢出了。语法分析器要解决的问题很直接拿到词法分析器吐出来的一串Token按照文法规则判断这段代码是否符合语法并把符合的部分组织成一棵语法树。它上接词法、下接语义分析是编译器里最难糊弄过去的一个模块。适合谁读正在做collegevm5这类编译课程虚拟机实验、需要自己写或借助工具生成语法分析器的同学以及要把表达式解析、配置文件解析做扎实的工程从业者。读完你能确定一件事选择手写递归下降还是用生成器从此不再凭感觉。2. 自顶向下与自底向上LL(1)和LR(1)怎么选才不返工2.1 两种路线的核心差异谁在决定下一步看什么语法分析器分两大流派自顶向下和自底向上。自顶向下从开始符号出发试图推导出整个Token序列自底向上从Token序列出发试图归约回开始符号。教科书上这一句带过但实际写代码时它直接决定了你手里的控制流长什么样也决定了你后面排错看的是调用栈还是状态栈。自顶向下最典型的实现是递归下降分析。思路是给每个非终结符写一个函数函数里看一眼当前Token决定走哪条产生式然后递归调用其他非终结符对应的函数。比如解析表达式进入expr()之后当前Token是数字还是左括号决定了是先走term还是直接进括号分支。这种方式的代码和文法几乎一一对应出错时调试栈就是函数的调用栈哪一步错了一目了然。自底向上的代表是LR分析器。它维护一个状态栈根据当前状态和下一个Token决定移进还是归约。移进是把Token压栈归约是把栈顶若干符号按产生式还原成一个非终结符。LR能处理的文法范围比LL宽几乎所有手写文法都能找到对应的LR(1)形式但状态表动辄几十上百个状态手写等于给自己挖坑通常要靠Yacc/Bison自动生成。这里有一个容易混淆的概念LL里的第一个L表示从左到右扫描输入第二个L表示最左推导LR同理第一个L是扫描方向R是最右推导。考试和面试爱考这个但工程上你只需要记住一个判断标准如果文法改写后每个非终结符的每个分支都能靠当前Token唯一确定就用递归下降如果产生式之间有重叠、靠一个Token分不开要么改文法要么上LR生成器。FIRST集和FOLLOW集是判断能不能靠当前Token唯一确定的工具。FIRST集是一个非终结符能推导出的所有首Token的集合FOLLOW集是所有可能跟在其后的Token的集合。求这两个集合很机械手算几个简单文法就能明白但到了十几个非终结符的文法手算容易漏。在实际项目中我一般会在纸上列出每个非终结符的FIRST集和FOLLOW集或者写个小脚本算一遍作为写递归下降前的体检报告。2.2 文法改造消除左递归与提取左公因子递归下降最怕两类文法问题左递归和左公因子。这两件事不解决代码写出来不是无限递归就是逻辑全错。在大多数教材里比如清华大学出版社第三版的编译原理教材第二章的习题就是围绕FIRST集、FOLLOW集和预测分析表展开的把这部分练透递归下降基本不会出预测冲突。左递归就是产生式左边第一个符号还是自己例如 E - E T。递归下降遇到它expr()会无限调用自己读不到任何Token栈直接爆炸。解决办法是把左递归改写成右递归。经典表达式文法的改造过程是这样的原始文法E - E T | E - T | TT - T * F | T / F | FF - NUMBER | ( E )改造后E - T EE - T E | - T E | εT - F TT - * F T | / F T | εF - NUMBER | ( E )这里ε表示空串也就是E可以什么都不匹配直接结束。这个改造在纸上是一套固定替换规则但在实际手写代码时我更推荐直接用EBNF的循环写法也就是把 E - T ((|-) T)* 这样的形式直接翻译成while循环。它和右递归是等价的但代码可读性好得多学生作业里两种写法都常见我一般建议用循环少一层递归少一次栈压力。左公因子问题出现在同一非终结符的两条产生式开头相同。比如 IF_STMT - if (expr) stmt | if (expr) stmt else stmt两条都以if开头递归下降的决策点在看到if那一刻根本不知道后面跟的是else还是没有。解决办法是延迟决策提取公共前缀IF_STMT - if (expr) stmt TAILTAIL - else stmt | ε。这样先统一进if分支读到else再决定TAIL怎么走。这个延迟决策的思路在更复杂的文法里也适用。判断是否需要提取公因子我有个土办法把每个非终结符所有产生式的首符号列出来但凡有重复的就说明这个地方存在预测冲突先提取再往下写。别等到代码跑挂了再回头改那会儿改的是函数逻辑比改文法难多了。2.3 选型对照手写递归下降还是上生成器选型没有绝对标准我按自己做过的几个项目给一个参考。如果你的目标语言是几十行到几百行的规模语法以表达式和简单语句为主手写递归下降是最快的路径代码量小、报错位置精确、不依赖外部工具链。如果你要解析的是完整的C或Java语法或者语法还在频繁迭代直接用Yacc/Bison或ANTLR省下的时间够你多调试两轮生成器的冲突。生成器也不是零成本。Yacc/Bison意味着你要接受它的冲突报告是英文缩写、语义动作里写$$和$1这套约定、生成的C代码可读性差这些现实。ANTLR则要面对Java运行时依赖和语法文件版本匹配问题。对collegevm5这类课程虚拟机来说老师多半会限定解析范围比如只解析赋值、表达式、if和while。先看懂实验要求是手写parser还是允许工具生成这决定了后面几周的工作量方向。我的建议是实验要求不明确时能手写就手写因为生成器的产物在你的虚拟机里接起来调试成本往往比手写还要高。维度手写递归下降Yacc/Bison/LR文法范围需改造为LL(1)接受LR(1)及部分二义文法代码可控性高报错可精确到函数低纠错逻辑难定制学习成本低递归加匹配高状态机与冲突报告调试方式栈调用即解析路径看状态机文件与冲突位置适用规模小型语言原型中型以上完整语言这张表的结论不是手写优于生成器而是规模决定工具。我见过有人用Bison解析一个只需要支持加减乘除的小语言结果花在配置环境和处理冲突上的时间比手写整个parser还长也见过纯手写去解析类C语法写到两千行之后维护成本爆炸。先量规模再选路线。3. 手写递归下降语法分析器从表达式文法到可运行代码3.1 词法接口与Token流最小约定写语法分析器之前先和词法器把接口谈清楚。我的惯例是词法器暴露一个next_token()方法返回二元组(type, value)type是Token类型value是具体值。语法分析器只依赖type做决策value留到AST构建时用。再往下有一个约定容易被忽略语法分析器需要偷看当前Token做决策但不该消耗它。所以我不把Token流当成队列去pop而是维护一个current指针只有match成功时才移动。这样决策逻辑始终只盯着一个Token不会出现读掉了结果发现不对的尴尬。import re from enum import Enum class TokenType(Enum): NUMBER 1 PLUS 2 MINUS 3 STAR 4 SLASH 5 LPAREN 6 RPAREN 7 END 8 class Token: def __init__(self, type_, value, line, col): self.type type_ self.value value self.line line self.col col def __repr__(self): return f{self.type.name}({self.value}){self.line}:{self.col} def tokenize(text): tokens [] i 0 line, col 1, 1 token_spec [ (TokenType.NUMBER, r\d), (TokenType.PLUS, r\), (TokenType.MINUS, r-), (TokenType.STAR, r\*), (TokenType.SLASH, r/), (TokenType.LPAREN, r\(), (TokenType.RPAREN, r\)), ] while i len(text): if text[i] in \t: i 1 col 1 continue if text[i] \n: line 1 col 1 i 1 continue matched False for ttype, pattern in token_spec: m re.match(pattern, text[i:]) if m: tokens.append(Token(ttype, m.group(), line, col)) col len(m.group()) i len(m.group()) matched True break if not matched: raise SyntaxError(f未知字符 {text[i]!r} at {line}:{col}) tokens.append(Token(TokenType.END, None, line, col)) return tokens逻辑说明tokenize把输入字符串切成一串Token并在末尾追加END标记表示输入耗尽。每个Token记录行号和列号这一步看似多余实际上语法分析器报错时全靠它定位后面避坑章节会专门讲。空白字符被跳过数字用正则\d匹配。参数说明token_spec里正则的顺序有讲究NUMBER在最前面然后是单字符运算符。如果以后要支持标识符、关键字、赋值号往这个列表里追加即可注意长的模式要放在短模式前面比如 必须在 前面否则先匹配到就错了。这个顺序问题是最常见的词法翻车点改之前先想清楚匹配优先级。另外这里为了可读性用了text[i:]切片每次都会新建字符串工程上应该用带pos参数的编译后正则但语义完全一样。3.2 递归下降四件套match、expr、term、factor表达式文法在消除左递归之后用EBNF写就是三行 expr - term (( | -) term)* term - factor (( | /) factor)factor - NUMBER | ( expr )我直接用循环实现因为循环天然处理了右递归展开后的那几层调用省栈空间不说代码还短。class Parser: def __init__(self, tokens): self.tokens tokens self.pos 0 self.current tokens[0] def advance(self): if self.pos len(self.tokens) - 1: self.pos 1 self.current self.tokens[self.pos] def match(self, type_): if self.current.type type_: self.advance() else: raise SyntaxError( f期望 {type_.name}实际 {self.current.type.name} fat {self.current.line}:{self.current.col} ) def parse(self): node self.expr() self.match(TokenType.END) return node def expr(self): left self.term() while self.current.type in (TokenType.PLUS, TokenType.MINUS): op self.current.type self.advance() right self.term() left Node(binop, valueop, leftleft, rightright) return left def term(self): left self.factor() while self.current.type in (TokenType.STAR, TokenType.SLASH): op self.current.type self.advance() right self.factor() left Node(binop, valueop, leftleft, rightright) return left def factor(self): t self.current if t.type TokenType.NUMBER: self.advance() return Node(number, valueint(t.value)) if t.type TokenType.LPAREN: self.advance() node self.expr() self.match(TokenType.RPAREN) return node raise SyntaxError(f意外的Token {t.type.name} at {t.line}:{t.col})逻辑说明expr先调用term拿到左操作数再进入while循环。循环里看一下当前Token是加号还是减号是就消耗掉再解析右操作数把左右拼成一个binop节点。注意while条件用元组加in可以同时支持两个运算符比写两个if简洁。term对乘除做同样的事factor处理数字和括号括号内递归调用expr。参数说明这个结构里优先级完全由调用层级体现expr调termterm调factor所以乘除先绑定括号最优先。如果要加入一元负号在factor里新增一个MINUS分支先消耗负号再递归factor而不是在expr里处理否则 -23 会被解析成 -(23)。这个一元运算放因子层的规律在扩展文法时一定要记住放错层优先级就反了。补一个单测习惯写完这个Parser之后第一件事不是跑大用例而是跑边界用例。空输入应该报END期望错误单独一个数字应该能解析成功(12这种缺右括号的输入报错位置应该指向缺失的右括号附近。这三个用例过了parser的骨架才算稳。3.3 建AST而不是只判对错节点设计与遍历验证很多初学版本只做布尔判断输入合法返回True非法抛异常。这在验证语法阶段能应付但到了collegevm5这类要生成指令或中间代码的项目阶段你会发现自己得从头重构。所以第一版就把AST建起来后面每一步都省事。class Node: __slots__ (kind, value, left, right) def __init__(self, kind, valueNone, leftNone, rightNone): self.kind kind self.value value self.left left self.right right def dump(self, level0): pad * level if self.kind number: return f{pad}{self.value}\n op_name { TokenType.PLUS: , TokenType.MINUS: -, TokenType.STAR: *, TokenType.SLASH: /, }.get(self.value, str(self.value)) return (f{pad}{op_name}\n f{self.left.dump(level 1)} f{self.right.dump(level 1)})逻辑说明Node只有四个字段kind区分节点类型value在number节点存数值、在binop节点存运算符的TokenTypeleft和right连接子节点。dump方法做先序遍历打印number直接输出数值binop输出运算符并递归打印左右子树。用__slots__是为了少占内存在parser这种高频构造节点的场景省一点是一点。参数说明节点命名跟文法走。我没有用泛化的node而是用kindbinop加value存具体运算符这样后面做代码生成时遍历一次node.dump()就能看清整个表达式绑定的结构。验证AST对不对有一个好办法把 (23)4 和 234 两个表达式分别打印出来前者根节点是*后者根节点是如果打印结果反了说明term和expr之间的调用层级接错排查范围就锁定在expr和term两个函数里。4. 语法分析器避坑5条踩坑记录与排查思路4.1 左递归造成无限递归现象、原因、解决现象运行语法分析器输入一个简单表达式程序直接RecursionError甚至不需要输入任何内容初始化Parser那一刻就崩。原因文法保留了左递归产生式。常见于从教科书抄了原始文法没做改造或者用递归调用代替了while循环。expr()在读取任何Token之前先调用自己栈帧无限累加Python默认递归深度限制约1000层几毫秒就触顶。有些人会去调sys.setrecursionlimit那只是把爆炸时间往后推并不能解决问题。解决把左递归产生式改写成循环。用 E - T ((|-) T)* 这种EBNF形式让消耗Token的动作发生在循环体内。判断是否改干净的标准是每个非终结符函数的第一行代码必须读取或判断current而不是递归调用自己。如果看到函数开头就 self.expr()那一定是左递归没消除。4.2 回溯爆炸同一段输入被反复扫描现象输入一长就明显卡顿。短表达式毫秒级返回几十个Token的表达式肉眼可感知的延迟再长直接等不下去。原因递归下降里用了保存位置再回退的策略。比如factor里先尝试按NUMBER解析失败后把pos存回退到原地再尝试按括号解析。遇到多个可选分支时同一段Token流被反复扫描复杂度呈指数上升。这种实现思路在Prolog风格的逻辑编程里很常见但不适合手写parser。解决把文法往LL(1)方向改造让每个分支只依赖当前Token即可唯一决定。我的做法是绝不在Parser里保存pos做回退如果发现非回退不可先回去提取左公因子或者把产生式改写得更短。一个实用的检查方法是给每个非终结符算FIRST集如果两条产生式FIRST集有交集就是潜在回溯点。宁可花半小时改文法也不要留一个会在长输入上卡死的parser。4.3 优先级写反乘除比加减后执行现象输入23*4如果你期望的语义是左结合且乘除优先得到20就说明乘除没先绑定更明显的翻车是 (23)4 被解析成 2(34)AST形状完全反了。原因expr函数直接调用factor跳过了term这一层。调用层级只有两级乘除和加减在同层处理先到先结合优先级消失。还有一种是循环条件里把加减和乘除写在同一个集合里也会出现同层处理。解决恢复三层调用结构。expr调termterm调factorfactor管括号和数字。验证方法解析234后打印AST根节点必须是右子树是解析(23)4时根节点必须是。两个用例一对优先级有没有接对立刻知道。这是语法分析器里最便宜的一个验证手段比拿十个测试用例跑结果还有用。4.4 报错位置漂移错误信息指向行尾而不是出错点现象输入12报错信息说第1行第7列出问题实际号在第1行第3列。用户对着行尾找半天根本不知道错在哪。原因match抛出异常时没有携带Token位置或者异常被外层循环吞掉。如果parse入口抛错时current已经advance到了END那么错误位置自然落在末尾。另一个常见原因是把异常捕获放在parse外层try块里continue循环把错误状态冲掉了。解决每个抛出的SyntaxError都带上self.current.line和self.current.col报错信息里同时打印期望类型和实际类型。同时把异常处理放在parse的入口处只做一层捕获打印完整错误后退出不要在循环内吞异常。这样12会准确报在号的位置期望NUMBER实际STAR一看就知道是乘号后面缺了操作数。调试时可以临时在match里加一行print(fconsumed {self.current})看Token消耗到哪一步开始偏离预期。4.5 生成器冲突报告看不懂规则被静默解决现象用Bison生成的parser跑小用例全对跑大用例时某个if语句行为诡异。编译时其实有冲突报告输出但你是后来才注意到的warning级别信息被静默忽略了。原因文法有二义性最常见的悬空else——if (a) if (b) s1 else s2里的else到底匹配哪个if。Bison默认偏向移进else就近匹配这个决策对你可能不是想要的。运算符优先级没写%left声明时expr和expr之间也存在大量shift/reduce冲突全部被默认规则静默消化。解决文法里声明运算符优先级用%left和%right把运算符从低到高排列。悬空else如果不满意默认行为可以借助%prec或者改写文法分支。冲突还是看不懂时用bison -v输出以.output结尾的状态描述文件里面逐状态标明了冲突位置和参与符号是排错唯一靠谱的入口。别靠猜猜三次错三次的教训我经历过。5. 从手写验证到自动生成用Yacc/Bison做文法正确性的后悔药手写递归下降有个让人头疼的问题你很难证明自己的文法没有歧义。等写完三四个非终结符发现某个表达式存在两条解析路径时前面的代码可能得推翻重来。我后来养成的习惯是文法稍微复杂一点先用Yacc/Bison把文法描述跑一遍让它告诉我有没有冲突再动手手写。Bison这时候不是最终交付物而是一颗后悔药把问题拦截在动手之前。一个常见的Bison描述片段长这样%token NUMBER %left - %left * / %% expr: expr term { $$ make_node(, $1, $3); } | expr - term { $$ make_node(-, $1, $3); } | term { $$ $1; } ; term: term * factor { $$ make_node(*, $1, $3); } | term / factor { $$ make_node(/, $1, $3); } | factor { $$ $1; } ; factor: NUMBER { $$ make_node(number, $1); } | ( expr ) { $$ $2; } ; %%逻辑说明%left声明运算符优先级越靠后的行优先级越高所以乘法比加法先归约。产生式左边是左部非终结符右边是符号序列竖线分隔同一非终结符的多个选择。语义动作里$1是右部第一个符号的结果$3是第三个$$是当前产生式要返回的结果。这里expr仍保留左递归写法因为LR分析器能处理不需要像LL那样改写。参数说明如果只拿来做验证语义动作可以全部省略只保留%token、%left和产生式规则。Bison依然会做冲突检测并输出报告而不会因为省略$$而报错。拿到一份无冲突报告之后再按照同一套文法结构手写递归下降等于先有一张经过验证的图纸。手写时把expr这条左递归产生式换成循环写法就行。注意如果实验要求里明确写了不允许使用生成器Bison产出的parser只能用来对照验证不能作为最终提交。先问清楚规则再决定时间投入。我自己的流程是草稿纸上写出文法 → 消除左递归和左公因子 → 用Bison验证一份同样的文法 → 确认无冲突 → 才是写Parser代码。验证阶段的耗时通常不超过半小时但能省掉后面至少两天的重构时间。文法层面的错是最贵的错因为它会让到处的语义动作、AST节点全部跟着返工。希望帮到你至少别像我第一版那样写完了才发现乘除和加减优先级接反连夜重排调用层次。本文还有配套的精品资源点击获取