判断给定文法是否为LL(1)及改造求助：左递归消除问题

原文法 #

A -> Aac | Ab | Bb | a 
B -> Ac | Ad | ε 

一、是否为LL(1)文法？ #

不是，原因如下：

1. 存在直接左递归：产生式A -> Aac | Ab中，非终结符A的候选式以自身开头，属于直接左递归，LL(1)文法不允许任何形式的左递归（直接/间接）。
2. 存在间接左递归：推导链A → Bb → Acb/Adb最终回到A，形成循环依赖的间接左递归，违反LL(1)文法要求。

二、改造为LL(1)文法 #

你尝试改造后的文法仍存在间接左递归（B -> AB'导致A与B互相依赖），需通过先消除间接左递归，再消除直接左递归的步骤处理：

步骤1：消除间接左递归 #

将B的产生式代入A的产生式中（因为A依赖B，B又依赖A）：

• 把A -> Bb替换为A -> Acb | Adb | b（对应B的三个候选式Ac/Ad/ε）
• 替换后A的产生式变为：

  A -> Aac | Ab | Acb | Adb | a 
  

步骤2：消除A的直接左递归 #

使用直接左递归消除规则：对于A → Aα | β，改造为A → βA'，A' → αA' | ε。这里A的左递归候选式为Aac | Ab | Acb | Adb（对应α为ac/b/cb/db），非左递归候选式为a | b（对应β）。
改造后A的产生式：

A -> aA' | bA'
A' -> acA' | bA' | cbA' | dbA' | ε

步骤3：重新整理B的产生式 #

将A的新产生式代入B的原产生式，消除B对A的递归依赖：

B -> aA'c | aA'd | bA'c | bA'd | ε

可提取公共因子优化为：

B -> (a | b)A'B' | ε
B' -> c | d

最终LL(1)文法 #

A -> aA' | bA'
A' -> acA' | bA' | cbA' | dbA' | ε
B -> aA'B' | bA'B' | ε
B' -> c | d

验证LL(1)合法性 #

1. 无任何形式的左递归；
2. 每个非终结符的候选式FIRST集互不相交：
   • FIRST(A) = {a, b}，两个候选式的FIRST集无交集；
   • FIRST(A') = {a, b, c, d, ε}，各候选式的FIRST集两两无交集；
   • FIRST(B) = {a, b, ε}，FIRST(aA'B')/FIRST(bA'B')与FIRST(ε)无交集；
3. 含ε候选式的非终结符（A'、B），其FIRST集与FOLLOW集无交集（计算FOLLOW集后可验证）。

内容的提问来源于stack exchange，提问作者Ayoub Dhaouadi