LL(1)分析法实验：从FIRST/FOLLOW集到预测分析表的Python实现

简介一套面向山东科技大学编译原理课程实验的资源专注LL(1)语法分析法的实现与应用。内置可直接在Code::Blocks中运行的源代码和完整实验报告针对给定文法E→TG、G→TG|-TG|ε、T→FM、M→*FM|/FM|ε、F→(E)|i完成LL(1)预测分析表构造并对任意输入的符号串进行语法分析输出判定结果。压缩包约1.08MB内容主要分为源码与报告两部分源码中按FIRST集、FOLLOW集、预测分析表模块划分配有关键注释下载后无需额外配置即可直接运行。目前已累计913人学习浏览适合编译原理初学入门和课程设计巩固。借助其中代码与实验报告读者可理清LL(1)分析器的自上而下推导和报错处理流程掌握消除左递归、构造预测表等核心方法并可复用代码进行不同输入串的测试验证为后续自底向上分析学习打下坚实基础。1. LL(1)分析法语法分析实验里最容易“看着懂、写不出”的模块LL(1)分析法是编译原理课程语法分析阶段最经典的自顶向下方案也是山科大这类实验里几乎必做的一环。很多人上课能背出FIRST集和FOLLOW集的定义真到实验课对着一段文法写代码时却常常卡在“从哪一步开始”和“写出来怎么证明对了”。这篇按照一条能跑通的主线拆解先检查文法是否满足LL(1)条件再手算FIRST集和FOLLOW集接着构造预测分析表最后用表驱动方式完成输入串匹配。给出的是可以直接复现的Python代码后面跟着每个环节容易踩的坑。适合正在赶编译原理实验的学生也想借这份梳理把自顶向下语法分析再捋一遍的工程师。2. 先过文法关左递归消除与FIRST/FOLLOW集手算LL(1)里的三个字符含义第一个L表示从左到右扫描输入串第二个L表示推导时始终用最左推导(1)表示每一步只凭当前输入符号就能确定用哪个产生式。这意味着LL(1)分析法对文法有硬性要求先确认文法过关后面的代码才值得写。2.1 三个硬性要求无左递归、无二义、无回溯第一文法不能有左递归。比如E - E T | T这种产生式推导时E不断替换成E展开过程没有出口。表驱动分析器一旦碰到这类产生式栈里会反复压入相同的非终结符最后栈满或者超时。第二文法不能有二义性。比如E - E E | E * E | id同一个输入串可能对应两棵语法树预测分析表里同一个表格位置会同时填入两个产生式。第三产生式之间不能有回溯。比如A - ab | ac两个右部都能推出a开头分析器看到输入a时不知道选哪个。这三个要求本质上是同一个问题预测分析表不能出现冲突。如果实验给的文法存在左递归常见做法是先消除。标准模板是把A - Aα | β改成A - βAA - αA | ε。算术表达式文法左递归消除后一般是这组产生式非终结符产生式ET EE T E / εTF TT* F T / εF( E ) / id这个文法在后续所有步骤里都能用也方便验证结果。2.2 FIRST集手算规则和算例FIRST集描述一个符号串能推导出的所有可能开头终结符如果串本身能推导成空串ε也放进FIRST集。手算规则三条终结符的FIRST集就是它自己产生式X - a…形式a加入FIRST(X)产生式X - Y…形式FIRST(Y)去掉ε全部加入FIRST(X)如果Y可空继续看下一个符号右部全部可空时ε加入FIRST(X)。对上节的文法从最下层的F往上推。F有两个产生式F - ( E )开头是终结符(F - id开头是终结符id所以FIRST(F){ ( , id }。T - F TFIRST(F)不含ε因此FIRST(T)直接继承{ ( , id }。E同理FIRST(E){ ( , id }。再看EE - T E和ε得到FIRST(E){ , ε }。T同理FIRST(T){ * , ε }。全部列出来是非终结符FIRST集E{ ( , id }E{ , ε }T{ ( , id }T{ * , ε }F{ ( , id }手算最容易漏的是“右部全部可空才加ε”这条。比如例子里的E右部T ET不可空所以即使E可空E的FIRST集也不含ε。2.3 FOLLOW集手算三条规则和三个漏点FOLLOW集表示在推导过程中紧跟某个非终结符之后可能出现的终结符。手算规则开始符号的FOLLOW集先放入$产生式A - αBβFIRST(β)去掉ε全部加入FOLLOW(B)产生式A - αB或β可空时FOLLOW(A)全部加入FOLLOW(B)。对上面的文法先看E。E是开始符号FOLLOW(E)放入$F - ( E )说明紧跟E的是)FOLLOW(E){ $ , ) }。E出现在E - T E的末尾FOLLOW(E)直接继承FOLLOW(E)还是{ $ , ) }。T的FOLLOW来自两个地方E - T E里T后面是EFIRST(E)去掉ε是且E可空所以FOLLOW(E){$)}也并入E - T E同理。最终FOLLOW(T){ , $ , ) }。T在T - F T末尾继承FOLLOW(T)而F后面是TFIRST(T)去掉ε是*T可空FOLLOW(T)也并入所以FOLLOW(F){ * , , $ , ) }。整理非终结符FOLLOW集E{ $ , ) }E{ $ , ) }T{ , $ , ) }T{ , $ , ) }F{ * , , $ , ) }三个最容易漏的地方开始符号的$容易丢非终结符出现在产生式末尾时FOLLOW(A)的继承容易丢右部β可空时FOLLOW(A)并入FOLLOW(B)这步容易丢。这三个漏点在代码阶段会有对应的坑。2.4 冲突检查怎么判断文法能不能直接用有了FIRST和FOLLOW集可以手工判断文法是不是LL(1)对每个非终结符A的两条或多条产生式A - α | β要求FIRST(α)和FIRST(β)不相交如果再有一个右部能推出ε比如α可空还要求FIRST(β)和FOLLOW(A)不相交。拿上面文法验证E的两条产生式FIRST分别是{}和{ε}后者进一步要求FIRST({}){}与FOLLOW(E){$)}不相交成立。T同理*和FOLLOW(T){$)}不交。F的两条产生式FIRST分别是{(}和{id}也不交。这个文法是标准的LL(1)文法后面构造分析表只会每个表项恰好一个候选。如果检查发现冲突说明直接套表驱动分析器必然翻车。这时先回去改造文法而不是在分析器里打补丁。3. 用Python实现LL(1)从分析表到表驱动分析很多学校的编译原理实验指定Java我这边用Python把逻辑讲透因为字典和集合天然适合描述文法与非终结符集合。迁移到Java时把下文里的dict换成HashMapset换成HashSet循环逻辑一行都不用改。3.1 文法、终结符和非终结符先定义成什么用一个字典存产生式key是非终结符value是右部字符串的列表。终结符、非终结符分别用set存程序里判断一个符号是终结符还是非终结符时直接查这两个集合。有一个细节带撇号的E、T在字符串里没问题但要保证所有地方写法完全一致否则查表时匹配不上。# 终结符集合id 表示标识符实验中也可以换成 num terminals {, *, (, ), id} non_terminals {E, E, T, T, F} grammar { E: [T E], E: [ T E, ε], T: [F T], T: [* F T, ε], F: [( E ), id], } start E这段定义是后面全部代码的数据基础。注意ε在代码里当成普通符号处理但不放进terminals这样对终结符的遍历不会把ε当初终结符。3.2 求FIRST集用不动点迭代而不是递归手算FIRST集可以用递归推导代码里我更推荐不动点迭代维护一个集合不断把新元素加进去直到整个集合不再变化。好处是文法复杂时不会写错递归终止条件也不会有栈溢出。def first_sets(grammar, non_terminals, terminals): first {nt: set() for nt in non_terminals} changed True while changed: changed False for A, prods in grammar.items(): for rhs in prods: symbols rhs.split() # 遍历右部符号把可推导出的开头终结符加入 first[A] for idx, sym in enumerate(symbols): if sym in terminals or sym ε: if sym not in first[A]: first[A].add(sym) changed True if sym ! ε: break elif sym in non_terminals: # 把 first[sym] 里的非 ε 全部并入 for x in first[sym] - {ε}: if x not in first[A]: first[A].add(x) changed True if ε not in first[sym]: break else: # 右部符号全部可空说明 A 能推出空串 if ε not in first[A]: first[A].add(ε) changed True return first逻辑分为三层外层循环控制不动点迭代中层遍历每个非终结符的每条产生式内层遍历右部符号。遇到终结符或ε直接加入集合然后看是不是ε不是ε就说明这个右部已经“开头确定”break掉。遇到非终结符就把它的FIRST集非ε部分并进来如果它本身可空继续看下一个符号不能空就break。for-else结构当内层循环没有break时执行表示右部全部可空把ε加进去。提示Python的for-else在循环没有被break打断时执行else分支这里正好对应“右部所有符号都可空”的情况比手动维护一个布尔标记更简洁。这里有一个参数值得展开terminals集合里没有ε但代码里判断了sym ε这两者不冲突。ε只是内部使用的空串标记不参与终结符匹配。3.3 求FOLLOW集两个辅助函数先写好FOLLOW集同样用不动点迭代。但它的规则涉及“符号串β的FIRST集”和“符号串β是否可空”这两个判断在多个地方复用先写成辅助函数避免在FOLLOW主循环里写冗长的判断。def first_of_string(symbols, first, non_terminals, terminals): # 对符号串求 FIRST规则与单个符号一致 result set() for sym in symbols: if sym in terminals: result.add(sym) break if sym ε: result.add(ε) break result | (first[sym] - {ε}) if ε not in first[sym]: break else: result.add(ε) return result def can_derive_empty(symbols, first, non_terminals, terminals): # 符号串是否整体可空 for sym in symbols: if sym ε: continue if sym in terminals: return False if sym in non_terminals and ε not in first[sym]: return False return Truefirst_of_string和求单个非终结符FIRST的思路一样只是把右部一串符号逐个处理。can_derive_empty碰到终结符返回False碰到非终结符看它的FIRST里有没有ε全部通过才返回True。注意空列表调用can_derive_empty返回True这在产生式末尾判断是需要的。def follow_sets(grammar, non_terminals, terminals, first, start): follow {nt: set() for nt in non_terminals} follow[start].add($) # 开始符号的 FOLLOW 一定包含 $ changed True while changed: changed False for A, prods in grammar.items(): for rhs in prods: symbols rhs.split() for i, sym in enumerate(symbols): if sym not in non_terminals: continue beta symbols[i 1:] # 把 FIRST(beta) 的非 ε 部分加入 FOLLOW(sym) for x in first_of_string(beta, first, non_terminals, terminals): if x ! ε and x not in follow[sym]: follow[sym].add(x) changed True # beta 为空或可空时FOLLOW(A) 全部并入 if can_derive_empty(beta, first, non_terminals, terminals): for x in follow[A]: if x not in follow[sym]: follow[sym].add(x) changed True return followFOLLOW主循环里只有两类动作把beta的FIRST非ε并入以及把FOLLOW(A)并入。两个动作严格对应手算规则的第二条和第三条。can_derive_empty(beta)返回True同时覆盖了“beta是空串”和“beta可空”两种情况这是代码里最容易写漏的一处。3.4 构造预测分析表冲突在这里暴露预测分析表是二维结构行是非终结符列是终结符值是产生式右部。Python里适合用嵌套字典表示。填表规则对应手算冲突检查对产生式A - αFIRST(α)里每个终结符t在table[A][t]填入αFIRST(α)含ε时FOLLOW(A)里每个终结符t也在table[A][t]填入α。如果同一个位置被填了两次这个文法就不是LL(1)。def build_table(grammar, non_terminals, terminals, first, follow): # 列包含终结符和输入末尾标记 $$ 不算真实终结符 table {nt: {t: for t in (terminals | {$})} for nt in non_terminals} for A, prods in grammar.items(): for rhs in prods: symbols rhs.split() f_rhs first_of_string(symbols, first, non_terminals, terminals) # 规则一FIRST 里的每个终结符都填这条产生式 for t in f_rhs: if t ! ε: if table[A][t] ! : print(f冲突: table[{A}][{t}] 已有 {table[A][t]}再填 {rhs}) table[A][t] rhs # 规则二右部可空时FOLLOW 里的每个终结符也填 if ε in f_rhs: for t in follow[A]: if table[A][t] ! : print(f冲突: table[{A}][{t}] 已有 {table[A][t]}再填 {rhs}) table[A][t] rhs return tabletable初始化时空串表示没有产生式而不是把None放进去后面驱动分析时判断更方便。冲突检测打印要保留运行结果里一旦出现“冲突: table[E][]”这类输出直接说明文法不过关省得在驱动阶段花时间排错。3.5 表驱动分析器栈、输入串和动作三要素表驱动分析的核心是一个栈。初始时栈底放$再把开始符号压入输入串末尾也要追加$。每次取出栈顶符号top和当前输入符号a分三种情况top和a相同说明这一位匹配弹出栈顶并消费输入top是非终结符查表得到产生式弹出top把右部符号从右往左压栈top是终结符但和a不相同或者表项为空直接报错。def parse(input_tokens, table, start, terminals, non_terminals): tokens input_tokens [$] stack [$, start] ip 0 steps [] step_no 1 while stack: top stack[-1] a tokens[ip] action if top a: stack.pop() ip 1 action 匹配 elif top in terminals: print(f语法错误: 期望 {top}遇到 {a}) return False, steps elif table[top].get(a): rhs table[top][a] stack.pop() if rhs ! ε: for sym in reversed(rhs.split()): stack.append(sym) action f{top} - {rhs} else: print(f语法错误: 符号 {a} 无法从 {top} 推导) return False, steps steps.append((step_no, .join(stack), .join(tokens[ip:]), action)) step_no 1 return ip len(tokens) - 1, steps注意最后返回时ip要等于len(tokens)-1也就是消费到了输入串末尾的$。只判断stack为空还不够因为输入串可能还剩符号没消费。steps列表记录了每一步的栈、剩余输入和使用动作它是第五章做可视化的基础数据。假设输入已经切分成token列表比如id id * id直接split成[id,,id,*,id]词法切分不属于这部分的重点。4. 避坑LL(1)实验里最常见的五个翻车现场LL(1)分析器代码量不大但翻车点集中在文法处理和集合计算上。下面五条是我自己写这类实验时踩过或帮同学排查过的现象按“现象、原因、解决”展开。4.1 左递归没消除栈被越压越深现象程序跑起来不报错但输入很短也会卡住或者栈列表越来越长最后抛异常。原因文法里还有E - E T这类左递归表驱动分析器遇到输入开头是id时根据表项反复把E弹出又压回栈顶像一个死循环。解决先做左递归消除不要试图在分析器里限制栈深度。最稳的做法是把左递归产生式A - Aα | β改写成A - βAA - αA | ε改写完重新求FIRST和FOLLOW再检查一遍冲突。4.2 FIRST集把ε当成了终结符现象FIRST(E)正确求出了和ε但构造分析表时E在遇到)或$的地方没有填入E - ε导致输入idid结束后报错。原因代码里if sym in terminals判断时ε被错误地放进了terminals集合或者遍历FIRST集时没跳过ε导致ε被当作表列名。解决terminals集合绝不包含ε所有对FIRST集遍历并填表的循环里第一件事就是跳过ε。这个细节一次改到位后面不用再回来查。4.3 FOLLOW集漏掉$或漏掉继承现象FOLLOW(E)只有{)}没有{$}或者FOLLOW(T)只有{}没有{$,)}构造出来的表在输入串末尾报错。原因初始化时没有给开始符号的FOLLOW加入$或者产生式A - αB这种B在末尾的情况没把FOLLOW(A)继承给FOLLOW(B)。解决在follow_sets函数里第一步就执行follow[start].add($)对每条产生式遇到非终结符sym时无条件执行“sym后面一段为空或可空时并入FOLLOW(A)”。这里最隐蔽的是β可空也算很多版本只处理了β为空没处理β可空。4.4 符号串里的撇号导致split结果不匹配现象找遍表格发现table[E]是空的打印grammar的key却明明有E。原因代码里把带撇号的非终结符写成了E或全角撇号E′和non_terminals集合里定好的ASCII单引号E不是同一个字符。Python字符串比较严格一个字符不同就匹配不上。解决统一用ASCII单引号表示E或者干脆改用E1、T1这样的写法。我自己写这类实验的习惯是直接用E1省得在打印和转移时被终端转义搞乱。这个坑属于血泪经验排查时用肉眼很难看出来。4.5 输入串末尾的$没消费完现象输入idid*id栈已经只剩$程序还报语法错误或者反过来输入串多了一个符号程序还说成功。原因表驱动分析要求栈底$和输入串末尾$配对有些实现只在栈里放了$输入串没追加$循环结束时机就错了。解决parse函数第一行tokens input_tokens [$]返回值用ip len(tokens) - 1判断是否消费到末位。这行代码是整个分析器正确终止的保证缺了它程序就得靠运气退出。5. 把分析过程可视化答辩时能演示的三种做法LL(1)分析器本身跑通不难真正能在实验答辩里加分的是能说清楚每一步为什么这么做。最直接的办法是复用parse里记录的steps把栈、剩余输入和使用动作按表格打印出来print(f{步骤:4} {栈:12} {剩余输入:16} {动作}) for no, stack, rest, action in steps: print(f{no:4} {stack:12} {rest:16} {action})对输入idid*id输出大致是第1步栈是“$ E”剩余输入是“id id * id $”动作是“E - T E”第2步栈变成“$ E T”动作“T - F T”。答辩时这张表比任何文字说明都有说服力也是每个表项里产生式是怎么来的最直观见证。第二个做法是给分析器加一个简单的错误恢复。遇到表项为空时不再直接报错退出而是把栈顶非终结符的FOLLOW集当作同步记号集合跳过输入中不在其中的符号局部跳错后继续分析。这个策略在教材里叫恐慌模式实现量不大但能让分析器对id这类残缺输入给出“在附近发现错误”之类的定位信息。第三个做法是准备一组正例和反例做回归。正例至少覆盖单个id、idid、idid*id、(idid)*id反例至少覆盖id、id**id、(idid缺少右括号。把这组用例写进一个断言函数每次改动文法或分析器都跑一遍。我自己写编译原理实验的习惯是先让正例全过再确认反例全挂最后才去调可视化。这样改代码时不小心弄坏的东西能立刻暴露出来不用对着黑匣子瞎猜。这几招不复杂但能把一个“能跑”的实验变成“讲得清”的实验希望帮到你。本文还有配套的精品资源点击获取