内容发布更新时间 : 2024/11/17 16:44:01星期一 下面是文章的全部内容请认真阅读。
精品
因为产生式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)归约 分析成功 感谢下载载