编译原理与技术练习题汇总 下载本文

内容发布更新时间 : 2023/2/4 13:17:34星期一 下面是文章的全部内容请认真阅读。

《编译原理与技术》练习题 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 给出描述下面语句的翻译模式