精品
因为产生式B→SAc|cD| ε 中
FIRST（SAc）∩FOLLOW（B）={a,d}≠? （3）构造G[S]的LL（1）分析表。
按照LL（1）分析表的构造算法构造方法G[S]的LL（1）分析表如表4-3-2所示。
表4-3-2 G[S]的LL（1）分析表
S A B D a aAbDe BSD Sac/ε Se/ε b ε c BSD cD ε d d BSD Sac/ε Se/ε e e ε # 4解答： 对文法G[V]提取公共左因子后得到文法：
G′[V]：V→NA
A→ε|[E] E→VB B→ε|+E N→i
求出文法G′[V]中每一个非终结符号的FIRST集： FIRST(V)={i}
FIRST(E)={i} FIRST(N)={i}
FIRST(A)={[, ε} FIRST(B)={+, ε}
求出文法G′[V]中每一个非终结符号的FOLLOW集：
FOLLOW(V)={#}∪FIRST(B)\\{ε}∪FOLLOW(E)={#,+,]} FOLLOW(A)= FOLLOW(V)={+,,#}
感谢下载载
精品
FOLLOW(E)= FIRST(])\\{ε}∪FOLLOW(B)= FIRST(])\\{ε}∪FOLLOW(E)={]} FOLLOW(B)= FOLLOW(E)={ ]}
FOLLOW(N)= FIRST(A)\\{ε}∪FOLLOW(V)={[,],+,#}
可以看到，对文法G′[V]的产生式A→ε|[E]，有
FIRST([E])∩FOLLOW(A)={[}∩{+,],#}= ?
对产生式B→ε|+E，有
FIRST(+E)∩FOLLOW(B)={+}∩{]}= ?
而文法的其他产生式都只有一个不为ε的右部，所以文法G′[V]是LL(1)文法。 5解答：（1）因为产生式A→aAa|ε 有空产生式右部，而
FOLLOW(A)={#}∪FIRST(a)={a, #}
造成 FIRST(A)∩FOLLOW(A)={A, ε}∩{a, #}≠? 所以该文法不是LL（1）文法。
（2）若采用LL（1）方法进行语法分析，必须修改该文法。 因该文法产生偶数（可以为0）个a，所以得到文法
G′[A]： A→aaA|ε
此时对产生式A→aaA|ε， 有 FOLLOW(A)={#}∪FOLLOW(A)={#}，因而
FIRST(A)∩FOLLOW(A)={a, ε}∩{#}=?
所以文法G′[A]是LL（1）文法，按LL（1）分析表构造算法构造该文法的LL（1）分析表如表4-3-3所示。
表4-3-3
A
文法G′[A]的LL(1)分析表
A A→aaA # A→ε 感谢下载载
精品
（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表4-3-4所示。 表4-3-4
步骤 1 2 3 4 5 6 7 8
对符号串“aaaa”的分析过程
输入串 a a a a # a a a a # a a a # a a # a a # a# # # 产生式/动作 A→aaA 匹配 匹配 A→aaA 匹配 匹配 A→ε 接受 分析栈 #A #A a a #A a #A #A a a #A a #A # 第五章
1.设有文法G[S]为：
S→a|b|(A) A→SdA|S
（1） 完成下列算符优先关系表，见表5-7-1，并判断G[S]是否为算符优先文法。
表5-7-1 算符优先关系表 a b a b ( ) ? ? d # ? ? 感谢下载载
精品
( ) d #
? ? ? ? ? ? ? ? ? ? （2）给出句型（SdSdS）的短语、简单短语、句柄、素短语和最左素短语。 （3）给出输入串（adb）#的分析过程。 解答：
（1）先求文法G[S]的FIRSTVT集和LASTVT集：
由S→a|b|(A)得：FIRSTVT(S)={a,b,( );
由A→Sd…得：FIRSTVT(A)={d};又由A→S…得：FIRSTVT(S) ? FIRSTVT(A)，即FIRSTVT(A)={d,a,b,(};
由S→a|b|(A)得；LASTVT(S)={a,b,}};
由A→…dA得：LASTVT(A)={d},又由A→S得：LASTVT(S) ? LASTVT(A)，即LASTVT(A)={d,a,b,)}。
构造优先关系表方法如下：
① 对P→…ab…，或P→…aQb…，有a?b; ② 对P→…aR…，而b∈FIRSTVT(R)，有a?b; ③ 对P→…Rb…，而a∈FIRSTVT(R)，有a?b。 由此得到：
① 由S→(A)得：(?);
② 由S→(A…得：(?FIRSTVT(A)，即：(?d,(?a ,(?b,(?(;由A→…dA得：d?FIRSTVT(A)， 即：d?d,d?a,d?b,d?(;
③ 由S→A)得，LASTVT(A)?)，即：d?),a?),b?),)?);由A→Sd…得：LASTVT(S)?d，即：a?d,b?d,)?d;
此外，由#S#得：#?#；
由#?FIRSTVT(S)得：#?a,#?b,#?(；脂由LASTVT(S)?#得：d?#,a?#,b?#,)?#。
最后得到算符优先关系表，见表5-7-2。
表5-7-2 算符优先关系表
a b ( ) d # a ? ? ? b ? ? ? ( ? ? ? ) ? ? ? ? ? d ? ? ? ? # ? ? ? ? ?
由表5-7-2可以看出，任何两个终结符之间至少只满足?、?、?三种优先关系之一，故G[S]为算符优先文法。
（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如图5-7-3所示。由图5-7-3得到： 短语：S，SdS，SdSdS，（SdSdS）
S 简单短语（即直接短语）：S 句柄（即最左直接短语）：S
素短语：SdS，它同时也是该句型的最左素短语。
A （ ）
S d A 感谢下载载
S d A 精品
（3）输入串（adb）#的分析过程见表5-7-4
表5-7-4 输入串（adb）#的分析过程
符号栈 # #（ #（a #（S #（Sd #（Sdb #（SdS #（SdA #（A #（A） #S
输入串 (adb)# adb)# db)# db)# b)# )# )# )# )# # # 说明 移进 移进 用S→a归约 移进 移进 用S→b归约 用A→S归约 用A→SdA归约 移进 用S→（A）归约 分析成功 感谢下载载