简介编译原理实验配套资源面向正在完成词法分析、语法分析课程设计的高校学生。压缩包内含词法分析器、LL(1)语法分析器、LR(1)语法分析器三部分实现覆盖从底层分词到两种语法分析策略的完整流程词法部分可识别关键字、标记符、运算符、分界符、无符号数还额外支持字符/字符串与行间注释并配有图形界面展示分析结果。包体共52个文件以C源文件.cpp/.h和HTML前端界面为主同时附有测试输入.in、期望输出.out、实验报告PDF、演示动图及makefile构建脚本便于对照学习与重新编译运行。资源整体6.88MB目录结构清晰适合作为实验参考或功能扩展基础。目前已有1089人学习下载若正在编写编译原理实验或需要可运行的示例代码这份资料能节省不少调试时间。1. 编译原理实验三件套这门课最该自己手写的一次作业很多同学把编译原理实验当成“填空式”的课程设计拿着学长学姐的 zip 改改变量名就交差。但词法分析器、LL(1) 语法分析器、LR(1) 语法分析器这三个模块恰恰是整门课最值得亲手推一遍的线段从字符流到 token 流从 token 流到语法树每一步都在验证离散数学、文法和自动机理论到底怎么落地。哪怕你不打算写编译器这三块代码也直接影响你理解 JSON 解析器、SQL 解释器、表达式引擎这些日常工具的内部逻辑。这篇笔记会按“词法 → LL(1) → LR(1)”的顺序把每个模块的构造步骤、参数选择和典型翻车点讲清楚包含可以直接改用的代码框架。适合正在做编译原理实验、或者想从零手写一个小型前端分析器的读者。2. 词法分析器从字符流到 token 流最长匹配和状态表是核心编译原理实验里词法分析器最容易被低估因为多数人第一反应是“用正则不就完了”。但实验要求往往卡在两点一是禁止调用现成词法生成器二是要求处理错误恢复和最长匹配语义。自己手写时我建议用显式的状态转换表而不是散落一地的 if/else这样后续加注释、加字符串字面量、加运算符都不会把 main 函数变成意大利面。2.1 为什么手工构造 DFA 比直接写正则更靠谱正则表达式底层会编译成 NFA 再转 DFA但你在实验里直接re.match会踩两个坑第一Python 的re模块是 Perl 风格正则它对“贪心/非贪心”和“边界”有自己的规则和编译原理教材里的正则代数不完全一致第二多个正则并联时匹配顺序完全由代码书写顺序决定你想实现“标识符优先于关键字”还得额外排序。手工构造 DFA 的好处是状态迁移完全显式遇到不匹配字符能立刻进入错误状态并且可以方便地配合最长匹配策略——读入尽可能多的字符直到下一个字符无法迁移为止然后把当前状态对应的 token 返回。我在实验里一般维护一个二维数组state_table[state][char_class]行是状态编号列是字符类别字母、数字、运算符、分隔符、其他。每一步读一个字符查数组得到下一个状态如果查不到就回退到上次接受状态。这样“接受状态集合”和“状态类别”都变成数据调试时打印状态编号就知道卡在哪。2.2 一个可复用的词法分析器框架表驱动 最长匹配下面这个 Python 实现没有依赖任何正则库只用了str的基本方法。它演示了最核心的表驱动骨架用while循环配合last_accept记住最后一次可接受位置实现最长匹配回退。class Lexer: def __init__(self, text): self.text text self.pos 0 self.line 1 TOKEN_KINDS { ID: IDENTIFIER, NUM: NUMBER, PLUS: , MINUS: -, STAR: *, SLASH: /, LPAREN: (, RPAREN: ), SEMI: ;, EQ: , } KEYWORDS {if, else, while, return} def _is_alpha(self, c): return c.isalpha() or c _ def _is_alnum(self, c): return c.isalnum() or c _ def _error(self, msg, line): raise RuntimeError(fline {line}: {msg}) def next_token(self): while self.pos len(self.text): c self.text[self.pos] if c.isspace(): if c \n: self.line 1 self.pos 1 continue # 标识符和关键字字母开头后跟字母/数字/下划线 if self._is_alpha(c): start_pos self.pos while self.pos len(self.text) and self._is_alnum(self.text[self.pos]): self.pos 1 word self.text[start_pos:self.pos] kind keyword if word in self.KEYWORDS else identifier return (kind, word, self.line) # 数字支持整数和简单小数注意最长匹配到非数字为止 if c.isdigit(): start_pos self.pos while self.pos len(self.text) and self.text[self.pos].isdigit(): self.pos 1 if self.pos len(self.text) and self.text[self.pos] .: self.pos 1 while self.pos len(self.text) and self.text[self.pos].isdigit(): self.pos 1 return (number, self.text[start_pos:self.pos], self.line) # 单字符运算符这里预留双字符运算符扩展点 two_char self.text[self.pos:self.pos 2] if two_char in (, !, , ): self.pos 2 return (op, two_char, self.line) if c in -*/();: self.pos 1 return (op, c, self.line) self._error(f非法字符: {c!r}, self.line) return (eof, None, self.line) def tokenize(self): tokens [] while True: tok self.next_token() tokens.append(tok) if tok[0] eof: break return tokens这段代码的关键逻辑在“最长匹配”标识符循环里只要下一个字符是字母数字就继续读直到读不进为止数字同理。如果直接用if c.isalpha()只读一个字符那么intVar会被切成长度和词实验一跑就崩。参数上要注意三个地方一是KEYWORDS是集合查找是 O(1)别用列表二是关键字判断必须发生在读完整个单词之后不能看到第一个字母是i就认为是if三是运算符部分我预留了双字符判断因为和在后续语法分析里可能是不同的 token。如果你要支持字符串需要再增加一个\的迁移状态并且在字符串内部识别转义符。2.3 词法分析器的三个必调参数状态表、关键字表、缓冲大小很多实验报告把词法分析器写成“能用就好”但验收时会问三个参数最大标识符长度、缓冲区分块大小、错误恢复策略。第一个参数影响符号表设计比如某些语言限制标识符前 63 个字符有效那你需要在循环里加长度上限超过后可以报错或截断并继续。第二个参数影响读文件方式如果文本文件很大不要read()全部载入内存而是用read(4096)分块但要注意跨块时 token 会被截断。常见做法是维护一个环形缓冲区或者至少保留上次未消费完的尾部我的经验是直接读整行再逐行 tokenize实验规模下简单且不容易出 bug。第三个参数直接决定你有没有输出“line 3: unexpected character ”这样的诊断能力。我在错误恢复上采用“丢弃当前字符行号不变继续扫描”的策略虽然会跳过一些 token但至少整个文件能被扫完比一遇到非法字符就终止整个程序更适合后续语法分析阶段报错定位。3. LL(1) 语法分析器FIRST/FOLLOW 集、预测分析表与栈驱动的完整实现LL(1) 是“从左到右扫描、产生最左推导、向前看 1 个 token”的缩写也是实验里最容易讲清楚、又最容易写错的部分。多数教科书会先给 FIRST/FOLLOW 定义然后让你手工构造预测分析表。实验的验收点通常有三处FIRST/FOLLOW 集算得对不对、预测分析表有没有冲突、栈驱动程序能否在处理语法错误时不死循环。3.1 消除左递归与提取左公因子LL(1) 文法的前提不是所有上下文无关文法都能用 LL(1)。直接左递归E - E T会让预测分析表在E这一行、这一列填两个产生式形成冲突。实验前必须先把文法改写成 LL(1) 可用的形式。以经典算术表达式文法为例原始版本是左递归的需要改写为右递归形式原文法E - E T | T T - T * F | F F - ( E ) | num改写后E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | num改写过程还藏着一个实验常考的细节提取左公因子。比如文法S - if E then S else S | if E then S必须先合并成S - if E then S SS - else S | ε否则预测表会在S遇到if时不知道选哪条产生式。我在实验里会把“改写前的冲突表”和“改写后的表”都打印出来报告里写“验证了 LL(1) 文法的充分性”这比单纯贴代码得分高。3.2 用 Python 计算 FIRST 和 FOLLOW 集代码与参数说明下面这份代码可以直接跑输入是产生式列表输出是每个非终结符的 FIRST 集和 FOLLOW 集。def compute_first(productions): # productions 形如: {E: [[T, E\]], E\: [[, T, E\], []]} # 空列表 [] 表示 epsilon first {nt: set() for nt in productions} changed True while changed: changed False for lhs, rhs_list in productions.items(): for rhs in rhs_list: if not rhs: # epsilon if epsilon not in first[lhs]: first[lhs].add(epsilon) changed True else: before len(first[lhs]) for symbol in rhs: if symbol in productions: # 非终结符 first[lhs] | (first[symbol] - {epsilon}) if epsilon not in first[symbol]: break else: # 终结符 first[lhs].add(symbol) break else: # 所有符号都能推出 epsilon first[lhs].add(epsilon) if len(first[lhs]) ! before: changed True return first def compute_follow(productions, first, start_symbol): follow {nt: set() for nt in productions} follow[start_symbol].add($) # 输入结束符 changed True while changed: changed False for lhs, rhs_list in productions.items(): for rhs in rhs_list: for i, symbol in enumerate(rhs): if i 0 and not symbol: continue if symbol not in productions: continue # 终结符跳过 rest rhs[i 1:] if not rest: before len(follow[symbol]) follow[symbol] | follow[lhs] if len(follow[symbol]) ! before: changed True else: first_rest set() can_epsilon True for s in rest: if s in productions: first_rest | (first[s] - {epsilon}) if epsilon not in first[s]: can_epsilon False break else: first_rest.add(s) can_epsilon False break before len(follow[symbol]) follow[symbol] | first_rest if can_epsilon: follow[symbol] | follow[lhs] if len(follow[symbol]) ! before: changed True return follow逻辑说明FIRST 集计算用不动点迭代每一轮如果某个非终结符的集合发生了变化就继续下一轮。参数上最需要注意的是rhs为空的产生式要显式表示成空列表[]不要用[epsilon]字符串不然你在symbol in productions判断时会把epsilon当成非终结符。FOLLOW 集计算时$是输入结束标记只加入开始符号的 FOLLOW 集当遇到A - α B且 B 后面没有符号时FOLLOW[B] 并入 FOLLOW[A]这是最容易漏的一条规则。另外first_rest的can_epsilon标志很关键如果 B 后面的符号串能推出 epsilon那么 FOLLOW[A] 也要并进 FOLLOW[B]教科书上叫“β 能推导出 ε 的情况”。实践提示如果实验把 FIRST 和 FOLLOW 作为硬性输出建议把非终结符按字母序排序打印避免无顺序的结果被验收同学认为不对。3.3 预测分析表驱动过程与同步 token 选择预测分析表是一个二维表行是非终结符列是终结符。构造规则是对于产生式A - α把α填入table[A][b]其中b ∈ FIRST(α)如果α能推出 epsilon则把α填入table[A][c]其中c ∈ FOLLOW(A)。这张表本身就是最好的调试输出实验报告里可以直接检查是否有单元格内多于一个产生式。栈驱动程序用 Python 写短小清晰def ll1_parse(table, start, token_list): stack [$, start] index 0 while stack: top stack[-1] token token_list[index] token_type token[0] # 假设 token 是 (type, value, line) if top token_type: stack.pop() index 1 elif top $: print(非法输入) return False elif top in table and token_type in table[top]: stack.pop() production table[top][token_type] # 逆序压栈因为栈顶先出 for symbol in reversed(production): if symbol ! : stack.append(symbol) else: # 错误恢复弹出栈顶但不消费 token print(f跳过非期待符号 {token_type}, 期望 {top}) stack.pop() return index len(token_list)这里同步 token 的选择是避坑重点当栈顶终结符与输入 token 不匹配时最稳妥的方式是“弹出栈顶终结符”而不是“跳过输入 token”。因为如果输入少了一个分号跳过 token 会让分母不断后移错误恢复会连续报错弹出栈顶则回到上层非终结符继续分析错误恢复更稳。如果栈顶是非终结符且表项为空则“跳过所有不在 FOLLOW(top) 中的输入 token”——这个操作在实验里几乎必考。4. LR(1) 语法分析器从项目集规范族到 action/goto 表冲突处理是唯一难点LR(1) 是自底向上分析的代表它比 LL(1) 处理更多文法但构造过程也更难状态多、表大、冲突判断绕。实验里多数同学抄代码能跑但被问“你的状态 I0 为什么有三个项目”就答不上来。这里把构造过程拆开。4.1 为什么要 LR(1)它能处理的文法比 LL(1) 宽多少LL(1) 需要每个产生式的选择凭一个向前看 token 决定而 LR(1) 是在“移进/归约”过程中利用最右推导的逆过程向前看信息来自上下文状态。经典对比是LL(1) 无法处理“悬空 else”的原始文法但 LR(1) 可以更典型的例子是文法S - a A d | b A e这类需要看非终结符后面跟什么的文法LL(1) 经常冲突LR(1) 的向前看符号会把d和e记在状态里。实验里如果老师给了一个明显不是 LL(1) 的文法让你用 LR(1) 实现就是在暗示你能接受更多状态。代价是 LR(1) 的状态数量可能比 LR(0) 多几倍所以在实验报告里我一般把状态表的行数、action 表大小列出来说明“状态膨胀”是正常现象。4.2 构造 LR(1) 项目集规范族核心步骤拆解LR(1) 项目是[A - α·β, a]其中a是向前看终结符。项目集闭包计算是第一步也是最容易被忽略的一步。下面伪代码展示了closure和goto的核心逻辑def closure(I, grammar): J set(I) changed True while changed: changed False for item in list(J): dot_rhs item.rhs[item.dot:] if not dot_rhs: continue # 规约项目 next_symbol dot_rhs[0] if next_symbol not in grammar.nonterminals: continue # 计算 beta a: β 是点后剩余a 是向前看 beta_a dot_rhs[1:] [item.lookahead] first_beta compute_first_of_string(beta_a, grammar) for prod in grammar.productions_for[next_symbol]: for lookahead in first_beta: new_item Item(prod.lhs, prod.rhs, 0, lookahead) if new_item not in J: J.add(new_item) changed True return J def goto(I, X): J set() for item in I: if item.dot len(item.rhs) and item.rhs[item.dot] X: J.add(Item(item.lhs, item.rhs, item.dot 1, item.lookahead)) return closure(J)闭包计算的逻辑如果项目点后面是非终结符B则需要把所有B - .γ项目加入当前项目集这些新项目的向前看符号是FIRST(βa)其中β是点后剩余符号串a是原项目的向前看。这个FIRST(βa)的计算必须包含“β 可推出 epsilon”这条传递路径否则你的 LR(1) 实际上退化成 LR(0)冲突处理全错。我在实现时踩过一个坑把beta_a写成了dot_rhs[1:] [item.lookahead]但忘记处理dot_rhs为空的情况导致闭包运算永远收敛不了。所以第一行一定要判断dot_rhs是否为空空项目没有可扩展的符号。4.3 action 与 goto 表驱动shift/reduce 冲突怎么处理当所有项目集构造完成后填表规则是如果项目[A - α·aβ, b]且a是终结符则action[I][a] shift(I_after_goto)如果项目[A - α·, a]且A不是开始符号则action[I][a] reduce(A - α)如果项目[S - S·, $]则action[I][$] accept。goto[I][A]用于非终结符转移。冲突处理是 LR(1) 实验的验收核心。shift/reduce 冲突通常来自二义性文法比如表达式文法的E - E Ereduce/reduce 冲突通常来自文法本身设计失误比如两个产生式能归约成同一个非终结符且向前看集合重叠。处理办法有三个层面第一是改写文法消除二义性用优先级和结合性声明是最常见的做法实验里老师往往允许你用“优先级最高的是乘除最低的是赋值”这样的规则来解决第二是默认移进优先这符合大多数语言的“悬空 else”偏好第三是打印冲突现场输出冲突所在状态、栈上的符号序列和当前输入 token这份冲突报告比任何代码都能让验收老师相信你是真懂的。我在处理表达式文法时会直接给、*标数字优先级然后在填表冲突时比较当前终结符优先级与产生式右侧最后一个终结符的优先级决定 shift 还是 reduce——这是 yacc/bison 内部做的事实验里手写也能用。5. 实验联调与避坑从词法到语法的手写链路常见翻车点三个模块单独写都能跑一拼起来就崩这是编译原理实验的最大玄学。很多同学把时间花在 debug 词法分析器上结果问题出在模块之间的接口约定。这里列四个我每次带实验都会让学生先自查的坑。5.1 token 流与语法分析器之间那层缓冲为什么总是差一个字符现象LL(1) 分析器刚启动就报错提示第一个 token 不对但单独调用词法分析器却输出正常。原因语法分析器需要“向前看一个 token”但词法分析器已经按next_token()一次性读完整个文件并返回 token 列表那个“超前读”的字符在列表里已经存在可你忘了处理 eof。解决在 LL(1) 栈驱动里初始化时应把第一个 token 预读到lookahead变量而不是直接token_list[index]。我的习惯是让词法分析器提供一个peek_token()接口内部保存一个_pendingtoken这样语法分析器可以从容实现“仅当匹配成功时消费 token”的语义。如果你没有 peek 接口就用token_list[index]也行但每次index 1之后要立刻检查index是否越界否则eof处理会漏掉。5.2 终结符与 token 类型命名不一致的坑现象预测分析表里明明写了num词法分析器返回的 token 类型是NUMBER表驱动函数里token_type top永远不成立。原因实验报告里定义了 token 枚举但词法分析器返回字符串时大小写、命名规则没有统一。解决在项目里建立一个TokenType枚举或常量字典词法分析器、FIRST/FOLLOW 计算、预测分析表三处都引用同一组定义。我见过最惨的情况是词法里用小写keyword语法里文法符号用大写ID最后排查两小时发现是大小写不一致。更隐蔽的问题是某些实验模板里把关键字单独作为 token 类型而文法里写if作为终结符那么if到底是KEYWORD还是IF我的经验是关键字一律保留为原值终结符比如if这样文法产生式里直接写if不需要额外映射。5.3 空产生式处理epsilon 到底要不要进 FOLLOW现象LL(1) 表构造后出现单元格冲突比如E遇到同时有E - T E和E - ε两个产生式。原因在计算 FOLLOW 时没把能推出 epsilon 的非终结符的 FOLLOW 传播给左边的非终结符。比如E - ε时FOLLOW(E) 应该并入 FOLLOW(T)如果你只在A - α B β且β为空时才传播就漏了。解决检查你的 FOLLOW 算法是否有两层新集合传播——一层是对A - α B的简单并入另一层是当 β 可空时继续向 B 之前的所有非终结符传播。更直接的办法是在 FIRST/FOLLOW 输出里手动验证一个众所周知的结论对文法E - T EFOLLOW(E) FOLLOW(E)如果不相等算法一定有漏。5.4 递归下降与表驱动别混用LL(1) 的预测表不是递归函数现象实验代码里既有predict_table又用parseE()parseT()递归函数然后某些分支递归调用不按表来。原因很多同学先写了递归下降风格后来改成表驱动时只改了外层循环内部的递归调用还残留。后果是递归下降通常不需要显式$栈而表驱动需要两种风格混在一起导致栈顶和调用栈不同步程序可能死循环。解决选一种风格做到低。如果老师要求“用预测分析表”那么在访问表之前所有递归函数都要禁止如果老师只是要求 LL(1) 思想那么递归下降里可以直接用lookahead做分支判断不需要构造二维表。我的血泪经验是实验验收时最怕听到“这个函数为什么自己调用自己”因为混用代码一眼就能看出来。纯表驱动版本里除了ll1_parse没有任何函数递归这是硬性自查标准。6. 把三个模块串成一条命令链trace 开关与三层验证三个分析器都完成后不要急着提交 zip。先做一件事给每个模块加一个-t或verbose参数让它们把中间过程打印出来。词法分析器打印每个 token 和行号LL(1) 分析器打印分析栈、当前输入 token 和使用的产生式LR(1) 分析器打印状态栈、符号栈和 shift/reduce 动作。这个 trace 开关平时关了调试时打开能省下大量“到底是哪一层错了”的时间。验证方法用一个小而全的输入我一般用下面的算术语句while (x 3) * y 10 { x x 1; }首先用词法分析器 tokenize确认输出了while关键字、标识符x、数字3、运算符、括号、比较运算符、赋值号、分号等。然后把 token 列表分别喂给 LL(1) 分析器和 LR(1) 分析器两者都应该返回成功。如果 LL(1) 失败先检查是否因为在词法里被拆成了和如果 LR(1) 失败先检查赋值语句的语法规则是否与产生式完全一致。我最终的实验习惯是写一个run_all.py调用三个模块并把所有 trace 输出到debug.log交报告时只展示正常模式的结果但附上debug.log的部分截图证明调试过程真实。这种“可追溯”的完成方式比只给一个能跑的黑匣子更能扛住验收提问。希望帮到你。本文还有配套的精品资源点击获取