原问题：

给定文法 G[S]:
S → A
A → B | A i B
B → C | B + C
C → ) A * | (

要求：
(1) 将文法 G[S] 改写为 LL(1) 文法。
(2) 求经改写后的文法的每个非终结符的 FIRST 集和 FOLLOW 集。
(3) 构造相应的预测分析表。

第一步：理解原始文法

在开始之前，我们先明确文法中的符号：

• 非终结符 (Non-terminals): S, A, B, C (大写字母)
• 终结符 (Terminals): i, +, *, (, ) (小写字母或特殊符号)。这里 i 代表一个标识符或原子表达式。
• 产生式 (Productions): 上述规则。
• 开始符号 (Start Symbol): S

第二步：将文法 G[S] 改写为 LL(1) 文法 (消除左递归和提取左公因子)

LL(1) 文法要求：

1. 无左递归 (No Left Recursion): 任何非终结符 A 都不能通过 A $\Rightarrow^+$ A$\alpha$ 导出自身。
2. 无左公因子 (No Common Prefixes): 对于 A $\rightarrow \alpha \beta_1 | \alpha \beta_2$，需要提取左公因子。
3. LL(1) 条件满足： 对于 A $\rightarrow \alpha | \beta$，必须满足 FIRST($\alpha$) $\cap$ FIRST($\beta$) = $\emptyset$。如果其中一个产生式可以导出 $\epsilon$，则需要进一步检查 FIRST($\alpha$) $\cap$ FOLLOW(A) = $\emptyset$。

现在我们检查原始文法：

1. S → A (无左递归，无左公因子)
2. A → B | A i B
   • 存在左递归：A → A i B。
   • 消除左递归的通用规则：对于 $A \rightarrow A\alpha | \beta$，改写为 $A \rightarrow \beta A'$，$A' \rightarrow \alpha A' | \epsilon$。
   • 这里 $\beta = B$，$\alpha = i B$。
   • 改写后：
     • A → B A'
     • A' → i B A' | ε (ε 表示空串)
3. B → C | B + C
   • 存在左递归：B → B + C。
   • 这里 $\beta = C$，$\alpha = + C$。
   • 改写后：
     • B → C B'
     • B' → + C B' | ε
4. *C → ) A | (** (无左递归，无左公因子)

改写后的 LL(1) 文法 G'[S]：

1. S → A
2. A → B A'
3. A' → i B A' | ε
4. B → C B'
5. B' → + C B' | ε
6. C → ) A * | (

第三步：计算 FIRST 集和 FOLLOW 集

终结符： i, +, *, (, ), $ (其中 $ 是表示输入结束的特殊符号)
非终结符： S, A, A', B, B', C

计算 FIRST 集 (First Set)

定义： FIRST(X) 是所有可以由 X 导出的串的第一个终结符的集合。如果 X 可以导出空串 ε，则 ε 也包含在 FIRST(X) 中。

规则：

1. 如果 X 是终结符，则 FIRST(X) = {X}。
2. 如果 X 是非终结符，且有产生式 X → a... (其中 a 是终结符)，则将 a 加入 FIRST(X)。
3. 如果 X 是非终结符，且有产生式 X → Y1 Y2 ... Yk：
   • 将 FIRST(Y1) 中除 ε 外的所有符号加入 FIRST(X)。
   • 如果 ε 属于 FIRST(Y1)，则将 FIRST(Y2) 中除 ε 外的所有符号加入 FIRST(X)。
   • 依此类推，直到某个 Yi 的 FIRST 集中不包含 ε，或者所有 Yi 的 FIRST 集中都包含 ε。
   • 如果所有 Yi 的 FIRST 集中都包含 ε，则将 ε 加入 FIRST(X)。

计算过程：

1. 直接根据产生式判断：

   • A' → i B A' | ε $\Rightarrow$ FIRST(A') = {i, ε}
   • B' → + C B' | ε $\Rightarrow$ FIRST(B') = {+, ε}
   • C → ) A * | ( $\Rightarrow$ FIRST(C) = {), (}

2. 根据已知的 FIRST 集推导：

   • B → C B'：B 的第一个符号取决于 C。
     • FIRST(B) = FIRST(C) = {), (} (因为 FIRST(C) 不含 ε)
   • A → B A'：A 的第一个符号取决于 B。
     • FIRST(A) = FIRST(B) = {), (} (因为 FIRST(B) 不含 ε)
   • S → A：S 的第一个符号取决于 A。
     • FIRST(S) = FIRST(A) = {), (}

最终的 FIRST 集：

• FIRST(S) = {), (}
• FIRST(A) = {), (}
• FIRST(A') = {i, ε}
• FIRST(B) = {), (}
• FIRST(B') = {+, ε}
• FIRST(C) = {), (}

计算 FOLLOW 集 (Follow Set)

定义： FOLLOW(A) 是所有可能出现在非终结符 A 之后的终结符的集合。如果 A 是句子的最后一个符号，则 $ (输入结束符) 包含在 FOLLOW(A) 中。

规则：

1. 将 $ 加入 FOLLOW(S) (S 是开始符号)。
2. 如果存在产生式 A → $\alpha$ B $\beta$：
   • 将 FIRST($\beta$) 中除 ε 外的所有符号加入 FOLLOW(B)。
   • 如果 ε 属于 FIRST($\beta$)，则将 FOLLOW(A) 的所有符号加入 FOLLOW(B)。
3. 如果存在产生式 A → $\alpha$ B：
   • 将 FOLLOW(A) 的所有符号加入 FOLLOW(B)。

计算过程 (迭代进行，直到集合不再变化)：

初始状态：

• FOLLOW(S) = {$}
• FOLLOW(A) = {}
• FOLLOW(A') = {}
• FOLLOW(B) = {}
• FOLLOW(B') = {}
• FOLLOW(C) = {}

迭代 1：

• S → A: 根据规则 3，FOLLOW(A) += FOLLOW(S) = {$}。
  • FOLLOW(A) = {$}
• A → B A':
  • 根据规则 2，FOLLOW(B) += FIRST(A') = {i, ε}。所以 FOLLOW(B) += {i}。
  • 因为 ε 属于 FIRST(A')，所以 FOLLOW(B) += FOLLOW(A) = {$}。
  • FOLLOW(B) = {i, $}
• A' → i B A':
  • 根据规则 2，FOLLOW(B) += FIRST(A') = {i, ε}。所以 FOLLOW(B) += {i} (已存在)。
  • 因为 ε 属于 FIRST(A')，所以 FOLLOW(B) += FOLLOW(A')。
• B → C B':
  • 根据规则 2，FOLLOW(C) += FIRST(B') = {+, ε}。所以 FOLLOW(C) += {+}。
  • 因为 ε 属于 FIRST(B')，所以 FOLLOW(C) += FOLLOW(B) = {i, $}。
  • FOLLOW(C) = {+, i, $}
• B' → + C B':
  • 根据规则 2，FOLLOW(C) += FIRST(B') = {+, ε}。所以 FOLLOW(C) += {+} (已存在)。
  • 因为 ε 属于 FIRST(B')，所以 FOLLOW(C) += FOLLOW(B')。
• C → ) A *:
  • 根据规则 2，FOLLOW(A) += {*}。
  • FOLLOW(A) = {$, *}

当前状态 (迭代 1 结束)：

• FOLLOW(S) = {$}
• FOLLOW(A) = {$, *}
• FOLLOW(A') = {}
• FOLLOW(B) = {i, $}
• FOLLOW(B') = {}
• FOLLOW(C) = {+, i, $}

迭代 2： (主要传播上一步更新的 FOLLOW 集)

• A → B A': FOLLOW(B) += FOLLOW(A) = {$, *}。
  • FOLLOW(B) = {i, $, *} (更新)
• B → C B': FOLLOW(C) += FOLLOW(B) = {i, $, *}。
  • FOLLOW(C) = {+, i, $, *} (更新)
• A' → i B A': FOLLOW(B) += FOLLOW(A') (无新内容，因为 FOLLOW(A') 仍为空)。
• B' → + C B': FOLLOW(C) += FOLLOW(B') (无新内容，因为 FOLLOW(B') 仍为空)。

当前状态 (迭代 2 结束)：

• FOLLOW(S) = {$}
• FOLLOW(A) = {$, *}
• FOLLOW(A') = {}
• FOLLOW(B) = {i, $, *}
• FOLLOW(B') = {}
• FOLLOW(C) = {+, i, $, *}

迭代 3： (继续传播)

• A' → i B A': A' 在产生式 A → B A' 中，且 A' 可导出 ε。所以 FOLLOW(A') += FOLLOW(A) = {$, *}。
  • FOLLOW(A') = {$, *} (更新)
• B' → + C B': B' 在产生式 B → C B' 中，且 B' 可导出 ε。所以 FOLLOW(B') += FOLLOW(B) = {i, $, *}。
  • FOLLOW(B') = {i, $, *} (更新)

当前状态 (迭代 3 结束)：

• FOLLOW(S) = {$}
• FOLLOW(A) = {$, *}
• FOLLOW(A') = {$, *}
• FOLLOW(B) = {i, $, *}
• FOLLOW(B') = {i, $, *}
• FOLLOW(C) = {+, i, $, *}

检查： 集合不再变化。

最终的 FOLLOW 集：

• FOLLOW(S) = {$}
• FOLLOW(A) = {$, *}
• FOLLOW(A') = {$, *}
• FOLLOW(B) = {i, $, *}
• FOLLOW(B') = {i, $, *}
• FOLLOW(C) = {+, i, $, *}

第四步：构造预测分析表

定义： 预测分析表 M 是一个二维表，行是非终结符，列是终结符（包括 $）。M[A, a] 存储当栈顶是非终结符 A 且当前输入符号是终结符 a 时，应该使用的产生式 A → $\alpha$。

构造规则：
对于文法 G' 中的每个产生式 A → $\alpha$：

1. 对于 FIRST($\alpha$) 中的每一个终结符 a，将 A → $\alpha$ 加入 M[A, a]。
2. 如果 ε 属于 FIRST($\alpha$)，则对于 FOLLOW(A) 中的每一个终结符 b，将 A → $\alpha$ 加入 M[A, b]。

构建过程：

预测分析表 M：

LL(1) 文法判断：
观察上述预测分析表，每个单元格最多只包含一个产生式。这表明该文法是一个 LL(1) 文法。如果任何单元格包含多个产生式，则该文法不是 LL(1) 文法。

总结

通过以上步骤，我们成功地将原始文法改写为 LL(1) 文法，计算了所有非终结符的 FIRST 和 FOLLOW 集，并构建了相应的预测分析表。这个预测分析表可以用于自顶向下的语法分析器，根据输入符号和栈顶非终结符来确定下一步的推导规则，从而解析输入字符串。