与LR(1)语法分析器实现指南)
简介这是一份面向编译原理课程设计与实验的综合源码包覆盖词法分析器与 LL(1)、LR(1) 两类语法分析器的完整实现既可用于本科课设、实验复现也适合正在学习自上而下和自下而上语法分析方法的自学者对照理解。词法分析部分基于 C/C 编写除要求的关键字、标识符、运算符、分界符、无符号数外还额外支持字符/字符串与行间注释作者按老师偏好增加了图形界面前端使得输入输出和 Token 匹配结果直观可见。压缩包约 6.88MB共 52 个文件包含 cpp/h 源码、html/php 前端页面、makefile 构建脚本以及 in/out 测试输入输出、PDF 说明、GIF 演示、LICENSE 与 README 等目录模块划分清晰便于快速定位和对比运行。已有 1089 人学习下载是比较完整的编译原理课程设计参考资料也适合在期末复习时梳理词法、语法分析流程。1. 这个实验包到底在考什么词法、LL(1)、LR(1)三个关卡的关系拿到“编译原理实验之词法分析器、LL(1)语法分析器、LR(1)语法分析器.zip”这个压缩包很多人的第一反应是解压、找源码、改个名字就交。但这个包真正的考点不在“跑通”而在你能否把三件事串成一条前端流水线词法分析器把字符流切成tokenLL(1)或LR(1)语法分析器再把token流吃掉最终输出可验证的分析过程。像山东科技大学、燕山大学这类高校的编译原理实验课程设计通常要求一次交齐三个目录和实验报告老师会拿输入文件直接跑错一个token或者少一个动作整个分析链就断了。这篇文章不替你写作业而是把你要补的原理、能落地的代码骨架、以及最容易翻车的参数配置按实验顺序拆开。适合正在赶实验的本科生也适合工作后回来补编译原理基础的人。2. 词法分析器从状态转移图到最小可用实现2.1 词法分析器在实验包里到底要交付什么一个压缩包里的词法分析器交付物不只是“能识别单词”的程序。老师一般要求三样东西token类别定义、关键字表、可编译的状态转移实现。常见做法是把token定义成枚举和结构体C语言版本大概长这样typedef enum { TOKEN_ID, TOKEN_KEYWORD, TOKEN_INTEGER, TOKEN_PLUS, TOKEN_MINUS, TOKEN_ASSIGN, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SEMI, TOKEN_EOF, TOKEN_UNKNOWN } TokenType; typedef struct { TokenType type; char lexeme[64]; int line, col; } Token;这里type决定语法分析器怎么归约lexeme保存原始字符串line和col在报错时要用。很多同学把关键字当成普通标识符处理等跑到语法分析全错时才回头改——这就是没想清楚关键字表的用场。编译器在处理C语言“if”时不能把它归约为标识符所以词法分析器的第一步是查表读完一串字母后先查关键字表命中就返回TOKEN_KEYWORD否则返回TOKEN_ID。有些学校实验用Java写逻辑完全一样Token类、枚举、关键字HashMap区别只在容器API。对状态机本身来说语言不影响设计只影响你写回退字符时用的是ungetc还是自定义缓冲区。想少走弯路的话先把“状态图”画在纸上再写代码。2.2 用C语言的状态机识别关键字/标识符/整数的最小实现状态机实现以“当前状态当前字符”决定下一动作。下面这个骨架能识别标识符、关键字、整数、加号和文件结束是大多数实验包的最小可用版本#define MAX_ID_LEN 63 char buf[MAX_ID_LEN 1]; int state 0, pos 0; int next_char(void) { return getchar(); // 实际项目中换成从文件或缓冲区读取 } void unread_char(int c) { ungetc(c, stdin); // 把多读的字符放回输入流 } Token make_token(TokenType type, const char* text) { Token t; t.type type; strncpy(t.lexeme, text, MAX_ID_LEN); t.lexeme[MAX_ID_LEN] \0; return t; } Token next_token(void) { int c; state 0; pos 0; while ((c next_char()) ! EOF) { switch (state) { case 0: if (isalpha(c) || c _) { state 1; buf[pos] c; } else if (isdigit(c)) { state 2; buf[pos] c; } else if (c ) { return make_token(TOKEN_PLUS, ); } else if (isspace(c)) { // 空白符直接跳过这里还可以维护 line/col 计数 } else { return make_token(TOKEN_UNKNOWN, (char[2]){c, \0}); } break; case 1: if (isalnum(c) || c _) { buf[pos] c; } else { unread_char(c); buf[pos] \0; return is_keyword(buf) ? make_token(TOKEN_KEYWORD, buf) : make_token(TOKEN_ID, buf); } break; case 2: if (isdigit(c)) { buf[pos] c; } else { unread_char(c); buf[pos] \0; return make_token(TOKEN_INTEGER, buf); } break; } } return make_token(TOKEN_EOF, ); }这段代码里最关键的逻辑是“读到非标识符/数字字符时要把它放回输入”。比如输入ab状态机读到a后看到如果不把放回去下一次调用next_token时就丢掉了加号语法分析器拿到的token流就漏项。这就是词法分析里的最长匹配原则能读多长就读多长多读的那个字符必须回退。参数方面MAX_ID_LEN设成63是按“标识符最长64字符含结尾空字符”来的。如果你把它改成10超长标识符会被截断语义分析阶段查符号表时可能出现两个不同变量因为前缀相同而被当成同一个这是很阴间的坑。2.3 词法分析器必调的三个参数与四个边界这里把需要关注的参数和边界列成一张表方便你写实验报告时对照参数/边界推荐值说明MAX_ID_LEN63防止超长标识符拖垮状态机但截断后要发警告关键字表大小与实验语言一致数组还是HashMap看平台C语言可直接二分查找空白符处理跳过并记录行列号不要把换行也当成普通字符丢给语法分析器文件末尾EOF返回TOKEN_EOF只能返回一次之后再次调用要报错或继续返回EOF注释处理独立状态//和/* */不要混进标识符状态注释是高频翻车点。/* ... */如果写成“读到*就闭合”遇到**/这种输入会提前结束注释。正确做法是维护两个状态一个在注释内部一个在“刚读到*”的过渡状态只有过渡状态后跟/才是闭合。行号的维护也容易漏最省心的方案是单独写一个read_char函数在里面统一统计行号列号而不是在每个case里加一行line。提示词法分析器最容易被测试用例打死的点不是认错token而是“吞掉了一个不该读的字符”。所以ungetc路径和缓冲区预读路径必须分别测。把词法部分做扎实之后你有两个选择直接进入LL(1)或者先把词法输出保存到临时文件避免每次调试语法分析都要重新跑词法。我在做实验时习惯让词法分析器支持一个-t参数只打印token序列既方便调试也方便后面用管道把结果喂给语法分析器。3. LL(1)语法分析器FIRST/FOLLOW/预测分析表的落地3.1 先算FIRST和FOLLOW从文法到三个集合LL(1)的意思是“从左到右扫描、最左推导、向前看一个token”。它的核心是预测分析表而表的三根支柱是FIRST、FOLLOW和空串判断。很多同学一上来就写表等发现表里出现冲突才回头补集合这是最费时间的顺序。先用一个经典文法举例E - E T | TT - T * F | FF - ( E ) | id。这种左递归文法在LL(1)里没法直接用所以换成消除左递归后的版本E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | idFIRST集合用不动点迭代算最不容易漏Python代码可以这样productions { E: [[T, E\]], E\: [[, T, E\], [ε]], T: [[F, T\]], T\: [[*, F, T\], [ε]], F: [[(, E, )], [id]] } nonterminals set(productions.keys()) terminals {, *, (, ), id} first {nt: set() for nt in nonterminals} first.update({t: {t} for t in terminals}) changed True while changed: changed False for nt, alts in productions.items(): for alt in alts: before len(first[nt]) for sym in alt: if sym ε: first[nt].add(ε) break if sym in terminals: first[nt].add(sym) break # 非终结符把FIRST(sym)除去ε加进来 first[nt] | (first[sym] - {ε}) if ε not in first[sym]: break if len(first[nt]) ! before: changed True for nt in sorted(nonterminals): print(nt, sorted(first[nt]))这个迭代里最容易错的地方是“遇到不能推导出ε的符号就停”。比如对候选式T E如果T的FIRST不含ε那E的FIRST就不能被加进E的FIRST反过来如果T能出ε还要继续处理E。很多同学在这里漏了一层循环导致FIRST集合偏小。FOLLOW集合的计算比FIRST更容易混。核心规则只有三条开始符号的FOLLOW里放$对形如A - α B β的规则把FIRST(β)去掉ε加入FOLLOW(B)对A - α B或β能推出ε的规则把FOLLOW(A)加入FOLLOW(B)。用同样的不动点循环初始只给开始符号放$循环直到所有集合不再增长。计算完以后建议把结果打印出来和教材上的答案对一遍。这里不必去背某本编译原理教材第二章的课后答案关键是把集合和文法对上。3.2 消除左递归和提取左公因子动手写分析器之前必须做的等价变换左递归会造成预测分析表里出现“展开自己”的恶性循环因为M[E, id]既要用E - E T展开E又要等待一个E开头的符号表填不下去。标准做法是把左递归改成右递归再提取左公因子。def remove_direct_left_recursion(nt, productions): alphas [alt[1:] for alt in productions[nt] if alt[0] nt] betas [alt for alt in productions[nt] if alt[0] ! nt] if not alphas: return {nt: productions[nt]}, [] new_nt nt new_prod {nt: [beta [new_nt] for beta in betas], new_nt: [alpha [new_nt] for alpha in alphas] [[ε]]} return new_prod, [new_nt]这个函数的入参是一个非终结符和它的全部产生式。alphas是形如A - A x中的后缀betas是A - y中的非递归候选。输出里A的每个候选都变成y AA的候选是x A和空串。注意如果原文法里有A - ε这种候选它会被当作beta得到的等价文法包含A - A也就是“A能直接变成A”这没问题。提取左公因子是另一个必须做的变换比如A - a b | a c这种文法LL(1)会直接冲突因为向前看a无法区分到底选哪个候选。处理方法就是提公因子A - a XX - b | c。这个变换也要用程序自动做别手搓否则大文法一定出错。3.3 预测分析表驱动循环从表到分析树的最后一个环节FIRST和FOLLOW算完构造LL(1)预测表M的规则是对产生式A - α的每个终结符a属于FIRST(α)把该产生式填入M[A, a]如果α能推出ε则对每个b属于FOLLOW(A)把该产生式填入M[A, b]。同一个格子被填了两次就说明文法不是LL(1)。这就是“冲突检测”的唯一标准。拿上面那个文法跑出来的表大概是M[E, id] E - T EM[E, ] E - T EM[E, $] E - ε。注意M[E, $]这一项来自FOLLOW(E)如果你FOLLOW集合算错这一格就会空掉。驱动循环是一个栈栈底是$栈顶是当前要展开或匹配的非终结符或终结符。Python核心代码M {} for nt in nonterminals: for alt in productions[nt]: fset first_of_sequence(alt) # 整条候选式的FIRST for a in fset - {ε}: M[(nt, a)] alt if ε in fset: for b in follow[nt]: M[(nt, b)] alt def ll1_parse(tokens): stack [$, E] ip 0 while stack: X stack.pop() a tokens[ip] if ip len(tokens) else $ if X a: ip 1 elif X in terminals: raise SyntaxError(f期望 {X}实际 {a}) elif (X, a) in M: for sym in reversed(M[(X, a)]): if sym ! ε: stack.append(sym) else: raise SyntaxError(f非终结符 {X} 遇到 {a}无产生式)逻辑上栈里出不来的终结符必须和当前token匹配非终结符必须能在预测表里查到产生式查到后把产生式右部逆序压栈。这里有一个细节容易卡住倒序压栈是因为栈是后进先出要让最左边的符号先被弹出。空串产生式不要压栈直接匹配掉。如果你习惯用Java编译原理这个组合写实验这个驱动循环完全不用变把stack [$, E]换成StackStringtokens换成ListToken即可。最值得调参的是“栈深上限”。LL(1)理论上不限制栈深但实验实现里最好加一个MAX_STACK_DEPTH 1024超过就报错防止右递归文法在错误输入下陷入无限循环。设太小会让某些长表达式合法输入也崩所以1024是底线不是推荐值。错误恢复方面实验要求不高时最简单的同步办法是发现某非终结符遇到不该出现的token时丢掉当前token并继续读直到遇到该非终结符FOLLOW集合里的符号再恢复。这一招能让一个输入文件里报出两三个错误而不是卡在第一个错误就停下老师测试多错误用例时分数会明显不一样。4. LR(1)语法分析器从LR(0)项目集到规范LR(1)的构造4.1 LR(1)比LL(1)多出来的是什么展望符的传播与状态分裂LL(1)靠向前看一个token决定用哪个产生式LR(1)则结合“左边已经读入的符号栈”做决策。LR(1)项目是[A - α·β, a]点号前面是已经分析出来的部分点号后面是期望输入a是展望符。多出来的这个展望符专门用来解决LL(1)看不到的历史信息。一个教科书级别的例子是这样的简单文法S - S S - L R | R L - * R | id R - L这个文法在LR(0)自动机里会出现一个状态同时包含S - L· R和R - L·。前者要求下一步读等号再继续后者要求当前符号满足一定条件后把L归约为R。如果只看LR(0)这就是移进-归约冲突SLR(1)尝试用FOLLOW(R)解决但FOLLOW(R)里恰好有等号于是分不开LR(1)给这两个项目分别带上不同展望符后同一点位置的项目因为展望符不同而被拆成两个状态才让语法分析器能在“看到等号时移进、看到其他符号时归约”之间做正确选择。这就是为什么LR(1)状态数膨胀得很厉害一个LR(0)状态里的每个项目都要复制多份每个复制品带不同展望符。理解了这个本质后面看状态合并和LALR就顺了。4.2 构造LR(1)项目集和ACTION/GOTO表的代码骨架LR(1)的闭包计算比LR(0)多一个步骤点号后面的符号串要算FIRST再把原项目的展望符追加进去作为新项目的展望符。用Python的namedtuple表达最直接from collections import namedtuple Item namedtuple(Item, [prod_idx, dot, lookahead]) # prod_idx: 产生式编号dot: 点位置lookahead: 展望符 def closure(items, productions, first_all): items set(items) while True: added set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): B rhs[it.dot] if B in nonterminals: beta rhs[it.dot 1:] [it.lookahead] fset first_of_sequence(beta, first_all) for pi, prod in enumerate(productions): if prod[0] B: for la in fset: added.add(Item(pi, 0, la)) if not (added - items): break items | added return items def goto(items, X, productions, first_all): moved set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs) and rhs[it.dot] X: moved.add(Item(it.prod_idx, it.dot 1, it.lookahead)) return closure(moved, productions, first_all)这里最核心的坑是beta rhs[it.dot 1:] [it.lookahead]。很多人只算rhs[it.dot 1]的FIRST但这是不对的。比如项目[A - α·B C, d]点后面的符号串是C d如果C能推出空串那么d也要进入B的展望符。所以必须对“整条剩余串加原展望符”求FIRST。第一次写这个函数时建议单独构造一个极小的文法手推一遍闭包再对照代码输出否则很难发现这个错误。状态集合的构建是一个从初始状态{Item(0, 0, $)}开始的广度优先遍历states [] state_index {} start_items cls_item(Item(0, 0, $)) states.append(start_items) state_index[frozenset(start_items)] 0 worklist [0] while worklist: sidx worklist.pop() items states[sidx] symbols set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): symbols.add(rhs[it.dot]) for X in symbols: ns goto(items, X, productions, first_all) if ns: key frozenset(ns) if key not in state_index: state_index[key] len(states) states.append(ns) worklist.append(len(states) - 1)注意GOTO跳转的符号集合要从所有项目里收集不能只收集终结符否则非终结符转移边会漏掉。用frozenset(ns)做状态去重是因为set本身不可哈希但frozenset可以。4.3 ACTION/GOTO表填充规则和实验中最容易绕晕的“合并”操作规范LR(1)分析表的填充规则可以浓缩成四条项目[S - S·, $]对应的ACTION[s][$] acc项目[A - α·, a]对应ACTION[s][a] r_i按产生式编号归约点号后面是终结符x时对应ACTION[s][x] s_j移进到goto结果状态j点号后面是非终结符X时对应GOTO[s][X] j代码骨架ACTION {} GOTO {} for sidx, items in enumerate(states): for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): if lhs start_symbol and it.lookahead $: ACTION[(sidx, $)] acc else: ACTION[(sidx, it.lookahead)] fr{it.prod_idx} else: X rhs[it.dot] if X in terminals: j state_index[frozenset(goto(items, X, productions, first_all))] if (sidx, X) in ACTION and ACTION[(sidx, X)] ! fs{j}: raise ValueError(f状态{sidx}遇到{X}存在移进-归约或归约-归约冲突) ACTION[(sidx, X)] fs{j} elif X in nonterminals: GOTO[(sidx, X)] state_index[frozenset(goto(items, X, productions, first_all))]这里的冲突检查很重要。规范LR(1)理论上不含冲突但如果你把文法写错了或者LALR合并时生成表就会在这里报出来。我在实验报告里会写清楚冲突不是靠“后写的覆盖先写的”解决必须回到文法层面找问题。关于“LALR合并”两个状态如果项目核心相同不看展望符在规范LR(1)里是两个状态LALR会把它们合并成一个。合并后的状态相当于把两套展望符取并集原本没冲突的状态可能在合并后引入归约-归约冲突。实验里如果老师明确要求LR(1)一般不建议做LALR合并如果状态多到内存不够可以改用SLR或把产生式数量精简。把状态数压缩这件事和你最终得分没太大关系报告里把状态图附上反而更稳。5. 避坑三个实验串跑时的高频翻车现场5.1 词法分析器的“最长匹配”没做对语法分析全盘崩现象输入ifx词法分析器返回关键字if和标识符x语法分析器在期望一个标识符的地方看到关键字if直接报错或者输入123abc词法分析器返回一个整数123再接一个标识符abc而实验要求这里必须报“非法标识符”。原因第一个现象是把“查关键字表”放在了读字符循环里面读到i就匹配ififx被拆成两个token第二个现象是状态机在数字状态没判断后继字母导致该报错的输入被静默拆成两个合法token。解决先读完一串字母/数字放在缓冲区里再整体查关键字表在数字状态下遇到字母不要切token而是把整个123abc标记为TOKEN_UNKNOWN并报错。词法分析器宁可多报错也不要吐出一串“看似合法但语义错误”的token因为语法分析器管不了这种跨token的错误。5.2 FIRST/FOLLOW集合算错预测分析表出现“幽灵冲突”现象LL(1)表构造出来有冲突但用手推文法明明没有冲突或者表不冲突但跑输入时某个格子上查不到规则报“无产生式”。原因绝大多数是FOLLOW集合算错了。常见错误有三个没给开始符号的FOLLOW里放$对形如A - α B β的规则只把FIRST(β)加进FOLLOW(B)没处理β能推出空串的情况不动点循环提前结束集合没收敛。解决把FOLLOW计算也写成和FIRST一样的while循环直到集合大小不再变化算出后用打印语句输出每个非终结符的FOLLOW拿一道教材例题验证。这里不用去翻什么课后习题答案自己构造一个E - T E的小文法人工算一遍FOLLOW(E)如果程序输出和手工不一致那就一行一行调closure代码。幽灵冲突的另一个来源是first_of_sequence函数没有处理“空串符号串”补上就好。5.3 LR(1)状态数爆炸实验内存里跑不动现象文法才二十条产生式规范LR(1)状态数上千个用Python构造到一半内存飙到几个GB程序直接卡死。原因规范LR(1)每个项目都带展望符closure计算反复生成Item对象set去重成本高有些同学用列表嵌套列表表示项目每次比较都是O(n)操作状态一多必然跑不动。解决项目用(prod_idx, dot, lookahead)三元组打包成整数编码把lookahead也映射成小整数这样项目能哈希、能快速比较closure里频繁用到的FIRST结果提前缓存不要每次递归重算如果确实超大规模就退而求其次用SLR或者LALR在实验报告里说明取舍。另外生成状态时用工作队列避免递归深度过深Python递归默认一千层很容易栈溢出。5.4 输入缓冲与行号统计一个小数点误差连累报错信息现象单独跑词法分析器一切正常一接上语法分析器第一个token就少了一个字符或者报错行号整体偏移一行。原因词法分析器里自己维护了预读缓冲但语法分析器也自己读文件两边各读各的导致token流错位行号在状态机的多个case里都有line遇到换行被重复计数。解决规定只有一个入口负责读字符。词法分析器统一用next_char()读语法分析器只接收Token列表绝不直接碰字符流行号只在next_char()里line和col状态机其他位置不允许改行列号。如果用了ungetc放回的字符也要走同一个计数函数否则回退字符的行号会被重复计算。5.5 实验包的文件组织报告、makefile和测试用例的坑现象压缩包解压后是三个目录老师运行make时找不到公共头文件或者词法分析器单独编译通过链接语法分析器时token枚举顺序不一致跑出来的结果完全不对劲。原因三个实验各自复制了一份token定义改词法分析器时忘了同步改语法分析器公共头文件放在顶层目录而makefile用了相对路径从一个子目录里执行就找不到。解决把Token枚举和结构体放到顶层include/token.h三个子目录的源代码都include这个文件写好makefile根目录执行make能依次生成三个可执行文件测试用例单独放tests/目录每个测试文件配一个.out期望文件跑完用diff对比。压缩包里必须附README写明“先make再运行词法输入从stdin读”。我见过太多人栽在路径上老师双击Makefile运行失败直接扣了一档分数。6. 把三个分析器串起来验证方法、可视化与可复用设计三个分析器分开跑通不算完真正拉开差距的是把它们串成一个命令行工具。我习惯给词法分析器加一个-t参数让它只输出token序列这样语法分析器可以用管道直接接收./lexer -t test.c | ./ll1_parser管道方案比起在语法分析器里重新调词法分析函数好处是边界干净。两边只通过文本协议通信token类型用整数编号lexeme用引号包裹语法分析器解析起来很简单。如果你用Python更省事的是直接定义parse_tokens(tokens)把词法分析器返回的列表传进去不要起子进程。验证方法也有讲究。单测之外我强烈建议给LL(1)和LR(1)各加一个“动作轨迹”输出LL(1)每次压栈/弹栈都打印栈内容LR(1)每一轮打印当前状态栈和输入token以及执行的是移进还是归约。这样遇到失败用例可以拿轨迹和手工推导对拍十分钟就能定位到是表填错还是驱动循环写错。这个功能还能顺便生成实验报告里的分析过程表一举两得。另一个让我少熬夜的习惯是三个程序共享同一份Token定义但语法分析器永远不看lexeme字符串只按type判断。词法分析器改一个token名语法分析器完全不用动。测试用例只准备三类最小正确输入、最小错误输入、覆盖所有产生式的输入先用这三类跑通再上一个几千行的大文件做压力测试。大文件挂掉时先看是不是行号统计问题再看是不是栈深上限太小最后才怀疑文法本身。我自己当年做这个实验时把LR(1)的closure函数写了三遍才跑对原因是第一次没把β串后面的展望符拼进FIRST计算。后来学乖了不管多简单的集合运算先单独抽出函数再写测试小文法验证。这个习惯帮我把后面好几个编译实验的返工时间都省下来了。希望帮到你。本文还有配套的精品资源点击获取
编译原理实验核心：词法分析器、LL(1)与LR(1)语法分析器实现指南
简介这是一份面向编译原理课程设计与实验的综合源码包覆盖词法分析器与 LL(1)、LR(1) 两类语法分析器的完整实现既可用于本科课设、实验复现也适合正在学习自上而下和自下而上语法分析方法的自学者对照理解。词法分析部分基于 C/C 编写除要求的关键字、标识符、运算符、分界符、无符号数外还额外支持字符/字符串与行间注释作者按老师偏好增加了图形界面前端使得输入输出和 Token 匹配结果直观可见。压缩包约 6.88MB共 52 个文件包含 cpp/h 源码、html/php 前端页面、makefile 构建脚本以及 in/out 测试输入输出、PDF 说明、GIF 演示、LICENSE 与 README 等目录模块划分清晰便于快速定位和对比运行。已有 1089 人学习下载是比较完整的编译原理课程设计参考资料也适合在期末复习时梳理词法、语法分析流程。1. 这个实验包到底在考什么词法、LL(1)、LR(1)三个关卡的关系拿到“编译原理实验之词法分析器、LL(1)语法分析器、LR(1)语法分析器.zip”这个压缩包很多人的第一反应是解压、找源码、改个名字就交。但这个包真正的考点不在“跑通”而在你能否把三件事串成一条前端流水线词法分析器把字符流切成tokenLL(1)或LR(1)语法分析器再把token流吃掉最终输出可验证的分析过程。像山东科技大学、燕山大学这类高校的编译原理实验课程设计通常要求一次交齐三个目录和实验报告老师会拿输入文件直接跑错一个token或者少一个动作整个分析链就断了。这篇文章不替你写作业而是把你要补的原理、能落地的代码骨架、以及最容易翻车的参数配置按实验顺序拆开。适合正在赶实验的本科生也适合工作后回来补编译原理基础的人。2. 词法分析器从状态转移图到最小可用实现2.1 词法分析器在实验包里到底要交付什么一个压缩包里的词法分析器交付物不只是“能识别单词”的程序。老师一般要求三样东西token类别定义、关键字表、可编译的状态转移实现。常见做法是把token定义成枚举和结构体C语言版本大概长这样typedef enum { TOKEN_ID, TOKEN_KEYWORD, TOKEN_INTEGER, TOKEN_PLUS, TOKEN_MINUS, TOKEN_ASSIGN, TOKEN_LPAREN, TOKEN_RPAREN, TOKEN_SEMI, TOKEN_EOF, TOKEN_UNKNOWN } TokenType; typedef struct { TokenType type; char lexeme[64]; int line, col; } Token;这里type决定语法分析器怎么归约lexeme保存原始字符串line和col在报错时要用。很多同学把关键字当成普通标识符处理等跑到语法分析全错时才回头改——这就是没想清楚关键字表的用场。编译器在处理C语言“if”时不能把它归约为标识符所以词法分析器的第一步是查表读完一串字母后先查关键字表命中就返回TOKEN_KEYWORD否则返回TOKEN_ID。有些学校实验用Java写逻辑完全一样Token类、枚举、关键字HashMap区别只在容器API。对状态机本身来说语言不影响设计只影响你写回退字符时用的是ungetc还是自定义缓冲区。想少走弯路的话先把“状态图”画在纸上再写代码。2.2 用C语言的状态机识别关键字/标识符/整数的最小实现状态机实现以“当前状态当前字符”决定下一动作。下面这个骨架能识别标识符、关键字、整数、加号和文件结束是大多数实验包的最小可用版本#define MAX_ID_LEN 63 char buf[MAX_ID_LEN 1]; int state 0, pos 0; int next_char(void) { return getchar(); // 实际项目中换成从文件或缓冲区读取 } void unread_char(int c) { ungetc(c, stdin); // 把多读的字符放回输入流 } Token make_token(TokenType type, const char* text) { Token t; t.type type; strncpy(t.lexeme, text, MAX_ID_LEN); t.lexeme[MAX_ID_LEN] \0; return t; } Token next_token(void) { int c; state 0; pos 0; while ((c next_char()) ! EOF) { switch (state) { case 0: if (isalpha(c) || c _) { state 1; buf[pos] c; } else if (isdigit(c)) { state 2; buf[pos] c; } else if (c ) { return make_token(TOKEN_PLUS, ); } else if (isspace(c)) { // 空白符直接跳过这里还可以维护 line/col 计数 } else { return make_token(TOKEN_UNKNOWN, (char[2]){c, \0}); } break; case 1: if (isalnum(c) || c _) { buf[pos] c; } else { unread_char(c); buf[pos] \0; return is_keyword(buf) ? make_token(TOKEN_KEYWORD, buf) : make_token(TOKEN_ID, buf); } break; case 2: if (isdigit(c)) { buf[pos] c; } else { unread_char(c); buf[pos] \0; return make_token(TOKEN_INTEGER, buf); } break; } } return make_token(TOKEN_EOF, ); }这段代码里最关键的逻辑是“读到非标识符/数字字符时要把它放回输入”。比如输入ab状态机读到a后看到如果不把放回去下一次调用next_token时就丢掉了加号语法分析器拿到的token流就漏项。这就是词法分析里的最长匹配原则能读多长就读多长多读的那个字符必须回退。参数方面MAX_ID_LEN设成63是按“标识符最长64字符含结尾空字符”来的。如果你把它改成10超长标识符会被截断语义分析阶段查符号表时可能出现两个不同变量因为前缀相同而被当成同一个这是很阴间的坑。2.3 词法分析器必调的三个参数与四个边界这里把需要关注的参数和边界列成一张表方便你写实验报告时对照参数/边界推荐值说明MAX_ID_LEN63防止超长标识符拖垮状态机但截断后要发警告关键字表大小与实验语言一致数组还是HashMap看平台C语言可直接二分查找空白符处理跳过并记录行列号不要把换行也当成普通字符丢给语法分析器文件末尾EOF返回TOKEN_EOF只能返回一次之后再次调用要报错或继续返回EOF注释处理独立状态//和/* */不要混进标识符状态注释是高频翻车点。/* ... */如果写成“读到*就闭合”遇到**/这种输入会提前结束注释。正确做法是维护两个状态一个在注释内部一个在“刚读到*”的过渡状态只有过渡状态后跟/才是闭合。行号的维护也容易漏最省心的方案是单独写一个read_char函数在里面统一统计行号列号而不是在每个case里加一行line。提示词法分析器最容易被测试用例打死的点不是认错token而是“吞掉了一个不该读的字符”。所以ungetc路径和缓冲区预读路径必须分别测。把词法部分做扎实之后你有两个选择直接进入LL(1)或者先把词法输出保存到临时文件避免每次调试语法分析都要重新跑词法。我在做实验时习惯让词法分析器支持一个-t参数只打印token序列既方便调试也方便后面用管道把结果喂给语法分析器。3. LL(1)语法分析器FIRST/FOLLOW/预测分析表的落地3.1 先算FIRST和FOLLOW从文法到三个集合LL(1)的意思是“从左到右扫描、最左推导、向前看一个token”。它的核心是预测分析表而表的三根支柱是FIRST、FOLLOW和空串判断。很多同学一上来就写表等发现表里出现冲突才回头补集合这是最费时间的顺序。先用一个经典文法举例E - E T | TT - T * F | FF - ( E ) | id。这种左递归文法在LL(1)里没法直接用所以换成消除左递归后的版本E - T E E - T E | ε T - F T T - * F T | ε F - ( E ) | idFIRST集合用不动点迭代算最不容易漏Python代码可以这样productions { E: [[T, E\]], E\: [[, T, E\], [ε]], T: [[F, T\]], T\: [[*, F, T\], [ε]], F: [[(, E, )], [id]] } nonterminals set(productions.keys()) terminals {, *, (, ), id} first {nt: set() for nt in nonterminals} first.update({t: {t} for t in terminals}) changed True while changed: changed False for nt, alts in productions.items(): for alt in alts: before len(first[nt]) for sym in alt: if sym ε: first[nt].add(ε) break if sym in terminals: first[nt].add(sym) break # 非终结符把FIRST(sym)除去ε加进来 first[nt] | (first[sym] - {ε}) if ε not in first[sym]: break if len(first[nt]) ! before: changed True for nt in sorted(nonterminals): print(nt, sorted(first[nt]))这个迭代里最容易错的地方是“遇到不能推导出ε的符号就停”。比如对候选式T E如果T的FIRST不含ε那E的FIRST就不能被加进E的FIRST反过来如果T能出ε还要继续处理E。很多同学在这里漏了一层循环导致FIRST集合偏小。FOLLOW集合的计算比FIRST更容易混。核心规则只有三条开始符号的FOLLOW里放$对形如A - α B β的规则把FIRST(β)去掉ε加入FOLLOW(B)对A - α B或β能推出ε的规则把FOLLOW(A)加入FOLLOW(B)。用同样的不动点循环初始只给开始符号放$循环直到所有集合不再增长。计算完以后建议把结果打印出来和教材上的答案对一遍。这里不必去背某本编译原理教材第二章的课后答案关键是把集合和文法对上。3.2 消除左递归和提取左公因子动手写分析器之前必须做的等价变换左递归会造成预测分析表里出现“展开自己”的恶性循环因为M[E, id]既要用E - E T展开E又要等待一个E开头的符号表填不下去。标准做法是把左递归改成右递归再提取左公因子。def remove_direct_left_recursion(nt, productions): alphas [alt[1:] for alt in productions[nt] if alt[0] nt] betas [alt for alt in productions[nt] if alt[0] ! nt] if not alphas: return {nt: productions[nt]}, [] new_nt nt new_prod {nt: [beta [new_nt] for beta in betas], new_nt: [alpha [new_nt] for alpha in alphas] [[ε]]} return new_prod, [new_nt]这个函数的入参是一个非终结符和它的全部产生式。alphas是形如A - A x中的后缀betas是A - y中的非递归候选。输出里A的每个候选都变成y AA的候选是x A和空串。注意如果原文法里有A - ε这种候选它会被当作beta得到的等价文法包含A - A也就是“A能直接变成A”这没问题。提取左公因子是另一个必须做的变换比如A - a b | a c这种文法LL(1)会直接冲突因为向前看a无法区分到底选哪个候选。处理方法就是提公因子A - a XX - b | c。这个变换也要用程序自动做别手搓否则大文法一定出错。3.3 预测分析表驱动循环从表到分析树的最后一个环节FIRST和FOLLOW算完构造LL(1)预测表M的规则是对产生式A - α的每个终结符a属于FIRST(α)把该产生式填入M[A, a]如果α能推出ε则对每个b属于FOLLOW(A)把该产生式填入M[A, b]。同一个格子被填了两次就说明文法不是LL(1)。这就是“冲突检测”的唯一标准。拿上面那个文法跑出来的表大概是M[E, id] E - T EM[E, ] E - T EM[E, $] E - ε。注意M[E, $]这一项来自FOLLOW(E)如果你FOLLOW集合算错这一格就会空掉。驱动循环是一个栈栈底是$栈顶是当前要展开或匹配的非终结符或终结符。Python核心代码M {} for nt in nonterminals: for alt in productions[nt]: fset first_of_sequence(alt) # 整条候选式的FIRST for a in fset - {ε}: M[(nt, a)] alt if ε in fset: for b in follow[nt]: M[(nt, b)] alt def ll1_parse(tokens): stack [$, E] ip 0 while stack: X stack.pop() a tokens[ip] if ip len(tokens) else $ if X a: ip 1 elif X in terminals: raise SyntaxError(f期望 {X}实际 {a}) elif (X, a) in M: for sym in reversed(M[(X, a)]): if sym ! ε: stack.append(sym) else: raise SyntaxError(f非终结符 {X} 遇到 {a}无产生式)逻辑上栈里出不来的终结符必须和当前token匹配非终结符必须能在预测表里查到产生式查到后把产生式右部逆序压栈。这里有一个细节容易卡住倒序压栈是因为栈是后进先出要让最左边的符号先被弹出。空串产生式不要压栈直接匹配掉。如果你习惯用Java编译原理这个组合写实验这个驱动循环完全不用变把stack [$, E]换成StackStringtokens换成ListToken即可。最值得调参的是“栈深上限”。LL(1)理论上不限制栈深但实验实现里最好加一个MAX_STACK_DEPTH 1024超过就报错防止右递归文法在错误输入下陷入无限循环。设太小会让某些长表达式合法输入也崩所以1024是底线不是推荐值。错误恢复方面实验要求不高时最简单的同步办法是发现某非终结符遇到不该出现的token时丢掉当前token并继续读直到遇到该非终结符FOLLOW集合里的符号再恢复。这一招能让一个输入文件里报出两三个错误而不是卡在第一个错误就停下老师测试多错误用例时分数会明显不一样。4. LR(1)语法分析器从LR(0)项目集到规范LR(1)的构造4.1 LR(1)比LL(1)多出来的是什么展望符的传播与状态分裂LL(1)靠向前看一个token决定用哪个产生式LR(1)则结合“左边已经读入的符号栈”做决策。LR(1)项目是[A - α·β, a]点号前面是已经分析出来的部分点号后面是期望输入a是展望符。多出来的这个展望符专门用来解决LL(1)看不到的历史信息。一个教科书级别的例子是这样的简单文法S - S S - L R | R L - * R | id R - L这个文法在LR(0)自动机里会出现一个状态同时包含S - L· R和R - L·。前者要求下一步读等号再继续后者要求当前符号满足一定条件后把L归约为R。如果只看LR(0)这就是移进-归约冲突SLR(1)尝试用FOLLOW(R)解决但FOLLOW(R)里恰好有等号于是分不开LR(1)给这两个项目分别带上不同展望符后同一点位置的项目因为展望符不同而被拆成两个状态才让语法分析器能在“看到等号时移进、看到其他符号时归约”之间做正确选择。这就是为什么LR(1)状态数膨胀得很厉害一个LR(0)状态里的每个项目都要复制多份每个复制品带不同展望符。理解了这个本质后面看状态合并和LALR就顺了。4.2 构造LR(1)项目集和ACTION/GOTO表的代码骨架LR(1)的闭包计算比LR(0)多一个步骤点号后面的符号串要算FIRST再把原项目的展望符追加进去作为新项目的展望符。用Python的namedtuple表达最直接from collections import namedtuple Item namedtuple(Item, [prod_idx, dot, lookahead]) # prod_idx: 产生式编号dot: 点位置lookahead: 展望符 def closure(items, productions, first_all): items set(items) while True: added set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): B rhs[it.dot] if B in nonterminals: beta rhs[it.dot 1:] [it.lookahead] fset first_of_sequence(beta, first_all) for pi, prod in enumerate(productions): if prod[0] B: for la in fset: added.add(Item(pi, 0, la)) if not (added - items): break items | added return items def goto(items, X, productions, first_all): moved set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs) and rhs[it.dot] X: moved.add(Item(it.prod_idx, it.dot 1, it.lookahead)) return closure(moved, productions, first_all)这里最核心的坑是beta rhs[it.dot 1:] [it.lookahead]。很多人只算rhs[it.dot 1]的FIRST但这是不对的。比如项目[A - α·B C, d]点后面的符号串是C d如果C能推出空串那么d也要进入B的展望符。所以必须对“整条剩余串加原展望符”求FIRST。第一次写这个函数时建议单独构造一个极小的文法手推一遍闭包再对照代码输出否则很难发现这个错误。状态集合的构建是一个从初始状态{Item(0, 0, $)}开始的广度优先遍历states [] state_index {} start_items cls_item(Item(0, 0, $)) states.append(start_items) state_index[frozenset(start_items)] 0 worklist [0] while worklist: sidx worklist.pop() items states[sidx] symbols set() for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): symbols.add(rhs[it.dot]) for X in symbols: ns goto(items, X, productions, first_all) if ns: key frozenset(ns) if key not in state_index: state_index[key] len(states) states.append(ns) worklist.append(len(states) - 1)注意GOTO跳转的符号集合要从所有项目里收集不能只收集终结符否则非终结符转移边会漏掉。用frozenset(ns)做状态去重是因为set本身不可哈希但frozenset可以。4.3 ACTION/GOTO表填充规则和实验中最容易绕晕的“合并”操作规范LR(1)分析表的填充规则可以浓缩成四条项目[S - S·, $]对应的ACTION[s][$] acc项目[A - α·, a]对应ACTION[s][a] r_i按产生式编号归约点号后面是终结符x时对应ACTION[s][x] s_j移进到goto结果状态j点号后面是非终结符X时对应GOTO[s][X] j代码骨架ACTION {} GOTO {} for sidx, items in enumerate(states): for it in items: lhs, rhs productions[it.prod_idx] if it.dot len(rhs): if lhs start_symbol and it.lookahead $: ACTION[(sidx, $)] acc else: ACTION[(sidx, it.lookahead)] fr{it.prod_idx} else: X rhs[it.dot] if X in terminals: j state_index[frozenset(goto(items, X, productions, first_all))] if (sidx, X) in ACTION and ACTION[(sidx, X)] ! fs{j}: raise ValueError(f状态{sidx}遇到{X}存在移进-归约或归约-归约冲突) ACTION[(sidx, X)] fs{j} elif X in nonterminals: GOTO[(sidx, X)] state_index[frozenset(goto(items, X, productions, first_all))]这里的冲突检查很重要。规范LR(1)理论上不含冲突但如果你把文法写错了或者LALR合并时生成表就会在这里报出来。我在实验报告里会写清楚冲突不是靠“后写的覆盖先写的”解决必须回到文法层面找问题。关于“LALR合并”两个状态如果项目核心相同不看展望符在规范LR(1)里是两个状态LALR会把它们合并成一个。合并后的状态相当于把两套展望符取并集原本没冲突的状态可能在合并后引入归约-归约冲突。实验里如果老师明确要求LR(1)一般不建议做LALR合并如果状态多到内存不够可以改用SLR或把产生式数量精简。把状态数压缩这件事和你最终得分没太大关系报告里把状态图附上反而更稳。5. 避坑三个实验串跑时的高频翻车现场5.1 词法分析器的“最长匹配”没做对语法分析全盘崩现象输入ifx词法分析器返回关键字if和标识符x语法分析器在期望一个标识符的地方看到关键字if直接报错或者输入123abc词法分析器返回一个整数123再接一个标识符abc而实验要求这里必须报“非法标识符”。原因第一个现象是把“查关键字表”放在了读字符循环里面读到i就匹配ififx被拆成两个token第二个现象是状态机在数字状态没判断后继字母导致该报错的输入被静默拆成两个合法token。解决先读完一串字母/数字放在缓冲区里再整体查关键字表在数字状态下遇到字母不要切token而是把整个123abc标记为TOKEN_UNKNOWN并报错。词法分析器宁可多报错也不要吐出一串“看似合法但语义错误”的token因为语法分析器管不了这种跨token的错误。5.2 FIRST/FOLLOW集合算错预测分析表出现“幽灵冲突”现象LL(1)表构造出来有冲突但用手推文法明明没有冲突或者表不冲突但跑输入时某个格子上查不到规则报“无产生式”。原因绝大多数是FOLLOW集合算错了。常见错误有三个没给开始符号的FOLLOW里放$对形如A - α B β的规则只把FIRST(β)加进FOLLOW(B)没处理β能推出空串的情况不动点循环提前结束集合没收敛。解决把FOLLOW计算也写成和FIRST一样的while循环直到集合大小不再变化算出后用打印语句输出每个非终结符的FOLLOW拿一道教材例题验证。这里不用去翻什么课后习题答案自己构造一个E - T E的小文法人工算一遍FOLLOW(E)如果程序输出和手工不一致那就一行一行调closure代码。幽灵冲突的另一个来源是first_of_sequence函数没有处理“空串符号串”补上就好。5.3 LR(1)状态数爆炸实验内存里跑不动现象文法才二十条产生式规范LR(1)状态数上千个用Python构造到一半内存飙到几个GB程序直接卡死。原因规范LR(1)每个项目都带展望符closure计算反复生成Item对象set去重成本高有些同学用列表嵌套列表表示项目每次比较都是O(n)操作状态一多必然跑不动。解决项目用(prod_idx, dot, lookahead)三元组打包成整数编码把lookahead也映射成小整数这样项目能哈希、能快速比较closure里频繁用到的FIRST结果提前缓存不要每次递归重算如果确实超大规模就退而求其次用SLR或者LALR在实验报告里说明取舍。另外生成状态时用工作队列避免递归深度过深Python递归默认一千层很容易栈溢出。5.4 输入缓冲与行号统计一个小数点误差连累报错信息现象单独跑词法分析器一切正常一接上语法分析器第一个token就少了一个字符或者报错行号整体偏移一行。原因词法分析器里自己维护了预读缓冲但语法分析器也自己读文件两边各读各的导致token流错位行号在状态机的多个case里都有line遇到换行被重复计数。解决规定只有一个入口负责读字符。词法分析器统一用next_char()读语法分析器只接收Token列表绝不直接碰字符流行号只在next_char()里line和col状态机其他位置不允许改行列号。如果用了ungetc放回的字符也要走同一个计数函数否则回退字符的行号会被重复计算。5.5 实验包的文件组织报告、makefile和测试用例的坑现象压缩包解压后是三个目录老师运行make时找不到公共头文件或者词法分析器单独编译通过链接语法分析器时token枚举顺序不一致跑出来的结果完全不对劲。原因三个实验各自复制了一份token定义改词法分析器时忘了同步改语法分析器公共头文件放在顶层目录而makefile用了相对路径从一个子目录里执行就找不到。解决把Token枚举和结构体放到顶层include/token.h三个子目录的源代码都include这个文件写好makefile根目录执行make能依次生成三个可执行文件测试用例单独放tests/目录每个测试文件配一个.out期望文件跑完用diff对比。压缩包里必须附README写明“先make再运行词法输入从stdin读”。我见过太多人栽在路径上老师双击Makefile运行失败直接扣了一档分数。6. 把三个分析器串起来验证方法、可视化与可复用设计三个分析器分开跑通不算完真正拉开差距的是把它们串成一个命令行工具。我习惯给词法分析器加一个-t参数让它只输出token序列这样语法分析器可以用管道直接接收./lexer -t test.c | ./ll1_parser管道方案比起在语法分析器里重新调词法分析函数好处是边界干净。两边只通过文本协议通信token类型用整数编号lexeme用引号包裹语法分析器解析起来很简单。如果你用Python更省事的是直接定义parse_tokens(tokens)把词法分析器返回的列表传进去不要起子进程。验证方法也有讲究。单测之外我强烈建议给LL(1)和LR(1)各加一个“动作轨迹”输出LL(1)每次压栈/弹栈都打印栈内容LR(1)每一轮打印当前状态栈和输入token以及执行的是移进还是归约。这样遇到失败用例可以拿轨迹和手工推导对拍十分钟就能定位到是表填错还是驱动循环写错。这个功能还能顺便生成实验报告里的分析过程表一举两得。另一个让我少熬夜的习惯是三个程序共享同一份Token定义但语法分析器永远不看lexeme字符串只按type判断。词法分析器改一个token名语法分析器完全不用动。测试用例只准备三类最小正确输入、最小错误输入、覆盖所有产生式的输入先用这三类跑通再上一个几千行的大文件做压力测试。大文件挂掉时先看是不是行号统计问题再看是不是栈深上限太小最后才怀疑文法本身。我自己当年做这个实验时把LR(1)的closure函数写了三遍才跑对原因是第一次没把β串后面的展望符拼进FIRST计算。后来学乖了不管多简单的集合运算先单独抽出函数再写测试小文法验证。这个习惯帮我把后面好几个编译实验的返工时间都省下来了。希望帮到你。本文还有配套的精品资源点击获取