编译原理课后部分答案

《编译原理课后部分答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章问答第1题　　PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。（数组CODE存放的只读目标程序，它在运行时不改变。）运行时的数据区S是由解释程序定义的一维整型数组，解释执行时对数据空间S的管理遵循后进先出规则，当每个过程(包括主程序)被调用时，才分配数据空间，退出过程时，则所分配的数据空间被释放。应用动态链和静态链的方式分别解决递归调用和非局部变量的引用问题问答第2题　　程序执行到赋值语句b∶=10时运行栈的布局示意图为：问答第3题　　题2中当程序编译到r的过程体时的名字表table的内容为：namekindlevel/valadrs

2、izexvariable0dx yvariable0dx+1 pprocedure0过程p的入口（待填）5avariable1dx qprocedure1过程q的入口4sprocedure1过程s的入口（待填）5cvariable2dx dvariable2dx rprocedure2过程r的入口5evariable3dx fvariable3dx+1 注意：q和s是并列的过程，所以q定义的变量b被覆盖。问答第4题　　栈顶指针T，最新活动记录基地址指针B，动态链指针DL，静态链指针SL与返回地址RA的用途说明如下：　　T：栈顶寄存器T指出了当前栈中最新分配的单元(T也是数组S

3、的下标)。　　B：基址寄存器，指向每个过程被调用时，在数据区S中给它分配的数据段起始地址，也称基地址。　　SL：静态链，指向定义该过程的直接外过程（或主程序）运行时最新数据段的基地址，用以引用非局部（包围它的过程）变量时，寻找该变量的地址。　　DL：动态链，指向调用该过程前正在运行过程的数据段基地址，用以过程执行结束释放数据空间时，恢复调用该过程前运行栈的状态。　　RA：返回地址，记录调用该过程时目标程序的断点，即调用过程指令的下一条指令的地址，用以过程执行结束后返回调用过程时的下一条指令继续执行。　　在每个过程被调用时在栈顶分配3个联系单元，用以存放SL，DL，RA。问答第

4、5题　　PL/0编译程序所产生的目标代码中有3条非常重要的特殊指令，这3条指令在code中的位置和功能以及所完成的操作说明如下：　　INT0A　　在过程目标程序的入口处，开辟A个单元的数据段。A为局部变量的个数+3。　　OPR00　　在过程目标程序的出口处，释放数据段（退栈），恢复调用该过程前正在运行的过程的数据段基址寄存器B和栈顶寄存器T的值，并将返回地址送到指令地址寄存器P中，以使调用前的程序从断点开始继续执行。　　CALLA　　调用过程，完成填写静态链、动态链、返回地址，给出被调用过程的基地址值，送入基址寄存器B中，目标程序的入口地址A的值送指令地址寄存器P中，使指令从

5、A开始执行。问答第6题　　对PL/0语言作如下功能扩充时的语法图和EBNF的语法描述如下：　　(2)扩充条件语句的语法图为：　　EBNF的语法描述为：〈条件语句〉::=if〈条件〉then〈语句〉[else〈语句〉]　　(3)扩充repeat语句的语法图为：　　EBNF的语法描述为：〈重复语句〉::=repeat〈语句〉{；〈语句〉}until〈条件〉第3章文法和语言习题参考答案1.L(G)={abc}2.L(G[N])是无符号整数。3.G3:E→D+E

6、D-E

7、DD→0

8、1

9、2

10、3

11、4

12、5

13、6

14、7

15、8

16、94.L(G[Z])={anbn

17、n>0}5.(1)G5:N→DN

18、EE

19、→0

20、2

21、4

22、6

23、8D→E

24、1

25、3

26、5

27、7

28、9(2)G5:N→AB

29、EB→DB

30、EA→1

31、2

32、3

33、4

34、5

35、6

36、7

37、8

38、9E→0

39、2

40、4

41、6

42、8D→A

43、06.(1)EÞTE(5)EÞE+TE(6)EÞE+TEÞFTÞT+TE+TÞT+TE+TÞiFÞF+TTFÞF+TTT*FiÞi+TF(E)Þi+TFFiÞi+FiE+TÞi+T*FiiÞi+(E)TFÞi+F*FÞi+(E+T)FiÞi+i*FÞi+(T+T)iÞi+i*iÞi+(F+T)Þi+(i+T)Þi+(i+F)Þi+(i+i)7.EEi+i*i的两棵语法树不同，EOEEOE故文法是二义的。i+EOEEOE*ii*i

44、i+i8.SSabc的两棵语法树不同，AcaB故文法是二义的。abbc9.(1)S(2)该文法生成的语言是后缀表达式，SS*或称为逆波兰式。SS+aaa10.（1）该文法生成的语言是“可并列或嵌套的配对的括号串”。（2）文法是二义的，因为句子“()()”有两棵不同的语法树。SSS(S)SS(S)SS(S)SeeeeS(S)Seeeeee11.可构造E+T*F的语法树如右所示：E短语：E+T*FT*F故为文法的句型。E+T其中，T*F是直接短语和句柄T*F13.（1）最左推导最右推导(2)文法规则可有：(