文法G(E)为:E→aTb|iE|i T→TE|E (1)提公因子和消除左递归;(2)改造后的文法计算每个非终结符的FIRST集和FOLLOW集并判断是否为LL(1)文法。
时间: 2024-02-23 22:56:38 浏览: 143
(1) 提公因子和消除左递归:
首先我们要提取公因子,可以看到在E的产生式中有一个公共的i,我们可以将其提取出来,得到以下文法:
E → iE' | aTb
E' → iE' | ε
T → TE | E
接下来我们需要消除左递归,对于E'的产生式,我们可以通过以下方式进行改写:
E' → iE'E''
E'' → ε | E'
得到以下文法:
E → iE' | aTb
E' → iE'E'' | ε
E'' → ε | E'
T → TE | E
(2) 计算每个非终结符的FIRST集和FOLLOW集并判断是否为LL(1)文法:
首先计算E的FIRST集,可以得到FIRST(E) = {i, a}。
接下来计算E'的FIRST集,可以得到FIRST(E') = {i, ε}。
计算E''的FIRST集,可以得到FIRST(E'') = {ε}。
计算T的FIRST集,可以得到FIRST(T) = {i, a}。
计算E的FOLLOW集,可以得到FOLLOW(E) = {$, b}。
计算E'的FOLLOW集,可以得到FOLLOW(E') = {b}。
计算E''的FOLLOW集,可以得到FOLLOW(E'') = {b}。
计算T的FOLLOW集,可以得到FOLLOW(T) = {$, b}。
可以发现,该文法满足LL(1)文法的条件,因为每个非终结符的FIRST集和FOLLOW集都不相交,且对于任意非终结符A和终结符a,最多只有一个产生式可以匹配a。因此,该文法是LL(1)文法。
阅读全文