编译原理课后部分答案.docVIP

第二章问答第1题PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题问答第2题程序执行到赋值语句b=10时运行栈的布局示意图为：问答第3题题2中当程序编译到r的过程体时的名字表table的内容为：namekindlevel/valadrsizexvariable0dxyvariable0dx+1pprocedure0过程p的入口（待填）5avariable1dxqprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dxdvariable2dxrprocedure2过程r的入口5evariable3dxfvariable3dx+1注意：q和s是并列的过程，所以q定义的变量b被覆盖。问答第4题栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途说明如下： T： 栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S的下标)。B：基址寄存器，指向每个过程被调用时，在数据区S中给它分配的数据段起 始 地址，也称基地址。SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL， RA。 问答第5题PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操作说明如下：INT 0 A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。 OPR 0 0在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。CAL L A调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。问答第6题对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述如下： (2) 扩充条件语句的语法图为：EBNF的语法描述为： 条件语句:= if条件then语句else语句 (3) 扩充repeat语句的语法图为： EBNF的语法描述为： 重复语句:= repeat语句；语句until条件 第3章 文法和语言习题参考答案1. L(G)=abc2. L(GN)是无符号整数。3. G3: ED+E | D-E | D D0|1|2|3|4|5|6|7|8|94. L(GZ)=anbn | n05. (1) G5: NDN | E E0|2|4|6|8 DE|1|3|5|7|9 (2) G5: NAB|E BDB|E A1|2|3|4|5|6|7|8|9 E0|2|4|6|8 DA|06. (1) ET E (5) E E+T E (6) E E+T EF T T+T E + T T+T E + Ti F F+T T F F+T T T * F i i+T F ( E ) i+T F F i i+F i E + T i+T*F i i i+(E) T F i+F*F i+(E+T) F i i+i*F i+(T+T) i i+i*i i+(F+T) i+(i+T) i+(i+F) i+(i+i)7. E E i+i*i的两棵语法树不同， E O E E O E 故文法是二义的。 i + E O E E O E * i i * i i + i8. S S abc的两棵语法树不同， A c a B 故文法是二义的。 a b b c9. (1) S (2) 该文法生成的语言是后缀表达式， S S * 或称为逆波兰式。 S S + a a a10. （1）该文法生成的语言是“可并列或嵌套的配对的括号串”。（2）文法是二义的，因为句子“()()”有两棵不同的语法树。 S S S ( S ) S S ( S ) S S ( S ) S e e e e S ( S ) S e e e e e e 11. 可构造E+T*F的语法树如右所示： E 短语： E+T*F T*F 故为文法的句型。 E + T 其中，T*F是直接短语和句柄 T * F13. （1）最左推导 最右推导 (2) 文法规则可有： (3) 短语 直接短语 句柄 SABS SABS SABS | Aa |e abbaa aBS ABAa Aa a a a aSBBS ABaa BSBB | b e e aBBS ASBBaa b b abBS ASBbaa b b abbS ASbbaa bb abbAa Abbaa a a abbaa abbaa aa14. (1) G1: SCD (2) G2: S1S0|A CaCb|e A0A1|eDaDb|e (3) G3: S0S0|aSa|a15WaW上下文无关，W对应编程语言中的各种括号； anbmcndm上下文有关。16. (1) G1: AaA|e (2) G2: AaA|aB (3) G3: AaA|bB|cC|e BbB|b BbB|cC|e CcC|e17、6、7和11题的文法等价。19. 刻画语言的语法有文法、正则式和自动机等方式。第4章问答第1题（1）解：先构造NFA：用子集法将NFA确定化 .01X.AAAABABACABACAABYABYACAB除X，A外，重新命名其他状态，令AB为B、AC为C、ABY为D，因为D含有Y（NFA的终态），所以D为终态。.01X.AAABBCBCADDCBDFA的状态图：:问答第3题解：用子集法将NFA确定化： .01SVQQUVQVZQUQUVQUZVZZZVZ.QUZVZQUZZZZ重新命名状态子集，令VQ为A、QU为B、VZ为C、V为D、QUZ为E、Z为F。.01SABACBBDECFFDF.ECEFFFDFA的状态图：因为C、E、F含有Z，所以都是终态问答第4题解： 初始分划得0：终态组0，非终态组1,2,3,4,5 对非终态组进行审查： 1,2,3,4,5a 0,1,3,5而0,1,3,5既不属于0，也不属于1,2,3,4,5 4 a 0，所以得到新分划 1：0，4，1,2,3,5 对1,2,3,5进行审查：1,5 b 42,3 b 1,2,3,5，故得到新分划 2：0，4，1, 5，2,31, 5 a 1, 5 2,3 a 1,3，故状态2和状态3不等价，得到新分划3：0，2，3，4，1, 5 这是最后分划了最小DFA：问答第5题解：按题意相应的正规表达式是(0*10)*0*，或0*(0 | 10)*0* 构造相应的DFA，首先构造NFA为用子集法确定化：II0I1X,0,1,3,Y0,1,3,Y21,3,Y0,1,3,Y0,1,3,Y1,3,Y1,3,Y222重新命名状态集：S0112342244333 DFA的状态图：可将该DFA最小化：终态组为1,2,4，非终态组为3，1,2,40 1,2,4，1,2,41 3，所以1,2,4为等价状态，可合并。 7根据题意构造相应的NFA。由于E和F状态由初态不能通过任何路径到达,所以在NFA中可以省略,并且引入新的终态Z： Ab AabbbbbaaaS D B ZaQ 状态IaIbSAQAABZBQDDABQQDZZ构造状态子集得：编号状态子集IaIbab1SAQ232AABZ243QQDZ354BZQD365DZAB276DAB277BQD36化简：(1,2,3,6,7),(4,5) (1,6,7),(2,3),(4,5) (1),(6,7),(2,3),(4,5)化简成1、6、2、4四个状态：b b a b bb ba bb ba b1 2 4 6 a11构造相应的NFA:a babS Ab b bZ 状态abSAAASZSA利用表格构造状态子集：编号状态子集IaIbab1ZSAA222AAS33ASASA32构造出的DFA如下：abbaa1 2 3所以其正则式为|(a|b)a(a|ba)*13. (1)改变为：:=l|d:=l|d|:=d|l表示字符，d表示数字。l(2)相应的DFA为：l单词 标识符ddd整数第五章问答第1题第5章1（1）S（T）(T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S) (a,(a,S) (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) （2）改写文法如下：Sa|(T)TSTT ,ST|递归子程序为：P(S)if(SYM=a)P(a);else if(SYM=)P();else if(SYM=( )GetSym();P(T);match() ）； else Error();P(T)P(S)；P(T)；P(T)if(SYM=,)match(,);P(S);P(T);else if(SYM=()return;else error();(3) Sa|(T)TSTT ,ST|First(S)=a( Follow(S)=#,) First(T)=a( Follow(T)=) First(T)=, Follow(T)=) Select(Sa)=a Select(S)= Select(S(T)=( Select(TST)= a( Select(T,ST)=, Select(T=)由于相同左部的Select集的交集为空，所以所改写的文法是LL(1)的。写出该文法的预测分析表：a(,)#Sa(T)TSTSTSTT,ST#OK(4)对符号串(a,a)#的分析过程步骤分析栈剩余输入串所用产生式1#S(a,a)#S(T)2#)T(a,a)#(匹配3#)Ta,a)#TST4#)TSa,a)#Sa5#)Taa,a)#a匹配6#)T,a)#T,ST7#)TS,a)#，匹配8#)TSa)#Sa9#)Taa)#a匹配10#)T)#T11#)#)匹配12#接受所以(a,a)#是G的句子。问答第3题文法：SMH|aHLSo| KdML|LeHfMK|bLM 展开为：0） SM H1） Sa2） HL S o 3） H 4） Kd M L 5） K6） Le H f 7） MK 8） Mb L M 非终结符FIRST集FOLLOW集Sa,d,b,e#,o.Md,b.e,#,o.H,e.#,f,o.Le.a,d,b,e,o,#Kd,.e,#,o.对相同左部的产生式可知： SELECT(SM H)SELECT(Sa) = d,b ,e，#,o a =SELECT(HL S o)SELECT(H) = e #,f,o =SELECT(Kd M L)SELECT(K) = d e,#,o =SELECT(MK)SELECT(Mb L M) = d，e,#,o b =所以文法是LL(1)的。预测分析表（Predicting Analysis Table）aodefb#SaMHMHMHMHMHMKKKbLMKHLSoLeHfKdML由预测分析表中无多重入口也可判定文法是LL(1)的。6.（2)B有相同左因子，所以该文法不是LL(1)的。BD(b|)改写为 BDBBb|此时最终的文法为：SABSBa|BDBBb|Dd|而此文法不是LL(1)的。(4)因为文法具有左递归，所以不是LL(1)的。改写该文法：Si|(E)ESEE+SE|-SE|计算新文法的First集和Follow集。VFirstFollowSi (# + -Ei ()E+ -)计算Select集:Select(Si)=iSelect(S(E)=(Select(ESE)=i(Select(E+SE)=+Select(E-SE)=-Select(E)=) （等于follow（E）由此可以看出此文法是LL(1)的。构造相应的递归下降识别器：（即递归子程序）P(S)if(SYM=i)match(i);else if(SYM=()match();P(E);match();P(E)P(S);P(E);P(E)if(SYM=+)match(+);P(S);P(E);else if(SYM=-)match(-);P(S);P(E);else if(SYM=)returnelse error();问答第7题7消除了左递归，提取了左公因子并不一定是LL(1)的。（1)改写文法得：AbaB|BbaBbb|bb|a消除公共左因子得:AbaB|BbB|aBaBbb|b求其First集和Follow集：VFirstFollowAb#Bab#bBab#b计算Select集:Select(AbaB)=bSelect(A=# （即follow（A）Select(BbB=bSelect(Ba=aSelect(BaBbb=aSelect(Bb=b由此可见所改写的文法是LL(1)的。（2） 文法： AaABe|a BBb|d 提取左公共因子和消除左递归后文法变为：0) Aa N1) NA B e 2) N 3) Bd N14) N1b N15) N1非终结符FIRST集FOLLOW集Aa.#,dBd.e.Na,#,dN1b,e.对相同左部的产生式可知： SELECT(NA B e)SELECT(N) = a #,d =SELECT(N1b N1)SELECT(N1) = b e =所以文法是LL(1)的。预测分析表（Predicting Analysis Table）aebd#Aa NBd N1N1b N1NABe也可由预测分析表中无多重入口判定文法是LL(1)的。 (3)改写文法得：SAa|bAbabAA-aabA|求以上状态的First集和Follow集：VFirstFollowSb#AbaAaa求每个产生式的Select集合得：Select(SAa)=bSelect(Sb)=b由此可见，此文法不是LL(1)的。（4）文法：SAa|b ASBBab第1种改写：用A的产生式右部代替S的产生式右部的A得： SSBa|bBab消除左递归后文法变为： 0) Sb N1) NB a N2) N3) Ba b 非终结符FIRST集FOLLOW集Sb.#Ba.aN,a#对相同左部的产生式可知： SELECT(NB a N)SELECT(N) = a # =所以文法是LL(1)的。预测分析表（Predicting Analysis Table）ab#Sb NBa bNB a N也可由预测分析表中无多重入口判定文法是LL(1)的。 第2种改写：用S的产生式右部代替A的产生式右部的S得： SAa|bAAaB|bBBab 消除左递归后文法变为： 0) SA a 1) Sb 2) Ab B N3) Na B N4) N 5) Ba b非终结符FIRST集FOLLOW集Sb.#Ab.aBa.aNa,a对相同左部的产生式可知：SELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的。预测分析表（Predicting Analysis Table）ab#SA a.b.Ab B NBa b.Na B N.也可由预测分析表中含有多重入口判定文法不是LL(1)的。（5)可以看出A有公共左因子。消去得：SAb|aaAaAA（A|)此时，已经消除了左递归，并且没有了公共左因子。但是Select(SAb)=aSelcect(Saa)=a显然文法不是LL(1)的。第六章一、 问答题答案问答第1题第1题(1) FIRSTVT - LASTVT表 非终结符FIRSTVT集LASTVT集S a ( . a ) .T a ( , a ) , (2) 算符优先关系表 a ( ) , a ( , 优先关系唯一，所以是一个算符优先文法。 (3) 算符优先函数表： a , ( ) f 4 4 4 2 4 g 5 5 3 5 2检验发现，存在优先函数。(4)对输入串（a,a）#的算符优先分析过程为栈（STACK）当前输入字符（CHAR）剩余输入串（INPUT_STRING）动作（ACTION）#(#(a#(S#(S,#(S,a#(S,S#(T#(T)#S(a,a)#a,a)#.,a)#.a)#.a)#.)#.#.#.#.移进移进归约: Sa移进移进归约: Sa归约: TT,S 移进归约: S(T)对输入串（a,(a,a)）# 的算符优先分析过程为：栈 f(SYN(top) 关系 剩余序列 动作 产生式# 0 a,(a,a)# 移进，读# ( 2 (a,a)# 归约，不读 Sa# ( 2 (a,a)# 移进，读# ( , 4 a,a)# 移进，读# (, ( 2 a)# 规约，不读 Sa# ( , ( 2 a)# 移进，读# ( , ( , 4 )# 归约，不读 Sa#( , (, 4 )# 归约，不读 TT,S# ( , ( 2 )# 移进，读#( ,() 4 # 规约，不读 S(T)#( , 4 # 规约，不读 TT,S# ( 2 # 移进，读# () 4 规约，不读 S(T)# S OK问答第2题第2题文法：Sa|(T) TT,S|S (a,a)的最右推导过程为：S(T) (T,S) (T,a)(S,a) (a,a)(a,(a,a)的最右推导过程为: S(T) (T,S)(T,(T) (T,(T,S)(T,(T,a) (T,(S,a) (T,(a,a)(S,(a,a) (a,(a,a) 对输入串(a,a)# 的规范归约过程为： 栈（stack）剩余输入串（input left）动作（action）#( #( a#( S#( T#( T,#( T,a#( T,S#( T#(T)#S(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.#.#.移进移进归约 by :S a归约 by :TS移进移进归约 by :S a归约 by :T T,S移进归约 by :S (T)对输入串（a,(a,a)）# 的规范归约过程为：栈剩余输入串动作#( #( a#( S#( T#( T,#( T,(#( T,(a#( T,(S#( T,(T#( T,(T,#( T,(T,a#( T,(T,S#( T,(T#( T,(T)#( T,(S#( T#( T)#S(a,(a,a)#.a,(a,a)#.,(a,a)#.,(a,a)#.,(a,a)#.(a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.)#.)#.)#.)#.)#.)#.#.#.移进移进归约 by :S a归约 by :TS移进移进移进归约 by :S a归约 by :T S移进移进归约 by :S a归约 by :T TS移进归约 by :S (T)归约 by :T T,S移进归约 by :S (T)第七章问答第1题文法： AaAd|aAb| 拓广文法为G，增加产生式SA若产生式排序为：0 S A 1 A aAd2 A aAb3 A 由产生式知： First (S ) = ,aFirst (A ) = ,aFollow(S ) = # Follow(A ) = d,b,#G的LR(0)项目集族及识别活前缀的DFA如下图所示： 在I0中：A .aAd和A .aAb为移进项目，A .为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I0、I2中：Follow(A) a= d，b，# a=所以在I0、I2中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下： 题目1的SLR(1)分析表 状态（State）ActionGotoad b #A012345S2r3r3r3 accS2r3r3r3S4S5r1r1r1 r2r2r21.3题目1对输入串ab#的分析过程状态栈（state stack） 文法符号栈 剩余输入串（input left）动作（action）00 20 2 30 2 30 1#a#aA#aAb#Aab#.b#.b#.#.#.ShiftReduce by :A ShiftReduce by :A aAb分析成功，说明输入串ab是题目1文法的句子问答第2题文法： SL.L|L LLB|BB0|1 拓广文法为G，增加产生式SS若产生式排序为：0 S S 1 S L.L 2 S L 3 L LB 4 L B5 B 06 B 1 由产生式知： First (S ) = 0,1First (S ) = 0,1 First (L ) = 0,1First (B ) = 0,1Follow(S ) = # Follow(S ) = #Follow(L ) = .,0,1,#Follow(B ) = .,0,1,#G的LR(0)项目集族及识别活前缀的DFA如下图所示： 在I2中：B .0和 B .1为移进项目，S L.为归约项目，存在移进-归约冲突，因此所给文法不是LR(0)文法。在I2、I8中：Follow(s) 0，1= # 0，1=所以在I2 、I8中的移进-归约冲突可以由Follow集解决，所以G是SLR(1)文法。 构造的SLR(1)分析表如下：题目2的SLR(1)分析表 状态（State）ActionGoto 01 #SLB012345678S4S5 accS6S4S5r2r4r4r4r4r5r5r5r5r6r6r6r6S4S5r3r3r3r3S4S5r1123.7.83. 7题目2对输入串101.110#的分析过程状态栈（state stack） 文法符号栈剩余输入串（input left）动作（action）0 50 30 20 2 40 2 70 2 0 2 50 2 70 2 0 2 60 2 6 5 0 2 6 3 0 2 6 8 0 2 6 8 50 2 6 8 70 2 6 80 2 6 8 40 2 6 8 70 1#1#B#L#L0#LB#L#L1#LB#L#L.#L.1#L.B#L.L#L.L1#L.LB#L.L#L.L0#L.LB#S101.110#.01.110#.01.110#.01.110#.1.110#.1.110#.1.110#.110#.110#.110#.110#.10#.10#.10#.0#.0#.0#.#.#.#.ShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S LBShiftReduce by :B 1Reduce by :S LBShiftShiftReduce by :B 1Reduce by :S BShiftReduce by :B 1Reduce by :S LBShiftReduce by :B 0Reduce by :S L.L分析成功，说明输入串101.110是题目2文法的句子。3(1) 构造增广文法，SS文法的LR(0)项目有：1. S.S2. SS.3. S.AS4. SA.S5. SAS.6. S.b7. Sb.8. A.SA9. AS.A10. ASA.11. A.a12. Aa.（2）所产生的NFA略。由规则构造所需的DFA:I5:AS.AA.SAAa.S.ASSb.I1:SS.AS.AA.SAA.aS.ASS.b S S A b aI7:ASA.SA.SS.ASS.bA.SAA.a a AI0:S.SS.ASS.bA.SAA.aI2:Aa. aa bI3:Sb. b S bAI6:SAS.AS.AA.SAA.aS.ASS.bI4:SA.SS.ASS.bA.SAA.a abA A S S则LR(0)项目集规范族为：CI0,I1,I2,I3,I4,I5,I6,I7（3）可以看到I1,I6,I7存在着移进归约的冲突。冲突是不能用SLR(1)的方法来解决。比如I6:对于状态SAS. 和S.bFollow(S)=#,a,b与b相交不为空。所以以上文法不是SLR(1)文法。（4）为验证该文法是否为LALR或LR(1)的，构造LR(1)项目集。对于I5,产生了移进归约矛盾，所以这个文法不是LR(1)文法。于是也不是LALR文法。问答第6题文法：SUTa|Tb TS|Sc|dUUS|e 拓广文法为G，增加产生式SS若产生式排序为：0 S S1 S UTa 2 S Tb 3 T S 4 T Sc5 T d 6 U US 7 U e 由产生式知： First (S ) = d,eFirst (S ) =