内容发布更新时间 : 2024/11/17 18:58:51星期一 下面是文章的全部内容请认真阅读。

精品

因为产生式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）归约 分析成功 感谢下载载