发布时间 : 星期六 文章编译原理习题及答案（整理后）更新完毕开始阅读ddf7e3777fd5360cba1adb58
第四章
1、 构造下面文法的LL（1）分析表。
D→ TL T→ int | real L→ id R R→ , id R | ε
2、 下面文法G[S]是否为LL（1）文法？说明理由。
S → A B | P Q x A → x y B → b c P → d P | ε Q → a Q | ε 3、 设有以下文法：
G[S]：S→aAbDe|d A→BSD|e B→SAc| cD| ε D→Se| ε
（1）求出该文法的每一个非终结符U的FOLLOW集。 （2）该文法是LL（1）文法吗？ （3）构造C[S]的LL（1）分析表。 4、 将文法G[V]改造成为LL(1)的。
G[V]：V→N|N[E] E→V|V+E N→i 5、已知文法： G[A]： A→aAa|ε
（1）该文法是LL（1）文法吗？为什么？
（2）若采用LL（1）方法进行语法分析，如何得到该文法的LL（1）分析表？ （3）若输入符号串“aaaa”，请给出语法分析过程。 1解答： LL（1）分析表见表4-3-1
分析 虽然这个文法很简单，我们还是从求开始符号集合和后继符号集合开始。
FIRST（D）=FIRST（T）={int, real} FOLLOW（D）=FOLLOW（L）={#}
FIRST（L）={id} FOLLOW（T）={id} FIRST（R）={，, ε} FOLLOW（R）={#}
有了上面每个非终结符的FIRST集合，填分析表时要计算一个产生式右部α的FIRST（α）就不是件难事了。
填表时唯一要小心的时，ε是产生式R→ε右部的一个开始符号，而#在FOLLOW（R）中，所以R→ε填在输入符号#的栏目中。
表4-3-1 LL（1）分析表 非终结符 D T L R int D→TL T→int 输入符号 real D→TL T→real id L→id R ， R→,id R # R→ ε
2解答： 该文法不是LL（1）文法，见下面分析中的说明。
分析 只有三个非终结符有两个选择。
1、P的两个右部d P 和ε 的开始符号肯定不相交。
2、Q的两个右部a Q 和 ε 的开始符号肯定不相交。
3、对S来说，由于x ∈ FIRST(A B)，同时也有x ∈ FIRST(P Q x)（因为P和Q都可能为空）。所以该文法不是LL（1）文法。
3解答： （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）分析表如表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(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解答：（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 文法G′[A]的LL(1)分析表
A
（3）若采用LL(1)方法进行语法分析，对符号串“aaaa”的分析过程如表4-3-4所示。
表4-3-4 对符号串“aaaa”的分析过程 步骤 1 2 3 4 5 6 7 8
分析栈 #A #A a a #A a #A #A a a #A a #A # 输入串 a a a a # a a a a # a a a # a a # a a # a# # # 产生式/动作 A→aaA 匹配 匹配 A→aaA 匹配 匹配 A→ε 接受 A A→aaA # 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 A d
S A d
S 图5-7-3 句型（SdSdS）的语法树