编译原理陈火旺第三版第七章课后题答案

编程小6 (3) 2024-05-14 13:23

Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说编译原理陈火旺第三版第七章课后题答案,希望能够帮助你!!!。

下面的答案仅供参考！

1. 给出下面表达式的逆波兰表示（后缀式）：

a*(-b+c) not A or not (C or not D)

a+b*(c+d/e) (A and B) or (not C or D)

-a+b*(-c+d) (A or B) and (C or not D and E)

if (x+y)*z=0 then (a+b) ↑c else a ↑ b ↑ c

答：

*2．假定所有算符都是二目的,那么,由算符和操作数组成的符号串是一个后缀式的必要充分条件为:(1)算符的个数比操作数的个数少1;(2)每段非空前缀中算符的个数少于操作数的个数。

答：(1) 算符的个数比操作数的个数少1，也就是说，如果我们用"#"表示操作数的个数，用"$"表示算符的个数，那么后缀式的形式应该是 "# # ... # $ # ... # $"，其中"#"出现了n次，"$"出现了n-1次。
(2) 每个非空前缀中算符的个数少于操作数的个数，也就是说，对于后缀式中的任意一个位置i，前缀式子串[0,i]中的算符的个数都小于等于操作数的个数。
这两个条件是后缀式的必要充分条件，因为后缀式的定义就是将操作数写在前面，算符写在后面的一种表达式形式。因此，如果我们在后缀式中碰到一个算符，那么它一定是前面已经出现的某两个操作数之间的运算结果，这就保证了第二个条件的成立。另外，由于每个算符都是二目的，所以一个算符只能用于计算前面的两个操作数，因此算符的个数一定比操作数的个数少1，这就保证了第一个条件的成立。

3. 请将表达式-(a+b)*(c+d)-(a+b+c)分别表示为三元式、间接三元式和四元式序列。

解题思路：

四元式由4个部分组成:算符op、第一和第二运算量arg1和 arg2，以及运算结果result。运算量和运算结果有时指用户自定义的变量，有时指编译程序引进的临时变量。如果op是一个算术或逻辑算符，则result总是一个新引进的临时变量，用于存放运算结果。
三元式只需三个域: op、arg1和 arg2。与四元式相比，三元式避免了临时变量的填人，而是通过计算这个临时变量值的语句的位置来引用这个临时变量。我们很容易把一个算术表达式或一个赋值句表示为四元式序列或三元式序列。
间接三元式是指用一张间接码表辅以三元式表的办法来表示中间代码。间接码表按运算的先后顺序列出有关三元式在三元表中的位置，相同的三元式无需重复出现在三元表中。

4.按7.3节所说的办法,写出下面赋值句
A: = B* (- C+ D)
的自下而上语法制导翻译过程。给出所产生的三地址代码。
答：

5.按照7.3.2节所给的翻译模式,把下列赋值句翻译为三地址代码:
A[i,j]:= B[i,j]+ C[A[k,1]]+ d[i+j]

答：

6.按7.4.2节的办法,写出布尔式A or (B and not (C or D))的四元式序列。

答：

7. 用7.5.1节的办法,把下面的语句翻译成四元式序列:
while A < C and B < D do
if A= 1 then C: = C+ 1 else
while A≤D do A: = A+ 2;

答：

8．在7.4.2节中,关系式被翻成相继的两个四元式

这种翻译法常常浪费一个四元式。如果我们把这个关系翻译成如下的一个四元式:

请按上述要求改写翻译布尔式的语义动作。

答：

9.写出翻译布尔表达式的递归下降程序(参考6.4.3节中介绍的技术)。

答：

10.设有一台单累加器的计算机,它的汇编语言含有通常的指令:LOAD、STORE、ADD和 MULT。
(1)写一个递归下降程序,把下面文法所定义的赋值句翻译成汇编语言:
A一i：=E
E→E+E|E*E|(E)|i

答：

(2)利用加、乘满足交换律这一性质,改进你的翻译程序,以期产生较高效的目标代码。

答：由(1)的翻译子程序产生的汇编代码中存在一些多余的存取指令。可利用加法和乘法满足交换律这一性质,对上述翻译子程序加以改造,提高汇编代码的效率。改进的翻译程序如下:

11．C语言中的for语句的一般形式为

试构造一个属性文法和翻译模式,把C语言的for语句翻译成三地址代码。

解题思路：本题既要求构造属性文法,也要求构造相应的翻译模式。因此,有必要回忆一下属性文法和翻译模式的区别。我们知道,属性文法(有时也称语法制导定义)可以看作是关于语言翻译的高级规范说明,其中隐去实现细节,使用户从明确说明翻译顺序的工作中解脱出来;而翻译模式(也称为翻译方案)是一种适合语法制导翻译的描述形式,它给出了使用语义规则进行计算的次序,这样就可把某些实现细节表示出来。
为了明确翻译目标,我们首先给出for语句的中间代码结构如图所示。

根据C语言的for语句的语义和以上中间代码结构可以构造出属性文法。
为了构造属性文法相应的翻译模式,通常可采用两种方法:一-种方法是在原有产生式中引入必要的标记非终结符;另一种方法是对文法进行分解和改造。两种方法的目的都是为了便于语法制导翻译。

解答：把C语言的for语句翻译成三地址代码的属性文法如下:

下面我们用两种方法构造相应上述属性文法的翻译模式。

方法一:
引入M1、M2和 N3个标记非终结符。M1用来记住E2的开始地址,M2用来记住M3的开始地址。N是用来产生E3后面的goto语句,从上面的中间代码结构来看,产生这个goto语句时,转移地址应该是已知的了,但该语句是在N→e归约时产生的,这时不能访问M1的属性,因此这个转移的目标地址要回填。

这样改写是因为,语法制导翻译过程中,在产生E2的代码之前要记下E2的代码地址;在产生E3的代码之前要记下E3的代码地址,并要对E2的“真”出口进行“回填”;而在产生E3的代码之后要生成一条goto语句。

12. Pascal语言中，语句

for v：＝initial to final do stmt

与下列代码序列有相同含义

begin

t1:=initial; t2:=final;

if t1<=t2 then begin

v:=t1;

s；

while v<>t2 do begin

v：=succ（v)；

s；

end

(1)试考虑下述Pascal程序

program forloop(input, output);

var i,initial,final: integer;

begin

read(initial, final);

for i:= initial to final do

write(i)

end

对于initial=MAXINT-5和final= MAXINT，问此程序将做些什么？其中MAXINT为目标机器允许的最大整数。

答：如果该程序执行,则先会打印出MAXINT-5到MAXINT的6个数,然后对于有些实现可能会因为整型数溢出而出现运行时的异常。

(2)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。

答：根据其语义,先确定PASCAL语言for语句的中间代码结构如下:

13.分别对下列类型写出类型表达式:

(1)一个指向实型量的指针数组,其下标范围1~100;
(2)一个二维数组,其行下标0~9,列下标-10~10;
(3)一个函数,其实参为一个整型数,返回值为-个指针,指向由一个整型数和一个字符组成的记录。
解题思路：从教材中类型表达式的定义我们可知:
(1)对于数组,如果T是一个类型表达式,则array(I,T)是一个类型表达式,表示一个数组类型,其中数组元素的类型为T,下标的集合为I。
(2)记录的类型表达式是把类型构造符record施于一个二元组构成的且二元组中包含各域的名称及其相应的类型。
(3)如果T是一个类型表达式,则 pointer(T)是表示“指向T类型对象的指针"类型。
(4)函数的类型用类型表达式D→R表示。即把函数的类型处理成由作用域类型D到值域类型R的映射。