《编译原理：第五章语法分析_习题》由会员分享，可在线阅读，更多相关《编译原理：第五章语法分析_习题（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谢谢收看！谢谢收看！
