从FIRST/FOLLOW集到预测分析表：图解LL(1)文法分析全过程（附C++核心算法）

从FIRST/FOLLOW集到预测分析表：图解LL(1)文法分析全过程

在编译器的语法分析阶段，LL(1)文法因其清晰的逻辑结构和高效的解析能力成为经典选择。但许多开发者面对FIRST集、FOLLOW集的计算和预测分析表的构建时，常陷入数学符号的迷宫。本文将用可视化思维拆解这三个关键环节，结合实例演算展示算法背后的直觉逻辑。

1. FIRST集：文法推导的起点探测器

FIRST集的核心功能是预测产生式右部的最左终结符。给定非终结符A，FIRST(A)包含所有可能出现在A推导结果首位的终结符。计算时需处理三种典型情况：

def compute_first(A, productions): first_set = set() for prod in productions[A]: first_symbol = prod[0] if is_terminal(first_symbol): first_set.add(first_symbol) # 情况1：直接加入终结符 elif is_nonterminal(first_symbol): first_set.update(compute_first(first_symbol, productions) - {EPSILON}) # 情况2：合并非终结符FIRST集 if EPSILON in compute_first(first_symbol, productions): handle_epsilon_case(prod, first_set) # 情况3：ε传递处理 return first_set

典型误区警示：

• 当产生式右部为A → BCD时，若ε ∈ FIRST(B)，必须继续检查FIRST(C)
• 只有所有右部符号都含ε时，才能将ε加入FIRST(A)

以文法E → TA, A → +TA | ε, T → FB, B → *FB | ε, F → (E) | i为例，其FIRST集计算过程可通过依赖图直观展示：

2. FOLLOW集：上下文环境的扫描仪

FOLLOW集记录非终结符后可能出现的终结符，其计算需要关注产生式右部结构。关键规则包括：

1. 基础规则：文法开始符号的FOLLOW集包含$（输入结束符）
2. 传递规则：对于产生式A → αBβ：
   • 将FIRST(β)-{ε}加入FOLLOW(B)
   • 若β可推导出ε，则将FOLLOW(A)加入FOLLOW(B)

def compute_follow(productions, first_sets): follow_sets = defaultdict(set) follow_sets[start_symbol].add('$') # 规则1 changed = True while changed: changed = False for A in productions: for prod in productions[A]: for i, B in enumerate(prod): if is_nonterminal(B): # 处理A → ...Bβ情况 beta = prod[i+1:] first_beta = compute_sequence_first(beta, first_sets) old_size = len(follow_sets[B]) follow_sets[B].update(first_beta - {EPSILON}) if EPSILON in first_beta or not beta: follow_sets[B].update(follow_sets[A]) # 规则2 if len(follow_sets[B]) > old_size: changed = True return follow_sets

冲突检测点：当同一非终结符的FOLLOW集与FIRST集出现重叠时，可能产生LL(1)分析冲突。例如：

S → aA | bA A → c | ε

此时FOLLOW(A)包含$，而FIRST(A)包含c和ε，需检查SELECT集是否相交。

3. 预测分析表：文法规则的决策矩阵

预测分析表是FIRST和FOLLOW集的联合应用产物，其构建算法可分为三步：

1. 对每个产生式A → α，将A → α加入Table[A][a]，其中a ∈ FIRST(α)
2. 若ε ∈ FIRST(α)，则对每个b ∈ FOLLOW(A)，将A → α加入Table[A][b]
3. 检查每个表项是否唯一，否则文法不是LL(1)

可视化构建示例（部分表格）：

冲突排查技巧：

• 检查同一单元格是否存在多个产生式
• 验证是否满足FIRST(α) ∩ FIRST(β) = ∅对于所有A → α | β
• 确认若ε ∈ FIRST(α)，则FIRST(β) ∩ FOLLOW(A) = ∅

4. 实战演练：从文法到分析器的完整路径

让我们用具体案例串联全流程。给定增强版文法：

S → E E → E + T | T T → T * F | F F → ( E ) | i

步骤1：消除左递归后得到LL(1)文法：

S → E E → TE' E' → +TE' | ε T → FT' T' → *FT' | ε F → ( E ) | i

步骤2：计算关键集合：

FIRST集： - FIRST(F) = { (, i } - FIRST(T') = { *, ε } - FIRST(T) = { (, i } - FIRST(E') = { +, ε } - FIRST(E) = { (, i } - FIRST(S) = { (, i } FOLLOW集： - FOLLOW(S) = { $ } - FOLLOW(E) = { $, ) } - FOLLOW(E') = { $, ) } - FOLLOW(T) = { +, $, ) } - FOLLOW(T') = { +, $, ) } - FOLLOW(F) = { *, +, $, ) }

步骤3：构建预测分析表（关键部分）：

步骤4：分析验证：输入串i+i*i的分析过程如下：

步骤 栈顶 输入 动作 1 S i+i*i$ S → E 2 E i+i*i$ E → TE' 3 TE' i+i*i$ T → FT' 4 FT'E' i+i*i$ F → i 5 iT'E' i+i*i$ 匹配i 6 T'E' +i*i$ T' → ε 7 E' +i*i$ E' → +TE' 8 +TE' +i*i$ 匹配+ 9 TE' i*i$ T → FT' 10 FT'E' i*i$ F → i 11 iT'E' i*i$ 匹配i 12 T'E' *i$ T' → *FT' 13 *FT'E' *i$ 匹配* 14 FT'E' i$ F → i 15 iT'E' i$ 匹配i 16 T'E' $ T' → ε 17 E' $ E' → ε 18 空栈 $ 接受

在实现预测分析器时，两个核心数据结构值得关注：

1. 符号栈：组合使用std::stack和std::vector实现高效操作
2. 分析表：采用std::unordered_map压缩存储，键值设计示例：

struct TableKey { char non_terminal; char terminal; bool operator==(const TableKey&) const = default; }; namespace std { template<> struct hash<TableKey> { size_t operator()(const TableKey& k) const { return (hash<char>()(k.non_terminal) << 8) ^ hash<char>()(k.terminal); } }; } using PredictTable = std::unordered_map<TableKey, Production>;

当处理i**i这类非法输入时，分析器会在步骤12检测到错误——T'面对*时应选择T' → *FT'，但后续F无法推导出第二个*。这种即时错误定位能力正是LL(1)分析器的优势。