简介：一份面向编译原理学习者的C语言源码，实现算术表达式的LR语法分析。程序包含词法分析器与LR分析器核心逻辑，可读取用户输入的算术表达式，完成移进/归约操作并验证语法正确性，适合编译器设计入门及相关实验参考。压缩包仅含1个c文件，大小约6KB，结构精简、代码集中，便于查看完整实现。目前已有156人学习浏览。该程序覆盖了上下文无关文法定义、LR分析表构建、状态栈与输入栈操作、冲突处理等关键环节。通过阅读和运行源码，可直接观察单词识别、产生式归约与接受状态的执行过程；也可在此基础上扩展运算优先级、错误处理或语义动作，是理解自底向上语法分析的良好示例。
1. 看到 byq.rar，先想清楚算术表达式为什么是 LR 教学的常客
"byq.rar_算术表达式LR" 这个压缩包名字，十有八九是编译原理课程设计或个人学习项目留下的。它要解决的问题很具体：输入2+3*4，程序不能急着算，得先明白乘法比加法优先；输入1-2-3，又必须保证减法从左往右算。这类中缀表达式的解析，恰好是 LR 分析最经典的教材场景，也是递归下降这类自顶向下方法做起来最别扭的地方。这篇笔记的服务对象，是正在做编译原理实验、想在嵌入式设备里塞一个公式计算器、或者在公司内部实现配置表达式引擎的工程师。这篇不打算把课本里的完整理论复述一遍，只讲从文法设计、分析表构造到驱动代码落地这条路怎么走，以及这条路上我踩过的几个坑。
2. 算术表达式文法设计：优先级、左结合和左递归三个门槛
2.1 中缀表达式为什么逼着你用 LR：先算谁得往后看
一个反直觉的结论是：对2+3*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 判断实现的，而是靠推导层次实现的。2+3*4的推导过程里，3*4必须在 T 层先成型，E 层做加法时，右边已经是一个计算完整的 T，不会再出现"先算加法后算乘法"的可能性。
我一般会把这张文法表贴在代码文件头部的注释里，因为分析表可以重新生成，但文法一旦写错，后面每一步都是错的。检查文法时有个笨办法：把几个关键表达式从 F 层开始画推导树，2+3*4、(2+3)*4、2*3+4各画一遍，如果某一棵树的某个运算符深度不对，说明层次划分有问题。
2.3 左递归在 LR 里不是病，而是左结合的解药
很多写过递归下降的工程师，都被《编译原理》第一章教育过"要消除左递归"，因为 LL(1) 预测分析处理不了E -> E + T这种产生式。但到了 LR 这边，左递归恰恰是描述左结合语义最直接的方式。1-2-3应该等于 -4 而不是 1，因为减法左结合；文法写成E -> E - T，语法树天然左倾，归约顺序自然从左边开始。
反过来，如果把减法写成右递归形式E -> T - E，1-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 E | GOTO T |
|---|---|---|---|---|---|
| 0 | s3 | 1 | 2 | ||
| 1 | s4 | acc | |||
| 2 | r(E→T) | r(E→T) | |||
| 3 | r(T→num) | r(T→num) | |||
| 4 | s3 | 5 | |||
| 5 | r(E→E+T) | r(E→E+T) |
拿num + num + num手工跑一遍：状态 0 看到 num 移进到 3；读加号，状态 3 归约 T，GOTO 跳到 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(f'bad 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(f"unexpected {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(f"unexpected {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]测试一下2+3+4：
tokens = [ ('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，或者解析结果严重偏离预期，比如2+3算出 5 但2+3*4算出 24 而不是 14。原因：状态栈和符号栈没有保持同步，或者归约时弹出次数写成了常量。我见过有人把E -> E + T的归约写死成弹三次，结果换文法后 GOTO 查出来的状态完全对不上。
解决：在循环开头加断言，assert len(state_stack) == len(sym_stack) + 1，状态栈始终比符号栈多一个栈底状态。归约时按len(rhs)循环弹，不要手写具体数字。调试时在每次归约后打印两个栈的完整内容，能很直观看出哪一步开始分叉。
5.2 忘记给输入末尾补$：到达不了接受状态
现象：表达式算到最后一个数字后，程序报错说找不到对应的 ACTION，或者解析完成但parse没有返回。原因：LR 表的接受动作只在输入$时触发，而词法层通常不会自然产生$。如果 token 列表没有结尾标记，状态永远等不到接受。
解决：词法输出后统一在末尾追加('$', None)。我习惯在测试里显式写'2+3$'这种字符串形态的输入，方便肉眼检查。同时注意多 token 输入的最后一个 token 后如果有换行，别把换行也当成合法 token 塞进去，否则会挡住$的到达。
5.3 一元负号把归约流程带崩
现象：-1+2报 syntax error，但1+2和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(debug=True, outputlog=log)把冲突明细重定向到日志，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。这个策略不追求恢复得完全正确，只求下一个错误别跟着连环报。现在拿到一个文法，我第一件事永远是把-1+2、(2+3)*4、1-2-3、空输入这四类用例单独拎出来跑一遍，这个习惯救过我很多次，也养成了一拿到解析器就检查错误路径的毛病。希望这篇笔记能帮你把算术表达式 LR 分析这条路走通，走稳。
本文还有配套的精品资源，点击获取
