题目

设有如下文法G[S]:SaABbcd | AASd | BSAh | eC | CSf | Cg | (1) 求每个产生式的Predict集。(2) 该文法是否为LL(1)文法?为什么?

题目解答

答案

答:(1)

Predict(SaABbcd)={a}

Predict(S )={#,d,f,a,h }

Predict(AASd)={a,d}

Predict(A )={h,a,d,b,e}

Predict(BSAh)={a,d,h}

Predict(B eC)={e}

Predict(B )={b}

Predict(CSf)={a,f}

Predict(C Cg)={a,f,g}

Predict(C )={g,b}

(2)由于Predict(AASd) Predict(A ),所以该文法不是LL(1)文法。

解析

步骤 1：计算Predict集
Predict集是产生式左部非终结符的First集，如果First集包含ε，则Predict集还包含产生式左部非终结符的Follow集。
步骤 2：计算First集
First集是产生式右部第一个终结符的集合，如果产生式右部第一个符号是ε，则First集包含ε。
步骤 3：计算Follow集
Follow集是产生式左部非终结符的Follow集，如果产生式右部最后一个符号是ε，则Follow集包含产生式左部非终结符的Follow集。
步骤 4：检查LL(1)文法
如果一个文法的每个产生式的Predict集互不相交，则该文法是LL(1)文法。