《编译原理课后部分答案》由会员分享，可在线阅读，更多相关《编译原理课后部分答案（38页珍藏版）》请在金锄头文库上搜索。
1、第二章问答第1题PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题问答第2题程序执行到赋值语句b=10时运行栈的布局示意图为：问答第3题题2中当程序编译到r的过程体时的名字表table的内容为：namekindlevel/valadrsizexvariable0dxy
2、variable0dx+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中给它分配
3、的数据段起 始 地址，也称基地址。SL： 静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。DL： 动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。 RA： 返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL， RA。 问答第5题PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位
4、置和功能以及所完成的操作说明如下：INT 0 A在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。 OPR 0 0在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。CAL L A调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从A开始执行。问答第6题对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述如下： (2) 扩充条件语句的语法图为：E
5、BNF的语法描述为： 条件语句:= 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) E
6、T 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
7、 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) 文法规则可
8、有： (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:
9、 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重新命名状态子集，令
10、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 这是最后分划了
