编译原理 第二 第五章答案
- 格式：doc
- 大小：79.00 KB
- 文档页数：12
第五章 第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->ε
FIRST FOLLOW S a ^ ( # , ) T a ^ ( ) N , ε )
对左部为N2的产生式可知： FIRST （->, S N2）={，} FIRST （->ε）={ε} FOLLOW （N2）={)} {，}∩ { )}=Ø 所以文法是LL(1)的。 预测分析表 a ^ ( ) , # S ->a ->^ ->( T ) T ->S N ->S N ->S N N ->ε ->, S N
也可由预测分析表中无多重入口判定文法是LL(1)的。 (4)对输入串（a,a）#的分析过程为：
步骤 状态栈 当前字符 剩余输入串 操作 1 #S ( a,a)# S->(T) 2 #)T( ( a,a)# 匹配 3 #)T A ,a)# T->SN2 4 #)N2S A ,a)# S->a 5 #)N2a A ,a)# 匹配 6 #)N2 , a)# N2->,SN2 7 #)N2S, , a)# 匹配 8 #)N2S a )# S->a 9 #)N2a a )# 匹配 10 #)N2 ) # N2->ε 11 #) ) # 匹配 12 # # 可见输入串（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)的。 (3)由以上算出的SELECT集可以构造该文法的预测分析表如下： + * ( ) a b ^ # E →TE′ →TE′ →TE′ →TE′ E′ →+E →ε →ε T →FT′ →FT′ →FT′ →FT′ T′ →ε →T →ε →T →T →T →ε F →PF′ →PF′ →PF′ →PF′ F′ →ε →*F′ →ε →ε →ε →ε →ε →ε P →(E) →a →b →^ void P() { Getchar(); if ch=’(’ { E(); Getchar();if ch=’)’Getchar();} else if ch=’a’ Getchar(); else if ch=’b’ Getchar(); else error(), }
}
void F’() { Getchar(); if ch=’*’ F’(); else error(); } F’(); }
void F() { P(); F’(); }
void T’() { T(); } （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|ε
