编译原理课后答案——第六章_运行时存储空间组织

第六章习题答案4．文法G：S→S;G|GG→G(T)|HH→a|(S)T→T+S|S（1）该文法是算符文法，且不包含ε产生式。

计算每个非终结符的FIRSTVT集合：FIRSTVT(S) = FIRSTVT(S)∪{;}∪FIRSTVT(G) = {;, a, (}FIRSTVT(G) = FIRSTVT(G)∪{(}∪FIRSTVT(H) = {a, (}FIRSTVT(H) = {a, (} = {a, (}FIRSTVT(T) = FIRSTVT(T)∪{+}∪FIRSTVT(S) = {+, ;, a, (}计算每个非终结符的LASTVT集合：LASTVT(S) = {;}∪LASTVT(G) = {;, a, )}LASTVT(G) = {)}∪LASTVT(H) = {a, )}LASTVT(H) = {a, )} = {a, )}LASTVT(T) = {+}∪LASTVT(S) = {+, ;, a, )}①关系由#S#可知：##由G→G(T)|H可知：()②关系S# LASTVT(S)#→{;, a, )}#S; LASTVT(S);→{;, a, )};G( LASTVT(G)( →{a, )}(T) LASTVT(T)) →{+, ;, a, )})S) LASTVT(S)) →{;, a, )})T+ LASTVT(T)+ →{+, ;, a, )}+③关系#S #FISRTVT(S)→ #{;, a, (};G ;FISRTVT(G)→ ;{a, (}(T (FISRTVT(T)→ ({+, ;, a, (}(S (FISRTVT(S)→ ({;, a, (}+S +FISRTVT(S)→ +{;, a, (}构造算符优先关系表如下：+ ; a ( ) # +;a()#由该文法的算符优先关系表可知，该文法是算符优先文法。

（2）句型a(T+S);H;(S)的语法树如右图所示：短语：a(T+S);H;(S)，a(T+S);H ，a(T+S)，a ，T+S ，H ，(S)句柄：a素短语：a ，T+S ，(S)最左素短语：a（3）对a;(a+a)进行算符优先分析步骤如下：对采用算符优先分析方法进行分析，可知：a;(a+a)和(a+a)均应为该文法的句子。

第1 章引论第1 题解释下列术语：（1）编译程序（2）源程序（3）目标程序（4）编译程序的前端（5）后端（6）遍答案：（1）编译程序：如果源语言为高级语言，目标语言为某台计算机上的汇编语言或机器语言，则此翻译程序称为编译程序。

（2）源程序：源语言编写的程序称为源程序。

（3）目标程序：目标语言书写的程序称为目标程序。

（4）编译程序的前端：它由这样一些阶段组成：这些阶段的工作主要依赖于源语言而与目标机无关。

通常前端包括词法分析、语法分析、语义分析和中间代码生成这些阶段，某些优化工作也可在前端做，也包括与前端每个阶段相关的出错处理工作和符号表管理等工作。

（5）后端：指那些依赖于目标机而一般不依赖源语言，只与中间代码有关的那些阶段，即目标代码生成，以及相关出错处理和符号表操作。

（6）遍：是对源程序或其等价的中间语言程序从头到尾扫视并完成规定任务的过程。

第2 题一个典型的编译程序通常由哪些部分组成？各部分的主要功能是什么？并画出编译程序的总体结构图。

答案：一个典型的编译程序通常包含8 个组成部分，它们是词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、中间代码优化程序、目标代码生成程序、表格管理程序和错误处理程序。

其各部分的主要功能简述如下。

词法分析程序：输人源程序，拼单词、检查单词和分析单词，输出单词的机内表达形式。

语法分析程序：检查源程序中存在的形式语法错误，输出错误处理信息。

语义分析程序：进行语义检查和分析语义信息，并把分析的结果保存到各类语义信息表中。

中间代码生成程序：按照语义规则，将语法分析程序分析出的语法单位转换成一定形式的中间语言代码，如三元式或四元式。

中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处理。

目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。

表格管理程序：负责建立、填写和查找等一系列表格工作。

表格的作用是记录源程序的各类信息和编译各阶段的进展情况，编译的每个阶段所需信息多数都从表格中读取，产生的中间结果都记录在相应的表格中。

第6章 属性文法和语法制导翻译7. 下列文法由开始符号S 产生一个二进制数，令综合属性v al 给出该数的值：试设计求S.val 的属性文法，其中，已知B 的综合属性c, 给出由B 产生的二进位的结果值。

例如，输入101.101时，S.val=5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。

【答案】11. 设下列文法生成变量的类型说明：(1)构造一下翻译模式，把每个标识符的类型存入符号表；参考例6.2。

【答案】第7章 语义分析和中间代码产生1. 给出下面表达式的逆波兰表示（后缀式）：3. 请将表达式－(a+b)*(c+d)-(a+b+c)分别表示成三元式、间接三元式和四元式序列。

【答案】间接码表：(1)→(2)→(3)→(4)→(1)→(5)→(6)4. 按7.3节所说的办法，写出下面赋值句A:=B*(－C+D ) 的自下而上语法制导翻译过程。

给出所产生的三地址代码。

【答案】5. 按照7.3.2节所给的翻译模式，把下列赋值句翻译为三地址代码： A[i, j]:=B [i, j] + C[A [k, l]] + d [ i+j] 【答案】6. 按7.4.1和7.4.2节的翻译办法，分别写出布尔式A or ( B and not (C or D) )的四元式序列。

【答案】用作数值计算时产生的四元式： 用作条件控制时产生的四元式：其中：右图中(1)和(8)为真出口，(4)(5)(7)为假出口。

7. 用7.5.1节的办法，把下面的语句翻译成四元式序列： While A<C and B<D do if A=1 then C:=C+1else while A ≦D do A:=A+2; 【答案】第9章 运行时存储空间组织4. 下面是一个Pascal 程序：当第二次( 递归地) 进入F 后，DISPLAY 的内容是什么？当时整个运行栈的内容是什么？ 【答案】第1次进入F 后，运行栈的内容： 第2次进入F 后，运行栈的内容：第2次进入F 后，Display 内容为：5. 对如下的Pascal 程序，画出程序执行到(1)和(2)点时的运行栈。

第一章编译程序概述1.1什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多 数计算机系统都含有不止一个高级语言的编译程序。

对有些高 级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复 杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过 程是划分成阶段进行的，每个阶段将源程序的一种表示形式转 换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连 接在一起的。

一般一个编译过程划分成词法分析、语法分析、 语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起， 这些阶段间的源程序的中间表示形式就没必要构造岀来了。

我 们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理 和岀错处理与上述六个阶段都有联系。

编译过程中源程序的各 种信息被保留在种种不同的表格里，编译各阶段的工作都涉及 到构造、查找或更新有关的表格，因此需要有表格管理的工作； 如果编译过程中发现源程序有错误，编译程序应报告错误的性 质和错误发生的地点，并且将错误所造成的影响限制在尽可能 小的范围内，使得源程序的其余部分能继续被编译下去，有些 编译程序还能自动校正错误， 这些工作称之为岀错处理。

图1.3表示了编译的各个阶段。

图1.3编译的各个阶段它不生成目标代码，它每遇到一个语句，就要对这个语句进行 分析以决定语句的含义，执行相应的动作。

右面的图示意了它 的工作机理第二章：PL/O 编译程序问答第1题 PL/0语言允许过程嵌套定义和递归调用，试问 它的编译程序如何解决运行时的存储管理。

答：PL/0语言允许过程嵌套定义和递归调用，它的编译程序在运行时采用了栈式动态存储管理。

(数组CODE 存放的只读目 标程序，它在运行时不改变。

)运行时的数据区S 是由解释程序 定义的一维整型数组，解释执行时对数据空间S 的管理遵循后进先岀规则，当每个过程(包括主程序)被调用时，才分配数据 空间，退出过程时，则所分配的数据空间被释放。

第六章习题解答6.1根据语法树，得到下述优先关系：E′*(E T′>+ F>* i>*+<T +<F +<i *<(6.2由文法各条产生式，有然后构造<：FIRST={(Z,b),(M,(),(M,a),(L,M)}FIRST+={(Z,b),(M,(),(M,a),(L,M),(L,(),(L,a)}FIRST*=FIRST+∪{(a,a),(b,b),((,(),( ),)),(Z,Z),(M,M),(L,L)}所以<={(b,(),(b,a),((,M),((,(),((,a))再构造>：LAST={(Z,b),(M,L),(M,a),(L,))}LAST+={(Z,b),(M,L),(M,a),(M,))(L,))}(LAST+)T={(b,Z),(L,M),(a,M),( ),M},( ),L}}(LAST+)T所以>={(L,b),(L,a),(a,b),(a,a),( ),b),(),a)}将这三种关系合并得到表6.1。

利用此算法分析符号串b((aa)a)b是否是文法G[Z]的句子，过程如表6.2所示。

分析成功，符号串b((aa)a)b是文法G[Z]的句子。

表6.1 G[Z]的简单优先关系矩阵表6.2 简单优先分析过程6.3由优先关系矩阵中所示的优先关系：a>c a<b b>b b以及优先函数的定义，应该有f(a)>g(c)，f(a)<g(b)，f(b)>g(b)，f(b)=g(c)则有f(a)>g(c)=f(b)>g(b)>f(a)矛盾。

所以该文法不存在优先函数。

6.4①定义集合∑=N，R={(x,y)∣x,y∈∑,x是y的因子}②定义集合∑=N,R={(x,y)|x,y∈∑,x和y均能被3整除}③定义集合∑=N-{1}，R={(x,y)|x,y∈∑,x和y有大于1的公约数}④定义集合∑=N,R为关系“=”6.5关系可以用集合定义，也可以用布尔矩阵表示。

第一章编译程序概述1.1 什么是编译程序编译程序是现代计算机系统的基本组成部分之一，而且多数计算机系统都含有不止一个高级语言的编译程序。

对有些高级语言甚至配置了几个不同性能的编译程序。

1.2编译过程概述和编译程序的结构编译程序完成从源程序到目标程序的翻译工作，是一个复杂的整体的过程。

从概念上来讲，一个编译程序的整个工作过程是划分成阶段进行的，每个阶段将源程序的一种表示形式转换成另一种表示形式，各个阶段进行的操作在逻辑上是紧密连接在一起的。

一般一个编译过程划分成词法分析、语法分析、语义分析、中间代码生成，代码优化和目标代码生成六个阶段,这是一种典型的划分方法。

事实上，某些阶段可能组合在一起，这些阶段间的源程序的中间表示形式就没必要构造出来了。

我们将分别介绍各阶段的任务。

另外两个重要的工作：表格管理和出错处理与上述六个阶段都有联系。

编译过程中源程序的各种信息被保留在种种不同的表格里，编译各阶段的工作都涉及到构造、查找或更新有关的表格，因此需要有表格管理的工作；如果编译过程中发现源程序有错误，编译程序应报告错误的性质和错误发生的地点，并且将错误所造成的影响限制在尽可能小的范围内，使得源程序的其余部分能继续被编译下去，有些编译程序还能自动校正错误，这些工作称之为出错处理。

图1.3表示了编译的各个阶段。

图1.3 编译的各个阶段1.3 高级语言解释系统为了实现在一个计算机上运行高级语言的程序,主要有两个途径：第一个途径是把该程序翻译为这个计算机的指令代码序列，这就是我们已经描述的编译过程。

第二个途径是编写一个程序，它解释所遇到的高级语言程序中的语句并且完成这些语句的动作，这样的程序就叫解释程序。

从功能上说，一个解释程序能让计算机执行高级语言。

它与编译程序的主要不同是它不生成目标代码，它每遇到一个语句，就要对这个语句进行分析以决定语句的含义，执行相应的动作。

右面的图示意了它的工作机理第二章：PL/0编译程序问答第1题PL/0语言允许过程嵌套定义和递归调用，试问它的编译程序如何解决运行时的存储管理。

第六章第6章自底向上优先分析P122 练习1、已知文法G[S]为：S a|^|(T)T T,S|S(1)计算G[S]的FIRSTVT和LASTVT。

(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。

(4)给出输入串(a,a)#和(a,(a,a))#的算符优先分析过程。

【解】(1)FIRSTVT LASTVTS a、^、（a、^、）T ，、a、^、（，、a、^、)(2)a ( ) , ^ #a ≯≯≯( ≮≮=≮≮) ≯≯≯, ≮≮≯≯≮^ ≯≯≯# ≮≮≮步骤栈优先关系当前符号剩余输入串移进或归约1 # #≮( ( a,a)# 移进4S->S;G|GG->G(T)|HH->a|(S)T->T+S|S(1)构造G[S]的算符优先关系表，并判断G[S]是否为算符优先文法。

(2)给出句型a（T+S）;H;(S)的短语、句柄、素短语和最左素短语。

【解】（1）FIRSTVT(S)={； ( a }FIRSTVT(G)={ ( a }FIRSTVT(T)={+ ； ( a}LASTVT(S)={； a ) }LASTVT(G)={ a ) }LASTVT(T)={+ ; a ) }>关系：LASTVT(S) >;LASTVT(G)>(LASTVT(T)>)LASTVT(S)>)LASTVT(T)> +< 关系;<FIRSTVT< SPAN>(G)(<FIRSTVT(T)(<FIRSTVT(S)< SPAN>+< FIRSTVT(S)= 关系( = );()a+# ;<..><..>.> (<.<.<..> ).>.>.>a .>.>.>+<.<..><..>.> #<.<.<.<.<.（2）建立句型的语法子树如下：短语为：a, T+S, H, (S), a(T+S),a(T+S);H , a（T+S）;H;(S)句柄：a素短语：a, T+S, (S)最左素短语：a如有侵权请联系告知删除，感谢你们的配合！如有侵权请联系告知删除，感谢你们的配合！。