发布时间 : 星期日 文章(整理完)编译原理网上作业题参考答案20121101更新完毕开始阅读
因为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）分析表
4．将文法G[V]改造成为LL(1)的。（﹡﹡﹡） G[V]：V→N|N[E] E→V|V+E N→i
解答：对文法G[V]提取公共左因子后得到文法： G′[V]：V→NA A→ε|[E] E→VB B→ε|+E N→i
求出文法G′[V]中每一个非终结符号的FIRST集： FIRST(V)={i} FIRST(A)={[,ε} FIRST(E)={i} FIRST(B)={+,ε} FIRST(N)={i}
求出文法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．已知文法：（﹡﹡﹡） G[A]： A→aAa|ε
（1）该文法是LL（1）文法吗？为什么？
（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？ （3）若输入符号串“aaaa”，请给出语法分析过程。 解答：（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）分析表如下表所示。
表 文法G′[A]的LL(1)分析表
（3）若采用LL(1)方法进行语法分析， 对符号串“aaaa”的分析过程如下表所示。
表 对符号串“aaaa”的分析过程
6．设有文法G[S]为：（﹡﹡﹡）
S→a|b|(A) A→SdA|S
（1）完成下列算符优先关系表，见下表，并判断G[S]是否为算符优先文法。
表 算符优先关系表
（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)={d,a,b,(}；
由S→a|b|(A)得；LASTVT(S)={a,b,}}；
由A→…dA得：LASTVT(A)={d},又由A→S得：LASTVT(S) 构造优先关系表方法如下：
①对P→…ab…，或P→…aQb…，有ab； ②对P→…aR…，而b∈FIRSTVT(R)，有ab； ③对P→…Rb…，而a∈FIRSTVT(R)，有ab。 由此得到：
①由S→(A)得：()；
②由S→(A…得：(FIRSTVT(A)，即：(d，(a，(b，((；由A→…dA得：dFIRSTVT(A)，即：dd，da，db，d(；
③ 由S→A)得，LASTVT(A))，即：d)，a)，b)，))；由A→Sd…得：LASTVT(S)d，即：ad，bd，)d； 此外，由#S#得：##；
由#FIRSTVT(S)得：#a，#b，#(；由LASTVT(S)#得： d#，a#，b#，)#。 最后得到算符优先关系表，见下表。
LASTVT(A)，即LASTVT(A)={d,a,b,)}。
FIRSTVT(A)，即
表 算符优先关系表
由上表可以看出，任何两个终结符之间至少只满足、、三种优先关系之一，故G[S]为算符优先文法。
（2）为求出句型（SdSdS）的短语、简单短语、句柄，我们先画出该句型对应的语法树，如下图所示。由图得到：
短语：S，SdS，SdSdS，（SdSdS） 简单短语（即直接短语）：S 句柄（即最左直接短语）：S
素短语：SdS，它同时也是该句型的最左素短语。
图 句型（SdSdS）的语法树
（3）输入串（adb）#的分析过程见下表。