考虑下面文法G1:

Question

1.考虑下面文法G1:
S→a|∧|(T)
T→T,S|S
(1)消去G1的左递归.然后对每个非终结符,写出不带回溯的递归子程序。
(2)经改写后的文法是否是LL(1)的?给出他的预测分析表。

Answer 1

(1)消去左递归后:
S→a|∧|(T)
T→ST’
T’ →,ST’|ε

(2)计算每个非终结符的FIRST集合和FOLLOW集合:
FIRST(S)={a,∧,(}
FIRST(T)={ a,∧,(}
FIRST(T’)={, ε}
FOLLOW(S)={,#}
FOLLOW(T)={ )}
FOLLOW(T’)={ )}
预测分析表如下:
a ∧ ( ) , #
S S→a S→∧ S→(T)
T T→ST’ T→ST’ T→ST’
T’ T’ →ε T’ →,ST’
构造的预测分析表中没有多重入口,所以改造后的文法是LL(1)文法。

Answer 2

最佳答案
(1)消去左递归后:
S→a|∧|(T)
T→ST’
T’ →,ST’|ε
(2)计算每个非终结符的FIRST集合和FOLLOW集合:
FIRST(S)={a,∧,(}
FIRST(T)={ a,∧,(}
FIRST(T’)={, ε}
FOLLOW(S)={,#)}
FOLLOW(T)={ )}
FOLLOW(T’)={ )}