编译原理课设实战：词法分析、LL(1)与LR(1)分析器完整实现解析

简介这是一份面向编译原理课程设计与实验的完整源码包内含词法分析器、LL1语法分析器和LR1语法分析器三个独立模块适合正在学习编译原理、需要完成课程设计或对照实现的学生与开发者。资源共五十二个文件压缩包约六点八八兆字节以CPP源文件、H头文件、Makefile构建脚本为主辅以PDF说明文档、HTML前端界面、输入输出测试用例、GIF演示截图等目录中还保留了项目说明与许可证文件结构清晰便于直接编译运行或二次修改。词法分析部分支持识别关键字、标识符、运算符、分界符、无符号数并额外支持字符字符串和行间注释同时带有图形化前端便于观察分析过程语法分析部分覆盖自顶向下与自底向上两类常用算法可作为理解LL(1)、LR(1)分析流程的参考实现。目前已有千余人学习下载适合作为课程设计参考配套材料也能帮助初学者快速构建完整的编译实验框架。1. 词法分析器不是热身那么简单多数人把词法分析当成编译原理里最简单的一环实际上它决定了后续语法分析器能看到什么样的 Token 流。你写的正则、手写的状态机、最长匹配策略都会直接影响 LL(1) 和 LR(1) 的输入质量。这个实验包里把词法分析器、LL(1) 分析器、LR(1) 分析器三样东西串在了一起且词法部分还支持字符/字符串和行间注释明显不是老师说的“热身实验”能糊弄完的。我拆完这套代码后最大的感受是很多“很简单”的实验真正的成本不在算法本身而在边界处理和前端展示。下面的内容会按词法、LL(1)、LR(1) 的顺序逐层展开最后给你一套能把三个模块串起来跑的验证方案适合正在做课程设计或者想补全编译器前端实现细节的人。2. 词法分析器状态机、Token类别与注释处理2.1 从正则到状态枚举这里没必要建NFA/DFA很多教材先用正则表达式描述词法规则再用子集法构造 DFA但实验代码里一般不会真的去构建自动机。原因很简单一个小型语言的词法规则有限直接手写状态枚举效率最高。比如关键字if、else和标识符i之间用一条“字母开头后跟字母数字”的状态迁移就能覆盖。这个实验包的词法部分要求识别五类基本 Token关键字、标记符通常指标识符、运算符、界符和无符号数。后来又增加了字符/字符串和行间注释。你会发现一旦加了注释和字符串状态机就开始复杂了。因为字符串里面可以出现运算符、界符甚至关键字如果状态设计得不够细就会出现“把字符串内容当普通单词切出去”的 bug。2.2 关键字与标识符的识别最长匹配和查表谁先谁后我一般实现的时候会先做“读入整个合法标识符”再去查关键字表。反过来先查关键字再回退会出错因为ifx不是一个合法关键字但它必须是合法标识符。下面这段 Java 风格的状态枚举是这套实验里最核心的判别逻辑之一。// 伪代码从输入流中识别标识符或关键字 public Token nextToken() { // 跳过空白和注释注释部分在后面实现 // 读入当前字符ch if (Character.isLetter(ch)) { StringBuilder sb new StringBuilder(); while (Character.isLetterOrDigit(ch) || ch _) { sb.append(ch); ch readChar(); // 前进一个字符 } // 回退一个字符保证主循环不会消费掉下一个Token的首字符 retract(); String word sb.toString(); // keywordSet 是预置的 HashSet if (keywordSet.contains(word)) { return new Token(TokenType.KEYWORD, word); } else { return new Token(TokenType.IDENTIFIER, word); } } }关键点在于retract()。词法分析器通常需要一个“超前读一个字符”的能力但读到非字母数字字符时不能直接丢掉要退回输入流。没有回退机制的词法分析器很难处理ab这样的输入因为读完a后已经读到了如果不回退就永远丢失了。关键字查表用HashSet即可不要用HashMap放多余信息但要注意大小写敏感性实验要求里如果区分大小写If就是标识符而不是关键字。2.3 无符号数与运算符判定顺序决定成败无符号数常见格式是123、3.14、.5、2e10。状态转移时要注意小数点可能出现在数字中间也可能出现在数字开头。如果在读数字时遇到.就直接当作运算符那3.14会被切成3、.,14三个 Token显然不对。正确处理是遇到.后还要看下一位是不是数字是数字就继续走小数状态。运算符和界符相对简单但有两个坑一是多字符运算符比如、、。我建议在处理每个运算符时先尝试两字符匹配再退回单字符匹配。二是界符和运算符的定义不要重叠。比如括号算界符算运算符实验中给的表格通常已经分好类自己扩展时要保持TokenType不产生歧义。下面这个表格是这套实验里典型的状态与输入映射关系我在实现时直接把它翻译成了状态迁移条件当前状态输入字符下一状态/动作备注START字母IDENTIFIER继续累积IDENTIFIER字母/数字/_IDENTIFIER最长匹配IDENTIFIER其他字符回退并查关键字表产生TokenSTART数字NUMBER_INT整数部分NUMBER_INT数字NUMBER_INT累积NUMBER_INT.NUMBER_FLOAT还需看下一位NUMBER_FLOAT数字NUMBER_FLOAT小数部分START/尝试注释注意力与除法区分DIVISION/LINE_COMMENT行间注释LINE_COMMENT换行START注释结束2.4 字符、字符串与行间注释扩展功能后的真实边界实验包额外支持了字符/字符串和行间注释这属于加分项但也最容易写崩。字符是单引号括起的一个字符字符串是双引号括起的一串字符。它们内部允许出现、、空格甚至关键字所以这些符号必须全部在“字符串状态”里被吞掉不能进入主判定分支。我实现时会为字符串单独维护一个STRING状态读入后进入该状态直到遇到下一个结束。如果字符是\则还要跳过下一个字符避免转义引号导致状态错误。注释同理读入//后进入LINE_COMMENT状态遇到换行才回START。要注意的是//和/的冲突读入/后必须再多读一位如果是/就按注释处理否则是要回退的。这里最容易出的 bug 是读完//后忘了回退导致第二个/被丢掉。提示词法分析器的单元测试要覆盖“字符串里有双引号”和“注释里有关键字”这两类用例很多同学在期末考试和课程设计验收时就是挂在注释和字符串的边界上。3. LL(1)分析器First集、Follow集与预测分析表的工程实现3.1 文法表示与预处理先消除左递归LL(1) 分析器要求文法不含有左递归并且同一非终结符的多个候选式不能有公共左因子。实验里通常给的算术表达式文法已经做过处理比如E - E T | T要先改成E - T E、E - T E | ε的形式。但你自己写代码时不能假设输入文法都是现成的一般要先做一遍消除左递归和提取左因子。我在这里用 Python 语言实现因为实验里用 Java/C 写逻辑比较啰嗦而 Python 的字典和集合操作非常适合构建 First/Follow 集。文法我用一个字典表示键是非终结符值是产生式右侧的符号列表列表。例如E - T E就记作{E: [[T, E\]]}E - ε记作[ε]。一个容易忽略的点是空串 ε 的表示。不要把None混在符号表里否则计算 First/Folloow 集合时总会忘记判断空串。统一用字符串ε在所有算法里都检查它这样最不容易出错。3.2 迭代法求First和Follow现场手写比库函数可靠网上有现成的 First/Follow 计算库但它们往往和你的数据结构不匹配。手写迭代法稳定性更高因为它们本质上是固定点迭代不断往集合里加元素直到不再变化为止。下面这个求 First 集的函数就是典型的闭包式写法。def compute_first_sets(grammar, terminals): # grammar: {E: [[T, E\]], E\: [[, T, E\], [ε]], ...} first {nt: set() for nt in grammar} changed True while changed: changed False for nt, prods in grammar.items(): for prod in prods: # 空产生式直接加 ε if prod [ε]: if ε not in first[nt]: first[nt].add(ε) changed True continue # 逐符号累积 for symbol in prod: if symbol in terminals: if symbol not in first[nt]: first[nt].add(symbol) changed True break # 遇到终结符该产生式结束 else: # 非终结符先把它的 First 并进来但 ε 特殊处理 before len(first[nt]) first[nt] | (first[symbol] - {ε}) if len(first[nt]) ! before: changed True # 如果该非终结符没有 ε则不再向后传播 if ε not in first[symbol]: break # 如果循环结束都没有 break说明整串可空需要给当前非终结符加 ε else: if ε not in first[nt]: first[nt].add(ε) changed True return first这个函数的关键在于break的位置遇到终结符立即停止遇到非终结符时先并入其 First 集合中除 ε 的部分如果该非终结符不能推出 ε也停止如果整条产生式所有符号都能推出 ε则最后通过for...else把 ε 加入当前非终结符。这样写出来逻辑清晰调试时也容易加print观察迭代过程。Follow 集的计算更依赖产生式的右部位置。对A - α B β这种形式B 的 Follow 集合要加入 β 的 First 集合除 ε。如果 β 可空那么还要加入 A 的 Follow 集合。这里我建议对所有产生式遍历直到不再变化而不是用递归函数。递归方法容易陷入左递归导致死循环。非终结符First 集Follow 集E{(, id}{), $}E{, ε}{), $}T{(, id}{, ), $}T{*, ε}{, ), $}F{(, id}{*, , ), $}上面是经典算术表达式文法的结果。注意 Follow 集里一定包含输入结束符$这是很多实现容易漏掉的一点。另外Follow 集对开始符号要预先加入$否则预测分析表在输入结束时会找不到入口直接报语法错误。3.3 预测分析表构建与驱动用栈和动作表复现课本流程有了 First 和 Follow预测分析表的填充规则是对产生式A - α如果a ∈ First(α)则M[A, a]填入该产生式如果α可空那么对b ∈ Follow(A)在M[A, b]填入该产生式。这个规则听起来简单但代码实现时一定要注意顺序先填 First 部分再填 Follow 部分。如果同个表格单元先后被不同产生式填充就说明文法不是 LL(1) 的需要报冲突。下面我给出一段 LL(1) 预测分析的驱动代码输入是 Token 序列输出是匹配成功与否def ll1_parse(parse_table: dict, start_symbol: str, token_stream: list): # parse_table: {(nt, terminal): production_index} stack [$, start_symbol] token_stream.append($) # 输入结尾 pos 0 while len(stack) 1: top stack[-1] current token_stream[pos] if top current: stack.pop() pos 1 elif top in grammar_terminals: print(f错误栈顶终结符 {top} 与输入 {current} 不匹配) return False else: key (top, current) if key not in parse_table: print(f错误非终结符 {top} 在输入 {current} 下无产生式) return False prod parse_table[key] # 例如 [E, [T, E\]] stack.pop() # 逆序入栈保证左端符号在栈顶 for symbol in reversed(prod[1]): if symbol ! ε: stack.append(symbol) return pos len(token_stream)这里栈和 Token 流都使用了结束符$。逆序入栈是标准做法把产生式右侧从左到右倒着放进栈中这样弹出时左脚先弹出。注意 ε 产生式不能入栈任何符号只弹掉左部即可。预测分析表的存储我用字典而不是二维数组因为很多单元格是空的字典能省空间也容易在调试时输出缺失键。如果你需要可视化表格再转成 pandas DataFrame 或二维数组也不复杂。注意LL(1) 分析失败时不要只返回False最好打出当前栈内容和输入位置否则在图形界面上根本没法定位是哪一行导致的语法错误。4. LR(1)分析器项集族、CLOSURE与GOTO的代码实现4.1 LR(1)项与自动机构造比SLR(1)多一个向前看符号LR(1) 和 SLR(1) 的核心差异在于 LR(1) 的项里带了一个向前看符号。比如产生式A - B · C, a中的a表示这条项在归约时要用a来检查后续输入。这个向前看符号集让 LR(1) 能处理更多文法但代价是状态数爆炸。工程实现时不建议直接用 LR(1) 自动机做全部解析更常见的做法是用 LALR(1) 合并同心项集不过实验要求里说的是 LR(1)那我们就按严格 LR(1) 来实现。我会把 LR(1) 项表示为一个三元组产生式左部、产生式右侧符号包含圆点位置、向前看符号集合。实际编码中圆点可以用索引表示比如[A, B C, 1, {a}]表示A - B · C, a。用元组比较麻烦我一般直接用类或者namedtuple但为了效率也可以用(prod_index, dot_pos, lookahead_tuple)。4.2 CLOSURE与GOTO两个函数打遍天下LR(1) 自动机的构造完全由两个函数驱动CLOSURE 和 GOTO。CLOSURE 负责补全当前项集中所有“圆点后是非终结符”的项。GOTO 负责把项集里的圆点移动一位后生成新的项集。下面这两段代码就是整个分析表构造的核心。def closure(items, grammar, first_sets): # items: set of LR(1) item triples (prod_index, dot, lookahead) # grammar: list of productions, each is (left, right) changed True while changed: changed False for prod_idx, dot, lookahead in list(items): right grammar[prod_idx][1] if dot len(right): continue # 圆点已在末尾无需扩展 symbol right[dot] if symbol not in nonterminals: continue # 计算 beta 部分的 First 集beta right[dot1:] beta_first compute_first_sequence(right[dot1:], first_sets) # 新的 lookahead 是 beta_first 与原有 lookahead 的组合 new_lookahead set() for a in lookahead: if ε in beta_first: new_lookahead | (beta_first - {ε}) | {a} else: new_lookahead | beta_first # 为每个产生式 symbol - ... 添加项 for idx, (left, right2) in enumerate(grammar): if left symbol: new_item (idx, 0, tuple(sorted(new_lookahead))) if new_item not in items: items.add(new_item) changed True return items注意compute_first_sequence需要返回一个集合并且能正确判断整串是否可空。如果整串可空则把原来的向前看符号a也包含进去。这里有个很多教科书没强调的细节当beta推出 ε 时新的向前看符号是First(beta) - {ε} 原lookahead。漏掉“加原 lookahead”会让 LR(1) 退化成 SLR(1) 的效果导致无法处理非 SLR 文法。GOTO 的实现相对直接对当前项集中所有圆点后符号为 X 的项把圆点右移一位生成新项然后再对新项集执行 CLOSURE。要注意去重同一状态重复出现时要复用已有的状态 id否则自动机会无限膨胀。这个去重用dict以 frozenset 为键最合适。状态项集描述规约项归约后的 lookaheadI0E - ·E, $无无I1E - E·, $E - E·, $$I2E - E·, $无无I3E - E·E, $无无I4E - EE·, $E-EE·, $$, 上面是一个极简文法E - E和E - E E的部分状态表。我拿它说明一点同一产生式的同一圆点位置会因为 lookahead 不同而分到不同状态。在合并状态时如果忽略 lookahead就是 LALR 的做法。实验如果严格要求 LR(1)就不能合并。4.3 ACTION/GOTO表生成与冲突检测CLOSURE 和 GOTO 构造好状态图后ACTION 表分两类动作移进和归约。对项A - α · a β, b在状态 i 遇到终结符 a 时移进到状态 j GOTO(i, a)。对项A - α ·, a在状态 i 遇到 lookahead a 时用产生式A - α归约。GOTO 表则处理非终结符转移。冲突检测是 LR(1) 实现中必须有的环节。如果同一个 ACTION 表项里既出现移进又出现归约那是移进归约冲突如果出现两个不同产生式的归约那是归约归约冲突。在严格 LR(1) 文法中这两种冲突都不应该存在。实际实验里我可以主动打印冲突位置这比直接抛出异常更有价值if action_key in action_table: existing action_table[action_key] if existing[0] ! action_kind: print(f冲突状态{state} 符号{terminal} 已有{existing}新增{action_kind}) elif existing[1] ! action_val: print(f冲突同一动作不同值 {existing} vs {action_kind})这里我把动作编码成(shift, state_id)或(reduce, prod_index)的元组。冲突发生时如果你已经确认文法不是 LR(1)可以考虑改用向前看符号合并策略降级为 LALR(1)但实验题目要求 LR(1) 的话这种降级不能作为最终答案。5. 三个实验如何串成一个可演示项目测试驱动与前端解耦5.1 用一条命令验证三个模块我把三个分析器放在同一个包下词汇 Token 流作为 LL(1) 和 LR(1) 的共同输入。实际串联时词法分析器输出Token对象列表LL(1) 和 LR(1) 都接收同一个token_stream。为了方便测试我额外实现了一个main入口输入一串源码字符按顺序执行 “词法分析 - LL(1) 分析 - LR(1) 分析”每一步的结果都可以输出日志。下面这个命令格式我用的是python3 main.py -s a b c * 2;它会返回每个阶段的输出摘要。python3 main.py -s int a; a 3 4 * 5; --print-tokens --print-parse-tree这里--print-tokens打印词法结果--print-parse-tree打印 LL(1) 或 LR(1) 的推导动作序列。这个命令行模式很适合课程设计验收时展示老师通常不想打开图形界面点来点去直接在终端看到结果更有说服力。5.2 常见边界用例与隐性失分点我整理了几个很容易被忽略的用例实验报告中最好都能覆盖到。一是空输入和只有注释的输入词法分析器应返回空 Token 流LL(1) 和 LR(1) 都应该直接判定为语法错误而不是崩溃。二是连续两个运算符的情况比如a * * b语法分析器必须报错。三是长标识符和长数字比如超过 1024 字符的标识符状态机不能溢出。我在实现时给标识符长度加了一个上限超出后报“词法错误标识符过长”。另一个隐性得分点是错误信息的行号和列号。Token 对象里只存种类和值不存源位置导致报错时只能输出“第几个 Token 出错”这在验收时不友好。我在词法分析器里给每个 Token 增加了line和column字段后续语法分析报错可以被前端定位到具体代码位置。5.3 图形界面该放多少逻辑实验包原作者说老师喜欢图形界面所以加了前端。我的建议是前端只负责代码输入、按钮触发、结果展示所有分析逻辑都放在后端类里。用 Java 就写Lexer、LL1Parser、LR1Parser三个独立类用 Python 就拆成对应的模块文件。前端调用时只需要传入字符串拿到输出列表不要在前端事件函数里写任何分析算法。这样你可以在不打开 GUI 的情况下运行命令行测试而且后续换 Java Swing、JavaFX 或者 Web 前端后端完全不用改。图形界面里一个实用的设计是“分步展示”解析一次后将 Token 列表按步骤显示每个 Token 关联一个高亮色块。语法分析时则在文本框中标记当前读入位置。这种效果看起来很惊艳但实现并不难只需要在分析器里预先把动作序列保存下来前端按动作序列逐帧回放。学过这套实验的人再看看整个项目结构就会明白为什么源代码里src、LICENSE、README.md的布局这么干净后端抽象的边界做对了后续加什么前端都只是时间问题。本文还有配套的精品资源点击获取