编译原理作业集-第七章

第七章 语义分析和中间代码产生

本章要点

1. 中间语言，各种常见中间语言形式；

2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译； 3. 过程调用的处理； 4. 类型检查；

本章目标

掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。

本章重点

1．中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示； 3．赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式； 4．各种控制流语句的翻译及其中间代码格式； 5．过程调用的中间代码格式； 6．类型检查；

本章难点

1. 各种语句的翻译； 2. 类型系统和类型检查；

作业题

一、单项选择题：

1. 布尔表达式计算时可以采用某种优化措施，比如A and B用if-then-else可解释为_______。

a. if A then true else B； b. if A then B else false； c. if A then false else true； d. if A then true else false； 2. 为了便于优化处理，三地址代码可以表示成________。

a. 三元式 b. 四元式 c. 后缀式 d. 间接三元式 3. 使用三元式是为了________：

- 1 - - -

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

编译原理作业集－第七章 语义分析和中间代码产生

a. 便于代码优化处理 b. 避免把临时变量填入符号表 c. 节省存储代码的空间 d. 提高访问代码的速度 4. 表达式-a+b*(-c+d)的逆波兰式是________。

a. ab+-cd+-*；b. a-b+c-d+*；c. a-b+c-d+*；d. a-bc-d+*+； 5. 赋值语句x:=-(a+b)/(c-d)-(a+b*c)的逆波兰式表示是_______。

a. xab+cd-/-bc*a+-:=；a. xab+/cd-bc*a+--:=；a. xab+-cd-/abc*+-:=；a. xab+cd-/abc*+--:=； 6. 在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以由________来描述。

a. 抽象语法树；b. 语法规则；c. 依赖图；d. 三地址代码；

7. 按照教材中的约定，三地址语句if x relop y then L表示成四元式为 。

a. (relop，x，y，L)；b. (relop，L，x，y)；c. (relop，x，L，y)；d. (L，x，y，relop)； 8. 在编译程序中， 不是常见的中间语言形式。

a.波兰式；b. 三元式；c. 四元式； d. 抽象语法树； 9. 在编译程序中安排中间代码生成的目的是________。

a. 便于提高编译效率； b. 便于提高分析的正确性；

c. 便于代码优化和目标程序的移植；d.便于提高编译速度； 10. 按照教材中的约定，下面 不是类型表达式：

a. boolean；b. type-error；c. real；d. DAG； 11. 一个Pascal函数

function f ( a, b:char ) :↑integer; ……

其作用域类型是 ：

a. char×integer；b. char×char；c. char×pointer(integer)；d. integer×integer；

12. 因为标识符可用于多种情况，比如常量标识符、变量标识符、过程标识符等等。因此，在符号表中为了给出各个符号的标志，常给标识符引入一个属性kind，然后在相应产生式的语义动作中添加给kind属性赋值的语句。比如，在在产生式Did:T的语义动作中添加赋值语句id.kind= 。

a. VAR； b. CONSTANT；c. PROC；d. FUNC；

13. 下面 情况下，编译器需要创建一张新的符号表。

a. 过程调用语句；b. 标号说明语句；c. 数组说明语句；d.记录说明语句； 14. 函数function f(a,b:char):↑integer;… 所以f函数的类型表达式为：

a. char×char→pointer(integer)； b. char×char→pointer；

c. char×char→integer； d. char×char→integer (pointer)

15. 如果一个语言的编译器能保证编译通过的程序，在运行时不会出现类型错误，则称该语言是 。

a. 静态的；b. 强类型的；c. 动态的；d. 良类型的；

一．答案：1. b；2. d；3. b；4. d；5. c；6. c.；7. a；8. a；9. c；10. d；11. b；12. a；13. d；14. a；15. b；

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 2 - - -

编译原理作业集－第七章 语义分析和中间代码产生

二、填空题：

1. 语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的________规则进行的。

2. 多目运算x:=y[i]的三元式表示为两部分：________________和________________。 3. 生成三地址代码时，临时变量的名字对应抽象语法树的____________。

4. 一个类型表达式或者是基本类型，或者由____________施加于其它类型表达式组成。 5. 在程序设计语言中，布尔表达式有两个基本的作用：一个是 ；另一个是 。

6. 允许嵌套过程的语言，其过程说明语句的翻译用两个栈tblptr和offset分别保存尚未处理完的过程的 和它们的offset，这两个栈顶的元素分别是正在处理的过程的的符号表指针和 。

7. 在一些pascal的实现中，如果说明中出现了没有名字的类型表达式，编译器这样处理：建立一个 来和每个声明的变量标识符相联系。

8. 赋值语句a:=b*-c+b*-c的后缀式为 。

9. 多目运算X[i]:=y的三元式表示为两部分：________________和________________。 10. 编译器遇到常量说明时，要把常量值登录入 并回送序号；在 中为等号左边的标识符建立新条目，在该条目中填入常量标志、相应类型和常量表序号。 11. 典型的转移条件语句：if E then S1 else S2中，作为转移条件的布尔表达式E，赋予它两种“出口”：一是 ；二是 。

12. 类型表达式或者是 ，或者是 作用在其它类型表达式上得到的新的类型表达式。

13. pascal变量说明： var A:array[1..10] of integer

与A相关的类型表达式为： 。 14. 若T是类型 表达式，则pointer(T)是类型表达式，它表示 类型 。 15. 通过一遍扫描来产生布尔表达式和控制流语句的代码存在一个问题，就是当生成某些转移语句时可能还不知道该语句将要转移到的语句的地址是什么。采用 的办法来解决这个问题。

二．1. 语义；2. (0): ( [ ]=, y, i )，(1): ( assign, x, (0) )；3. 内部结点；4. 类型构造符；5. 计算逻辑值；作控制流语句中的条件表达式；6. 符号表指针，相对地址；7. 隐含的类型名；8. a b c uminus * b c uminus * + assign；9. (0):（=[ ]，x，i）；(1):（assign，(0)，y）；10. 常量表；符号表；11. “真”出口，转向S1；“假”出口，转向S2；12. 基本类型；类型构造符；13. array(1..10, integer) ；14. “指向T类型对象的指针”；15. “拉链－回填”

三、判断题：

1. 中间代码是独立于机器的，复杂性介于源语言和机器语言之间，便于进行与机器无关调换代码优化工作。（ ）

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 3 - - -

编译原理作业集－第七章 语义分析和中间代码产生

2. 在程序设计语言中，一般来说，布尔表达式仅仅用于条件、循环等控制流语句中的条件表达式计算。（ ）

3. “回填”技术用于对过程中的说明语句进行处理时把计算出的有关符号的属性填入符号表。 ( )

4. 如果E是一个常量或变量，则E的逆波兰式是E自身。( ) 5. 对于任何一个编译程序来说，中间代码的产生是不一定必要的。（ ）

6. 由于三元式中的三个域中，仅有两个域与地址有关，所以，三元式不是严格意义上的三地址代码。（ ）

7. 两个类型表达式要么是同样的基本类型，要么是同样的类型构造符作用于结构等价的类型，我们就说，这两个类型系统等价。（ ）

8. 对于Pascal这样允许嵌套过程的语言，每当遇到过程说明Dproc id ; D1; S时，便创建一张新的符号表，也就是说，让每个过程说明都有自己一张独立的符号表。（ ）

9. 记录类型的各个域变量分配存储区域的地址的确定是相对于为记录类型变量所分配存储区域的首地址的，所以记录类型不应该建立自己的符号表。（ ） 10. 类型表达式中不可出现类型变量，即类型变量值不是类型表达式。（ ）

11. 所谓类型系统就是把类型表达式赋给语言各相关结构成分的规则的集合。同一种语言（比如C++语言）的编译程序，在不同的实现系统里（比如微软的Visual C++和Linux下的开源编译器TCC），可能使用不同的类型系统。

12. 四元式表示的是四地址代码，三元式表示的是三地址代码。（ ） 13. 生成三地址代码时，临时变量的名字对应抽象语法树的内部结点。（ ）

14. 后缀式是抽象语法树的线性表示形式，后缀式是树结点的一个序列，其中每个结点 都是在所有子结点之后立即出现的。（ ）

15. 后缀表示形式只是用于表达式的，其他的语法结构比如条件语句、循环语句等不能使用后缀式。（ ）

三．答案：1. ；2. ×；3. ×；4. ；5. ；6. ×；7. ；8. ；9. ×；10. ×；11. ；12. ×；13. ；14. ；15. ×；

四、名词解释：

1. 三地址代码； 2. 回填；

3. 类型表达式； 4. 类型系统； 5. 静态语义检查

四．答案：

1. 三地址代码是由下面一般形式的语句构成的序列：x:= y op z。其中x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等，每个语句的右边只能有一个运算符。

2. 通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于，当生成某些转移语句时我们可能还不知道该语句将要转移到的标号是什么。为了解决这个问题，可以在生成形成分支的跳转指令时，暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 4 - - -

编译原理作业集－第七章 语义分析和中间代码产生

令的标号键入这个链表，一旦目标确定之后再把它填入有关的跳转指令中。这种技术称为回填。

3. 一个类型表达式或者是基本类型，或者由类型构造符施于其他类型表达式组成。基本类型和类型构造符都因具体语言的不同而不同。 Ⅰ. 一个基本类型是一个类型表达式。 Ⅱ. 类型名是一个类型表达式

Ⅲ. 类型构造符作用于类型表达式，其结果仍然是类型表达式 Ⅳ. 类型表达式中可出现类型变量，即变量值是类型表达式。

4. 所谓类型系统就是把类型表达式赋给语言各相关成分的规则的集合。同一种语言的编译程序，在不同的实现系统里，可能使用不同的类型系统。

5. 静态语义检查就是编译过程中进行的语义检查。主要工作有：类型检查、控制流检查、一致性检查、相关名字检查，还有名字的作用域分析等。

五、简答题：

1. 四元式和三元式有什么不同？

2. 为什么要使用中间代码的表示形式？

3. 现在有四种程序设计语言：PASCAL、FORTRAN、C和BASIC。要求在A、B、C和D四种机器上都能编译这四种语言，而编译程序需要在中间语言级别上进行优化处理。问：需要编制多少个编译程序的前后端接口？

4. 为什么三元式没有存放计算结果的单元？

5. 过程调用语句在翻译的时候，如何处理参数传递的问题（只考虑传递实在参数地址的情况）？P200.

五．答案： 1. 一个四元式是一个带有四个域的记录结构，分别为op，arg1，arg2，result。四元式之间的联系是通过临时变量来实现的，更改一个四元式表很容易，因此对中间代码进行优化处理时比较方便。 一个三元式是一个带有三个域的记录结构，分别为op，arg1，arg2。三元式之间的联系是通过指针来实现的，更改一个三元式表没有四元式表那样容易，但是，对中间代码进行优化处理时，四元式和间接三元式同样方便。 2. 使用中间代码有如下好处：

（1）中间形式与具体机器无关，把与机器特性紧密相关的内容尽可能放到后端，有利于目标重定位，一种中间形式可以为生成多种不同型号目标机上的目标代码服务。 （2）可以对中间代码进行与机器无关的优化，有利于提高目标代码的质量。 （3）使各阶段的开发复杂性降低，有利于编译程序的开发。

3. 由于各种不同的程序设计语言都有很多不同的特点，所以，若有m种不同的程序设计语言，就会有m个前端。这时，如果有n种不同的机器，也就会有n个后端。从理论上讲，如果要移植一个现有的编译程序到另外一台新机器上，只需要重新编写它的后端即可。 现在有四种程序设计语言：PASCAL、FORTRAN、C和BASIC，那么可以得到四个前端：有A、B、C和D四种机器，要求在每种机器上都能编译上述四种语言，只需要根据四种不同机器的特点为每种语言构造四个后端就行了。所以要在A、B、C和D四种机器上都能编译上述四种语言，总共需要编制16个前后端的接口即可。

4. 由于中间语言（包括三元式）是用来辅助生成目标代码的，并不会真正进行计算，也就

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 5 - - -

编译原理作业集－第七章 语义分析和中间代码产生

不需要一个临时单元存放结果，那么在编制后面的三元式时如果要用到这些运算结果，可以用这些三元式的编号来代替。

六、应用题：

1. 已知产生布尔表达式的语法定义如下： E→E1 or E2 E→E1 and E2 E→not E1

E→(E1)

E→id1 relop id2

E→id1

a写出翻译模式；

b画出语法树（语义动作也表示在其中）；

c通过对语法树的遍历，写出对布尔表达式a1. 答案：见教材P187，图7.14。

E→E1 or E2 {E.place:=newtemp; emit(E.place ':=' E1.place 'or' E2.place)} E→E1 and E2 {E.place:=newtemp; emit(E.place ':=' E1.place 'and' E2.place)} E→not E1 {E.place:=newtemp; emit(E.place ':=' 'not' E1.place)} E→(E1) {E.place:= E1.place} E→id1 relop id2 {E.place:=newtemp; emit('if' id1.place relop.op id2.place 'goto' nextstat+3); emit(E.place ':=' '0'); emit('goto' nextstat+2); emit(E.place ':=' '1')} E→id1 {E.place:=id.place}

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 6 - - -

编译原理作业集－第七章 语义分析和中间代码产生

E 动作5 E or 动作1 E 动作4 id (a) relop (<) id (b) id (c) E or 动作2 E 动作3 id (e) relop (<) id (f) relop (<) id (d) 100: if a104: if c108: if e112: T4:=T2 and T3 113: T5:=T1 or T4

2. 画出赋值语句a:=b*-c+b*-c的抽象语法树和DAG图，并写出它的后缀式表示法。 2. 答案：见教材P168，图7.3。 assign assign a * b uminus + * b uminus a + * b uminus c c c 后缀式表示法：a b c uminus * b c uminus * + assign 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 7 - - -

编译原理作业集－第七章 语义分析和中间代码产生

3. 翻译算术表达式a*- (b+c)为

a)：一棵语法树 b)：后缀式 c)：三地址代码 3. 答案：（1）

（2） 后缀式： a b c + uminus * （3） 三地址代码序列为：

t1:= b + c t2 := - t1 t3 := a* t2

4. 翻译算术表达式 –(a+b)*(c+d) +(a+b+c) 为

a)：四元式 b)：三元式 c)：间接三元式 4. 答案：（1）四元式序列为：

op arg1 arg2 result (1) + a b t1 (2) + c d t2 (3) * t1 t2 t3 (4) uminus t3 t4 (5) + a b t5 (6) + t5 c t6 (7) + t4 t6 t7 （2）三元式序列为： op arg1 arg2 (1) + a b (2) + c d (3) * (1) (2) (4) uminus (3) (5) + a b 西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 8 - - -

编译原理作业集－第七章 语义分析和中间代码产生

(6) + (5) c (7) + (4) (6) （3）间接三元式表示：

statement op arg1 arg2 (1) (11) (11) + a b (2) (12) (12) + c d (3) (13) (13) * (11) (12) (4) (14) (14) uminus 13 (5) (11) (15) + (11) c (6) (15) (16) + (14) (15) (7) (16)

5. 已知数组翻译模式如下： (1) S  L := E

{ if L.offset = null then // 简单变量 emit(L.place „:=‟ E.place) else //数组元素

emit(L.place „[‟ L.offset „]‟ „:=‟ E.place) } (2) E  E1 + E2

{ E.place := newtemp;

emit(E.place „:=‟ E1.place „+‟ E2.place) } (4) E  L

{ if L.offset = null then E.place := L.place else begin

E.place := newtemp;

emit(E.place „:=‟ L.place„[‟ L.offset „]‟) end }

(5) L  Elist ]

{ L.place := newtemp;

emit(L.place „:=‟ Elist.array „-‟, ck); L.offset := newtemp;

emit(L.offset „:=‟ w „*‟ Elist.place) } (6) L  id

{ L.place := id.place; L.offset := null }

(7) Elist  Elist1, E

{ t := newtemp;

m:= Elist1.ndim + 1;

emit(t „:=‟ Elist1.ndim „*‟

limit(Elist1.array, m)); emit(t „:=‟ t „+‟ E.place); Elist.array := Elist1.array; Elist.place := t;

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 9 - - -

编译原理作业集－第七章 语义分析和中间代码产生

Elist.ndim := m }

(8) Elist  id [ E

{ Elist.place := E.place; E.ndim := 1;

Elist.array := id.place }

利用该翻译模式对下面赋值语句：A[i,j] :=B[i,j] + C[A[k,l]] + D[i+j]。 （1）画出并注释语法分析树； （2）翻译成三地址代码；

5. 答案：对于C语言的数组，每维的下界约定为0。例如，对A[10,20]来说，A[0,0]是第一元素，A[i,j]的相对地址为：base + ( i * n2 + j ) * w 三地址序列如下：

t11 := i * 20 t12 := t11+j t13 := A-84; t14 := 4*t12

t15 := t13[t14] //A[i,j] t21 := i*20 t22 := t21+j t23 := B-84; t24 := 4*t22

t25 := t23[t24] //B[i,j] t31 := k*20 t32 := t31+l t33 := A-84 t34 := 4*t32

t35 := t33[t34] //A[k,l] t36 := 4*t35 t37 := C-4

t38 := t37[t36] //C[A[k,l]] t41 := i+j t42 := 4*t41 t43 := D-4

t44 := t43[t42] //D[i+j] t1 := t25 +t38 t2 := t1 + t44 t23[t24] := t2

注：A,B,C,D分别表示数组A,B,C,D的基地址。

6. 试把下列C语言程序的可执行语句

main(){ int i; int a[10];

while (i<=10) a[i]=0;

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 10 - - -

编译原理作业集－第七章 语义分析和中间代码产生

}

翻译为：(1)一棵语法树， (2)后缀式， (3)三地址代码。

6.答案：（1）

（2） 后缀式为： i 10 <= a i [] 0 = while

从理论上可以说 while ( i <= 10 ) a[i] = 0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为：

i 10 <= <下一个语句开始地址> BM a i [] 0 = <本语句始址>BRL

其中BM操作为当表达式为假时转向<下一个语句开始地址>，BRL是一个一目运算，无条件转向<本语句始址>。 （3） 三地址代码序列为： 100 if i <= 10 goto 102 101 goto 106 102 t1 := 4 * i 103 t2 := a 104 t2[t1] := 0 105 goto 100 106

7. 已知布尔表达式翻译成三地址代码的翻译模式如下： E→E1 or E2 { E.place:=newtemp; emit(E.place ':=' E1.place 'or' E2.place) } E→E1 and E2 { E.place:=newtemp; emit(E.place ':=' E1.place 'and' E2.place) } E→not E1 { E.place:=newtemp; emit(E.place ':=' 'not' E1.place) } E→(E1) { E.place:= E1.place } E→id1 relop id2 { E.place:=newtemp; emit('if' id1.place relop.op id2.place 'goto' nextstat+3); emit(E.place ':=' '0'); emit('goto' nextstat+2); emit(E.place ':=' '1') } E→id1 { E.place:=id.place }

试编写一个递归下降程序，用来该属性文法。

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 11 - - -

编译原理作业集－第七章 语义分析和中间代码产生

7. 答案：

首先消除该翻译模式的左递归：

（注：'{','}'为元语言符号。） 递归预测翻译程序如下：

TYPE link = 表类型; PROCEDURE E ; VAR E.truelist, E.falselist, T.truelist, T.falselist: link; BEGIN { E.truelist, E,falselist } := T; WHILE ( lookahead == 'or ' ) DO BEGIN match(or); M.quad := nextquad; { T.truelist, T.falselist } := T; backpatch(E.falselist, M.quad); E.truelist := merge(E.truelist, T.truelist); E.falselsit := T.falselist END; return({E.truelist, E.falselist}) END;

PROCEDURE T; VAR T.truelist, T.falselist, F.truelsit, F.falselist: link;

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 12 - - -

编译原理作业集－第七章 语义分析和中间代码产生

BEGIN { T.truelist, T,falselist } := F; WHILE ( lookahead == 'and ' ) DO BEGIN match(and); M.quad := nextquad; { F.truelist, F.falselist } := F; backpatch(T.truelist, F.truelist); T.truelist := F.truelist; T.falselist := merge(T.falselist, F.falselist) END; return({T.truelist, T.falselist}) END;

PROCEDURE F; VAR F.truelist, F.falselist, E.truelsit, E.falselist: link; BEGIN CASE ( lookahead ) OF 'not' :BEGIN match(not); { E.truelist, E.falselist } := F; F.truelist := E.falselist; F.falselist := E.truelist END; '( ' : BEGIN match((); { E.truelist, E.falselist ) := E; match()); F.truelist := E.truelist; F.falselist := E.falselist END; 'id' : BEGIN match(id); match(relop); match(id); F.truelist := makelist(nextquad); F.falselist := makelist(nextquad+1); emit('if' id1.place relop id２.place 'goto-'); emit('goto-') END； 'true': BEGIN match(true); F.truelist := makelist(nextquad);

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 13 - - -

编译原理作业集－第七章 语义分析和中间代码产生

F.falselist := null; emit('goto-') END; 'false':BEGIN match(false); F.truelist := makelist(nextquad); F.falselist := null; emit('goto-') END otherwise : error END of CASE return({F.truelist, F.falselist}) END;

8. 试编写翻译模式，用来实现do-while语句的回填算法。 8.答案：

do-while语句的三地址代码结构如下：

从do-while语句的三地址代码结构可以知道，开始，要记录下L.code的开始地址，以填写E.truelist。 生成E.code之前，要记录下E.code的开始地址，用它填写L.nextlist。为此，在规则相应处添加标记非终结符，以完成相应的语义动作。翻译模式如下：

9. Pascal语言中，语句

for v：＝initial to final do stmt

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 14 - - -

编译原理作业集－第七章 语义分析和中间代码产生

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

begin t1:=initial; t2:=final; if t1<=t2 then begin v:=t1; stmt while v<>t2 do begin v：=succ（v)； stmt end end 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为目标机器允许的最大整数。

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

（1）显示如下六个整数： MAXINT -5 MAXINT -4 MAXINT -3 MAXINT -2 MAXINT -1 MAXINT

（2）为简单起见，for语句的三地址代码如下：

t1 := initial t2 := final

if t1 > t2 goto S.next v := t1 stmt.code S.begin:

if v > t2 goto S.next v := succ(v) stmt.code goto S.begin

语法制导定义如下：

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 15 - - -

编译原理作业集－第七章 语义分析和中间代码产生

产生式 动作 S→for E do S1 S.begin := newlabel S.first := newtemp S.last := newtemp S.curr:= newtemp S.code:=gen(S.first “:=” E.init) ||gen(S.last “:=” E.final) ||gen(“if” S.first “>” S.last “goto” S.next) ||gen(S.curr “:=” S.first) ||gen(S.begin “:” ) ||gen(“if ” S.curr “>” S.Last “goto” S.next) ||S1.code ||gen(S.curr := succ(S.curr)) ||gen(“goto” S.begin) E→v:=initial to final E.init := initial.place E.final := final.place

10. 假如有下面的Pascal说明

TYPE atype=ARRAY [0..9,-10..10] OF integer; cell=RECORD a,b:integer END;

pcell=↑cell;

foo=ARRAY [1..100] OF cell;

FUNCTION bar(r:integer;y:cell):pcell; BEGIN……END;

写出atype,cell,pcell,foo和bar的类型表达式。

10.答案：

atype: ARRAY(0..9, ARRAY(-10..10, integer)); cell: RECORD((a× integer)× (b×integer)); pcell: POINTER(cell);

或: POINTER(RECORD((a ×integer)× (b× integer))); foo: ARRAY(1..100, cell);

或 : ARRAY(1..100, RECORD((a ×integer)× (b× integer))); bar: integer× cell→pcell;

或 : integer× cell→POINTER(RECORD((a×integer) ×(b×integer)));

11. 已知语句序列的类型检查翻译方案：

S→id:=E { if id.type=E.type then S.type:=void else S.type:=type_error } S→if E then S1 { if E.type=boolean

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 16 - - -

编译原理作业集－第七章 语义分析和中间代码产生

then S.type:=S1.type else S.type:=type_error } S→while E do S1 { if E.type=boolean then S.type:=S1.type else S.type:=type_error } S→S1:S2 { if S1.type=void and S2.type=void then S.type:=void else S.type:=type_error } 修改该翻译方案，使之能够处理：

（1）语句有值。赋值语句的值是赋值号右边的表达式的值。条件语句或当语句的值是语句体的值，语句表的值是表中最后一个语句的值。

（2）布尔表达式。加上逻辑算符and,or和not,还有关系算符的产生式，然后给出适当的翻译规则，计算出这些表达式的类型。 11. 答案：(1)

S -> id:=E { S.type:= IF id.type=E.type THEN E.type ELSE type_error; S.val:= IF id.type=E.type THEN E.val ELSE val_error } S -> IF E THEN S1 {S.type:= IF E.type=boolean THEN S1.type ELSE type_error S.val:= IF E.type=boolean THEN S1.val ELSE val_error}

S -> WHILE E DO S1 {S.type:= IF E.type=boolean THEN S1.type ELSE type_error S.val:= IF E.type=boolean THEN S1.val ELSE val_error} S -> S1;S2 {S.type:=S2.type; S.val:=S2.val} (2)

E -> E1 AND E2 {E.type:= IF(E1.type=boolean)AND(E2.type=boolean) THEN boolean ELSE type_error}

E -> E1 OR E2 {E.type:= IF(E1.type=boolean)AND(E2.type=boolean) THEN boolean ELSE type_error} E -> NOT E1 {E.type:= IF(E1.type=boolean) THEN boolean ELSE type_error}

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18

- 17 - - -

编译原理作业集－第七章 语义分析和中间代码产生

E -> E1 op E2 {E.type:= IF(E1.type=E2.type) THEN boolean ELSE type_error} 注：op为关系运算符，包括 =, <>, <, >, <=, >=

12. 文法G[P]及其产生式如下：

P→D;E

D→D;D|id:T

T→list of T|char|integer E→(L)|Literal|num|id L→E,L|E

这个文法产生由字面常量组成的表。符号的解释和文法（7.11)相同，增加类型List，它表示类型为T的元素构成的表。写一个翻译模式，以确定表达式（E）和表（L）的类型（注：表中每个元素的类型是一样的）。

12.答案：

D -> id:T {addtype(id.entry,T.type))} T -> char {T.type:=char} T -> integer {T.type:=integer}

T -> list of T1 {T.type:=list(T1.type)} E -> num {E.type:=integer} E -> id {E.type:=lookup(id.entry)} E -> Literal {E.type:=char} E -> (L) {E.type:=list(L.type)}

L -> E,L1 {L.type:=IF (E.type=L1.type) THEN E.type ELSE type_error} L -> E {L.type:=E.type}

西安理工大学计算机科学与工程学院，张发存编写 2013-5-20，9:37:18 - 18 - - -