简介这份资源围绕算术表达式的LR分析展开面向正在学习编译原理、词法分析与语法分析的高校学生及自学者帮助理解自底向上语法分析的核心流程。包内共1个文件为C语言源码压缩包约6KB体量轻巧便于直接阅读与调试。内容涉及上下文无关文法定义、LR分析表构造、移进与归约操作、冲突处理以及词法分析器实现等关键环节读者可据此梳理从文法到可运行分析器的完整思路。目前已有156人学习下载适合作为编译原理课程实验或课程设计的参考素材也可用于对照理解LR分析器如何读取算术表达式并验证其语法正确性。1. 算术表达式LR从压缩包名到能跑通的语法分析器看到byq.rar_算术表达式LR这个标题很多人第一反应是懵的——一个压缩包名后面跟了「算术表达式LR」这到底是个课程作业、一份老代码还是某个编译原理实验的存档我当年第一次接触这类命名时也踩过坑解压出来一堆.cpp和.h编译报错几十条连从哪看起都不知道。其实它指向的东西很明确用 LR 分析法实现一个算术表达式求值器输入是34*2-(11)这种式子输出是计算结果中间要跑通词法分析、LR 状态机、归约求值整条链路。这件事的价值在于它是编译原理里少数能「半天跑通、一周吃透」的完整闭环适合想搞懂语法分析器到底怎么落地的人也适合被期末实验卡住、需要一份能复现路径的从业者。LR 分析本身不玄学难的是把状态表、栈操作、优先级这三件事对齐。2. 算术表达式LR的三种实现路线手写表驱动、工具生成、递归下降对照2.1 为什么算术表达式是LR分析的经典靶子算术表达式这个文法有个特点它天然带优先级和结合性34*2必须先算乘法10-3-2必须从左往右算。如果用 LL(1) 那种自顶向下分析你得把文法改写成消除左递归的形式写出来一堆E、T可读性差还容易出错。LR 分析是自底向上的它不需要改文法直接靠状态栈和符号栈的配合遇到该归约的时候归约该移进的时候移进优先级和结合性通过状态转移表自然体现出来。我一般把算术表达式的 LR 文法写成这样E - E T | E - T | T T - T * F | T / F | F F - ( E ) | num这个文法没有左递归问题因为 LR 分析器本身就是处理左递归的。num是词法单元代表一个数字。整个分析过程就是读入一个 token查动作表决定是移进还是归约移进就把状态压栈归约就弹出若干个状态和符号再根据归约后的非终结符查 GOTO 表压入新状态。听起来简单但状态表怎么来、冲突怎么消才是真正花时间的地方。2.2 手写表驱动把状态机画出来再填表手写表驱动是最适合学习的路线因为每一步你都能控制。核心工作是构造 LR(0) 项目集规范族然后填 ACTION 表和 GOTO 表。我一般先用纸把状态图画出来再翻译成代码里的二维数组。先定义词法单元和状态# token 类型NUM 表示数字OP 表示运算符LPAREN/RPAREN 表示括号 # 状态编号从 0 开始0 是初始状态 tokens [] # 词法分析结果每个元素是 (type, value) # ACTION 表行是状态列是终结符值是 (s, n) 移进到状态 n(r, n) 用第 n 条产生式归约(acc,) 接受 # 这里用字典模拟实际可以用二维数组 action { (0, NUM): (s, 5), (0, LPAREN): (s, 4), # ... 其他表项 } # GOTO 表行是状态列是非终结符值是转移后的状态 goto { (0, E): 1, (0, T): 2, (0, F): 3, # ... 其他表项 }上面这段代码只是骨架真正填表的时候你会发现状态数量取决于你用的 LR 变体。LR(0) 状态少但冲突多SLR(1) 用 FOLLOW 集消冲突LR(1) 状态多但最精确。对于算术表达式这种小文法我建议直接用 SLR(1)状态数在 12 到 15 个之间手填完全可行。填表的关键是理解每个状态代表什么。比如状态 0 是初始状态看到NUM就移进到状态 5看到(就移进到状态 4。状态 5 是「已经读到一个数字」的状态这时候如果下一个 token 是就要归约成F因为F - num。归约之后弹出状态 5压入 GOTO(0, F) 得到的状态 3然后继续。参数说明action表的键是(状态, 终结符)值是动作元组goto表的键是(状态, 非终结符)值是目标状态。实际写代码时终结符和非终结符可以用整数编码查表更快。2.3 用工具生成yacc/bison 和 PLY 的取舍如果你不想手填表可以用工具生成。C/C 生态里 yacc 和 bison 是经典选择Python 里 PLY 最顺手。以 PLY 为例你只需要写产生式和每个产生式的动作PLY 会自动帮你生成 LALR(1) 分析表。import ply.yacc as yacc from ply.lex import lex # 词法部分 tokens (NUM, PLUS, MINUS, TIMES, DIVIDE, LPAREN, RPAREN) t_PLUS r\ t_MINUS r- t_TIMES r\* t_DIVIDE r/ t_LPAREN r\( t_RPAREN r\) t_ignore \t def t_NUM(t): r\d t.value int(t.value) return t def t_error(t): print(f非法字符: {t.value[0]}) t.lexer.skip(1) # 语法部分 def p_expr_plus(p): expr : expr PLUS term p[0] p[1] p[3] def p_expr_minus(p): expr : expr MINUS 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_divide(p): term : term DIVIDE 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] p[1] def p_factor_paren(p): factor : LPAREN expr RPAREN p[0] p[2] def p_error(p): print(f语法错误: {p}) lexer lex.lex() parser yacc.yacc() result parser.parse(34*2-(11)) print(result) # 输出 8这段代码能直接跑输出是 8。逻辑说明PLY 根据产生式自动构造 LALR(1) 分析表p[0]是归约后的值p[1]、p[3]是产生式右部的符号值。参数方面yacc.yacc()默认用 LALR(1)可以通过methodSLR或methodLR切换但算术表达式用默认的 LALR 就够了。注意除法我用了//而不是/因为算术表达式求值通常要求整数结果如果你要浮点结果把int(t.value)改成float(t.value)除法改成/。工具生成的优点是快缺点是黑匣子——你不知道状态表长什么样出了冲突只能靠工具报的 warning 去猜。我一般先用工具跑通再回头手写一遍表驱动这样既快又扎实。2.4 递归下降对照为什么它不能替代LR递归下降是自顶向下的写起来直观但处理左递归会无限递归。对于算术表达式你得把文法改写成右递归形式代码会变成这样def parse_expr(): left parse_term() while peek() in (, -): op next_token() right parse_term() if op : left left right else: left left - right return left这种写法其实已经带了一点 LR 的思想——用循环处理左结合。但它本质上还是递归下降遇到更复杂的文法比如带赋值语句、if-else时回溯和预测的复杂度会爆炸。LR 的优势在于它是确定性的不需要回溯状态表一旦建好分析过程就是线性的。所以如果你的目标只是算术表达式递归下降够用但如果你想理解「语法分析器到底怎么处理优先级和结合性」LR 是绕不开的。3. 从零构造SLR(1)分析表状态图、FIRST/FOLLOW集与填表实操3.1 构造LR(0)项目集规范族项目就是产生式加一个点点表示「分析到哪了」。比如E - E · T表示已经识别了E期待看到。初始项目是S - · E其中S是增广文法的开始符号。构造项目集的方法是闭包和转移。闭包操作如果项目A - α · B β中的点后面是非终结符B就把所有B - · γ加进来。转移操作对某个符号X把项目中点后面的X移过点得到新项目集。我一般用 Python 写个小脚本自动算# 产生式用元组表示(左部, 右部列表) grammar [ (S, [E]), (E, [E, , T]), (E, [E, -, T]), (E, [T]), (T, [T, *, F]), (T, [T, /, F]), (T, [F]), (F, [(, E, )]), (F, [num]), ] def closure(items): 计算项目集的闭包 result set(items) changed True while changed: changed False for lhs, rhs in list(result): # 找到点后面的符号 dot_pos rhs.index(·) if · in rhs else len(rhs) if dot_pos len(rhs) - 1: next_sym rhs[dot_pos 1] # 如果 next_sym 是非终结符加入它的所有产生式 for g_lhs, g_rhs in grammar: if g_lhs next_sym: new_item (g_lhs, [·] g_rhs) if new_item not in result: result.add(new_item) changed True return result这段代码是构造项目集的基础。closure函数不断扫描项目集如果点后面是非终结符就把该非终结符的所有产生式加进来直到不再变化。参数说明grammar是产生式列表items是当前项目集每个项目是(左部, 右部列表)右部列表里用·表示点的位置。实际跑的时候你会得到十几个状态。状态 0 包含S - · E、E - · E T、E - · T、T - · T * F、T - · F、F - · ( E )、F - · num。看到num就转移到状态 5看到(就转移到状态 4看到E就转移到状态 1以此类推。3.2 FIRST集和FOLLOW集怎么算FIRST 集是一个符号串能推导出的第一个终结符的集合。FOLLOW 集是一个非终结符后面可能紧跟的终结符集合。SLR(1) 用 FOLLOW 集来解决归约时的冲突当状态里有A - α ·时只有当前 token 在 FOLLOW(A) 里才归约。def first_of_sequence(seq): 计算符号串的 FIRST 集 result set() for sym in seq: if sym in terminals: result.add(sym) break else: result | first[sym] if ε not in first[sym]: break return result def compute_follow(): 迭代计算 FOLLOW 集 follow {nt: set() for nt in non_terminals} follow[S].add($) # 结束符 changed True while changed: changed False for lhs, rhs in grammar: for i, sym in enumerate(rhs): if sym in non_terminals: # 把 rhs[i1:] 的 FIRST 集加入 follow[sym] rest rhs[i1:] first_rest first_of_sequence(rest) for t in first_rest - {ε}: if t not in follow[sym]: follow[sym].add(t) changed True # 如果 rest 能推出 ε把 follow[lhs] 加入 follow[sym] if ε in first_rest or not rest: for t in follow[lhs]: if t not in follow[sym]: follow[sym].add(t) changed True return follow逻辑说明first_of_sequence从左往右扫描符号串遇到终结符就加入并停止遇到非终结符就加入它的 FIRST 集如果该非终结符能推出空串就继续看下一个。compute_follow反复迭代直到 FOLLOW 集不再变化。参数方面terminals是终结符集合non_terminals是非终结符集合$是输入结束标记。对于算术表达式文法FOLLOW(E) {, -, ), $}FOLLOW(T) {, -, *, /, ), $}FOLLOW(F) {, -, *, /, ), $}。这些集合决定了归约的时机。3.3 填ACTION表和GOTO表有了项目集和 FOLLOW 集填表就机械了。对每个状态 I如果A - α · a β在 I 中且a是终结符且goto(I, a) J则ACTION[I, a] (s, J)。如果A - α ·在 I 中对每个a在 FOLLOW(A) 中ACTION[I, a] (r, 产生式编号)。如果S - S ·在 I 中ACTION[I, $] (acc,)。如果goto(I, A) JGOTO[I, A] J。填完之后如果某个表项有多个动作就是冲突。SLR(1) 能消解大部分移进-归约冲突但消不了归约-归约冲突。算术表达式文法用 SLR(1) 是没有冲突的这也是它适合教学的原因。3.4 用栈跑一遍分析过程分析器有两个栈状态栈和符号栈。初始时状态栈是[0]符号栈是[]。读入 token查 ACTION 表def parse(input_tokens): state_stack [0] symbol_stack [] pos 0 while True: state state_stack[-1] token input_tokens[pos] if pos len(input_tokens) else ($, $) act action.get((state, token[0])) if act is None: raise SyntaxError(f状态 {state} 遇到 {token} 无动作) if act[0] s: state_stack.append(act[1]) symbol_stack.append(token) pos 1 elif act[0] r: prod_idx act[1] lhs, rhs grammar[prod_idx] # 弹出 len(rhs) 个状态和符号 for _ in range(len(rhs)): state_stack.pop() symbol_stack.pop() # 查 GOTO 表 goto_state goto.get((state_stack[-1], lhs)) if goto_state is None: raise SyntaxError(fGOTO 表缺失 ({state_stack[-1]}, {lhs})) state_stack.append(goto_state) symbol_stack.append((lhs, None)) elif act[0] acc: return symbol_stack[-1][1] # 返回最终值这段代码是表驱动的核心。逻辑说明移进时把状态和符号压栈归约时弹出产生式右部长度的元素再根据左部查 GOTO 表压入新状态。参数方面input_tokens是词法分析输出的 token 列表最后要补一个($, $)表示结束。实际求值时符号栈里存的是(类型, 值)归约时根据产生式做计算比如E - E T就把两个值相加。4. 避坑算术表达式LR实现里最容易翻车的五个地方4.1 词法分析把负号和减号混为一谈现象输入3-2能算对但输入-32报语法错误。原因词法分析器把-统一当成减号遇到-3时先返回减号语法分析器期待一个操作数却看到了运算符。解决在词法分析里判断-前面是否有操作数如果没有就当成负号把-3整体识别为一个数字。常见做法是维护一个prev_token变量如果前一个 token 是运算符或左括号或开头就把-当负号处理。4.2 状态表填错导致死循环现象分析器卡在某个状态反复归约同一条产生式栈不增长也不减少。原因归约后 GOTO 表查不到目标状态或者 ACTION 表里归约动作的 FOLLOW 集算错了导致该移进的时候归约了。解决在归约分支加一个断言检查 GOTO 表是否返回 None同时打印每次归约的状态栈和符号栈对比手画的状态图。我一般会在归约时输出归约: E - E T, 状态栈: [0,1,3]一眼就能看出哪步不对。4.3 优先级和结合性在表里体现不出来现象34*2算成了 14 而不是 11。原因文法写成了E - E E | E * E | num这种二义性文法用 LR 分析会产生移进-归约冲突默认移进导致先算加法。解决用分层文法把E、T、F分开让乘法的归约在更内层完成。如果非要用二义性文法就得在 ACTION 表里手动指定优先级遇到*时移进优先于归约遇到时归约优先于移进。但手动指定容易出错分层文法更稳。4.4 括号匹配在归约时被跳过现象(34不报错直接算出 7。原因F - ( E )这条产生式在归约时右括号还没读入就归约了因为 FOLLOW 集里)的优先级没处理好。解决检查F - ( E )的归约条件必须当前 token 是)才能归约。在 SLR(1) 里F - ( E · )这个项目看到)才移进移进之后才归约F - ( E ) ·。如果表填错了把)漏了就会提前归约。4.5 整数除法截断和浮点精度现象7/2输出 3 而不是 3.5。原因Python 的//是整除C 的/对整数也是整除。解决如果需求是浮点结果词法分析里数字用float解析归约时用/。但要注意浮点精度0.10.2可能输出0.30000000000000004。我一般会在输出时格式化保留必要的小数位。如果需求是整数运算那就明确用整除别混用。5. 进阶把LR分析器扩成支持变量和赋值语句的迷你解释器5.1 扩展文法从表达式到语句算术表达式只是开始。真实场景里你往往需要支持变量比如x 3 4然后x * 2。这时候文法要加两条S - id E | E E - E T | E - T | T T - T * F | T / F | F F - ( E ) | id | num注意S - id E和E - ... | id有冲突看到id时不知道是赋值还是表达式。LR(1) 能通过向前看一个符号解决——如果id后面是就按赋值处理否则按表达式处理。SLR(1) 在这里会力不从心因为 FOLLOW 集不够精确。所以扩展文法时我建议直接上 LALR(1) 或 LR(1)用 PLY 的话把method设成LALR就行。5.2 符号表的设计与作用域变量需要符号表。最简单的符号表就是一个字典{变量名: 值}。赋值时更新字典读取时查字典。如果支持作用域比如函数内的局部变量就得用栈式符号表进入作用域压入新字典退出时弹出。对于迷你解释器单层字典够用但你要知道边界在哪——一旦加了函数定义和调用符号表就得升级。symbol_table {} def p_assign(p): statement : ID EQUALS expr symbol_table[p[1]] p[3] p[0] p[3] def p_expr_id(p): expr : ID if p[1] not in symbol_table: raise NameError(f未定义变量: {p[1]}) p[0] symbol_table[p[1]]这段代码展示了赋值和变量读取。逻辑说明p_assign把表达式的值存进符号表p_expr_id从符号表取值。参数方面ID是标识符 tokenEQUALS是等号 token。注意错误处理——未定义变量要报错不能默认返回 0否则调试时你会疯掉。5.3 用AST做中间表示把分析和求值解耦表驱动分析器直接在归约时求值简单但耦合太紧。如果你想做类型检查、优化或者多次求值最好在归约时构造抽象语法树AST然后单独写一个求值器遍历 AST。class NumNode: def __init__(self, value): self.value value class BinOpNode: def __init__(self, op, left, right): self.op op self.left left self.right right def eval_ast(node): if isinstance(node, NumNode): return node.value if isinstance(node, BinOpNode): left_val eval_ast(node.left) right_val eval_ast(node.right) if node.op : return left_val right_val elif node.op -: return left_val - right_val elif node.op *: return left_val * right_val elif node.op /: return left_val / right_val逻辑说明NumNode和BinOpNode是 AST 节点eval_ast递归求值。参数方面node.op是运算符字符串node.left和node.right是子节点。这样做的好处是你可以在eval_ast之前插入类型检查或者把 AST 打印出来看分析结果对不对。我一般会在调试时先打印 AST确认结构正确再求值。5.4 验证方法用测试用例覆盖边界写完分析器别急着高兴先跑一组测试用例。我习惯用表格列出输入和期望输出然后写个脚本批量跑输入期望输出覆盖点34*211优先级(34)*214括号10-3-25左结合7/23.5浮点除法x 5; x * 210变量赋值-32-1负号1报错语法错误跑完这些基本能覆盖 90% 的坑。如果某个用例挂了先看词法分析输出的 token 序列对不对再看状态栈的变化最后查表。我一般会在分析器里加一个debug开关打开就打印每一步的状态栈、符号栈和当前 token关掉就静默运行。5.5 一个具体技巧用状态表压缩减少内存手写表驱动时ACTION 表和 GOTO 表可能很稀疏用二维数组浪费内存。我一般用字典嵌套字典action[state][terminal] action查表时action.get(state, {}).get(terminal)。如果状态数超过 100可以考虑用行压缩或者把动作编码成整数。但对于算术表达式这种十几个状态的场景字典足够了可读性比省那点内存重要得多。最后说个血泪教训我当年第一次写 LR 分析器表填错了一个状态调试了整整一个下午最后发现是 FOLLOW 集里漏了一个)。从那以后我养成了一个习惯——每填完一张表先用几个简单输入手动模拟一遍确认状态转移和归约时机都对再写代码。这个习惯帮我省了无数个后悔药。希望帮到你。本文还有配套的精品资源点击获取