文法G(E)为:E→aTb|iE|i T→TE|E (1)提公因子和消除左递归;(2)改造后的文法计算每个非终结符的FIRST集和FOLLOW集并判断是否为LL(1)文法。
时间: 2024-02-23 22:56:40 浏览: 29
(1) 对文法G(E)进行提取公因子和消除左递归的步骤如下:
首先,将文法G(E)改写为如下形式:
E → iE | aTb | i
T → TE | E
接下来,对E → iE | aTb进行提取公因子:
E → iE' | aTb
E' → E | ε
然后,对T → TE | E进行消除左递归:
T → ET'
T' → ET' | ε
最终,G(E)的新文法为:
E → iE' | aTb
E' → E | ε
T → ET'
T' → ET' | ε
(2) 计算FIRST集和FOLLOW集:
对于这个文法,我们可以按照以下步骤计算FIRST集和FOLLOW集:
1. 计算E的FIRST集和FOLLOW集:
FIRST(E) = {i, a}
FOLLOW(E) = {$, b}
2. 计算E'的FIRST集和FOLLOW集:
FIRST(E') = {i, a, ε}
FOLLOW(E') = {b, $}
3. 计算T的FIRST集和FOLLOW集:
FIRST(T) = {i, a}
FOLLOW(T) = {b, $}
4. 计算T'的FIRST集和FOLLOW集:
FIRST(T') = {ε, i, a}
FOLLOW(T') = {b, $}
判断是否为LL(1)文法:
对于一个文法来说,如果它满足LL(1)文法的条件,那么它就是一个LL(1)文法。LL(1)文法的条件如下:
1. 对于每一个产生式A → α,都有FIRST(α) ∩ FIRST(β) = ∅,其中β是A的任意一个后继符号串。
2. 如果有A → α和A → β是两个产生式,那么FIRST(α) ∩ FIRST(β) = ∅。
3. 如果有A → α和B → β是两个产生式,且α和β都可以推出ε,那么FOLLOW(A) ∩ FOLLOW(B) = ∅。
根据上述条件,我们可以得到如下结论:
对于文法G(E)来说,它不是LL(1)文法。因为A → iE'和A → aTb是两个产生式,且FIRST(iE') ∩ FIRST(aTb) 不为空。