题目
设有以下文法：（﹡﹡﹡）G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε（1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造C[S]的LL（1）分析表。
设有以下文法：（﹡﹡﹡）G[S]：S→aAbDe|dA→BSD|eB→SAc|cD|εD→Se|ε（1）求出该文法的每一个非终结符U的FOLLOW集。（2）该文法是LL（1）文法吗？（3）构造C[S]的LL（1）分析表。
题目解答
答案
（1）求文法的每一个非终结符U的FOLLOW集的过程如下：
因为：
①S是识别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含
FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#}
={a,d}∪{a,d,c,e}∪{e}∪{#}
={a,c,d,e#}
②又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。
因为S→aAbDe和B→SAc,所以
FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}
综合①、②得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}
因为A→BSD，所以 FOLLOW（B）=FIRST（SD）={a,d}
因为S→aAbDe | d、A→BSD| e和B→SAc | cD，所以
FOLLOW（D）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）
={e}∪{b,c}∪{a,d}={a,b,c,d,e}
（2）G[S]不是LL（1）文法。
因为产生式B→SAc|cD|ε中
FIRST（SAc）∩FOLLOW（B）={a,d}≠
（3）构造G[S]的LL（1）分析表。
按照LL（1）分析表的构造算法构造方法G[S]的LL（1）分析表如下表所示。
表 G[S]的LL（1）分析表
解析
步骤 1：求出文法中每个非终结符的FOLLOW集
首先，我们需要求出文法中每个非终结符的FOLLOW集。FOLLOW集是所有可能出现在非终结符之后的终结符的集合。我们从识别符号S开始，逐步求出其他非终结符的FOLLOW集。
步骤 2：求出FOLLOW(S)
因为S是识别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}。又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。因为S→aAbDe和B→SAc,所以FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}。综合得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}={a,b,c,d,e,#}。
步骤 3：求出FOLLOW(A)
因为A→BSD，所以FOLLOW（A）=FIRST（SD）={a,d}。
步骤 4：求出FOLLOW(B)
因为S→aAbDe | d、A→BSD| e和B→SAc | cD，所以FOLLOW（B）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）={e}∪{b,c}∪{a,d}={a,b,c,d,e}。
步骤 5：求出FOLLOW(D)
因为D→Se，所以FOLLOW（D）=FOLLOW（S）={a,b,c,d,e,#}。
步骤 6：判断文法是否为LL(1)文法
根据LL(1)文法的定义，如果对于文法中的每个非终结符A，其所有产生式的FIRST集的并集与FOLLOW集的交集为空，则该文法为LL(1)文法。我们检查产生式B→SAc|cD|ε，发现FIRST（SAc）∩FOLLOW（B）={a,d}≠，因此该文法不是LL(1)文法。
步骤 7：构造LL(1)分析表
按照LL(1)分析表的构造算法构造方法G[S]的LL(1)分析表。由于该文法不是LL(1)文法，因此无法构造出完整的LL(1)分析表。
首先，我们需要求出文法中每个非终结符的FOLLOW集。FOLLOW集是所有可能出现在非终结符之后的终结符的集合。我们从识别符号S开始，逐步求出其他非终结符的FOLLOW集。
步骤 2：求出FOLLOW(S)
因为S是识别符号，且有A→BSD、B→SAc、D→Se，所以FOLLOW（S）应包含FIRST(D)∪FIRST(Ac) ∪FIRST(e) ∪{#}={a,d}∪{a,d,c,e}∪{e}∪{#}={a,c,d,e#}。又因为A→BSD和D→ε，所以FOLLOW中还包含FOLLOW(A)。因为S→aAbDe和B→SAc,所以FOLLOW（A）=FIRST（bDe）∪FIRST（c）={b,c}。综合得FOLLOW（S）={a,d,c,e,#}∪{a,b,c,d,e,#}={a,b,c,d,e,#}。
步骤 3：求出FOLLOW(A)
因为A→BSD，所以FOLLOW（A）=FIRST（SD）={a,d}。
步骤 4：求出FOLLOW(B)
因为S→aAbDe | d、A→BSD| e和B→SAc | cD，所以FOLLOW（B）=FIRST（e）∪FOLLOW（A）∪FOLLOW（B）={e}∪{b,c}∪{a,d}={a,b,c,d,e}。
步骤 5：求出FOLLOW(D)
因为D→Se，所以FOLLOW（D）=FOLLOW（S）={a,b,c,d,e,#}。
步骤 6：判断文法是否为LL(1)文法
根据LL(1)文法的定义，如果对于文法中的每个非终结符A，其所有产生式的FIRST集的并集与FOLLOW集的交集为空，则该文法为LL(1)文法。我们检查产生式B→SAc|cD|ε，发现FIRST（SAc）∩FOLLOW（B）={a,d}≠，因此该文法不是LL(1)文法。
步骤 7：构造LL(1)分析表
按照LL(1)分析表的构造算法构造方法G[S]的LL(1)分析表。由于该文法不是LL(1)文法，因此无法构造出完整的LL(1)分析表。