编译原理第二版第五章答案
第五章
第5章自顶向下语法分析方法
练习(P99) 1.文法 S->a|^|(T) T->T,S|S
(1) 对(a,(a,a)和(((a,a),^,(a)),a)的最左推导。
(3)经改写后的文法是否为LL(1)的?给出它的预测分析表。 (4)给出输入串(a,a)#的分析过程,并说明该串是否为G的句子。 (1) 对(a,(a,a)的最左推导为: S=>(T)
=>(T,S) =>(S,S) =>(a,S) =>(a,(T)) =>(a,(T,S)) =>(a,(S,S)) =>(a,(a,S)) =>(a,(a,a))
对(((a,a),^,(a)),a) 的最左推导为:
S=>(T) =>(T,S) =>(S,S) =>((T),S) =>((T,S),S) =>((T,S,S),S) =>((S,S,S),S) =>(((T),S,S),S) =>(((T,S),S,S),S) =>(((S,S),S,S),S) =>(((a,S),S,S),S) =>(((a,a),S,S),S) =>(((a,a),^,S),S) =>(((a,a),^,(T)),S) =>(((a,a),^,(S)),S) =>(((a,a),^,(a)),S) =>(((a,a),^,(a)),a) (3)改写文法为: 0) S->a 1) S->^ 2) S->( T ) 3) T->S N 4) N->, S N 5) N->ε
对左部为N2的产生式可知: FIRST (->, S N2)={,} FIRST (->ε)={ε} FOLLOW (N2)={)} {,}∩ { )}=Ø 所以文法是LL(1)的。
也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串(a,a)#的分析过程为:
可见输入串(a,a)#是文法的句子。 2.对下面的文法G: E→TE′ E′→+E|ε T→FT′ T′→T|ε F→PF′ F′→* F′|ε P→(E)|a|b|^
(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。 (2) 证明这个文法是LL(1)的。 (3) 构造它的预测分析表。 (4) 构造它的预测下降分析程序
【解】(1)由题意分析得可推导出ε的非终结符表为: 各非终结符的FIRST集为:
FIRST(E)= FIRST(T)={(,a,b,^} FIRST(E′)={+}∪{ ε}={+,ε} FIRST(T)= FIRST(F)={(,a,b,^}
FIRST(T′)= FIRST(T) ∪{ ε}={(,a,b,^,ε}
FIRST(F)= FIRST(P)={(,a,b,^} FIRST(F′)={*}∪{ ε}={*,ε} FIRST(P)={(,a,b,^}
∴最终求得各非终结符的FIRST集为:
FIRST(E)={(,a,b,^} FIRST(E′)={+,ε} FIRST(T)={(,a,b,^} FIRST(T′)= {(,a,b,^,ε} FIRST(F)={(,a,b,^} FIRST(F′)={*,ε} FIRST(P)={(,a,b,^} 各非终结符的FOLLOW集为: FOLLOW(E)={#}∪FOLLOW(E′) ∪{ )} FOLLOW(E′)= FOLLOW(E)
FOLLOW(T)= FOLLOW(T′) ∪(FIRST(E′)-{ ε})∪FOLLOW(E) FOLLOW(T′)= FOLLOW(T)
FOLLOW(F)= (FIRST(T′)-{ ε})∪FOLLOW(T) FOLLOW(F′)= FOLLOW(F) ∪FOLLOW(F′)
FOLLOW(P)= (FIRST(F′)-{ ε})∪FOLLOW(F) ∴最终求得各非终结符的FOLLOW集为:
FOLLOW(E)={#,)} FOLLOW(E′)= {#,)} FOLLOW(T)= {#, + , ) } FOLLOW(T′)= {#, + ,)} FOLLOW(F)= {(,a,b,^,#,+,)}
FOLLOW(F′)= {(,a,b,^,#,+,)} FOLLOW(P)= {*,(,a,b,^,#,+,)} (2)各产生式的SELECT集为:
SELECT(E→TE′)=FIRST(TE′)= FIRST(T)={(,a,b,^} SELECT(E ′→+E)=FIRST(+E)={+}
SELECT(E ′→ε)=(FIRST(ε)-{ ε})∪FOLLOW(E′)= FOLLOW(E′)={#,)} SELECT(T→FT′)=FIRST(FT′)= FIRST(F)={(,a,b,^} SELECT(T′→T)=FIRST(T)= {(,a,b,^}
SELECT(T′→ε)=(FIRST(ε)-{ ε})∪FOLLOW(T′)= FOLLOW(T′)={#,+,)} SELECT(F→PF′)=FIRST(PF′)= FIRST(P)= {(,a,b,^} SELECT(F′→*F′)=FIRST(*F′)= FIRST(P)= {*}
SELECT(F′→ε)=(FIRST(ε)-{ ε})∪FOLLOW(F′)= FOLLOW(F′)={(,a,b,^,#,+,)} SELECT(P→(E))=FIRST((E))={(} SELECT(P→a)=FIRST(a)={a} SELECT(P→b)=FIRST(b)={b} SELECT(P→^)=FIRST(^)={^}
∴由以上结果得相同左部产生式的SELECT交集为: SELECT(E ′→+E) ∩SELECT(E ′→ε)= {+}∩{#,)}
SELECT(T′→T) ∩SELECT(T′→ε)= {(,a,b,^)∩{#,+,)}= Φ SELECT(F′→*F′) ∩SELECT(F′→ε)={*} ∩{(,a,b,^,#,+,)} = Φ
SELECT(P→(E))∩SELECT(P→a)∩SELECT(P→b) ∩SELECT(P→^)={(}∩{a}∩{b}∩{^}= Φ ∴相同左部产生式的SELECT集合的交集为空。 ∴这个文法是LL (1)的。
(4)不妨约定:在进入一个非终结符号相应的子程序前,已读到一个单词ch:存放当前读到的单词,Getchar()为一子程序,每调用一次,完成读取一单词的任务,Error()为出错处理程序。
4.证明下述文法不是LL(1)文法。 S->C$ C-> bA|aB A->a|aC|bAA B->b|bC| aBB
你能否构造一等价的文法,使其是LL(1)?并给出判断过程。
【解】因为SELECT(A->a)∩SELECT(A->aC)≠Ф,根据LL(1)文法的判定条件: (1)文法不含左递归
(2)对于文法U的任意两个不同的规则有:
Select(U→α) ∩ Select(U→)=Φ一个文法若满足以上条件,称该文法G为LL(1)文法。得出该文法不是LL(1)文法。 该文法含公共因子,消除后的文法为: S->C$ C-> bA|aB A->aA'|bAA A’->C|ε B->bB'| aBB B’->C|ε
【证明】因为SELECT(C-> bA) ∩SELECT(C->aB)= Φ SELECT(A->Aa) ∩SELECT(A->bAA) = Φ
SELECT(A’->C) ∩SELECT(A’->ε)=(FIRST(C)-{ ε})∩FOLLOW(A’) ≠Ф 因此消除公共因子后得到文法也不是LL(1)文法。
7.对于一个文法若消除了左递归,提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写,并对改写后的文法进行判断。 (1)A->baB|ε [1] B->Abb|a [2] (2) A→aABe|a [1] B→Bb|d [2] (3) S→Aa|b [1]
A→SB [2] B→ab [3] 【解】
对于一个文法若消除了左递归,提取了左公因子后不一定是LL(1)文法。 1题: A->baB|ε B->Abb|a 先改写文法为: 0) A->baB 1) A->ε 2) B->baBbb 3) B->bb 4) B->a 再改写文法为:
1) A->ε 2) B->bN 3) B->a 4) N->aBbb 5) N->b
预测分析表
由预测分析表中无多重入口判定文法是LL(1)的。 2题:
[2]将产生式[1] 提取左公因子后得: A→a(ABe|ε ) 进一步变换为文法G1: A→aA′ A′→Abe A′→ε B→Bb|d
消除(2)中的直接左递归,将B→Bb|d 变换为: B→dB ′ B′→bB′ |ε
该文法最终改写成的形式为: A→aA′ A′→Abe|ε B→dB ′ B′→bB′ |ε
对此改写后的文法进行判断其是否是LL(1)文法。
各非终结符的FIRST集为: FIRST(A)={a}
FIRST(A′)= FIRST(A)∪{ε}={a,ε} FIRST(B)={d} FIRST(B′)={b}∪{ε}={b,ε} 各非终结符的FOLLOW集为:
FOLLOW(A)={#} ∪(FIRST(B)- {ε})={#,d} FOLLOW(A′)=FOLLOW(A)={#,d} FOLLOW(B)= {e}
FOLLOW(B′)= FOLLOW(B′) ∪FOLLOW(B)= {e}
各产生式的SELECT集为: SELECT(A→aA′)=FIRST(aA′)={a}
SELECT(A′→ABe)=FIRST(ABe)= FIRST(A)={a}
SELECT(A′→ε)=(FIRST(ε)-{ ε})∪FOLLOW(A′)= FOLLOW(A′)= {#,d} SELECT(B→dB ′ )=FIRST(dB ′)= {d} SELECT(B′→bB′)=FIRST(bB′)= {b}
SELECT(B′→ε)=(FIRST(ε)-{ ε})∪FOLLOW(B′)= FOLLOW(B′)= {e} 由以上结果得相同左部产生式的SELECT交集为: SELECT(A′→ABe)∩SELECT(A′→ε)={a}∩{#,d}=Φ SELECT(B′→bB′) ∩ SELECT(B′→ε)= {b}∩{e}=Φ ∴相同左部产生式的SELECT集合的交集为空。 ∴改写后的文法是LL (1)的。 3题:
该文法的非终结符S,A为间接左递归,以S,A,B为序消除一切左递归。 将(1)的右部代入(2)得: A→AaB|bB 消除其直接左递归得: A→bBA′ A′→aB A′|ε 此时文法变成如下形式: S→Aa|b (1) A→bBA′ (2) A′→aB A′|ε B→ab
此文法中的(1), (2)产生式存在隐含的左公因子,消除隐含的左公因子后文法变成如下的形式: S→b S′
S′→BA′a|ε A→bBA′ A′→aB A′|ε B→ab
此形式中A→bBA′是不可达的产生式,是多余的,所以应将其去掉。
所以文法最终改写成的形式为:
S→b S′
S′→BA′a|ε
A′→aB A′|ε
B→ab
相同左部产生式的SELECT集为:
SELECT(S′→BA′a)={a}
SELECT(S′→ε)={#}
SELECT(A′→aB A′)={a}
SELECT(A′→ε)={a}
相同左部产生式的SELECT交集为:
SELECT(S′→BA′a)∩SELECT(S′→ε)={a}∩{#} =Φ
SELECT(A′→aB A′)∩SELECT(A′→ε)={a}∩{a} ≠Φ
∴关于A′的相同左部其产生式的SELECT集的交集不为空
∴此改写后的文法不是LL(1)的。
4题:
S->AS|b
A->SA|a
该文法含间接左递归,因此运用间接左递归的算法对文法进行改写后的文法为: S->AS|b
A->bAA'|aA’
A’->SAA’|ε
SELECT(S->AS) ∩ SELECT(S->b)={b,a}∩{b}≠Φ, ∴此改写后的文法不是LL(1)的。