简介一份面向编译原理学习者的C语言源码实现算术表达式的LR语法分析。程序包含词法分析器与LR分析器核心逻辑可读取用户输入的算术表达式完成移进/归约操作并验证语法正确性适合编译器设计入门及相关实验参考。压缩包仅含1个c文件大小约6KB结构精简、代码集中便于查看完整实现。目前已有156人学习浏览。该程序覆盖了上下文无关文法定义、LR分析表构建、状态栈与输入栈操作、冲突处理等关键环节。通过阅读和运行源码可直接观察单词识别、产生式归约与接受状态的执行过程也可在此基础上扩展运算优先级、错误处理或语义动作是理解自底向上语法分析的良好示例。1. 看到 byq.rar先想清楚算术表达式为什么是 LR 教学的常客byq.rar_算术表达式LR 这个压缩包名字十有八九是编译原理课程设计或个人学习项目留下的。它要解决的问题很具体输入23*4程序不能急着算得先明白乘法比加法优先输入1-2-3又必须保证减法从左往右算。这类中缀表达式的解析恰好是 LR 分析最经典的教材场景也是递归下降这类自顶向下方法做起来最别扭的地方。这篇笔记的服务对象是正在做编译原理实验、想在嵌入式设备里塞一个公式计算器、或者在公司内部实现配置表达式引擎的工程师。这篇不打算把课本里的完整理论复述一遍只讲从文法设计、分析表构造到驱动代码落地这条路怎么走以及这条路上我踩过的几个坑。2. 算术表达式文法设计优先级、左结合和左递归三个门槛2.1 中缀表达式为什么逼着你用 LR先算谁得往后看一个反直觉的结论是对23*4如果只从左往右扫描看到加号的时候根本没法决定2能不能先归约成一个结果因为后面可能还有乘号。真正的决定要等看到足够多的 token 之后才能做。递归下降的做法是进入每一个优先级层去匹配写起来不复杂但一旦表达式里出现嵌套括号、负号、多层优先级代码里的函数调用会迅速膨胀而 LR 分析器换了一个思路先不急着归约把看到的东西压进栈等看够了再一次性弹出归约。这就是移进-归约思想。「2」读进来先压栈「」读进来因为栈顶的「2」没法单独归约成完整的表达式还是压栈读到「3」时仍然先压栈因为必须等看到「*」或者「」之后才能知道「3」到底应该先和谁结合。这个再等等的策略本质上就是 LR 里的移进动作。归约动作一旦做错没有后悔药所以 LR 宁可多等一拍。这种看完右部再动手的机制让算术表达式这类优先级层级清晰的语言成为 LR 文法最合适的教学载体。2.2 用 E、T、F 三层结构把优先级写进文法算术表达式文法最常见的写法是把运算符分成两层加一层原子从上到下优先级递增E - E T E - E - T E - T T - T * F T - T / F T - F F - ( E ) F - num这个文法里E 层只处理加减法T 层只处理乘除法F 层负责数字和括号。优先级不是靠程序里的 if 判断实现的而是靠推导层次实现的。23*4的推导过程里3*4必须在 T 层先成型E 层做加法时右边已经是一个计算完整的 T不会再出现先算加法后算乘法的可能性。我一般会把这张文法表贴在代码文件头部的注释里因为分析表可以重新生成但文法一旦写错后面每一步都是错的。检查文法时有个笨办法把几个关键表达式从 F 层开始画推导树23*4、(23)*4、2*34各画一遍如果某一棵树的某个运算符深度不对说明层次划分有问题。2.3 左递归在 LR 里不是病而是左结合的解药很多写过递归下降的工程师都被《编译原理》第一章教育过要消除左递归因为 LL(1) 预测分析处理不了E - E T这种产生式。但到了 LR 这边左递归恰恰是描述左结合语义最直接的方式。1-2-3应该等于 -4 而不是 1因为减法左结合文法写成E - E - T语法树天然左倾归约顺序自然从左边开始。反过来如果把减法写成右递归形式E - T - E1-2-3 会解析成 1-(2-3)结果变成 2。这是写计算器最容易犯的错尤其当你从别的语言翻译代码时很容易顺手把产生式调个方向。我自己的经验是解析器调试时先测1-2-3如果输出不是 -4先检查减法产生式是不是写成左递归了别急着查表。LR 为什么不怕左递归因为它是自底向上的。分析器先收集终结符等累积到能构成产生式右部的程度才做归约产生式右部第一个符号是 E 还是终结符对归约动作没有影响。所以在这里左递归不需要消除你甚至可以把它当作 LR 的一项优势写进项目文档里。2.4 一元负号的坑减号和负号在词法层长一个样文法设计的第一个坑出现在负号上。-1 2里的减号和3 - 2里的减号是同一个字符前者是一元前缀运算符后者是二元中缀运算符。如果只在语法层处理常见的做法是给 F 层加一条前缀产生式F - - F这样-1整体在 F 层先成型不会干扰 T 层的乘除归约。但这条产生式会立刻带来一个移进-归约冲突栈里已经有内容时读到减号分析器无法立刻判断它是二元减法还是下一个负数的前缀。多数解析器生成工具默认选择移进这个默认行为对大部分表达式是对的但3 * -2这类场景必须单独测试。我更常用的做法是把判断挪到词法层词法扫描时看一眼前一个 token。如果前一个 token 是数字、右括号或者语法上已经归约出 E这个减号就是二元运算符否则当作一元负号处理返回一个不同的 token 类型。这样语法层保持简洁冲突也少一个来源。词法上下文判断看起来像偷懒实际是工程上最省事的方案。3. 从文法到分析表SLR 手工构造的步骤与一张能跑的表3.1 增广文法和项目集状态机的两个关键算法分析表不是凭空来的。自底向上分析器真正做的工作是在一个有限状态机上移动状态由当前语法分析进行到什么位置决定。描述这个位置的工具叫 LR 项目形如E - E · T圆点表示已看到左部哪些符号。为了让接受动作唯一先把原文法增广一条产生式比如给上面的文法加S - E。增广的意义在于分析器只有在栈顶状态遇到S - E ·这类项目时才知道整个分析结束否则归约完成后不知道什么时候该停。状态机的两个操作是闭包和转移。闭包的规则是如果某个项目里圆点右边是一个非终结符 B那么所有以 B 为左部的产生式都要以圆点在右部最前面的形式加入当前项目集。转移的规则是把圆点往右移一个符号得到新项目再对新项目求闭包。这两条规则反复迭代就能从初始状态出发生成所有状态。我用一个类比帮助理解闭包是当前正在期待一个 B所以 B 的所有可能的开头都必须预先铺好转移是真的读到了这个符号圆点可以往前挪一步。手工做的时候建议先用铅笔把所有状态列出来再填动作顺序不能反。3.2 SLR 归约规则FOLLOW 集合当看门人拿到项目集状态机之后填分析表遵循三条规则。第一项目A - α · t β里圆点右边是终结符 t那么 ACTION[状态, t] 填移进新状态由转移得到。第二项目A - α ·表示右部已经看完可以归约但归约不是所有输入符号下都能做只有当前输入符号属于 FOLLOW(A) 时才能归约这正是 SLR 开头那个 S 的含义。第三增广产生式S - E ·对应的状态里在输入$上填接受。ACTION 表 圆点后是终结符 t - 移进 圆点后是输入结束 $ - 接受 圆点后没有符号且输入在 FOLLOW 中 - 归约 GOTO 表 状态 s 在非终结符 A 上的转移FOLLOW 集合在这里非常重要。某个产生式能归约并不意味着什么输入都能归约归约会改变栈顶的非终结符而转移后的状态能否处理后续输入取决于该非终结符后面可能跟什么。算数表达式里E 后可以跟$、、)所以 E 的归约只有在这些符号出现时才有效。移进-归约冲突产生的根源是一个状态里同时出现了圆点后是终结符的移进项目和圆点后没有符号的归约项目。教科书上会用优先级声明来解决工程上一般交给工具处理但如果你手写表必须正面面对这个冲突。3.3 一张六状态的加减法表先读懂表再谈生成器完整算术表达式文法的分析表有将近二十个状态手工构造容易出错学习阶段最好先用缩小版看结构。下面这张表对应文法S - E、E - E T、E - T、T - num只支持加法和数字但 LR 表的移进、归约、接受三类动作全部齐全。状态 0 : S - · E E - · E T E - · T T - · num 状态 1 : S - E · E - E · T 状态 2 : E - T · 状态 3 : T - num · 状态 4 : E - E · T T - · num 状态 5 : E - E T ·根据 FOLLOW 集合E 后可以跟$或T 后可以跟$或。填入 ACTION 表和 GOTO 表后状态输入 num输入 输入 $GOTO EGOTO T0s3121s4acc2r(E→T)r(E→T)3r(T→num)r(T→num)4s355r(E→ET)r(E→ET)拿num num num手工跑一遍状态 0 看到 num 移进到 3读加号状态 3 归约 TGOTO 跳到 2状态 2 在加号下归约 E进入状态 1状态 1 在加号下移进到 4后面重复一轮最终状态 1 读到$接受。整个过程能看出左结合是怎么实现的第一个 num 在第二个 num 还没有完整归约前就先生成 T再被压成 E。3.4 完整版本用生成器自动产出PLY 的简单用法手工构造完整算术表达式表不是不行但状态数量多、易错效率太低。工程上更常见的做法是用一种 yacc 移植工具自动生成分析表然后把表打印出来存成字典。PLY 是 Python 生态里常见的选择文法和语义动作写在函数 docstring 里import ply.lex as lex import ply.yacc as yacc tokens (NUM, PLUS, TIMES, LPAREN, RPAREN) t_PLUS r\ t_TIMES r\* t_LPAREN r\( t_RPAREN r\) t_NUM r\d t_ignore \t def t_error(t): raise SyntaxError(fbad token {t.value!r}) lexer lex.lex() def p_expr(p): expr : expr PLUS term p[0] p[1] p[3] def p_expr_term(p): expr : term p[0] p[1] def p_term_times(p): term : term TIMES factor p[0] p[1] * p[3] def p_term_factor(p): term : factor p[0] p[1] def p_factor_num(p): factor : NUM p[0] int(p[1]) def p_factor_paren(p): factor : LPAREN expr RPAREN p[0] p[2] def p_error(p): raise SyntaxError(syntax error) parser yacc.yacc() print(parser.action) print(parser.goto)这段代码里每个p_函数的 docstring 是文法产生式函数体是归约动作。p[0]是归约后左部的值p[1]、p[2]是右部符号的值。parser.action和parser.goto就是最终的分析表可以直接打印出来看也可以转成 JSON 或二进制字典套一节里的驱动循环来用。用 bison 的-v参数也能得到类似的分析表文件跨语言项目里同样常用。4. 用驱动表跑通 LR 分析一份可运行的最小计算器实现4.1 两份核心数据结构状态栈与符号栈LR 分析器运行时维护三个栈但真正必需的只有状态栈和符号栈。状态栈保存分析状态编号符号栈保存已经归约出来的终结符和非终结符。两者必须严格同步移进时同时压入一个状态和一个终结符归约时按右部长度同时弹出再按 GOTO 压入新状态和新非终结符。状态栈比符号栈恰好多一个元素这是天然的调试断言。我在写驱动循环之前通常先把这张表存成两个字典结构约定写清楚。ACTION 表的值统一存成(shift, 目标状态)或(reduce, 产生式编号)产生式字典里再存左部和右部。这样做的好处是切换成 PLY 生成的表时只要把字典的格式对上驱动循环完全不用改。4.2 三步循环移进、归约、接受主循环只有三步但每一步的弹栈顺序都不能乱ACTION { 0: {num: (shift, 3)}, 1: {: (shift, 4), $: (accept, 0)}, 2: {: (reduce, 2), $: (reduce, 2)}, 3: {: (reduce, 3), $: (reduce, 3)}, 4: {num: (shift, 3)}, 5: {: (reduce, 1), $: (reduce, 1)}, } GOTO { 0: {E: 1, T: 2}, 4: {T: 5}, } PROD { 1: (E, (E, , T)), 2: (E, (T,)), 3: (T, (num,)), } def parse(tokens): # tokens 是已经处理过的 token 列表末尾必须带 ($, None) state_stack [0] sym_stack [] i 0 while True: state state_stack[-1] kind, value tokens[i] act ACTION[state].get(kind) if act is None: raise SyntaxError(funexpected {kind} at position {i}) kind_act, target act if kind_act shift: state_stack.append(target) # 压入新状态 sym_stack.append(kind) # 压入终结符 i 1 elif kind_act reduce: lhs, rhs PROD[target] for _ in rhs: # 右部多长就弹多少次 state_stack.pop() sym_stack.pop() top state_stack[-1] state_stack.append(GOTO[top][lhs]) sym_stack.append(lhs) elif kind_act accept: return True这段代码里移进只是把 token 压栈真正的运算发生在归约。归约时不能手写弹两次这种常量必须按照rhs的长度循环弹出否则文法一变就翻车。GOTO[top][lhs]里那个top必须是弹出的状态栈栈顶而不是任意状态这也是新手最容易写错的地方。4.3 在归约动作里顺便求值把语法分析器变成计算器语法分析只告诉你能不能接受这段输入但实际项目里我们还要它的值。做法是加一个值栈与符号栈同步压弹。归约时从值栈取出右部对应的值按产生式计算左部的值再压回去PROD { 1: (E, (E, , T), lambda vals: vals[0] vals[2]), 2: (E, (T,), lambda vals: vals[0]), 3: (T, (num,), lambda vals: vals[0]), } def parse(tokens): state_stack [0] val_stack [] i 0 while True: state state_stack[-1] kind, value tokens[i] act ACTION[state].get(kind) if act is None: raise SyntaxError(funexpected {kind} at position {i}) kind_act, target act if kind_act shift: state_stack.append(target) val_stack.append(value) # 值是词法层填进来的数字 i 1 elif kind_act reduce: lhs, rhs, fn PROD[target] n len(rhs) vals val_stack[-n:] # 取右部对应的值从左到右 del val_stack[-n:] # 弹出右部 for _ in rhs: state_stack.pop() state_stack.append(GOTO[state_stack[-1]][lhs]) val_stack.append(fn(vals)) # 归约即计算 elif kind_act accept: return val_stack[-1]测试一下234tokens [ (num, 2), (, None), (num, 3), (, None), (num, 4), ($, None), ] print(parse(tokens)) # 9归约E - E T时值栈从低到高分别是 E 的值、加号、T 的值取vals[-3:]得到的就是从左到右的顺序vals[0] vals[2]就是表达式的值。这张教学表只有加法但驱动循环不关心文法细节。把文法换成完整算术表达式文法用 PLY 或者其他生成器产出ACTION、GOTO、PROD三张表驱动代码一行都不用改。提示归约顺序本身就是左结合的体现。1-2-3如果按左结合归约第一次归约发生在1-2第二次才是(1-2)-3。所以观察归约顺序比看结果更能确认结合性对不对。5. 算术表达式 LR 分析器常见问题排查4 个最容易翻车的毛病5.1 状态栈和符号栈错位最常见的轴心错误现象程序跑到归约时报 IndexError或者解析结果严重偏离预期比如23算出 5 但23*4算出 24 而不是 14。原因状态栈和符号栈没有保持同步或者归约时弹出次数写成了常量。我见过有人把E - E T的归约写死成弹三次结果换文法后 GOTO 查出来的状态完全对不上。解决在循环开头加断言assert len(state_stack) len(sym_stack) 1状态栈始终比符号栈多一个栈底状态。归约时按len(rhs)循环弹不要手写具体数字。调试时在每次归约后打印两个栈的完整内容能很直观看出哪一步开始分叉。5.2 忘记给输入末尾补$到达不了接受状态现象表达式算到最后一个数字后程序报错说找不到对应的 ACTION或者解析完成但parse没有返回。原因LR 表的接受动作只在输入$时触发而词法层通常不会自然产生$。如果 token 列表没有结尾标记状态永远等不到接受。解决词法输出后统一在末尾追加($, None)。我习惯在测试里显式写23$这种字符串形态的输入方便肉眼检查。同时注意多 token 输入的最后一个 token 后如果有换行别把换行也当成合法 token 塞进去否则会挡住$的到达。5.3 一元负号把归约流程带崩现象-12报 syntax error但12和3-2都正常。原因文法里没有处理一元负号的产生式词法层又把-一律解释成二元减法。分析器读到最开头的-时期望的是 num实际收到减号ACTION 表里根本查不到这一项。解决两种路线。其一词法层做上下文判断前一个 token 是数字、右括号或 E 时识别为减号否则识别为负号 token。其二语法层加F - - F但要注意因此产生的移进-归约冲突生成工具默认选择移进需要单独验证3 * -2这类表达式。我的习惯是词法层处理语法层保持单纯。5.4 冲突被工具静默解决现象PLY 或 bison 构建时在终端打了一行 shift/reduce conflict 的警告但没阻止生成测试几个普通表达式也都正确于是忽略警告。换到3-2-1这类依赖左结合的用例时结果变成 2。原因冲突发生时工具默认选移进这个默认行为不是按你的语义要求来的优先级规则没写清楚时归约可能偏离预期。解决把每次生成的 warning 当错误处理。PLY 里通过yacc.yacc(debugTrue, outputloglog)把冲突明细重定向到日志bison 的-v参数也会输出.output文件查看每个状态里的冲突项目。看到冲突后要么给运算符声明优先级要么调整文法层次让冲突消失在结构设计里而不是依赖工具的默认值。6. 给 LR 分析器加一个错误定位技巧同步符号与恐慌模式完整项目里解析失败时只抛一句 syntax error 是不够用的。词法扫描时顺手给每个 token 带上行号和列号错误信息立刻能说清楚第几行第几列附近出现了什么。这一步成本极低收益却很大是排错环节的后悔药。语法层面的恢复常见做法是恐慌模式。设计一组同步符号通常选分号、右括号、结束符$因为它们是语句或表达式的天然边界。解析出错后先从输入流里丢弃 token直到遇到同步符号同时从状态栈里往外弹弹到某个状态在 GOTO 表里对某个非终结符有定义为止重新进入相对稳定的状态继续分析SYNC {$, ), ;} def recover(state_stack, tokens, i): while i len(tokens) and tokens[i][0] not in SYNC: i 1 while state_stack and state_stack[-1] not in SAFE_STATES: state_stack.pop() return iSAFE_STATES里通常放那些可以接受表达式开头的状态比如初始状态 0。这个策略不追求恢复得完全正确只求下一个错误别跟着连环报。现在拿到一个文法我第一件事永远是把-12、(23)*4、1-2-3、空输入这四类用例单独拎出来跑一遍这个习惯救过我很多次也养成了一拿到解析器就检查错误路径的毛病。希望这篇笔记能帮你把算术表达式 LR 分析这条路走通走稳。本文还有配套的精品资源点击获取 算术表达式LR分析实战：从文法设计到驱动表实现
简介一份面向编译原理学习者的C语言源码实现算术表达式的LR语法分析。程序包含词法分析器与LR分析器核心逻辑可读取用户输入的算术表达式完成移进/归约操作并验证语法正确性适合编译器设计入门及相关实验参考。压缩包仅含1个c文件大小约6KB结构精简、代码集中便于查看完整实现。目前已有156人学习浏览。该程序覆盖了上下文无关文法定义、LR分析表构建、状态栈与输入栈操作、冲突处理等关键环节。通过阅读和运行源码可直接观察单词识别、产生式归约与接受状态的执行过程也可在此基础上扩展运算优先级、错误处理或语义动作是理解自底向上语法分析的良好示例。1. 看到 byq.rar先想清楚算术表达式为什么是 LR 教学的常客byq.rar_算术表达式LR 这个压缩包名字十有八九是编译原理课程设计或个人学习项目留下的。它要解决的问题很具体输入23*4程序不能急着算得先明白乘法比加法优先输入1-2-3又必须保证减法从左往右算。这类中缀表达式的解析恰好是 LR 分析最经典的教材场景也是递归下降这类自顶向下方法做起来最别扭的地方。这篇笔记的服务对象是正在做编译原理实验、想在嵌入式设备里塞一个公式计算器、或者在公司内部实现配置表达式引擎的工程师。这篇不打算把课本里的完整理论复述一遍只讲从文法设计、分析表构造到驱动代码落地这条路怎么走以及这条路上我踩过的几个坑。2. 算术表达式文法设计优先级、左结合和左递归三个门槛2.1 中缀表达式为什么逼着你用 LR先算谁得往后看一个反直觉的结论是对23*4如果只从左往右扫描看到加号的时候根本没法决定2能不能先归约成一个结果因为后面可能还有乘号。真正的决定要等看到足够多的 token 之后才能做。递归下降的做法是进入每一个优先级层去匹配写起来不复杂但一旦表达式里出现嵌套括号、负号、多层优先级代码里的函数调用会迅速膨胀而 LR 分析器换了一个思路先不急着归约把看到的东西压进栈等看够了再一次性弹出归约。这就是移进-归约思想。「2」读进来先压栈「」读进来因为栈顶的「2」没法单独归约成完整的表达式还是压栈读到「3」时仍然先压栈因为必须等看到「*」或者「」之后才能知道「3」到底应该先和谁结合。这个再等等的策略本质上就是 LR 里的移进动作。归约动作一旦做错没有后悔药所以 LR 宁可多等一拍。这种看完右部再动手的机制让算术表达式这类优先级层级清晰的语言成为 LR 文法最合适的教学载体。2.2 用 E、T、F 三层结构把优先级写进文法算术表达式文法最常见的写法是把运算符分成两层加一层原子从上到下优先级递增E - E T E - E - T E - T T - T * F T - T / F T - F F - ( E ) F - num这个文法里E 层只处理加减法T 层只处理乘除法F 层负责数字和括号。优先级不是靠程序里的 if 判断实现的而是靠推导层次实现的。23*4的推导过程里3*4必须在 T 层先成型E 层做加法时右边已经是一个计算完整的 T不会再出现先算加法后算乘法的可能性。我一般会把这张文法表贴在代码文件头部的注释里因为分析表可以重新生成但文法一旦写错后面每一步都是错的。检查文法时有个笨办法把几个关键表达式从 F 层开始画推导树23*4、(23)*4、2*34各画一遍如果某一棵树的某个运算符深度不对说明层次划分有问题。2.3 左递归在 LR 里不是病而是左结合的解药很多写过递归下降的工程师都被《编译原理》第一章教育过要消除左递归因为 LL(1) 预测分析处理不了E - E T这种产生式。但到了 LR 这边左递归恰恰是描述左结合语义最直接的方式。1-2-3应该等于 -4 而不是 1因为减法左结合文法写成E - E - T语法树天然左倾归约顺序自然从左边开始。反过来如果把减法写成右递归形式E - T - E1-2-3 会解析成 1-(2-3)结果变成 2。这是写计算器最容易犯的错尤其当你从别的语言翻译代码时很容易顺手把产生式调个方向。我自己的经验是解析器调试时先测1-2-3如果输出不是 -4先检查减法产生式是不是写成左递归了别急着查表。LR 为什么不怕左递归因为它是自底向上的。分析器先收集终结符等累积到能构成产生式右部的程度才做归约产生式右部第一个符号是 E 还是终结符对归约动作没有影响。所以在这里左递归不需要消除你甚至可以把它当作 LR 的一项优势写进项目文档里。2.4 一元负号的坑减号和负号在词法层长一个样文法设计的第一个坑出现在负号上。-1 2里的减号和3 - 2里的减号是同一个字符前者是一元前缀运算符后者是二元中缀运算符。如果只在语法层处理常见的做法是给 F 层加一条前缀产生式F - - F这样-1整体在 F 层先成型不会干扰 T 层的乘除归约。但这条产生式会立刻带来一个移进-归约冲突栈里已经有内容时读到减号分析器无法立刻判断它是二元减法还是下一个负数的前缀。多数解析器生成工具默认选择移进这个默认行为对大部分表达式是对的但3 * -2这类场景必须单独测试。我更常用的做法是把判断挪到词法层词法扫描时看一眼前一个 token。如果前一个 token 是数字、右括号或者语法上已经归约出 E这个减号就是二元运算符否则当作一元负号处理返回一个不同的 token 类型。这样语法层保持简洁冲突也少一个来源。词法上下文判断看起来像偷懒实际是工程上最省事的方案。3. 从文法到分析表SLR 手工构造的步骤与一张能跑的表3.1 增广文法和项目集状态机的两个关键算法分析表不是凭空来的。自底向上分析器真正做的工作是在一个有限状态机上移动状态由当前语法分析进行到什么位置决定。描述这个位置的工具叫 LR 项目形如E - E · T圆点表示已看到左部哪些符号。为了让接受动作唯一先把原文法增广一条产生式比如给上面的文法加S - E。增广的意义在于分析器只有在栈顶状态遇到S - E ·这类项目时才知道整个分析结束否则归约完成后不知道什么时候该停。状态机的两个操作是闭包和转移。闭包的规则是如果某个项目里圆点右边是一个非终结符 B那么所有以 B 为左部的产生式都要以圆点在右部最前面的形式加入当前项目集。转移的规则是把圆点往右移一个符号得到新项目再对新项目求闭包。这两条规则反复迭代就能从初始状态出发生成所有状态。我用一个类比帮助理解闭包是当前正在期待一个 B所以 B 的所有可能的开头都必须预先铺好转移是真的读到了这个符号圆点可以往前挪一步。手工做的时候建议先用铅笔把所有状态列出来再填动作顺序不能反。3.2 SLR 归约规则FOLLOW 集合当看门人拿到项目集状态机之后填分析表遵循三条规则。第一项目A - α · t β里圆点右边是终结符 t那么 ACTION[状态, t] 填移进新状态由转移得到。第二项目A - α ·表示右部已经看完可以归约但归约不是所有输入符号下都能做只有当前输入符号属于 FOLLOW(A) 时才能归约这正是 SLR 开头那个 S 的含义。第三增广产生式S - E ·对应的状态里在输入$上填接受。ACTION 表 圆点后是终结符 t - 移进 圆点后是输入结束 $ - 接受 圆点后没有符号且输入在 FOLLOW 中 - 归约 GOTO 表 状态 s 在非终结符 A 上的转移FOLLOW 集合在这里非常重要。某个产生式能归约并不意味着什么输入都能归约归约会改变栈顶的非终结符而转移后的状态能否处理后续输入取决于该非终结符后面可能跟什么。算数表达式里E 后可以跟$、、)所以 E 的归约只有在这些符号出现时才有效。移进-归约冲突产生的根源是一个状态里同时出现了圆点后是终结符的移进项目和圆点后没有符号的归约项目。教科书上会用优先级声明来解决工程上一般交给工具处理但如果你手写表必须正面面对这个冲突。3.3 一张六状态的加减法表先读懂表再谈生成器完整算术表达式文法的分析表有将近二十个状态手工构造容易出错学习阶段最好先用缩小版看结构。下面这张表对应文法S - E、E - E T、E - T、T - num只支持加法和数字但 LR 表的移进、归约、接受三类动作全部齐全。状态 0 : S - · E E - · E T E - · T T - · num 状态 1 : S - E · E - E · T 状态 2 : E - T · 状态 3 : T - num · 状态 4 : E - E · T T - · num 状态 5 : E - E T ·根据 FOLLOW 集合E 后可以跟$或T 后可以跟$或。填入 ACTION 表和 GOTO 表后状态输入 num输入 输入 $GOTO EGOTO T0s3121s4acc2r(E→T)r(E→T)3r(T→num)r(T→num)4s355r(E→ET)r(E→ET)拿num num num手工跑一遍状态 0 看到 num 移进到 3读加号状态 3 归约 TGOTO 跳到 2状态 2 在加号下归约 E进入状态 1状态 1 在加号下移进到 4后面重复一轮最终状态 1 读到$接受。整个过程能看出左结合是怎么实现的第一个 num 在第二个 num 还没有完整归约前就先生成 T再被压成 E。3.4 完整版本用生成器自动产出PLY 的简单用法手工构造完整算术表达式表不是不行但状态数量多、易错效率太低。工程上更常见的做法是用一种 yacc 移植工具自动生成分析表然后把表打印出来存成字典。PLY 是 Python 生态里常见的选择文法和语义动作写在函数 docstring 里import ply.lex as lex import ply.yacc as yacc tokens (NUM, PLUS, TIMES, LPAREN, RPAREN) t_PLUS r\ t_TIMES r\* t_LPAREN r\( t_RPAREN r\) t_NUM r\d t_ignore \t def t_error(t): raise SyntaxError(fbad token {t.value!r}) lexer lex.lex() def p_expr(p): expr : expr PLUS term p[0] p[1] p[3] def p_expr_term(p): expr : term p[0] p[1] def p_term_times(p): term : term TIMES factor p[0] p[1] * p[3] def p_term_factor(p): term : factor p[0] p[1] def p_factor_num(p): factor : NUM p[0] int(p[1]) def p_factor_paren(p): factor : LPAREN expr RPAREN p[0] p[2] def p_error(p): raise SyntaxError(syntax error) parser yacc.yacc() print(parser.action) print(parser.goto)这段代码里每个p_函数的 docstring 是文法产生式函数体是归约动作。p[0]是归约后左部的值p[1]、p[2]是右部符号的值。parser.action和parser.goto就是最终的分析表可以直接打印出来看也可以转成 JSON 或二进制字典套一节里的驱动循环来用。用 bison 的-v参数也能得到类似的分析表文件跨语言项目里同样常用。4. 用驱动表跑通 LR 分析一份可运行的最小计算器实现4.1 两份核心数据结构状态栈与符号栈LR 分析器运行时维护三个栈但真正必需的只有状态栈和符号栈。状态栈保存分析状态编号符号栈保存已经归约出来的终结符和非终结符。两者必须严格同步移进时同时压入一个状态和一个终结符归约时按右部长度同时弹出再按 GOTO 压入新状态和新非终结符。状态栈比符号栈恰好多一个元素这是天然的调试断言。我在写驱动循环之前通常先把这张表存成两个字典结构约定写清楚。ACTION 表的值统一存成(shift, 目标状态)或(reduce, 产生式编号)产生式字典里再存左部和右部。这样做的好处是切换成 PLY 生成的表时只要把字典的格式对上驱动循环完全不用改。4.2 三步循环移进、归约、接受主循环只有三步但每一步的弹栈顺序都不能乱ACTION { 0: {num: (shift, 3)}, 1: {: (shift, 4), $: (accept, 0)}, 2: {: (reduce, 2), $: (reduce, 2)}, 3: {: (reduce, 3), $: (reduce, 3)}, 4: {num: (shift, 3)}, 5: {: (reduce, 1), $: (reduce, 1)}, } GOTO { 0: {E: 1, T: 2}, 4: {T: 5}, } PROD { 1: (E, (E, , T)), 2: (E, (T,)), 3: (T, (num,)), } def parse(tokens): # tokens 是已经处理过的 token 列表末尾必须带 ($, None) state_stack [0] sym_stack [] i 0 while True: state state_stack[-1] kind, value tokens[i] act ACTION[state].get(kind) if act is None: raise SyntaxError(funexpected {kind} at position {i}) kind_act, target act if kind_act shift: state_stack.append(target) # 压入新状态 sym_stack.append(kind) # 压入终结符 i 1 elif kind_act reduce: lhs, rhs PROD[target] for _ in rhs: # 右部多长就弹多少次 state_stack.pop() sym_stack.pop() top state_stack[-1] state_stack.append(GOTO[top][lhs]) sym_stack.append(lhs) elif kind_act accept: return True这段代码里移进只是把 token 压栈真正的运算发生在归约。归约时不能手写弹两次这种常量必须按照rhs的长度循环弹出否则文法一变就翻车。GOTO[top][lhs]里那个top必须是弹出的状态栈栈顶而不是任意状态这也是新手最容易写错的地方。4.3 在归约动作里顺便求值把语法分析器变成计算器语法分析只告诉你能不能接受这段输入但实际项目里我们还要它的值。做法是加一个值栈与符号栈同步压弹。归约时从值栈取出右部对应的值按产生式计算左部的值再压回去PROD { 1: (E, (E, , T), lambda vals: vals[0] vals[2]), 2: (E, (T,), lambda vals: vals[0]), 3: (T, (num,), lambda vals: vals[0]), } def parse(tokens): state_stack [0] val_stack [] i 0 while True: state state_stack[-1] kind, value tokens[i] act ACTION[state].get(kind) if act is None: raise SyntaxError(funexpected {kind} at position {i}) kind_act, target act if kind_act shift: state_stack.append(target) val_stack.append(value) # 值是词法层填进来的数字 i 1 elif kind_act reduce: lhs, rhs, fn PROD[target] n len(rhs) vals val_stack[-n:] # 取右部对应的值从左到右 del val_stack[-n:] # 弹出右部 for _ in rhs: state_stack.pop() state_stack.append(GOTO[state_stack[-1]][lhs]) val_stack.append(fn(vals)) # 归约即计算 elif kind_act accept: return val_stack[-1]测试一下234tokens [ (num, 2), (, None), (num, 3), (, None), (num, 4), ($, None), ] print(parse(tokens)) # 9归约E - E T时值栈从低到高分别是 E 的值、加号、T 的值取vals[-3:]得到的就是从左到右的顺序vals[0] vals[2]就是表达式的值。这张教学表只有加法但驱动循环不关心文法细节。把文法换成完整算术表达式文法用 PLY 或者其他生成器产出ACTION、GOTO、PROD三张表驱动代码一行都不用改。提示归约顺序本身就是左结合的体现。1-2-3如果按左结合归约第一次归约发生在1-2第二次才是(1-2)-3。所以观察归约顺序比看结果更能确认结合性对不对。5. 算术表达式 LR 分析器常见问题排查4 个最容易翻车的毛病5.1 状态栈和符号栈错位最常见的轴心错误现象程序跑到归约时报 IndexError或者解析结果严重偏离预期比如23算出 5 但23*4算出 24 而不是 14。原因状态栈和符号栈没有保持同步或者归约时弹出次数写成了常量。我见过有人把E - E T的归约写死成弹三次结果换文法后 GOTO 查出来的状态完全对不上。解决在循环开头加断言assert len(state_stack) len(sym_stack) 1状态栈始终比符号栈多一个栈底状态。归约时按len(rhs)循环弹不要手写具体数字。调试时在每次归约后打印两个栈的完整内容能很直观看出哪一步开始分叉。5.2 忘记给输入末尾补$到达不了接受状态现象表达式算到最后一个数字后程序报错说找不到对应的 ACTION或者解析完成但parse没有返回。原因LR 表的接受动作只在输入$时触发而词法层通常不会自然产生$。如果 token 列表没有结尾标记状态永远等不到接受。解决词法输出后统一在末尾追加($, None)。我习惯在测试里显式写23$这种字符串形态的输入方便肉眼检查。同时注意多 token 输入的最后一个 token 后如果有换行别把换行也当成合法 token 塞进去否则会挡住$的到达。5.3 一元负号把归约流程带崩现象-12报 syntax error但12和3-2都正常。原因文法里没有处理一元负号的产生式词法层又把-一律解释成二元减法。分析器读到最开头的-时期望的是 num实际收到减号ACTION 表里根本查不到这一项。解决两种路线。其一词法层做上下文判断前一个 token 是数字、右括号或 E 时识别为减号否则识别为负号 token。其二语法层加F - - F但要注意因此产生的移进-归约冲突生成工具默认选择移进需要单独验证3 * -2这类表达式。我的习惯是词法层处理语法层保持单纯。5.4 冲突被工具静默解决现象PLY 或 bison 构建时在终端打了一行 shift/reduce conflict 的警告但没阻止生成测试几个普通表达式也都正确于是忽略警告。换到3-2-1这类依赖左结合的用例时结果变成 2。原因冲突发生时工具默认选移进这个默认行为不是按你的语义要求来的优先级规则没写清楚时归约可能偏离预期。解决把每次生成的 warning 当错误处理。PLY 里通过yacc.yacc(debugTrue, outputloglog)把冲突明细重定向到日志bison 的-v参数也会输出.output文件查看每个状态里的冲突项目。看到冲突后要么给运算符声明优先级要么调整文法层次让冲突消失在结构设计里而不是依赖工具的默认值。6. 给 LR 分析器加一个错误定位技巧同步符号与恐慌模式完整项目里解析失败时只抛一句 syntax error 是不够用的。词法扫描时顺手给每个 token 带上行号和列号错误信息立刻能说清楚第几行第几列附近出现了什么。这一步成本极低收益却很大是排错环节的后悔药。语法层面的恢复常见做法是恐慌模式。设计一组同步符号通常选分号、右括号、结束符$因为它们是语句或表达式的天然边界。解析出错后先从输入流里丢弃 token直到遇到同步符号同时从状态栈里往外弹弹到某个状态在 GOTO 表里对某个非终结符有定义为止重新进入相对稳定的状态继续分析SYNC {$, ), ;} def recover(state_stack, tokens, i): while i len(tokens) and tokens[i][0] not in SYNC: i 1 while state_stack and state_stack[-1] not in SAFE_STATES: state_stack.pop() return iSAFE_STATES里通常放那些可以接受表达式开头的状态比如初始状态 0。这个策略不追求恢复得完全正确只求下一个错误别跟着连环报。现在拿到一个文法我第一件事永远是把-12、(23)*4、1-2-3、空输入这四类用例单独拎出来跑一遍这个习惯救过我很多次也养成了一拿到解析器就检查错误路径的毛病。希望这篇笔记能帮你把算术表达式 LR 分析这条路走通走稳。本文还有配套的精品资源点击获取