简介压缩包内为一份C语言实现的算术表达式LR语法分析器源码面向编译原理学习者、软件工程专业学生及对自底向上语法分析感兴趣的开发者。程序以单个byq.c文件承载词法分析与LR分析核心逻辑根据算术表达式文法E→ET|T等构建分析表完成读入表达式、词法识别、移进/归约及结果接受等流程。资源共1个文件为C源码压缩包大小约6KB结构紧凑适合直接阅读和二次调试。文件已获得156人次学习浏览常用于编译原理课程设计或实验参考。通过研读这份源码可清晰了解LR(0)/SLR类分析表的构造方法、移进-归约冲突的常见处理思路以及词法分析器与语法分析器如何衔接配套的标识符与运算符处理细节、状态栈和符号栈设计也便于与教材理论对照。对想将LR分析理论落地为可运行程序的读者而言这份代码提供了简洁但完整的示例。1. 算术表达式 LR解压即用也得先懂它要解决什么编译原理课设里最容易被低估的实验就是算术表达式 LR 分析器。它看起来只是识别 123、算个结果可真正动手才发现一个 byq.rar 解压出来主循环不过几十行真正决定对错的是那张 LR 分析表。表上填错一个动作程序不报错而是把 123 算成 9——这种翻车方式比崩溃更难排查。这篇就讲清楚算术表达式 LR 分析器从文法设计、分析表生成到主循环实现的完整路径以及那些不会写进报告的坑。适合正在做编译原理实验、需要独立完成 LR 分析实现的人也适合想用手写解析器替换正则表达式做小型规则引擎的从业者。2. 为什么算术表达式选 LR从 LL 的左递归困境到 LR 的归约时机2.1 算术表达式的文法设计一条产生式决定先乘除还是先加减拿到需求别急着写代码先写文法。算术表达式最经典的错误做法是直接来一条E - E E | E * E | ( E ) | num这条文法能生成所有合法表达式但它有二义性。12*3 既能按(12)3 归约也能按 1(23) 归约。LR 分析表构造时会在某个状态里同时出现移进和归约两个动作这个冲突不解决表就建不出来。即使你用手工填表的方式绕过冲突分析器也会在某些输入上给出违背优先级的结果。正确的写法是按运算优先级分层把乘法放在更深的非终结符上E - E T | E - T | T T - T * F | T / F | F F - ( E ) | numE 负责加减T 负责乘除F 负责括号和数字。LR 分析器在处理 12*3 时会先把 2 移进栈里看到 * 之后继续移进 3直到 F - num 和 T - T * F 完成归约最后才轮到 E - E T。这个乘法先归约、加法后归约的顺序本质上是由文法层级的深度决定的不是靠算符优先级表也不是靠运行时判断。这里还要注意左递归。1-2-3 按数学约定应该是 (1-2)-3 的左结合结果文法写成 E - E - T 正好是左递归。左递归在 LL 分析器里是死路递归下降会无限展开而 LR 分析器是移进-归约机制状态栈天然消化左递归。这也是为什么很多课设指定 LR让你体会左递归文法在 LR 里不仅合法还精确表达左结合性。2.2 ACTION 与 GOTO 表为什么说是一张表的两半LR 分析表初看是两张表ACTION 表按终结符查GOTO 表按非终结符查。但实际实现里我常把它们合成一个二维表对象行是状态编号列是符号符号分为终结符和非终结符两类。查表时拿到什么符号就走什么语义所以它更像一张表的两半。ACTION 表的格子只可能有四种内容s 移进。把当前输入符号和状态 n 压入栈输入指针后移。r 归约。用第 n 条产生式归约弹出右部长度个状态再查 GOTO 压入左部状态。acc接受。只有输入指向结束符 $ 且栈顶状态含增广文法的接受项目时才出现。空语法错误直接报错。GOTO 表只在归约完成后被查一次用来决定归约出的非终结符应该进入哪个状态。我见过不少实现把 ACTION 和 GOTO 用不同的数据结构存结果主循环里要写两套查表逻辑反而容易出问题。统一成table[state][symbol]后主循环变成一次查表、一个 switch。举一个实际格子的例子。在状态 2识别完 T 的状态遇到 时预期动作应该是 r3用 E - T 归约还是 s移进 这要查 FOLLOW(E) 是否包含 。包含所以 r3 合法但此时表达式可能是 123 的中间状态归约完才能继续匹配下一个 。这个决策就是下一节讲的 SLR(1) 核心。2.3 SLR(1) 与 LR(0) 的取舍FOLLOW 集合是归约动作的后悔药LR(0) 分析表是最朴素的版本只要某个状态里有一个归约项目它就在所有终结符列上都填 r。比如状态 3 是 T - F.它会在 、*、(、$ 甚至任何符号上都填 r3这必然与状态里可能存在的移进项目打架产生大量移进-归约冲突。算术表达式文法直接用 LR(0) 是建不出无冲突表的。SLR(1) 的改进很朴素归约动作只在下一个输入符号属于产生式左部非终结符的 FOLLOW 集合时才填 r。也就是说FOLLOW 提供了这个符号后面到底可能跟什么的信息把 LR(0) 那批无脑的 r 动作过滤掉一部分。这个过滤是手写分析器最容易偷懒又最容易出错的地方。对上面的算术表达式文法三个关键非终结符的 FOLLOW 集合是非终结符FOLLOW 集合E{ $, , -, ) }T{ $, , -, *, /, ) }F{ $, , -, *, /, ) }有了这套集合像状态 3T - F.就只在遇到 $、、-、*、/、) 时做 r6遇到 num、其他符号时就不会乱归约。这里的边界情况是右括号E 的 FOLLOW 里有 )所以 F - ( E ) 归约完成后遇 ) 才允许按 E 相关产生式继续处理如果 FOLLOW 漏了 )带括号的表达式会在右括号处报无动作错误。那 SLR(1) 够不够用对这个算术表达式增广文法够。因为它本来就没有需要向前看多个符号才能解决冲突的语法结构。如果你的课设要求识别复杂的函数调用或类型声明SLR(1) 可能在某些状态上仍然出现冲突那就需要换 LR(1) 或 LALR(1)。但只要范围锁死在四则运算加括号SLR(1) 是最省力且正确的选择。3. 把 LR(0) 自动机跑起来项目集闭包与 GO 转移的计算3.1 产生式编号先给规则编号后面所有表都靠编号说话分析表里的 r 动作不能写用 E - ET 归约这种字符串太占空间也不好查。标准做法是给每条产生式一个编号主循环里用整数索引。# productions[i] (左部, 右部符号元组) # 0 号是增广产生式用于触发接受动作 PRODUCTIONS [ (E, (E,)), # 0: S - E (E, (E, , T)), # 1 (E, (E, -, T)), # 2 (E, (T,)), # 3 (T, (T, *, F)), # 4 (T, (T, /, F)), # 5 (T, (F,)), # 6 (F, ((, E, ))), # 7 (F, (num,)), # 8 ] TERMINALS {, -, *, /, (, ), num, $} NONTERMINALS {E, T, F}注意这里把num当做一个终结符而不是把每个数字都当终结符。词法层面早就把连续数字归约为num了如果分析器直接面对 1、2、3 这种原始字符表会膨胀到没法看。这也是很多课程实现里一开始没想明白的地方LR 分析器处理的是 token 流不是字符流。产生式编号的含义在后续代码里会反复出现。r8表示用编号 8 的产生式 F - num 归约r3表示用 E - T 归约。如果你在 DEBUG 时看到r3却想不起来是哪条规则说明编号表没放在手边建议把这组编号常量直接打印到日志里。3.2 项目集闭包点号在非终结符前面时把它的产生式全部拉进来LR(0) 自动机的状态不是分析到哪一步而是一组可能正在进行的产生式分析。每个项目写作[A - α · β]点号左边表示已经看到的部分右边表示还没看到的部分。项目集闭包的作用是当点号后面是非终结符时要把这个非终结符的所有产生式都作为新的项目加进来并循环处理。def closure(items, productions, nonterminals): items set(items) queue list(items) while queue: lhs, rhs, dot queue.pop() if dot len(rhs) and rhs[dot] in nonterminals: symbol rhs[dot] for prod_lhs, prod_rhs in productions: if prod_lhs symbol: new_item (prod_lhs, prod_rhs, 0) if new_item not in items: items.add(new_item) queue.append(new_item) return items项目的表示是(左部, 右部元组, 点号位置)。以增广产生式起点为例初始项目集是{(E, (E,), 0)}闭包后变成E - ·E以及 E 的三个产生式、T 的三个产生式、F 的两个产生式总共 9 个项目。这就是状态 0。闭包里有个特别容易漏的点处理完一个非终结符后新加入的项目可能又引入新的非终结符比如 F - ·( E ) 不会引入但 E - ·ET 和 E - ·T 会继续引入 T 和 F 的项目。所以闭包必须用 while 队列循环不能只扫一遍初始集合。我在初版实现里犯过只循环一次的错结果状态 0 缺了 T 和 F 的全部产生式分析表直接少了几行凡是需要识别乘除法的地方全部报错。3.3 GO 转移与 ACTION/GOTO 表shift、reduce、accept 是怎么确定的GO 函数处理的是点号右移。从项目集 I 出发读入符号 X凡是点号后面正好是 X 的项目都把点号右移一位然后对新项目集做闭包。代码很直接def go(items, symbol, productions, nonterminals): next_items set() for lhs, rhs, dot in items: if dot len(rhs) and rhs[dot] symbol: next_items.add((lhs, rhs, dot 1)) return closure(next_items, productions, nonterminals)接着从初始状态开始做 BFS把每个项目集编成状态号记录 GO 边。等状态全部生成再扫一遍所有状态按三条规则填表对终结符 a如果go(I, a)得到状态 j则action[i][a] (s, j)。对归约项目[A - α ·]如果 A 不是增广左部则对 FOLLOW(A) 里的每个终结符 a填action[i][a] (r, 产生式编号)。对接受项目[E - E ·]填action[i][$] (acc,)。def build_table(productions, terminals, nonterminals, follow): start_item (E, (E,), 0) I0 closure({start_item}, productions, nonterminals) states [I0] state_id {frozenset(I0): 0} action {} goto {} queue [I0] while queue: items queue.pop() i state_id[frozenset(items)] for lhs, rhs, dot in items: if dot len(rhs): symbol rhs[dot] j go(items, symbol, productions, nonterminals) if frozenset(j) not in state_id: state_id[frozenset(j)] len(states) states.append(j) queue.append(j) if symbol in terminals: action[(i, symbol)] (s, state_id[frozenset(j)]) else: goto[(i, symbol)] state_id[frozenset(j)] else: if lhs E: action[(i, $)] (acc,) else: prod_idx productions.index((lhs, rhs)) for a in follow[lhs]: slot action.get((i, a)) if slot is not None: print(f冲突: 状态{i} 遇到 {a} 已有{slot}新增 r{prod_idx}) else: action[(i, a)] (r, prod_idx) return action, goto注意一个细节ACTION 填 s 时如果同一格已经填了 r那就是正宗的移进-归约冲突。上面代码先打冲突日志再继续这是排错的好习惯。SLR(1) 的 FOLLOW 过滤就是在填 r 之前用follow[lhs]挡了一道如果冲突仍然存在要么文法需要改写要么 SLR(1) 不够用。对算术表达式文法调整好层级和括号后这个构建过程不会打印任何冲突。4. 手写算术表达式 LR 分析器状态栈、符号栈和输入指针怎么配合4.1 词法 token 化数字必须变成 num否则表没法查LR 主循环吃的是 token 流。我见过最省事的方案是把每个字符当 token但这样 123 会被当成 1、2、3 三个 token分析器完全不认。所以先做一层薄薄的词法转换def lexer(text): tokens [] i 0 while i len(text): ch text[i] if ch.isspace(): i 1 elif ch.isdigit(): while i len(text) and text[i].isdigit(): i 1 tokens.append(num) elif ch in -*/(): tokens.append(ch) i 1 else: raise ValueError(f非法字符: {ch!r}) tokens.append($) return tokens这段代码把连续数字合并为一个num末尾补$作为输入结束符。没有这个$LR 主循环的 acc 动作永远没有触发条件。词法器本身不做数值计算它只负责分类真正算 12 的值得在归约动作里做或者等语法树建好后再求值。4.2 主循环数据结构状态栈和符号栈必须同步压弹LR 分析需要两个栈状态栈保存当前所在状态编号符号栈保存已经入栈的终结符或非终结符。它们是完全同步的每次压入符号的同时压入对应状态每次弹出右部长度个符号时也同时弹出相同数量的状态。只维护一个栈是常见的偷懒做法但一旦归约多层嵌套状态和符号对不上GOTO 查表立刻错。def parse(tokens, action, goto): state_stack [0] symbol_stack [$] i 0 while True: state state_stack[-1] a tokens[i] act action.get((state, a)) if act is None: raise SyntaxError(f状态{state} 遇到 {a} 无动作栈: {symbol_stack}) kind, val act if kind s: state_stack.append(val) symbol_stack.append(a) i 1 elif kind r: lhs, rhs PRODUCTIONS[val] print(f归约: 用 {lhs} - { .join(rhs)}) for _ in range(len(rhs)): state_stack.pop() symbol_stack.pop() top state_stack[-1] state_stack.append(goto[(top, lhs)]) symbol_stack.append(lhs) elif kind acc: return True主循环的逻辑就四步查表、移进、归约、接受。移进时输入指针 i 前进num或运算符被压入符号栈归约时右部符号和状态一起弹出再根据 GOTO 决定新的状态接受时直接返回。整个循环里最容易被忽略的是state_stack.pop()的次数必须等于len(rhs)而不是固定弹 1 次或弹 2 次——比如 F - ( E ) 右部长度 3就要弹 3 对。4.3 归约动作的细节弹出多少个状态、推什么符号、GOTO 往哪走归约的本质是把右部符号换回左部非终结符。比如分析 12*3栈里已经积累了num * num归约 F - num 后变成F * num再归约 T - T * F 变成T。每做一次归约符号栈右端长度等于右部符号数的内容被替换成左部非终结符而状态栈右端同样长度的内容被丢弃然后查 GOTO 表给新的非终结符找下一个状态。有一个很好的自查方法归约前后状态栈的栈顶变化。归约前栈顶是看到右部最后一个符号之后进入的状态归约后栈顶变成看到左部非终结符之后进入的状态。如果 GOTO 表填错这里的状态跳转会直接落在一个没有对应动作的格子上表现形式就是前面几个表达式都正常换了个括号位置就报无动作。parse函数里我留了一行调试打印。实际跑课设时强烈建议在移进和归约时都打印状态栈和符号栈一行行对着纸面上的分析过程看。LR 分析器是确定性自动机每一步都唯一打印出来的轨迹就是最好的排错依据。5. 算术表达式 LR 的四个高频踩坑点从表构造错到栈回溯5.1 二义性文法导致的移进-归约冲突现象自动建表时打印出冲突: 状态 X 遇到 已有 sY新增 rZ而且每次都发生在加法或乘法的归约项目上。原因文法没有分层比如直接写了 E - E E | E * E。状态里既有 E - E ·E 这种想继续移进的项目又有某个已经完成的归约项目同一个 列上既要求 s 又要求 r表没法填。SLR(1) 的 FOLLOW 过滤也救不了因为 FOLLOW(E) 本身就包含 和 *。解决回到文法分层把 E、T、F 三个层级写清楚。改完文法再重新生成项目集冲突自然消失。不要试着在填表时手动选择保留 s 删掉 r来绕过那等于放弃了优先级定义结果必然在某些嵌套表达式上算错。5.2 归约时状态栈弹出数量算错现象分析 12 时在归约 E - ET 后下一查表动作变成 None报 状态 X 遇到 $ 无动作。或者更隐蔽程序不报错但状态栈和符号栈长度对不上最终越界。原因归约弹栈时只弹了 1 个或者干脆用len(rhs) - 1。E - ET 的右部有三个符号必须弹 3 个状态如果只弹 1 个状态栈的栈顶还是处理 之前的状态查 GOTO 时自然找不到合理目标。解决严格写for _ in range(len(rhs))别在循环里写死数字。这个方法要求PRODUCTIONS里每条产生式的右部元组长度准确尤其是 F - ( E ) 这种带括号的右部长度是 3不是 1。5.3 增广文法缺失导致最后一步悬空现象整个表达式分析完成后程序没有走 acc而是继续查表最后报错或者接受条件被误写成某个非终结符归约完就返回导致输入串没消费完也被接受。原因LR 分析器需要判断整个输入串已经归约成初始符号并且输入指针停在 $。没有增广产生式 S - E就没有一个独立的接受项目来标记这个状态很多退而求其次的做法是检查符号栈是否只剩 E但这时输入可能还剩未消费的 token。解决在产生式列表开头加一条(E, (E,))编号 0。接受动作只挂在项目E - E ·上当状态栈顶是这个接受状态且当前输入是 $ 时才返回 acc。代码里已经处理if lhs E时填(acc,)。5.4 ACTION 表的 r 动作漏填 FOLLOW 边界现象普通表达式全对唯独1(23)在右括号处报无动作或者12*3的结果变成 9等于把优先级算反了。原因这其实是两个表象。第一个表象是 FOLLOW(E) 漏了)导致在含括号表达式里E 相关归约项目遇到右括号没有 r 动作。第二个表象是把E - T的 r 动作填到了*列上而*不在 FOLLOW(E) 里归约发生得太早乘号被留在后面加法反而先完成。解决每填一条 r 动作都回头对着 FOLLOW 表核对目标列。把第 2 章那张 FOLLOW 集合表打印出来贴在代码旁边尤其注意 E 的 FOLLOW 不含*和/T 的 FOLLOW 才包含它们。遇到右括号边界时确认所有相关非终结符的 FOLLOW 里都有)。5.5 测试用例只覆盖加法漏了优先级和结合性现象123、12都正确然后自信满满交上去老师用一个12*3或者1-2-3直接判错。原因加法满足交换律和结合律很多错误在纯加法场景下看不出来。比如乘法优先级填错12*3会算成 9结合性填错1-2-3会算成 2也就是按右结合处理了。只测加法相当于只验证了部分移进路径。解决固定一组覆盖优先级、结合性、括号嵌套的错误用例每次改动完表结构都跑一遍。具体用例清单放在最后一章组内每改一次代码就跑全套。6. 验证 LR 分析器是否真的对从最小表达式到错误输入的测试矩阵验证一个 LR 分析器光看能不能跑远远不够。我自己的固定做法是维护一张测试表每次改完表生成逻辑或主循环都跑一遍表挂在项目目录里当回归用例。输入期望行为验证重点12*3接受归约顺序先 T 后 E乘法优先级(12)*3接受括号内先归约括号作用域1-2-3接受结果为 -4 对应左结合左结合性12*(3-4)/5接受混合优先级和括号多层状态跳转12语法错误连续运算符检测(12语法错误未闭合括号12)语法错误多余右括号空串或只含空格语法错误起始状态处理跑测试时注意看两点错误输入必须抛异常而不是静默返回合法输入的状态栈深度变化曲线要平滑不能出现某次归约后栈长度骤减为 0 又突然增长。调完功能后还可以加一个进阶验证打印完整分析轨迹手动模拟一遍 12*3。从状态 0 出发依次经历移进 num、移进 *、移进 num、连续三次归约最后回到接受状态。这个过程每一步查的格子都能在分析表里找到对应位置。如果轨迹和教科书例子完全一致分析器基本可信。我后来做这类分析器养成的习惯是先写测试矩阵再写主循环最后才写表生成。因为表生成的错误太隐蔽没有回归用例兜底很容易改一处坏一处。有一回我为了给-和/单独建状态把 GOTO 表的一个键写错加法测试全过遇到除法就翻车。查了一下午最后就是靠测试矩阵里的12*(3-4)/5定位到状态 11 的/列。从那以后任何改动都先跑这组用例再提交。这个习惯也推荐给你希望帮到你。本文还有配套的精品资源点击获取