企业官网建设流程全解析

简介：一套面向山东科技大学编译原理课程实验的资源，专注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 -> βA'，A' -> αA' | ε。算术表达式文法左递归消除后一般是这组产生式：

这个文法在后续所有步骤里都能用，也方便验证结果。

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 T'，FIRST(F)不含ε，因此FIRST(T)直接继承：{ ( , id }。E同理，FIRST(E)={ ( , id }。再看E'，E' -> + T E'和ε，得到FIRST(E')={ + , ε }。T'同理，FIRST(T')={ * , ε }。全部列出来是：

手算最容易漏的是“右部全部可空才加ε”这条。比如例子里的E，右部T E'，T不可空，所以即使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后面是E'，FIRST(E')去掉ε是+，且E'可空，所以FOLLOW(E)={$，)}也并入；E' -> + T E'同理。最终FOLLOW(T)={ + , $ , ) }。T'在T -> F T'末尾，继承FOLLOW(T)；而F后面是T'，FIRST(T')去掉ε是*，T'可空，FOLLOW(T)也并入，所以FOLLOW(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换成HashMap，set换成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 True

first_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 follow

FOLLOW主循环里只有两类动作：把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 table

table初始化时空串表示没有产生式，而不是把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 -> βA'，A' -> αA' | ε，改写完重新求FIRST和FOLLOW，再检查一遍冲突。

4.2 FIRST集把ε当成了终结符

现象：FIRST(E')正确求出了+和ε，但构造分析表时E'在遇到)或$的地方没有填入E' -> ε，导致输入id+id结束后报错。原因：代码里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 输入串末尾的$没消费完

现象：输入id+id*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}")

对输入id+id*id，输出大致是：第1步栈是“$ E”，剩余输入是“id + id * id $”，动作是“E -> T E'”；第2步栈变成“$ E' T”，动作“T -> F T'”。答辩时这张表比任何文字说明都有说服力，也是每个表项里产生式是怎么来的最直观见证。

第二个做法是给分析器加一个简单的错误恢复。遇到表项为空时不再直接报错退出，而是把栈顶非终结符的FOLLOW集当作同步记号集合，跳过输入中不在其中的符号，局部跳错后继续分析。这个策略在教材里叫恐慌模式，实现量不大，但能让分析器对id+这类残缺输入给出“在+附近发现错误”之类的定位信息。

第三个做法是准备一组正例和反例做回归。正例至少覆盖：单个id、id+id、id+id*id、(id+id)*id；反例至少覆盖：id+、id**id、(id+id缺少右括号。把这组用例写进一个断言函数，每次改动文法或分析器都跑一遍。我自己写编译原理实验的习惯是：先让正例全过，再确认反例全挂，最后才去调可视化。这样改代码时不小心弄坏的东西能立刻暴露出来，不用对着黑匣子瞎猜。这几招不复杂，但能把一个“能跑”的实验变成“讲得清”的实验，希望帮到你。

本文还有配套的精品资源，点击获取