編譯原理：第五章語法分析_習題

1、G(S)：S - a | |(T)T - T,S | S【習題:】 給定文法如下：. 遞歸子程序法；IV. LL(1)分析法； 試分別用下述分析法，對給定的符號串進行語法分析：V. LR(0)( 或SLR（1）)分析法；設(shè) 給定的符號串為：= (a,),a)VI .簡單優(yōu)先（或算符優(yōu)先）分析法；. 找出這個句子的短語，簡單短語，句柄；. 證明符號串是文法的一個合法的句子；第5章 習題解答: (a,),a)是文法的一個句子。S =(T)=(T,S)=(S,S)=(T),S) =(T,S),S) =(S,S),S)=(a,S),S) =(a,),S =(a,),a) . 證明符號串是文法的一個合法

2、的句子；G(S)：S - a | |(T) T - T,S | S. 找出這個句子的短語，簡單短語，句柄；S( T )T , SS ( T )T , SSaa短語：(a,),a)；(a,),a； (a,)；a,；a；簡單短語： a；句柄：aG(S)：S-a | |(T) T-T,S | S. 構(gòu)造遞歸子程序法： 證明 G(S)是 LL(1)文法：select()= first(a)= a 求選擇集合：select()= first()= select()= first(T)= ( select()= first(T,S) = a ,( , select()= first(S) = a ,( ,

3、 選擇集合不相交, 相交， G（S）不是 LL(1) 文法！必須進行文法變換！G(S)：S-a | |(T) T-S,S變換后的文法G(S)S子程序主程序 構(gòu)造遞歸子程序(框圖)：入口 ,NEXT(w)出口nyST子程序 (NEXT(w)yn #NEXT(w)結(jié)束nyS開始err0入口出口 aerr2NEXT(w)nnyT )NEXT(w)y nyNEXT(w)G(S)：S-a | |(T) T-S,SSerr1select()= follow(T)= ) IV. LL(1)分析法： 證明 G(S)是 LL(1)文法：select()= first(a)= a 求選擇集合：select()=

4、first()=select()= first(T)= ( select()= first(ST) = a,( select()= first(,ST)= , 兩組選擇集合, 皆不相交， G（S）是 LL(1) 文法！即 LL(1)分析法可用！G(S)：S-a | |(T) T-T,S | SG(S)：S-a|(T) T-ST T-,ST | 變換后的文法G(S) 2. 構(gòu)造 LL(1)分析表： LL(1) 分析表： 帶有選擇集合的文法： G(S)：S-aa | |(T)( T-ST a,( T -,ST , |) a ( ) , # S T T V. LR(0)(SLR(1)分析法： 擴展文

5、法，編碼：G(S)：S- S1 0 S - a2 | 3 |(4T5)6 T - T7,8S9 | S10 構(gòu)造可規(guī)約前綴圖：0+S-OKa-r(1)-r(2)(T)-r(3)T,S -r(4)S10-r(5)a(a(是一個非確定有限自動機，需要轉(zhuǎn)換為確定機！V. LR(0)(SLR(1)分析法：G(S)：S- S1 0 S - a2 | 3 |(4T5)6 T - T7,8S9 | S10 3.構(gòu)造確定的有限自動機的變換表： 10 # S 1 5,7 0 4 9 ） ， 6 8 3 2 T （ a r(5)r(5)r(5)r(5)r(5) 910 1 OK 4 32 42 r(4)r(4)

6、r(2)r(1) r(3)r(2)rr(3)r(3)4325,7r(2)r(2)r(2)r(1)rr(1)3 8 6 r(4)r(4)r(4)r(3)r(3)V. LR(0)(SLR(1)分析法：G(S)：S- S1 0 S - a2 | 3 |(4T5)6 T - T5,8S9 | S10 4. 構(gòu)造確定的可規(guī)約前綴圖：0+S-OKa-r(1)-r(2)(T)-r(3),S -r(4)S10-r(5)a(a(VI .簡單優(yōu)先（算符優(yōu)先）分析法G(S)：S-a | |(T) T-T,S | S 證明 G(S)是 簡單優(yōu)先文法： 求FIRSTVT和LASTVT： S T FIRSTVT LAST

7、VT a,( a, )T,S,a,( S,a,)VI .簡單優(yōu)先（算符優(yōu)先）分析法G(S)：S-a|(T) T-T,S| S 求簡單優(yōu)先關(guān)系： S T FIRSTVT LASTVT a,( a, )T,S,a,( S,a,) ST a( ) , S T a ( ) , 優(yōu)先關(guān)系不唯一；G(S)文法不是簡單優(yōu)先文法！ =a | |(T) T-T,S | S2. 證明 G(S)是 算符優(yōu)先文法： 求FIRSTVT和LASTVT： S T FIRSTVT LASTVT a,( a, ) ,a,( ,a,)VI .簡單優(yōu)先（算符優(yōu)先）分析法G(S)：S-a|(T) T-T,S| S 求算符優(yōu)先關(guān)系：

8、S T FIRSTVT LASTVT a,( a, ),a,( ,a,) 優(yōu)先關(guān)系唯一，且文法產(chǎn)生式中不存在相同的右部；G(S)文法是算符優(yōu)先文法！ a ( ) , a ( ) , =aASb|Bd ; A -cS| ; B -bB|d 【解】入口出口 aerr2NEXT(w)Aerr1NEXT(w)S子程序nnnyyS bB dNEXT(w)y第5章 習題解答入口 cNEXT(w)出口遇時nySA子程序 bNEXT(w)出口nyB dNEXT(w)err3yn入口B子程序【習題5.5】已知文法：S - a A S b | B d A - c S | B - b B | d （1）求選擇集合；

9、證明是LL(1)文法；G(S): select()= select()= select()= select()= select()= select() = 【解】（1）求選擇集合（2） LL(1)分析表: 三對選擇集合兩兩不相交! G(S)是 LL(1)文法!dBAScbaab,dc=follow(A) a,b,dbd（2）構(gòu)造 LL(1)分析表?！玖曨}】 判斷下述文法事是否是 LL(1)文法 ?B-bCDE| ; C-DaB|ca ; D-dD| ; E-gAf|c【解】select()=first(B)+first(C)=b,d,a,c ; select()=first(D)+a=d,a

10、; select()=follow(B)=a,c,d,f,g,#follow(B)=first(C)+follow(A)+follow(C)=a,c,d,f,g,#follow(D)=b+follow(A)+first(E)+a=a,b,c,f,g,#select()=g; select()=b; select()=c; select()=d; select()=follow(D)=a,b,c,f,g,#select()=d; select()=c; 選擇集合兩兩不相交！所以是 LL(1)文法 ！A-BCc|gDB ; 三對選擇集合中，兩兩不相交！ G(S) 是LL(1)文法！ 【習題】 把下

11、述文法化為LL(1)文法！S -A ; A -B|AiB ; B -C|B+C ; C -)A*|(文法變換，消除左遞歸： A -B|AiB = A-BiB 則 A-BA ; A-iBA| B -C|B+C = B-C+C 則 B-CB ; B-+CB|整理并附加產(chǎn)生是序號后得：G(S):S -A ； A-BA ; A-iBA | B-CB ; B-+CB|; C -)A*|( select()= i ; select()= *,# ; select()= + ; select()= i,*,# ; select()= ) ; select()= ( ;G(S):Z-S1 (0)S-a2A3(

12、1)|b4B5 (2)A-06A7 (3)|18 (4) B-09B10(5)|111 (6)【習題】 考慮文法：G(S)S-aA|bB ; A-0A|1 ; B-0B|1 構(gòu)造活前綴的DFA(即句柄識別器)【解】擴展文法，編碼： 0+SaA0OKr(1)r(3)r(4)r(2)bA1B00Br(5)r(6)111011活前綴的DFA(即句柄識別器): 句柄識別器(DFA)中無沖突狀態(tài)！ G(S)是LR(0)文法! 是LR(0)文法嗎？ B1011109 9r(5)r(5)r(5)r(6)r(5) 10 S1 SA7 A3 A OK 1r(2)r(2)r(2)r(2)r(2) 5 b4 a2

13、0B511109 4r(4)r(4)r(4)r(4)r(4) 8r(6)r(3)18r(1)18 1 r(6)r(3)r(1) #06 6r(3)r(3)r(3) 7r(6)r(6)r(6) 11r(1)r(1)r(1) 3 2 B 0 b a 06 G(S)的 LR(0)分析表：第5章 習題解答【習題】 設(shè)有文法 G(S):S-rD ; D-D,i|i【解】 構(gòu)造活前綴的DFA(即句柄識別器)擴展文法，編碼：Z-S1 (0) S-r2D3 (1) D-D3,4i5 (2)|i6 (3)0+SrDOKr(1)r(2)r(3)，ii# 在狀態(tài)處出現(xiàn)(移進、歸約)沖突！ G(S)不是LR(0)文法

14、！ follow(S)=#,可以解決沖突：即 若 當前單詞為“ ，”, 則 移進 ,4 當前單詞為“ # ”, 則 歸約 r(1) G(S)是 SLR(1)文法！第5章 習題解答：r,i#SD0r2S11ok2i6D33,4r(1)4i55r(2)r(2)r(2)r(2)6r(3)r(3)r(3)r(3) 文法G(S)的SLR(1)分析表：第5章 習題解答：【習題】G(E):E - E + T | TT - ( E ) | iE- E1 (0)E - E2 +3 T4 (1)| T5(2)T - (6 E7 )8(3)| i9(4)G(E)1. 構(gòu)造句柄識別器：-Ti0E-OKE+T-r(1)

15、T-r(2)(E)-r(3)i r(4)E(i【解】+r(4)r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)r(3)8+3T5(6i9r(2)r(2)r(2)r(2)r(2)r(1)r(1)r(1)T4(6i9T5 E1(6i9OK+3r(1)r(1) ,2【習題】G(E):E - E + T | TT - ( E ) | iTE#)(+iE- E1 (0)E - E2 +3 T4 (1)| T5(2)T - (6 E7 )8(3)| i9(4)G(E)令 1,2,2,7 分別用 2，7 代之；是 SLR(1)分析表！2.用有限自動機確定化方法，直接構(gòu)造 SLR(1) 分析表：0 E 7982,765431,2注 2.第5章 習題解答：TE#)(+i3. 用SLR(1) 分析表，構(gòu)造確定的有限自動機：E2,7T5T4T5 E1,2r(3)r(3)r(4)r(2)OKr(1)r(4)r(3)8r(2)r(1)r(4)r(3)(6r(2)r(1)(6(6r(4)+3r(2)r(1)+3r(4)r(3)i9r(2)r(1)i9i90982