编译原理作业集

1、第七章 语义分析和中间代码产生本章要点1. 中间语言，各种常见中间语言形式；2. 说明语句、赋值语句、布尔表达式、控制语句等的翻译；3. 过程调用的处理；4. 类型检查；本章目标掌握和理解中间语言，各种常见中间语言形式；各种语句到中间语言的翻译；以及类型检查等内容。本章重点1中间代码的几种形式，它们之间的相互转换：四元式、三元式、逆波兰表示；3赋值语句、算术表达式、布尔表达式的翻译及其中间代码格式；4各种控制流语句的翻译及其中间代码格式；5过程调用的中间代码格式；6类型检查；本章难点1. 各种语句的翻译； 2. 类型系统和类型检查；作业题一、单项选择题：1. 布尔表达式计算时可以采用某种优化措

2、施，比如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. 使用三元式是为了_：a. 便于代码优化处理 b. 避免把临时变量填入符号表c. 节省存储代码的空间 d. 提高访问代码的速度4. 表达式-a+b*(-c+d)的逆波兰式是_。a. ab+-cd+-*；b.

3、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. (relo

4、p，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. c

5、har×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. 过

6、程调用语句；b. 标号说明语句；c. 数组说明语句；d.记录说明语句；14. 函数function f(a,b:char):integer;所以f函数的类型表达式为：a. char×charpointer(integer)； b. char×charpointer；c. char×charinteger； d. char×charinteger (pointer)15. 如果一个语言的编译器能保证编译通过的程序，在运行时不会出现类型错误，则称该语言是 。a. 静态的；b. 强类型的；c. 动态的；d. 良类型的；一答案：1. b；2. d；3. b；4.

7、 d；5. c；6. c.；7. a；8. a；9. c；10. d；11. b；12. a；13. d；14. a；15. b；二、填空题：1. 语法分析是依据语言的语法规则进行的，中间代码产生是依据语言的_规则进行的。2. 多目运算x:=yi的三元式表示为两部分：_和_。3. 生成三地址代码时，临时变量的名字对应抽象语法树的_。4. 一个类型表达式或者是基本类型，或者由_施加于其它类型表达式组成。5. 在程序设计语言中，布尔表达式有两个基本的作用：一个是 ；另一个是 。6. 允许嵌套过程的语言，其过程说明语句的翻译用两个栈tblptr和offset分别保存尚未处理完的过程的 和它们的off

8、set，这两个栈顶的元素分别是正在处理的过程的的符号表指针和 。7. 在一些pascal的实现中，如果说明中出现了没有名字的类型表达式，编译器这样处理：建立一个 来和每个声明的变量标识符相联系。8. 赋值语句a:=b*-c+b*-c的后缀式为 。9. 多目运算Xi:=y的三元式表示为两部分：_和_。10. 编译器遇到常量说明时，要把常量值登录入 并回送序号；在 中为等号左边的标识符建立新条目，在该条目中填入常量标志、相应类型和常量表序号。11. 典型的转移条件语句：if E then S1 else S2中，作为转移条件的布尔表达式E，赋予它两种“出口”：一是 ；二是 。12. 类型表达式或者

9、是 ，或者是 作用在其它类型表达式上得到的新的类型表达式。13. pascal变量说明：var A:array1.10 of integer与A相关的类型表达式为： 。14. 若T是类型 表达式，则pointer(T)是类型表达式，它表示 类型 。15. 通过一遍扫描来产生布尔表达式和控制流语句的代码存在一个问题，就是当生成某些转移语句时可能还不知道该语句将要转移到的语句的地址是什么。采用 的办法来解决这个问题。二1. 语义；2. (0): ( =, y, i )，(1): ( assign, x, (0) )；3. 内部结点；4. 类型构造符；5. 计算逻辑值；作控制流语句中的条件表达式；6

10、. 符号表指针，相对地址；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. 中间代码是独立于机器的，复杂性介于源语言和机器语言之间，便于进行与机器无关调换代码优化工作。（ ）2. 在程序设计语言中，一般来说，布尔表达式仅仅用于条件、循环等控制流语句中

11、的条件表达式计算。（ ）3. “回填”技术用于对过程中的说明语句进行处理时把计算出的有关符号的属性填入符号表。 ( )4. 如果E是一个常量或变量，则E的逆波兰式是E自身。( )5. 对于任何一个编译程序来说，中间代码的产生是不一定必要的。（ ）6. 由于三元式中的三个域中，仅有两个域与地址有关，所以，三元式不是严格意义上的三地址代码。（ ）7. 两个类型表达式要么是同样的基本类型，要么是同样的类型构造符作用于结构等价的类型，我们就说，这两个类型系统等价。（ ）8. 对于Pascal这样允许嵌套过程的语言，每当遇到过程说明D®proc id ; D1; S时，便创建一张新的符号表，也

12、就是说，让每个过程说明都有自己一张独立的符号表。（ ）9. 记录类型的各个域变量分配存储区域的地址的确定是相对于为记录类型变量所分配存储区域的首地址的，所以记录类型不应该建立自己的符号表。（ ）10. 类型表达式中不可出现类型变量，即类型变量值不是类型表达式。（ ）11. 所谓类型系统就是把类型表达式赋给语言各相关结构成分的规则的集合。同一种语言（比如C+语言）的编译程序，在不同的实现系统里（比如微软的Visual C+和Linux下的开源编译器TCC），可能使用不同的类型系统。12. 四元式表示的是四地址代码，三元式表示的是三地址代码。（ ）13. 生成三地址代码时，临时变量的名字对应抽象语

13、法树的内部结点。（ ）14. 后缀式是抽象语法树的线性表示形式，后缀式是树结点的一个序列，其中每个结点 都是在所有子结点之后立即出现的。（ ）15. 后缀表示形式只是用于表达式的，其他的语法结构比如条件语句、循环语句等不能使用后缀式。（ ）三答案：1. Ö；2. ×；3. ×；4. Ö；5. Ö；6. ×；7. Ö；8. Ö；9. ×；10. ×；11. Ö；12. ×；13. Ö；14. Ö；15. ×；四、名词解释：1. 三地址代码；2. 回

14、填；3. 类型表达式；4. 类型系统；5. 静态语义检查四答案：1. 三地址代码是由下面一般形式的语句构成的序列：x:= y op z。其中x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号如定点运算符、浮点运算符、逻辑运算符等等，每个语句的右边只能有一个运算符。2. 通过一遍扫描来产生布尔表达式和控制流语句的代码的主要问题在于，当生成某些转移语句时我们可能还不知道该语句将要转移到的标号是什么。为了解决这个问题，可以在生成形成分支的跳转指令时，暂时不确定跳转目标，而建立一个链表，把转向这个目标的跳转指令的标号键入这个链表，一旦目标确定之后再把它填入有关的跳转指令中。这种技术称为回填

15、。3. 一个类型表达式或者是基本类型，或者由类型构造符施于其他类型表达式组成。基本类型和类型构造符都因具体语言的不同而不同。. 一个基本类型是一个类型表达式。. 类型名是一个类型表达式. 类型构造符作用于类型表达式，其结果仍然是类型表达式. 类型表达式中可出现类型变量，即变量值是类型表达式。4. 所谓类型系统就是把类型表达式赋给语言各相关成分的规则的集合。同一种语言的编译程序，在不同的实现系统里，可能使用不同的类型系统。5. 静态语义检查就是编译过程中进行的语义检查。主要工作有：类型检查、控制流检查、一致性检查、相关名字检查，还有名字的作用域分析等。五、简答题：1. 四元式和三元式有什么不同？

16、2. 为什么要使用中间代码的表示形式？3. 现在有四种程序设计语言：PASCAL、FORTRAN、C和BASIC。要求在A、B、C和D四种机器上都能编译这四种语言，而编译程序需要在中间语言级别上进行优化处理。问：需要编制多少个编译程序的前后端接口？4. 为什么三元式没有存放计算结果的单元？5. 过程调用语句在翻译的时候，如何处理参数传递的问题（只考虑传递实在参数地址的情况）？P200.五答案： 1. 一个四元式是一个带有四个域的记录结构，分别为op，arg1，arg2，result。四元式之间的联系是通过临时变量来实现的，更改一个四元式表很容易，因此对中间代码进行优化处理时比较方便。一个三元式

17、是一个带有三个域的记录结构，分别为op，arg1，arg2。三元式之间的联系是通过指针来实现的，更改一个三元式表没有四元式表那样容易，但是，对中间代码进行优化处理时，四元式和间接三元式同样方便。2. 使用中间代码有如下好处：（1）中间形式与具体机器无关，把与机器特性紧密相关的内容尽可能放到后端，有利于目标重定位，一种中间形式可以为生成多种不同型号目标机上的目标代码服务。（2）可以对中间代码进行与机器无关的优化，有利于提高目标代码的质量。（3）使各阶段的开发复杂性降低，有利于编译程序的开发。3. 由于各种不同的程序设计语言都有很多不同的特点，所以，若有m种不同的程序设计语言，就会有m个前端。这时

18、，如果有n种不同的机器，也就会有n个后端。从理论上讲，如果要移植一个现有的编译程序到另外一台新机器上，只需要重新编写它的后端即可。现在有四种程序设计语言：PASCAL、FORTRAN、C和BASIC，那么可以得到四个前端：有A、B、C和D四种机器，要求在每种机器上都能编译上述四种语言，只需要根据四种不同机器的特点为每种语言构造四个后端就行了。所以要在A、B、C和D四种机器上都能编译上述四种语言，总共需要编制16个前后端的接口即可。4. 由于中间语言（包括三元式）是用来辅助生成目标代码的，并不会真正进行计算，也就不需要一个临时单元存放结果，那么在编制后面的三元式时如果要用到这些运算结果，可以用这

19、些三元式的编号来代替。六、应用题：1. 已知产生布尔表达式的语法定义如下： EE1 or E2EE1 and E2Enot E1 E(E1)Eid1 relop id2Eid1a写出翻译模式；b画出语法树（语义动作也表示在其中）；c通过对语法树的遍历，写出对布尔表达式a<b or c<d and e<f 生成的三地址代码。1. 答案：见教材P187，图7.14。EE1 or E2E.place:=newtemp;emit(E.place ':=' E1.place 'or' E2.place)EE1 and E2E.place:=newtemp

20、;emit(E.place ':=' E1.place 'and' E2.place)Enot E1 E.place:=newtemp;emit(E.place ':=' 'not' E1.place)E(E1)E.place:= E1.placeEid1 relop id2E.place:=newtemp;emit('if' id1.place relop.op id2.place 'goto' nextstat+3);emit(E.place ':=' '0');

21、emit('goto' nextstat+2);emit(E.place ':=' '1')Eid1E.place:=id.place100: if a<b goto 103101: T1:=0102: goto 104103: T1:=1104: if c<d goto 107105: T2:=0106: goto 108107: T2:=1108: if e<f goto 111109: T3:=0110: goto 112111: T3:=1112: T4:=T2 and T3113: T5:=T1 or T42. 画出赋

22、值语句a:=b*-c+b*-c的抽象语法树和DAG图，并写出它的后缀式表示法。2. 答案：见教材P168，图7.3。后缀式表示法：a b c uminus * b c uminus * + assign3. 翻译算术表达式a*- (b+c)为a)：一棵语法树b)：后缀式c)：三地址代码3. 答案：（1）（2） 后缀式： a b c + uminus * （3） 三地址代码序列为：t1:= b + c t2 := - t1t3 := a* t24. 翻译算术表达式 (a+b)*(c+d) +(a+b+c) 为a)：四元式b)：三元式c)：间接三元式4. 答案：（1）四元式序列为：op arg1

23、arg2 result (1)+abt1(2)+cd  t2(3)*t1t2t3(4)uminust3t4(5)+abt5(6)+t5ct6(7)+t4t6t7（2）三元式序列为： op arg1 arg2 (1)+ab(2)+cd(3)*(1)(2)(4)uminus(3)(5)+ab(6)+(5)c(7)+(4)(6)（3）间接三元式表示： statement op arg1 arg2 (1)(11)(11)+ab(2)(12)(12)+cd(3)(13)(13)*(11)(12)(4)(14)(14)uminus13(5)(11)(15)+(11)c(6)(15)(16)+(1

24、4)(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.pla

25、ce := 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;

26、emit(t := Elist1.ndim * limit(Elist1.array, m); emit(t := t + E.place); Elist.array := Elist1.array; Elist.place := t; Elist.ndim := m (8) Elist ® id E Elist.place := E.place; E.ndim := 1; Elist.array := id.place 利用该翻译模式对下面赋值语句：Ai,j :=Bi,j + CAk,l + Di+j。（1）画出并注释语法分析树；（2）翻译成三地址代码；5. 答案：对于C语言的数组

27、，每维的下界约定为0。例如，对A10,20来说，A0,0是第一元素，Ai,j的相对地址为：base + ( i * n2 + j ) * w三地址序列如下：t11 := i * 20 t12 := t11+jt13 := A-84;t14 := 4*t12t15 := t13t14 /Ai,jt21 := i*20t22 := t21+jt23 := B-84;t24 := 4*t22t25 := t23t24 /Bi,jt31 := k*20t32 := t31+lt33 := A-84t34 := 4*t32t35 := t33t34 /Ak,lt36 := 4*t35t37 := C-4

28、t38 := t37t36 /CAk,lt41 := i+jt42 := 4*t41t43 := D-4t44 := t43t42 /Di+jt1 := t25 +t38t2 := t1 + t44t23t24 := t2注：A,B,C,D分别表示数组A,B,C,D的基地址。6. 试把下列C语言程序的可执行语句 main() int i; int a10; while (i<=10) ai=0;翻译为：(1)一棵语法树， (2)后缀式， (3)三地址代码。6.答案：（1）（2） 后缀式为： i 10 <= a i 0 = while 从理论上可以说 while ( i <=

29、10 ) ai = 0; 的后缀式如上面表示。但若这样表示，在执行while操作时，赋值语句已经执行，这显然与语义不符，因此改为： i 10 <= <下一个语句开始地址> BM a i 0 = <本语句始址>BRL 其中BM操作为当表达式为假时转向<下一个语句开始地址>，BRL是一个一目运算，无条件转向<本语句始址>。 （3） 三地址代码序列为：100 if i <= 10 goto 102101 goto 106102 t1 := 4 * i103 t2 := a104 t2t1 := 0105 goto 1001067. 已知布尔

30、表达式翻译成三地址代码的翻译模式如下：EE1 or E2 E.place:=newtemp; emit(E.place ':=' E1.place 'or' E2.place) EE1 and E2 E.place:=newtemp; emit(E.place ':=' E1.place 'and' E2.place) Enot E1 E.place:=newtemp; emit(E.place ':=' 'not' E1.place) E(E1) E.place:= E1.place Eid1 r

31、elop 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') Eid1 E.place:=id.place 试编写一个递归下降程序，用来该属性文法。7. 答案：首先消除该翻译模式的左递归：（注：'',''

32、;为元语言符号。）递归预测翻译程序如下：TYPElink = 表类型;PROCEDURE E ;VARE.truelist, E.falselist, T.truelist, T.falselist: link;BEGIN E.truelist, E,falselist := T;WHILE ( lookahead = 'or ' ) DOBEGINmatch(or);M.quad := nextquad; T.truelist, T.falselist := T;backpatch(E.falselist, M.quad);E.truelist := merge(E.true

33、list, T.truelist);E.falselsit := T.falselistEND;return(E.truelist, E.falselist)END;PROCEDURE T;VART.truelist, T.falselist, F.truelsit, F.falselist: link;BEGIN T.truelist, T,falselist := F;WHILE ( lookahead = 'and ' ) DOBEGINmatch(and);M.quad := nextquad; F.truelist, F.falselist := F;backpatc

34、h(T.truelist, F.truelist);T.truelist := F.truelist;T.falselist := merge(T.falselist, F.falselist)END;return(T.truelist, T.falselist)END;PROCEDURE F;VARF.truelist, F.falselist, E.truelsit, E.falselist: link;BEGINCASE ( lookahead ) OF'not' :BEGINmatch(not); E.truelist, E.falselist := F;F.truel

35、ist := E.falselist;F.falselist := E.truelistEND;'( ' : BEGINmatch(); E.truelist, E.falselist ) := E;match();F.truelist := E.truelist;F.falselist := E.falselistEND;'id' : BEGINmatch(id);match(relop);match(id);F.truelist := makelist(nextquad);F.falselist := makelist(nextquad+1);emit(&#

36、39;if' id1.place relop id.place 'goto-');emit('goto-')END；'true': BEGINmatch(true);F.truelist := makelist(nextquad);F.falselist := null;emit('goto-')END;'false':BEGINmatch(false);F.truelist := makelist(nextquad);F.falselist := null;emit('goto-')END

37、otherwise : errorEND of CASEreturn(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 st

38、mt与下列代码序列有相同含义begint1:=initial; t2:=final;if t1<=t2 then beginv:=t1;stmtwhile v<>t2 do beginv：=succ（v)；stmtendendend(1)试考虑下述Pascal程序program forloop(input, output);var i,initial,final: integer;beginread(initial, final);for i:= initial to final dowrite(i)end对于initial=MAXINT-5和final= MAXINT，问此

39、程序将做些什么？其中MAXINT为目标机器允许的最大整数。(2)试构造一个翻译pascal的for语句为三地址代码的语法制导定义。9. （1）显示如下六个整数：MAXINT -5MAXINT -4MAXINT -3MAXINT -2MAXINT -1MAXINT（2）为简单起见，for语句的三地址代码如下：t1 := initialt2 := finalif t1 > t2 goto S.nextv := t1stmt.codeS.begin: if v > t2 goto S.nextv := succ(v)stmt.codegoto S.begin语法制导定义如下：产生式动作S

40、for E do S1S.begin := newlabelS.first := newtempS.last := newtempS.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

41、 := succ(S.curr) |gen(“goto” S.begin)Ev:=initial to finalE.init := initial.placeE.final := final.place10. 假如有下面的Pascal说明 TYPE atype=ARRAY 0.9,-10.10 OF integer;cell=RECORDa,b:integerEND;pcell=cell;foo=ARRAY 1.100 OF cell;FUNCTION bar(r:integer;y:cell):pcell;BEGINEND;写出atype,cell,pcell,foo和bar的类型表达式。

42、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× cellpcell;或

43、: integer× cellPOINTER(RECORD(a×integer) ×(b×integer);11. 已知语句序列的类型检查翻译方案：Sid:=Eif id.type=E.typethen S.type:=voidelse S.type:=type_errorSif E then S1if E.type=booleanthen S.type:=S1.typeelse S.type:=type_errorSwhile E do S1if E.type=booleanthen S.type:=S1.typeelse S.type:=type_errorSS1:S2if S1.type=void and S2.type=voidthen S.type:=voidelse S.type:=type_error修改该翻译方案，使之能够处理：（1）语句有值