编译技术4-3

Non LL(1) Grammar to LL(1) Grammar（非 LL(1) 文法到 LL(1) 文法）

✦ Non LL(1) Grammar（非 LL(1) 文法）

A grammar is not LL(1) if it contains:

  • Left recursion（左递归）
  • Left factoring（左因子提取）

即：若文法存在左递归或多个产生式拥有相同前缀，就不能被预测分析（非 LL(1)）。

⚠️ 注意：即使一个文法没有左递归和左因子，也不一定是 LL(1) 文法。

✦ Left Factoring（左因子提取）

➤ English Definition:

Left factoring occurs when two or more productions for a nonterminal start with the same prefix.

例如：

1
A → αβ | αρ

两个产生式都以 α 开头。

➤ 中文解释：

当一个非终结符的多个产生式拥有相同的开头串（前缀），称该文法具有左因子。

在这种情况下：

1
FIRST(αβ) ∩ FIRST(αρ) ≠ Ø

说明文法不是 LL(1)。

➤ Transformation（转换方法）

提取公因子 α：

1
2
A → αA′
A′ → β | ρ

✦ Left Recursion（左递归）

➤ English Definition:

A grammar is left recursive if there is a derivation such that:

1
A ⇒+ Aα

It can be:

  • Immediate Left Recursion（直接左递归）:
    • A → Aα
  • Indirect Left Recursion（间接左递归）:
    • A → Bβ, and B → Aγ

➤ 中文解释：

当某个非终结符 A 的产生式可以回到自己作为左边符号，称为左递归：

  • 直接左递归：如 A → Aα
  • 间接左递归：如 A → Bβ，B → Aγ，则 A ⇒+ A…

➤ 为什么不符合 LL(1)：

例子：

1
A → Aα | β

预测分析时不能根据当前输入决定使用哪个产生式， 因为：

1
FIRST(Aα) ⊇ FIRST(β)

造成冲突，所以不是 LL(1)。

➤ 消除直接左递归的方法：

1
2
3
原始： A → Aα | β
转换： A → βA′
        A′ → αA′ | ε

✦ 总结 Summary

问题类型 示例 解决方案
Left Factoring（左因子） A → αβ αρ 提取左因子 α
Left Recursion（左递归） A → Aα β 转换为右递归形式（使用 A′）

📘 非 LL(1) 文法转 LL(1) 文法 Non-LL(1) Grammar to LL(1) Grammar Notes

🎯 目标 Objective

将不符合 LL(1) 条件的文法，使用一些重写技术进行转换，使其满足 LL(1) 条件。主要技术包括： - 去除左递归 Left Recursion Removal - 提取左因子 Left Factoring

⚠️ 注意：即使使用这些方法，也不能保证一定能转换为 LL(1) 文法。

🌀 去除左递归 Left Recursion Removal

✅ 立即左递归（Immediate Left Recursion）

简单情况 Simple Case： 

1
A → Aα | β
转换成 Transformed: 
1
2
A → βA'
A' → αA' | ε

✅ 一般情况 General Case

1
A → Aα1 | Aα2 | ... | Aαm | β1 | β2 | ... | βn

转换成 Transformed: 

1
2
A  → β1A' | β2A' | ... | βnA'
A' → α1A' | α2A' | ... | αmA' | ε

📌 示例 Example

原文法 Grammar G： 

1
2
3
E → E + T | T
T → T * F | F
F → (E) | i
转换后文法 Grammar G'： 
1
2
3
4
5
6
7
E  → T E'
E' → + T E' | ε

T  → F T'
T' → * F T' | ε

F  → (E) | i

🌿 提取左因子 Left Factoring

✅ 简单情况 Simple Case

原始规则 Original: 

1
A → αβ | αr
提取公共前缀α，转换成： 
1
2
A  → αA'
A' → β | r

✅ 一般情况 General Case

1
A → αβ1 | αβ2 | ... | αβn

转换成： 

1
2
A  → αA'
A' → β1 | β2 | ... | βn

📌 示例 Example

原文法 G1： 

1
S → aSb | aS | ε
左因子为 aS，转换成： 
1
2
S  → aS S' | ε
S' → b | ε

也可以写成： 

1
S → aS(b|ε) | ε

📍 技巧总结 Tips Summary

  • 去除左递归是为了解决“递归下降分析器”无限循环的问题。
  • 左因子提取是为了避免两个候选项的 FIRST 集交叉。
  • 每次修改文法后要重新计算 FIRST / FOLLOW 集并检查 LL(1) 条件。
  • 判断 LL(1) 的标准：
    1. 对于 A → α1 | α2，必须满足 FIRST(α1) ∩ FIRST(α2) = ∅；
    2. 若 FIRST(αi) 包含 ε，则还要保证 FIRST(αi) ∩ FOLLOW(A) = ∅。