《编译原理:第五章语法分析_习题》由会员分享,可在线阅读,更多相关《编译原理:第五章语法分析_习题(26页珍藏版)》请在金锄头文库上搜索。
1、G(S)G(S):S - a | S - a | |(T) |(T)T - T,S | ST - T,S | S【习题习题: :】 给定文法如下:给定文法如下:. . 递归子程序法;递归子程序法;IV. LL(1). LL(1)分析法;分析法; 试分别用下述分析法,对给定的试分别用下述分析法,对给定的符号串符号串进行语法分析:进行语法分析:V. LR(0)( . LR(0)( 或或SLRSLR(1 1)) )分析法;分析法;设设 给定的符号串为:给定的符号串为:= (a,= (a,),a),a)VI . .简单优先(或算符优先)分析法;简单优先(或算符优先)分析法;. . 找出这个句子的短语,
2、简单短语,句柄;找出这个句子的短语,简单短语,句柄;. . 证明符号串是文法的一个合法的句子;证明符号串是文法的一个合法的句子;第第5 5章章 习题解答习题解答: : (a,a,),a),a)是文法的一个句子。是文法的一个句子。S =(T)=(T,S)=(S,S)=(T),S) =(T,S),S) S =(T)=(T,S)=(S,S)=(T),S) =(T,S),S) =(S,S),S)=(a,=(S,S),S)=(a,S S),S),S) =(a,=(a,),S),S =(a,=(a,),a),a) . . 证明符号串是文法的一个合法的句子;证明符号串是文法的一个合法的句子;G(S)G(S)
3、:S - a | S - a | |(T) |(T) T - T,S | ST - T,S | S. . 找出这个句子的短语,简找出这个句子的短语,简单短语,句柄;单短语,句柄;S S( T ( T ) )T , ST , SS S ( ( T T ) )T , ST , SS Sa aa a短语:短语:(a,a,),a),a);(a,(a,),a),a; (a,(a,) );a,a,;a a;简单短语:简单短语: a a;句柄:句柄:a aG(S)G(S):S-a S-a | | |(T)|(T) T-T,S T-T,S | S S. . 构造递归子程序法:构造递归子程序法: 证明证明 G(
4、S)G(S)是是 LL(1)LL(1)文法:文法:select()= first(select()= first(a a)= a )= a 求选择集合:求选择集合:select()= first(select()= first()= )= select()= first(T)= ( select()= first(T)= ( select()= first(select()= first(T,ST,S) = a ,( , ) = a ,( , select()= select()= first(first(S S) ) = = a ,( , a ,( , 选择集合选择集合不相交不相交, 相交,
5、相交, G G(S S)不是不是 LL(1) LL(1) 文法!文法! 必须进行文法变换!必须进行文法变换!G(S)G(S):S-a S-a | | |(T)|(T) T-S,ST-S,S变换后的文变换后的文法法G G(S)(S)S子程序子程序主程序主程序 构造递归子程序构造递归子程序(框图框图):入口入口 ,NEXT(w)出口出口nyST子程序子程序 (NEXT(w)yn #NEXT(w)结束结束nyS开始开始err0入口入口出口出口 aerr2NEXT(w)nnyT )NEXT(w)y nyNEXT(w)G(S)G(S):S-a S-a | | |(T)|(T) T-S,ST-S,SSer
6、r1select(select()= follow()= follow(T T)= )= ) ) IV. LL(1). LL(1)分析法:分析法: 证明证明 G G(S)(S)是是 LL(1)LL(1)文文法:法:select()= first(select()= first(a a)= a )= a 求选择集合:求选择集合:select()= first(select()= first()=)= select()= first(select()= first(T)(T)= ( )= ( select()= first(select()= first(STST) = a,) = a,(,( s
7、elect()= first(,select()= first(,STST)= ,)= , 两组选择集合两组选择集合, 皆不相交,皆不相交, G G(S S)是是 LL(1) LL(1) 文法!文法!即即 LL(1)LL(1)分析法可用!分析法可用!G(S)G(S):S-a S-a | | |(T)|(T) T-T,S T-T,S | S SG(S)G(S):S-S-aa| |(T)|(T) T-STT-ST T T-,ST-,ST | | 变换后的文变换后的文法法G G(S)(S) 2. 2. 构造构造 LL(1)LL(1)分析表:分析表: LL(1) LL(1) 分析表:分析表: 带有带有
8、选择集合选择集合的文法:的文法: G(S)G(S):S-aS-aaa | | |(T)|(T)( T-STT-ST a,( a,( T -,ST-,ST , , |) a a ( ( ) ) , , # # S S T T TT V. LR(0)(. LR(0)(SLR(1)SLR(1) )分析法:分析法: 扩展扩展文文法,编码:法,编码:G(S)G(S):S- SS- S1 1 0 0 S - a S - a2 2 | | 3 3 | |( (4 4T T5 5) )6 6 T - TT - T7 7, ,8 8S S9 9 | S| S10 10 构造构造可规约前缀图可规约前缀图:0 0+
9、S S -OKOKa a-r(1)r(1)-r(2)r(2)( (T T) )-r(3r(3) )T T, ,S S -r(4r(4) )S S10-r(5r(5) )a a( (a a( (是一个非确定有限自动机,需要转换为确定机!是一个非确定有限自动机,需要转换为确定机!V. LR(0)(. LR(0)(SLR(1)SLR(1) )分析法:分析法:G(S)G(S):S- SS- S1 1 0 0 S - a S - a2 2 | | 3 3 | |( (4 4T T5 5) )6 6 T - TT - T7 7, ,8 8S S9 9 | S| S10 10 3. 3.构造构造确定的有限自
10、动机的确定的有限自动机的变换表:变换表: 10 10 # # S S 1 1 5,7 5,7 0 0 4 4 9 9 ) , 6 6 8 8 3 3 2 2 T T ( a a r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5)r(5) 9 91010 1 1 OK OK 4 4 3 32 2 4 42 2 r(4)r(4)r(4)r(4) r(2)r(2)r(1)r(1) r(3)r(3)r(2)r(2)rrr(3)r(3)r(3)r(3)4 43 32 25,75,7r(2)r(2)r(2)r(2)r(2)r(2)r(1)r(1)rrr(1)r(1)3 3 8 8 6
11、 6 r(4)r(4) r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)V. LR(0)(. LR(0)(SLR(1)SLR(1) )分析法:分析法:G(S)G(S):S- SS- S1 1 0 0 S - a S - a2 2 | | 3 3 | |( (4 4T T5 5) )6 6 T - TT - T5 5, ,8 8S S9 9 | S| S10 10 4. 构造确定的构造确定的可规约前缀图可规约前缀图:0 0+S S -OKOKa a-r(1)r(1)-r(2)r(2)( (T T) )-r(3r(3) ), ,S S -r(4r(4) )S S10-r(5r(5)
12、 )a a( (a a( (VI .VI .简单优先(算符优先)分析法简单优先(算符优先)分析法G(S)G(S):S-a S-a | | |(T)|(T) T-T,S T-T,S | S S 证明证明 G(S)G(S)是是 简单优先文法:简单优先文法: 求求FIRSTVTFIRSTVT和和LASTVTLASTVT: S S T T FIRSTVT FIRSTVT LASTVT LASTVT a,( a,( a, ) a, )T,S,a,(T,S,a,( S,a,) S,a,)VI .VI .简单优先(算符优先)分析法简单优先(算符优先)分析法G(S)G(S):S-a|S-a|(T)|(T) T
13、-T,ST-T,S| S S 求简单优先关系:求简单优先关系: S S T T FIRSTVT FIRSTVT LASTVT LASTVT a,( a,( a, ) a, )T,S,a,(T,S,a,( S,a,) S,a,) S ST T a a( ( ) ) , , S S T T a a ( ( ) ) , , 优先优先关系不关系不唯一;唯一;G(S)G(S)文法不是文法不是简单优先简单优先文法!文法! =a S-a | | |(T)|(T) T-T,S T-T,S | S S2.2. 证明证明 G(S)G(S)是是 算符优先文法:算符优先文法: 求求FIRSTVTFIRSTVT和和LA
14、STVTLASTVT: S S T T FIRSTVT FIRSTVT LASTVT LASTVT a,( a,( a, ) a, ) ,a,( ,a,( ,a,) ,a,)VI .VI .简单优先(算符优先)分析法简单优先(算符优先)分析法G(S)G(S):S-a|S-a|(T)|(T) T-T,ST-T,S| S S 求算符优先关系:求算符优先关系: S S T T FIRSTVT FIRSTVT LASTVT LASTVT a,( a,( a, ) a, ),a,(,a,( ,a,) ,a,) 优先关优先关系唯一,且系唯一,且文法产生式文法产生式中不存在相中不存在相同的右部;同的右部;G
15、(S)G(S)文文法是算符优法是算符优先文法!先文法! a a ( ( ) ) , , a a ( ( ) ) , , =G(S): S -aASbaASb| |BdBd ; A - ; A -cScS| | ; B - ; B -bBbB|d|d 【解】【解】入口入口出口出口 aerr2NEXT(w)Aerr1NEXT(w)S子程序子程序nnnyyS bB dNEXT(w)y第第5 5章章 习题解答习题解答入口入口 cNEXT(w)出口出口遇遇 时时nySA子程序子程序 bNEXT(w)出口出口nyB dNEXT(w)err3yn入口入口B子程序子程序【习题习题5.55.5】已知文法:已知文
16、法:S - a A S b | B d S - a A S b | B d A - c S | A - c S | B - b B | dB - b B | d (1 1)求选择集合;证明是求选择集合;证明是LL(1)LL(1)文法;文法;G(S): G(S): select()= select()= select()= select()= select()= select()= select()= select()= select()= select()= select(select() ) = = 【解】【解】(1 1)求选择集合求选择集合(2 2) LL(1)LL(1)分析表分析表: :
17、 三对选择集合两两不相交三对选择集合两两不相交! ! G(S)G(S)是是 LL(1)LL(1)文法文法! !d dB BA AS Sc cb ba aa ab,db,dc c=follow(A) =follow(A) a a,b,d,b,db bd d(2 2)构造)构造 LL(1)LL(1)分析表。分析表。【习题习题】 判断下述文法事是否是判断下述文法事是否是 LL(1)LL(1)文法文法 ? ?B-B-bCDEbCDE| ; C- ; C-DaBDaB|ca |ca ; ; D-D-dDdD| ; ; E-E-gAfgAf|cc【解】【解】select()=select()=first(
18、B)+first(C)=first(B)+first(C)=b,d,a,cb,d,a,c ; ; select()select()=first(D)+a=first(D)+a=d,ad,a ; ; select()=select()=follow(B)=follow(B)=a,c,d,f,g,#a,c,d,f,g,# follow(B)=follow(B)=first(C)+follow(A)+follow(C)=first(C)+follow(A)+follow(C)=a,c,d,f,g,#a,c,d,f,g,#follow(D)=follow(D)=b+follow(A)+b+follow
19、(A)+first(E)+a=first(E)+a=a,b,c,f,g,#a,b,c,f,g,#select()=gselect()=g; ; select()=bselect()=b; ; select()=cselect()=c; ; select()=dselect()=d; ; select()select()=follow(D)=follow(D)=a,b,c,f,g,#a,b,c,f,g,# select()=dselect()=d; ; select()=cselect()=c; ; 选择集合两两不相交!所以是选择集合两两不相交!所以是 LL(1)LL(1)文法文法 !A-A-B
20、CcBCc|gDBgDB ; ; 三对选择集合中,三对选择集合中,两两不相交!两两不相交! G(S) G(S) 是是LL(1)LL(1)文法!文法! 【习题习题】 把下述文法化为把下述文法化为LL(1)LL(1)文法!文法!S -A ; A -B|S -A ; A -B|AiBAiB ; B -C|B+C ; C -)A*|( ; B -C|B+C ; C -)A*|(文法变换,消除左递归:文法变换,消除左递归:v A -B|A -B|AiBAiB = A-B = A-BiBiB 则则 A-BA ; A-A-BA ; A-iBAiBA| v B -C|B+C = B-C+C B -C|B+C
21、= B-C+C 则则 B-CB ; B-+CB|B-CB ; B-+CB| 整理并附加产生是序号后得:整理并附加产生是序号后得:G(S):G(S):S -A S -A ; A-BA ; A- A-BA ; A-iBAiBA | | B-CB ; B-+CB|B-CB ; B-+CB| ; ; C -)A*|(C -)A*|( select()= i ; select()= i ; select()= *,# ; select()= *,# ; select()= + ; select()= + ; select()= i,*,# ; select()= i,*,# ; select()= )
22、; select()= ) ; select()= ( ; select()= ( ;G(S)G(S): :Z-SZ-S1 1 (0) (0)S-aS-a2 2A A3 3(1)|b(1)|b4 4B B5 5 (2) (2)A-0A-06 6A A7 7 (3)|1 (3)|18 8 (4) (4) B-0B-09 9B B1010(5)|1(5)|11111 (6) (6)【习题习题】 考虑文法:考虑文法:G(S)G(S)S-S-aAaA| |bBbB ; A-0A|1 ; B-0B|1 ; A-0A|1 ; B-0B|1 构造活前缀的构造活前缀的DFA(DFA(即句柄识别器即句柄识别器)
23、 )【解】【解】扩展文法,编码:扩展文法,编码: 0 0+ +S Sa aA A0 0OKOKr(1)r(1)r(3r(3) )r(4)r(4)r(2)r(2)b bA A1 1B B0 00 0B Br(5)r(5)r(6)r(6)11111 10 01 11 1活前缀的活前缀的DFA(DFA(即句柄识别器即句柄识别器):): 句柄识别器句柄识别器( (DFA)DFA)中无冲突状态!中无冲突状态! G(S)G(S)是是LR(0)LR(0)文法文法! ! 是是LR(0)LR(0)文法吗?文法吗? B1011109 9r(5)r(5)r(5)r(6)r(5) 10 S1 SA7 A3 A OK
24、1r(2)r(2)r(2)r(2)r(2) 5 b4 a2 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)G(S)的的 LR(0)LR(0)分析表:分析表:第第5 5章章 习题解答习题解答【习题习题】 设有文法设有文法 G(S):G(S):S-S-rDrD ; D-D,i|i ; D-D,i|i【解】【解】 构造活前缀的构造活前缀的DFA(DFA(即即句柄识别器句柄识别器) )扩展文
25、法,编码:扩展文法,编码:Z-SZ-S1 1 (0) (0) S-rS-r2 2D D3 3 (1) (1) D-DD-D3 3, ,4 4i i5 5 (2)|i (2)|i6 6 (3) (3)0 0+ +S Sr rD DOKOKr(1r(1) )r(2)r(2)r(3r(3) ),i ii i# # 在状态在状态处处出现出现( (移进移进、归归约约) )冲突!冲突! G(S)G(S)不是不是LR(0)LR(0)文法!文法! follow(S)=#,follow(S)=#,可以解决冲突:可以解决冲突:即即 若若 当前单词为当前单词为“ “ ,”, , 则则 移进移进 , ,4 4 当前单
26、词为当前单词为“ “ # ”, # ”, 则则 归约归约 r(1)r(1) G(S)G(S)是是 SLR(1)SLR(1)文法!文法!第第5 5章章 习题解答:习题解答:r r, ,i i# #S SD D0 0r2r2S1S11 1okok2 2i i6 6D3D33 3, ,4 4r(1)r(1)4 4i i5 55 5r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)6 6r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3) 文法文法G(S)G(S)的的SLR(1)SLR(1)分析表:分析表:第第5 5章章 习题解习题解答:答:【习题习题】G(E):G(E):E
27、 - E + T | TE - E + T | TT - ( E ) | iT - ( E ) | iE- EE- E1 1 (0) (0)E - EE - E2 2 + +3 3 T T4 4 (1)| (1)| T T5 5(2)(2)T - (T - (6 6 E E7 7 ) )8 8(3)| i(3)| i9 9(4)(4)G(EG(E) )1. 1. 构造句柄识别器:构造句柄识别器:-T Ti i0 0E E-OKOKE E+T T-r(1)r(1)T T-r(2)r(2)( (E E) )-r(3)r(3)i i r(4)r(4)E E( ( (i i【解】【解】+r(4)r(4
28、)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(4)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)r(3)8)8+ +3 3T5T5(6(6i9i9r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(2)r(1)r(1)r(1)r(1)r(1)r(1)T4T4(6(6i9i9T5T5 E1 E1(6(6i9i9OKOK+ +3 3r(1)r(1)r(1)r(1) ,2 ,2【习题习题】G(E):G(E):E - E + T | TE - E + T | TT - ( E ) | iT - ( E ) | iTE#)(+i iE-
29、EE- E1 1 (0) (0)E - EE - E2 2 + +3 3 T T4 4 (1)| (1)| T T5 5(2)(2)T - (T - (6 6 E E7 7 ) )8 8(3)| i(3)| i9 9(4)(4)G(EG(E) )令令 1,2,2,7 1,2,2,7 分别用分别用 2 2,7 7 代之;代之;是是 SLR(1)SLR(1)分析表!分析表!2.2.用用有限自动机确定化有限自动机确定化方法,直接构造方法,直接构造 SLR(1) SLR(1) 分析表:分析表:0 0 E 7 E 79 98 82,72,76 65 54 43 31,21,2注注 2. 2.第第5 5章
30、章 习题解习题解答:答:TE#)(+i i3. 3. 用用SLR(1) SLR(1) 分析表,分析表,构造构造确确定的有定的有限自动限自动机机:E2,7E2,7T5T5T4T4T5T5 E1,2 E1,2r(3)r(3)r(3)r(3)r(4)r(4)r(2)r(2)OKOKr(1)r(1)r(4)r(4)r(3)r(3)8)8r(2)r(2)r(1)r(1)r(4)r(4)r(3)r(3)(6(6r(2)r(2)r(1)r(1)(6(6(6(6r(4)r(4)+ +3 3r(2)r(2)r(1)r(1)+ +3 3r(4)r(4)r(3)r(3)i9i9r(2)r(2)r(1)r(1)i9i
31、9i9i90 09 98 82,72,76 65 54 43 31,21,20 0-OKOKE E+T T-r(1)r(1)T T-r(2)r(2)( (E E) )-r(3)r(3)i i r(4)r(4)+ +( ( (i iT Ti i-1,2,2,71,2,2,7分别用分别用2 2,7 7代之代之4.4.用用构造项目集合的构造项目集合的方法,构造方法,构造可规约前缀图可规约前缀图:E E- - E EE-E- E+TE+TE-E-T TT-T- (E)(E)T-T-i iE EE E- -EEE-E-EE+T+TE-E-E+E+T TT-T- (E)(E)T-T-i i+E-E-E+TE+TT TOKOK# #-r(1r(1) )I I0 0T TE-E-TT-r(2r(2) )I I1 1I I2 2I I3 3I I4 4T-T-(E)E)E-E- E+TE+TE-E-T TT-T- (E)(E)T-T-i i( (I I5 5T-T-(E(E) )E-E-EE+T+TE EI I6 6) )T-T-(E)(E)I I7 7-r(3r(3) )i iT-T-iiI I8 8-r(3r(3) )T T( (i i+( (i iE EE+E+E+TE+TT T( (E(E(E(E) )i i谢谢收看!谢谢收看!