第三章习题解答_0

1、第三章第三章 语法分析语法分析 3.83.8 下述文法描述了下述文法描述了C C语言整数变量的声明语句：语言整数变量的声明语句： GD: DTL Tint|long|short Lid|L,id(1) 改造上述文法，使其接受相同的输入序列，但改造上述文法，使其接受相同的输入序列，但文法是右递归的；文法是右递归的；(2) 分别用上述文法分别用上述文法GD和改造后的文法和改造后的文法GD为为输入序列输入序列int a,b,c构造分析树。构造分析树。第三章第三章 语法分析语法分析 【解答】【解答】 (1) 消除左递归后，文法消除左递归后，文法GD如下：如下： DTL Tint|long|short

2、LidL L ,id L |第三章第三章 语法分析语法分析 图3-6 两种文法为int a,b,c构造的分析树 (a) 文法G(D)； (b) 文法G(D)第三章第三章 语法分析语法分析 3.11 将下述文法改造为将下述文法改造为LL(1)文法：文法： GV: VN | NE EV | V+E NI【解答】【解答】 LL(1)文法的基本条件是不含左递归和回溯文法的基本条件是不含左递归和回溯(公共左公共左因子因子)，而文法，而文法GV中含有回溯，所以先提取公共左因子，中含有回溯，所以先提取公共左因子，以消除回溯，得到文法以消除回溯，得到文法GV： G V：VNV V | E EVE E | +E

3、 Ni第三章第三章 语法分析语法分析 一个一个LL(1)文法的充要条件是：对每一个终结符文法的充要条件是：对每一个终结符A的任的任何两个不同产生式何两个不同产生式A|有下面的条件成立：有下面的条件成立：(1) FIRST()FIRST()=； (2) 假若假若,则有则有FIRST()FOLLOW(A)= 。即求出即求出GV的的FIRST集合集合和和LAST集合集合如下：如下： FIRST(N)=FIRST(V)=FIRST(E)=i FIRST(V)=, FIRST(E)=+, 第三章第三章 语法分析语法分析 FOLLOW(V)=FIRST(E )FOLLOW(E) #=+,#FOLLOW(V

4、 )= FOLLOW(V)=+,#FOLLOW(E)= FOLLOW(E )=FOLLOW(E )=FOLLOW(E) =FOLLOW(N)=FIRST(V ) FOLLOW(V) =,+, ,#第三章第三章 语法分析语法分析 n 对产生式对产生式V V |E |E 有：有：FIRST()FIRST(= ； FIRST()FOLLOW(V)=#,+,=；n 对对E | +E 有：有：FIRST()FIRST(+)= ； FIRST(+)FOLLOW(E)=+ =。故文法故文法GV为为LL(1)文法。文法。第三章第三章 语法分析语法分析 3.14 3.14 在算符优先分析法中，为什么要在找到最左

5、素在算符优先分析法中，为什么要在找到最左素短语的尾时才返回来确定其对应的头，能否按扫描顺短语的尾时才返回来确定其对应的头，能否按扫描顺序先找到头后再找到对应的尾，为什么？序先找到头后再找到对应的尾，为什么？ 【解答】【解答】 设句型的一般形式为设句型的一般形式为N N1 1a a1 1N N2 2a a2 2N Nn na an nN Nn+1n+1。其。其中，每个中，每个a ai i都是终结符，而都是终结符，而N Ni i则是可有可无的非终结符。则是可有可无的非终结符。对上述句型可以找出该句型中的所有素短语，每个素对上述句型可以找出该句型中的所有素短语，每个素短语都具有如下形式：短语都具有如

6、下形式： a aj-1j-1 a aj ja aj+1j+1a ai i a ai+1i+1 第三章第三章 语法分析语法分析 如果某句型得到的优先关系如下：如果某句型得到的优先关系如下： 则当从左至右扫描到第一个则当从左至右扫描到第一个“ ”时，再由此从右时，再由此从右至左扫描到第一个至左扫描到第一个“ ”时，它们之间时，它们之间( (当然不包含第当然不包含第一个一个“ ”前一个终结符和第二个前一个终结符和第二个“ ”后一个终结符后一个终结符) )即为最左素短语。即为最左素短语。第三章第三章 语法分析语法分析 3.16 3.16 给出文法给出文法GS: SGS: SaSbaSbP P P Pb

7、PcbPcbQcbQc Q QQaQaa a (1) (1) 它是它是ChomskyChomsky哪一型文法？哪一型文法？ (2) (2) 它生成的语言是什么？它生成的语言是什么？ (3) (3) 它是不是算符优先文法？请构造算符优先关它是不是算符优先文法？请构造算符优先关系表证实之；系表证实之；(4) (4) 文法文法GSGS消除左递归、提取公共左因子后是消除左递归、提取公共左因子后是不是不是LL(1)LL(1)文法？请证实。文法？请证实。第三章第三章 语法分析语法分析 【解答】【解答】 (1) (1) 根据根据ChomskyChomsky的定义，对任何形如的定义，对任何形如A A的产生式，

8、有的产生式，有A AV VN N，(V(VT TV VN N) )* *时为时为2 2型文法。而型文法。而文法文法GSGS恰好满足这一要求，故为恰好满足这一要求，故为Chomsky 2Chomsky 2型文法。型文法。(2) (2) 由文法由文法GSGS可以看出：可以看出：S S推出串的形式是推出串的形式是a ai i P P b bi i(i(i0)0)，P P推出串的形式是推出串的形式是b bj jQcQcj j(j(j1)1)，Q Q推出串的推出串的形式是形式是a ak k(k(k1)1)。因此，文法。因此，文法GSGS生成的语言是生成的语言是L=aL=ai ib bj ja ak kc

9、 cj jb bi i|i|i0, j0, j1, k1, k11。第三章第三章 语法分析语法分析 (3) (3) 求出文法求出文法GS的的FIRSTVT集和集和LASTVT集：集：FIRSTVT(S)=a,b FIRSTVT(P)=bFIRSTVT(Q)=aLASTVT(S)=b,c LASTVT(P)=cLASTVT(Q)=a根据优先关系构造规则有：根据优先关系构造规则有： aab ab b bc bc b bc LASTVT(Q) a构造优先关系表如表构造优先关系表如表3-83-8所示。所示。第三章第三章 语法分析语法分析 表表3-8 优先关系表优先关系表 由于表中的优先关系不唯一，故文

10、法由于表中的优先关系不唯一，故文法GS不是算符优不是算符优先文法。先文法。第三章第三章 语法分析语法分析 (4) 消除文法消除文法GS的左递归：的左递归： SaSb | P PbPc | bQc QaQ QaQ| 提取公共左因子后得到文法提取公共左因子后得到文法GS: SaSb | P PbP PPc | Qc QaQ QaQ| 第三章第三章 语法分析语法分析 求每个非终结符的求每个非终结符的FIRST集和集和FOLLOW集如下：集如下： FIRST(S)=a,b FIRST(P)=b FIRST(P)=a,b FIRST(Q)=a FIRST(Q)=a, FOLLOW(S)=b,# FOLL

11、OW(P)=b,c,# FOLLOW(P)=b,c,# FOLLOW(Q)=c FOLLOW(Q)=c 第三章第三章 语法分析语法分析 n 对于对于P Pc|Qc，有：，有： FIRST(P) FIRST(Q)=b a=n 对于对于Q a Q |，有：，有： FIRST(“aQ ”) = FIRST (“aQ(“aQ ”) ”) FOLLOW(Q Q )=a c= 所以，该文法是所以，该文法是LL(1)文法。文法。 第三章第三章 语法分析语法分析 3.223.22 文法文法G(S)的产生式集为的产生式集为 S(EtSeS) | (EtS) | i =E E+EF | F F*Fi | i 构造

12、文法构造文法G(S)的的SLR(1)分析表，要求先画出相应的分析表，要求先画出相应的DFA。第三章第三章 语法分析语法分析 【解答】【解答】 第一步，第一步，将文法将文法G拓广为文法拓广为文法GS： (0)SS (1) S(EtSeS) (2) S(EtS) (3) Si=E (4) E+EF (5) EF (6) F*Fi (7) Fi第三章第三章 语法分析语法分析 第二步，第二步，列出列出LR(0)LR(0)的所有项目：的所有项目：1. S1. SS S 2. S 2. SS S 3. S 3. S(EtSeS) (EtSeS) 4. S 4. S ( (EtSeS)EtSeS) 5. S

13、 5. S (E (EtSeS)tSeS) 6. S 6. S (Et (EtSeS)SeS)7. S7. S (EtS (EtSeS) eS) 8. S8. S (EtSe (EtSeS) S) 9. S 9. S (EtSeS (EtSeS) ) 10. S 10. S (EtSeS) (EtSeS) 第三章第三章 语法分析语法分析 11. S11. S(EtS) (EtS) 12. S 12. S ( (EtS) EtS) 13. S 13. S (E (EtS) tS) 14. S 14. S (Et (EtS)S) 15. S 15. S (EtS (EtS) ) 16. S 16.

14、 S (EtS) (EtS) 17. S 17. Si=E i=E 18. S 18. Si i=E=E 19. S 19. Si=i=E E 20. S 20. Si=Ei=E第三章第三章 语法分析语法分析 21. E21. E+EF+EF 29. F 29. F* *F Fi i22. E22. E+ +EFEF 30. F30. F* *FiFi 23. E23. E+E+EF F 31. F31. Fi i 24. E24. E+EF+EF 32. F32. Fi i25. E25. EF F 26. E26. EF F 27. F27. F* *FiFi28. F28. F* *Fi

15、Fi第三章第三章 语法分析语法分析 第三步，用第三步，用_CLOSURE_CLOSURE方法构造文法方法构造文法GSGS 的的LR(0)LR(0)项目项目集规范族：集规范族：I0: SS S(EtSeS) S(EtS) Si=E I I1: SS 第三章第三章 语法分析语法分析 I2: S (EtSeS) S (EtS) E+EF EF F *Fi F i I3: S(EtSeS) S(EtS) 第三章第三章 语法分析语法分析 I I4 4: S: S (Et (EtSeS) SeS) S S (Et (EtS)S)S S(EtSeS) (EtSeS) S S(EtS)(EtS)S Si=Ei

16、=EI I5 5: S: S (EtS (EtSeS)eS)S S (EtS (EtS) )第三章第三章 语法分析语法分析 I I6 6: S: S (EtSe (EtSeS) S) S S(EtSeS) (EtSeS) S S(EtS)(EtS) S Si=Ei=EI I7 7: : S S (EtSeS (EtSeS) ) I I8 8: : S S (EtSeS) (EtSeS) I I9 9: : S S (EtS) (EtS) 第三章第三章 语法分析语法分析 I10: Si=E I15: E+EF+EFI11: Si=E I16: EFF E+EF +EF I17: F* *FiFi

17、 EF F F* *FiFi FiiI12: Si=E =E I18: F* *Fi Fi I13: E+EF +EF I19: F* *Fi Fi E+EF +EF I20: Fii EFFI14: E+EF+EF F* *FiFi Fii第三章第三章 语法分析语法分析 )S(iiF*FieiS*(tEEEFFFi(S I1：SS I0： SS S(EtSeS) S(EtS) SiE I2： S(EtSeS) S(EtS) EEF EF I10：SiE I11： SiE EEF EF I12：SiE I3： S(EtSeS) S(EtS) I16：EF I13： EEF EEF EF I14

18、： EEF F*Fi Fi I17： F*Fi F*Fi Fi I15：EEF I20：Fi I18：F*Fi I19：F*Fi I4： S(EtSeS) S(EtS) S(EtSeS) S(EtS) SiE I5： S(EtSeS) S(EtS) I6： S(EtSeS) S(EtSeS) S(EtS) SiE I7：S(EtSeS) I8：S(EtSeS) I9：S(EtS)E图3-13 习题3.22的DFA 第四步，构造文法第四步，构造文法GS的的DFA如图如图3-13所示。所示。第三章第三章 语法分析语法分析 第五步，构造第五步，构造SLR(1)SLR(1)分析表。分析表。 首先求出所

19、有形如首先求出所有形如“A”的的FOLLOW(A)，即由，即由FOLLOW集的构造方法求得集的构造方法求得GS的的FOLLOW集如下：集如下：FOLLOW(S)=#； FOLLOW(S)=e ) #=e,),# FOLLOW(E)=FIRST(F) t FOLLOW(S) =*,i,t,e,),# FOLLOW(F)=i FOLLOW(E)= *,i,t,e,),# 最后最后, ,构造构造SLR(1)分析表如表分析表如表3-103-10所示所示。第三章第三章 语法分析语法分析 表3-10 习题3.22的SLR(1)分析表 第三章第三章 语法分析语法分析 3.24 3.24 文法文法GTGT及其

20、及其SLR(1)SLR(1)分析表分析表( (见表见表3-12)3-12)如下，给如下，给出串出串bibibibi的分析过程。的分析过程。 GT:(1) TGT:(1) TEbH EbH (2) E (2) Ed d (3) E (3) E (4) H (4) Hi i (5) H (5) HHbi Hbi (6) H (6) H第三章第三章 语法分析语法分析 表3-12 习题3.24的SLR(1)分析表ACTION GOTO 状 态 b d i # T E H 0 r3 s3 1 2 1 acc 2 s4 3 r2 4 r6 s6 r6 5 5 s7 r1 6 r4 r4 7 s8 8 r5

21、 r5 第三章第三章 语法分析语法分析 序号序号状态栈状态栈符号栈符号栈产生式产生式输入串输入串说明说明10#Ebibi# 归约归约 r3202#Ebibi# 移进移进3024#Ebibi# 移进移进40246#EbiH ibi# 归约归约 r450245#EbHbi# 移进移进602457#EbHbi# 移进移进7024578#EbHbiH Hbi# 归约归约 r580245#EbHT EbH# 归约归约 r1901#T# acc第三章第三章 语法分析语法分析 3.323.32 给出文法给出文法GS: SGS: SSaSSaSSbSSbScSdcSdeSeSf f。(1) (1) 请证实这是

22、一个二义文法；请证实这是一个二义文法；(2) (2) 给出什么样的约束条件可构造无冲突的给出什么样的约束条件可构造无冲突的LRLR分析表？分析表？请证实你的论点。请证实你的论点。 【解答】【解答】 (1) 对于语句对于语句fafbf，该文法存在两棵不同的，该文法存在两棵不同的语法树，如图语法树，如图3-20所示。所示。第三章第三章 语法分析语法分析 S a SSfS b SffSbSSfSaSff图3-20 语句fafbf的两棵不同语法树第三章第三章 语法分析语法分析 因此，因此，GSGS是二义文法。是二义文法。(2) (2) 首先将文法首先将文法GSGS拓广为拓广为GSGS ：(0) S(0

23、) SS S(1) S(1) SSaSSaS(2) S(2) SSbSSbS(3) S(3) ScSdcSd(4) S(4) SeSeS(5) S(5) Sf f该文法该文法GSGS 的的DFADFA如图如图3-213-21所示。所示。第三章第三章 语法分析语法分析 图3-21 习题3.32中GS的DFASbabaadbfeSbefcceScaSebfaffecS I0：S S SSaS SSbS ScSd SeS Sf I1：S S SSaS SSbS I2：ScSd SSaS SSbS ScSd SeS Sf I3：SeS SSaS SSbS ScSd SeS Sf I5：SSaS SSa

24、S SSbS ScSd SeS Sf I6：SSbS SSaS SSbS ScSd SeS Sf I7：ScSd SSaS SSbS I8：SeS SSaS SSbS I9：SSaS SSaS SSbS I10：SSbS SSaS SSbS I4：Sf I11：ScSdc第三章第三章 语法分析语法分析 状态状态I I1 1、I I8 8、I I9 9和和I I1010存在存在“移进移进”/ /“归约归约”冲突。计冲突。计算算GSGS 中所有非终结符的中所有非终结符的FOLLOWFOLLOW集：集： FOLLOW(SFOLLOW(S)=#)=# FOLLOW(S)=a,b,d,# FOLLOW(S)=a,b,d,# 对于对于I I1 1：S SS S S SS SaSaS S SS SbSbS可以采用可以采用SLR(1)SLR(1)解决冲突，即当解决冲突，即当LRLR分析器处于状态分析器处于状态1 1时，时，如果下一个输入符号是如果下一个输入符号是“# #”，则按，则按S SS S执行归约；执行归约；如果下一个输入符