《编译原理与技术》练习题 21

(1) 构造出串abc的分析树及其属性依赖图，并给出计算这些属性的一个正确顺序； (2) 假设S.u在属性求值之前的值是3，那么S.v在属性求值之后的值是什么？ (3) 如果语义规则修改如下，问题（2）的结果如何？

文法规则

S ? ABC

B.u := S.u C.u := A.v A.u := B.v + C.v S.v := A.v

A ? a B ? b C ? c

A.v := 2*A.u B.vl := B.u C.v := C.u ? 2

语义规则

8.7 设计有向图的一个拓扑排序算法，并用高级程序语言实现。

8.8 一个包含了综合属性和继承属性的属性文法中，如果综合属性依赖于继承属性（以及其它综合

属性），但是继承属性不依赖任何综合属性，那么，用一趟混合的后序遍历和前序遍历就可以计算所有的属性值。请用高级语言或伪代码设计这个算法。

8.9 例8.11中的三个属性isFloat、etype和val的语义规则如表8.8所示，它们需要遍历分析树或语

法树两次才能计算出来。第一遍后序遍历计算出综合属性isFloat的值，第二遍用混合的前序遍历和后序遍历计算出继承属性etype与综合属性val的值。 （1）请用高级语言或伪代码设计这个算法； （2）描述5/2/2.0属性的计算过程。

8.10 请按照例8.14中的语义规则，画出float x, y的带属性的分析树以及依赖关系图。 8.11 考虑文法

S ? ( L ) | a L ? L, S | S

（1）写一个打印括号对数的属性文法；

（2）写一个翻译模式，它输出每个a的嵌套深度。例如，对于输入串(a, (a, a))的输出是1，2，2。 （3）写一个翻译模式，它打印出每个a在句子中的位置。例如，对于输入串(a, (a, a))的结果是2，5，7。

8.12 下列文法由S符号开始产生一个二进制数，令综合属性val给出该数的值：

S ? L.L | L

《编译原理与技术》练习题 22

L ? LB | B L ? 0 | 1

请设计求S.val的属性文法。其中B的唯一综合属性c给出由B产生的二进位的结果值。例如，输入101.101时，S.val是5.625，其中第一个二进位的值是4，最后一个二进位的值是0.125。 8.13 考虑下列类似于C语言包含赋值语句的表达式的文法

S ? E

E ? E := E | E + E | (E) | id

即b := c表示把c的值赋给b的赋值表达式，而a:= ( b:= c)表示c的值赋给b后再赋给a。试构造语义规则，检查表达式的左部是一个左值。提示：同非终结符E的继承属性side表示生成的表达式出现在赋值运算符的左边还是右边。 8.14 请根据例8.5的属性文法，

（1）把语义规则翻译成LR属性求值器的栈操作代码（参考例8.12）； （2）建立对应的翻译模式；

（3）消除基础文法的左递归，对新增的符号增加综合属性和继承属性，编写无左递归的翻译模式;

（4）编写它的递归下降属性求值器。 8.15 为下列类型写出类型表达式

（1）指向实数的指针数组，下标范围从1到100；

（2）二维数组，行的下标从1到10，列的下标从－10到10；

（3）一个函数，它的定义域是从整型到整型指针的函数，值域是一个实型和字符组成的记录。 8.16 对下面C语言的声明：

typedef struct {

int a,b:

} CELL, *PCELL; CELL foo[100]; PCELL bar(x, y) int; CELL y; {...}

试为类型foo和函数bar写出类型表达式。

8.17 下列是一个包含文字串表的文法，其中符号的含义和图8.15中的一样。只是增加了类型list，它

《编译原理与技术》练习题 23

表示一个元素表，表中类型由of 后面的类型T确定。试设计一个翻译模式/语义规则，确定表达式(E)和(L)的类型。

P ? D; E D ? D; D | id:T

T ? list of T | char | integer E ? (L) | literal | num | id E ? E; L | E

8.18 修改表8.15的语义规则，使之可以处理

（1）有值语句。赋值语句的值是赋值号:=右边表达式的值；条件语句和循环语句的值是语句体的值；顺序语句的值是该序列中最后一个语句的值；

（2）布尔表达式。增加逻辑运算符and、or和not以及关系运算符、<、≤、=、>和≥，并且增加相应的翻译规则，给出这些表达式的类型。

《编译原理与技术》练习题 24

练习 9

9.1 把下列表达式变换成后缀式： （1）2＋3＋a＋b （2）a?b + 2?c?d （3）(x := x +3) ?4

（4）(x := y := 2) + 3?(x := 4) 9.2 把下列表达式变换成后缀式： （1）(not A and B) or (C or not D) （2）(A or B) and (C or not D and E)

（3）if (x+y) ?z = 0 then (a+b) ?c else (a?b) +b （4）a[a[i]] = b [ j+2]

9.3 请把do S while E和for (V = E1; E2; E3) S形式的循环语句写成后缀式。

9.4 如果允许处理过程递归，还需要改变表9.7的翻译模式。在产生式D ? proc id; N D1; S的S之前，执行语义动作把id插入其直接外围过程的符号表。请通过引入非终结符R及其?产生式，修改表9.7的语义动作，使它能够处理递归过程调用。

9.5 请根据表9.7的语义动作，补充图9.4中符号表的构造过程，画出符号表以及tblptr和offset： （1）当编译扫描完quicksort的局部变量说明var k, v: integer；时；

（2）当编译扫描完partition的声明、在局部变量说明var i, j: integer；之前； （3）当编译扫描完partition的整个过程时。 9.6 把下列表达式翻译成三地址代码： （1）x := y*(- a + b) （2）i := (j+k)*(10+m)

9.7 一般而言，程序设计语言都把算术表达式中不同类型的运算数进行转换，通常的规则是把整数转换成实数，然后进行运算。为了区别不同类型的运算，可以在运算符前加上类型，如实数加法的符号是real+，整数乘法的符号是int*。

（1）请利用单目转换符inttoreal以及表示类型的运算符，修改表9.9文法中加法表达式翻译规则，插入必要的类型转换。（提示：参考图9.6和表7.16，使用E的属性type和place） （2）把下列程序段的执行语句翻译成三地址代码：

《编译原理与技术》练习题 25

float x, y; int a, b; x := y + a*b

9.8 用9.3节所给的翻译模式，把下列赋值语句翻译成三地址代码： （1）a[i+j] := a[i]+a[j]*10

（2）A[i, j] := B[i, j] + C[A[k, 1]] + D[i+1]

9.9 按照表9.11翻译模式把下列布尔表达式翻译成三地址码（假设语句起始标号是10）： （1）ac

9.10 按照表9.12翻译模式把9.9题目中的布尔表达式翻译成三地址码。

9.11 利用回填技术把9.9题目中的布尔表达式翻译成四元式，假设语句起始标号是10，真值出口是100，假值出口是200。

9.12 根据9.4.2节的翻译规则，把下列语句翻译成抽象的三地址代码： （1）while a < b do

if c < d then x := y + z;

else x:= y ? z;

（2）while a < b and c > d do

if a = 1 then c := c + 1 else

while a <= d do begin d := d*2; c := c ? d end;

9.13 利用回填技术，分别把题目9.12中的语句翻译成四元式的形式。 9.14 C语言中的for语句的一般形式是

for (E1; E2; E3) S

含义如下：

E1;

while (E2) do begin end;

S; E3;

试构造一个把C语言for 语句翻译成三地址码的翻译模式。 9.15 给出描述下面语句的翻译模式