一、 什么是预测分析算法？
在编译原理中，预测分析算法（Predictive Parsing）是一种无回溯的自顶向下语法分析方法。它之所以被称为“预测”，是因为分析器在每一步都能根据当前栈顶非终结符和输入符号，唯一确定下一步要使用的产生式，而无需尝试错误的路径后回溯。
⚙️ 核心优势
预测分析器结构简单，易于手工构造或自动生成。由于消除了回溯，其执行效率远高于一般的递归下降分析器，是编译器前端广泛采用的技术。
⚙️ 适用文法
主要适用于LL(1)文法。LL(1)表示从左到右扫描输入，进行最左推导，且每次推导只需向前查看一个输入符号。
⚙️ 关键组件
预测分析器由三个部分组成：输入缓冲区、预测分析表（控制部分）和语法分析栈（工作存储）。
二、 LL(1)文法与集合计算
要使用预测分析算法，首先必须确保文法是LL(1)的。这涉及到两个核心集合的计算：First集和Follow集。
2.1 First集的计算
First(α)是α推导出的所有可能字符串的第一个终结符的集合。如果α能推导出ε，则ε也在First(α)中。
- 若X是终结符，则First(X) = {X}。
- 若X是非终结符，且X→a...是一条产生式，则将a加入First(X)。
- 若X→ε是一条产生式，则将ε加入First(X)。
- 若X→Y...，则将First(Y) - {ε}加入First(X)；若Y→ε，则也将First(Z) - {ε}加入First(X)。
2.2 Follow集的计算
Follow(A)是在文法开始符号S的最左推导中，紧跟在非终结符A后面的终结符的集合。若A是某个句型的最右符号，则#（结束符）在Follow(A)中。
- 对于开始符号S，将#加入Follow(S)。
- 若存在产生式B→αAβ，则将First(β) - {ε}加入Follow(A)。
- 若B→αA或B→αAβ且ε∈First(β)，则将Follow(B)加入Follow(A)。
2.3 LL(1)文法的判定条件
一个文法是LL(1)的，当且仅当对于每个非终结符A的任意两个不同产生式A→α和A→β，满足：
- First(α) ∩ First(β) = ∅
- 如果ε ∈ First(α)，则First(β) ∩ Follow(A) = ∅
| 步骤 | 操作 | 示例说明 |
|---|---|---|
| 1 | 消除左递归 | 将A→Aα|β转换为A→βA', A'→αA'|ε |
| 2 | 提取左公因子 | 若A→αβ1|αβ2，提取为A→αA', A'→β1|β2 |
| 3 | 计算First/Follow | 按定义迭代计算直至不动点 |
| 4 | 检查冲突 | 验证First交集和Follow交集是否为空 |
三、 预测分析表的构建算法
预测分析表M是一个二维表，行对应非终结符，列对应终结符（包括#）。构建过程如下：
构建算法详细步骤
- 对文法的每个产生式A→α，计算First(α)。
- 对于First(α)中的每个终结符a，将A→α加入M[A,a]。
- 若ε∈First(α)，则对于Follow(A)中的每个终结符b，将A→α加入M[A,b]。
- 若#∈Follow(A)且ε∈First(α)，将A→α加入M[A,#]。
- 所有未定义的条目标为错误。
实例：算术表达式文法
文法：
E → T E'
E' → + T E' | ε
T → F T'
T' → F T' | ε
F → ( E ) | id部分预测分析表：
| id | ( | + | ) | # | ||
|---|---|---|---|---|---|---|
| E | E→T E' | E→T E' | ||||
| E' | E'→+ T E' | E'→ε | E'→ε | |||
| T | T→F T' | T→F T' | ||||
| T' | T'→ε | T'→ F T' | T'→ε | T'→ε | ||
| F | F→id | F→( E ) |
构建中的常见错误
- 忽略Follow集：在计算ε产生式时，忘记将Follow(A)中的符号加入表中。
- 左递归未消除：存在左递归的文法无法构建预测分析表，因为会导致无限循环。
- First集计算错误：特别是处理间接左递归或复杂推导时，容易遗漏符号。
四、 预测分析过程与代码实现
预测分析器使用一个栈来模拟最左推导。算法流程如下：
初始化
栈顶压入#，然后压入开始符号S。输入指针指向第一个输入符号。
循环分析
设X为栈顶符号，a为当前输入符号。
- 若X == a == #，分析成功，结束。
- 若X == a != #，弹出X，输入指针前移。
- 若X是非终结符，查表M[X,a]。
- 若M[X,a]包含产生式X→α，弹出X，将α的符号串逆序压入栈（ε则不压入）。
- 若M[X,a]为空，报错。
错误处理
若遇到错误，可尝试弹出栈顶符号直到找到同步符号，或终止分析。
4.1 Python 示例代码
以下是一个简化的Python实现，演示如何使用字典存储预测分析表并进行分析：
def predictive_parser(grammar, input_string):
stack = ['#', 'E']
input_ptr = 0
length = len(input_string)
print(f"{'Step':<5} | {'Stack':<20} | {'Input':<10} | {'Action'}")
print("-" 60)
step = 1
while stack:
top = stack[-1]
curr_input = input_string[input_ptr] if input_ptr < length else '#'
if top == curr_input:
stack.pop()
input_ptr += 1
action = "Match"
elif top in grammar:
if (top, curr_input) in grammar:
prod = grammar[(top, curr_input)]
stack.pop()
if prod != 'ε':
stack.extend(reversed(prod.split()))
action = f"Expand {top}→{prod}"
else:
action = "Error"
break
else:
action = "Error"
break
print(f"{step:<5} | {''.join(stack)[::-1]:<20} | {curr_input:<10} | {action}")
step += 1
if not stack and curr_input == '#':
print("Success!")
else:
print("Failed!")
示例文法 (简化版)
grammar = {
('E', 'id'): ['T', "E'"],
('E', '('): ['T', "E'"],
("E'", '+'): ['+', 'T', "E'"],
("E'", ')'): ['ε'],
("E'", '#'): ['ε'],
('T', 'id'): ['F', "T'"],
('T', '('): ['F', "T'"],
("T'", ''): ['', 'F', "T'"],
("T'", '+'): ['ε'],
("T'", ')'): ['ε'],
("T'", '#'): ['ε'],
('F', 'id'): ['id'],
('F', '('): ['(', 'E', ')']
}
predictive_parser(grammar, "id+idid")六、 常见问题解答 (FAQ)
预测分析算法是一种自顶向下的语法分析方法，它使用一个预测分析表和一个栈来解析输入字符串。它不需要回溯，因此效率高，常用于编译器前端的设计。
一个文法是LL(1)的，当且仅当对于每个非终结符的任意两个不同产生式A→α和A→β，满足：First(α) ∩ First(β) = ∅；如果ε ∈ First(α)，则First(β) ∩ Follow(A) = ∅。
First集是指一个符号串推导出的所有可能字符串的第一个终结符的集合。Follow集是指在一个文法的某个句型中，紧跟在某个非终结符后面的终结符的集合。
直接左递归可以通过重写产生式消除，如A→Aα|β变为A→βA'，A'→αA'|ε。间接左递归需要通过代入法转化为直接左递归后再消除。
因为LL(1)文法进行的是最左推导，如果存在左递归（如A→Aα），分析器在展开A时会无限递归地调用A本身，导致栈溢出或无限循环，无法终止。