编译原理必过宝典(3)

while i≤20 do begin

prod:=prod+a[i]*b[i]; i:=i+1

end;、 (数组翻译3句

T1:= VARPART(与数组元素占的字节数相关比如4*i)

T2:=不变部分，一般为起始地址A或者起始地址A减单个数组元素所占字节数比如A-4（如果i从1开始，而且上面写为4*i,这里则需要写成A-4） T3:=T2[T1]

试按语法制导翻译法将源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。 四元式序列100 prod:=0 101 i:=1

102 if i≤20 goto 104 103 goto 114 104 T1:=4*i 105 T2:=A-4 106 T3:=T2[T1] 107 T4:=4*i 108 T5:=B-4 109 T6:=T5[T4] 110 T7:=T3*T6 111 prod:=prod+T7 112 i:=i+1 113 goto 102 114 ...

for I := 1 step 1 until Y do X := X+1

将被翻译成如下的四元式序列(对照P191)：

100 I := 1

101 goto _103_ 102 I := I + 1

103 if I ≤ Y goto _105_ 104 goto _108_ 105 T := X + 1 106 X := T 107 goto _102_ 108 ……

第十章：1. 程序的传值、传地址的结果

2. 活动记录（1）静态链、动态链的连接（2）Display表 典型例题：1. 当参数分别采用“传值”、“传地址”实现时，下面程序 输出a的值分别是什么？（5分） Program main(input,output) Procedure p(x,y,z); Begin y:=y+2; z:=z+x; End ; Begin

a:=2; b:=6; p(a+b, a, a); Print a; End. 答：2 12

2. 类PASCAL程序结构（嵌套过程）如下，该语言的编译程序采用栈式动态分

配策略管理目标程序存储空间。若过程调用情况为Demo->A->B->B,画出程序运行到第二个B过程的时刻，栈内静态链、动态链的指示情况。 Program Demo; Procedure A Procedure B Begin(*B*) … …

If d then B else A; End(*B*) Begin(*A*) B;

End(*A*) Begin(*Demo*) A

End(*Demo *)

动态链 静态链 B的过程活动记录

动态链 静态链 B的过程活动记录

动态链 静态链 A的过程活动记录

动态链 DEMO的过程活动记录

静态链

动态链 静态链 B的过程活动记录

动态链 静态链 B的过程活动记录

动态链 静态链 A的过程活动记录

动态链 静态链 DEMO的过程活动记录

练习1：考虑下面的程序：

…

procedure p(x, y, z)； begin y:=x+y; z:=z*z; end begin

A:=2; B:=A*2; P(A, A, B); Print A, B end.

试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么? 解：传地址 A=6, B=16

传值 A=2, B=4

第十一章 重点：1、基本块划分，并画出程序流程图 2.根据程序流程图，找出循环！ 典型习题：（8分）将下面程序划分为基本块，并画出其基本块程序流图。(2009年出过) (1) if a

(3) if c

答:

2. 对以下给定流图， （2010年出过）

（1）求出流图中B3、B4和B5的必经结点集D(n)； （2）求出流图中的回边及其对应的循环。

B1 B2 B3 B4 B5 答：（1）B3的必经结点集是{B1, B2 , B3}。

B4的必经结点集是{B1, B2, B4}。 B5的必经结点集是{B1, B2, B4, B5}。

（2）回边是B4－＞B2，对应的循环是{ B2, B3, B4}。

其它的

第二章、第九章、第十二章均直接考PL/0的内容，所以代码阅读很重要 重点：1. PL/0符号表的生成

2. PL/0某一个语法成分的程序填空。

典型习题：练习1：8分）对PL/0语言扩充单词: （2009年出过） ++ +=

请完成下列识别单词‘+’，‘++’和‘+=’（设单词内码分别为PLUS，PLUSPLUS和PLUSBECOMES）的词法分析程序段：

if ( CH=='+' ) {

① if ( ② ) {

SYM=PLUSBECOMES; GetCh(); } else if ( CH=='+' ) {

③ } else {

④ }

}

答：GetCh(); CH=='=' SYM=PLUSPLUS; GetCh(); SYM=PLUS; 2. PL/0示意程序为： var x;

procedure A; var d;

begin (* A *)

write(x); end (* A *); procedure B; const n=7; var e,g; procedure D; var j,k;

begin (* D *) read(j,k); x:=x+j*n; call A; end ;(* D *) begin (* B *) call D; end ;(* B *) begin (* main *) read(x); call B; end. (* main *)

给出PL/0示意程序编译到D过程体时TABLE表的内容。其中TABLE表的格式可为下表。 TABLE表的格式 name kind level val adr size 解：问答第5题PL/0示意程序编译到D过程体时TABLE表的内容如下表。 TABLE表的内容 name main x A B n e g D j k kind procedure variable procedure procedure constant variable variable procedure variable variable level . 0 0 0 . 1 1 1 2 2 val . . . . 7 adr 0 dx 过程A的入口 过程B的入口 （待填） . dx dx+1 过程D的入口 dx dx+1 size 4 . 4 （待填5） . . . 5 由于A和B是并列过程，当编译到B过程时A过程体已经编译结束，A所定义的标识符不会再被使用，所以由B过程定义的标识符覆盖。