第七章 语义分析和中间代码产生 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 静态检 查器

Presentation on theme: "第七章 语义分析和中间代码产生 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 静态检 查器"— Presentation transcript:

1 第七章 语义分析和中间代码产生 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 静态检 查器
第七章 语义分析和中间代码产生 静态语义检查 类型检查 控制流检查 一致性检查 相关名字检查 名字的作用域分析 语法分 析器 静态检 查器 中间代码 产生器 中间代码 优化器 国防科技大学计算机系602教研室

2 中间语言(复杂性界于源语言和目标语言之间)的好处：
便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确 Compiler Front End Compiler Back End 源语言 程序 中间语 言程序 目标语 言程序 国防科技大学计算机系602教研室

3 7.1 中间语言 常用的中间语言： 后缀式，逆波兰表示 图表示： DAG、抽象语法树 三地址代码 三元式 四元式 间接三元式
7.1 中间语言 常用的中间语言： 后缀式，逆波兰表示 图表示： DAG、抽象语法树 三地址代码 三元式 四元式 间接三元式 国防科技大学计算机系602教研室

4 7.1.1 后缀式 一个表达式E的后缀形式可以如下定义： 后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。
后缀式 后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1 E2 op，其中E1 和E2 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。 国防科技大学计算机系602教研室

5 逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。
后缀式的计算 用一个栈实现。 一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。 国防科技大学计算机系602教研室

6 把表达式翻译成后缀式的语义规则描述 产生式 E→E(1)op E(2) E→ (E(1)) E→id 语义动作
E.code:= E(1).code || E(2).code ||op E.code:= E(1).code E.code:=id E.code表示E后缀形式 op表示任意二元操作符 “||”表示后缀形式的连接。 国防科技大学计算机系602教研室

7 数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段
E→E(1)op E(2) E.code:= E(1).code || E(2).code ||op E→ (E(1)) E.code:= E(1).code E→id E.code:=id 数组POST存放后缀式：k为下标，初值为1 上述语义动作可实现为： 产生式 程序段 E→E(1)op E(2) {POST[k]:=op;k:=k+1} E→ (E(1)) {} E→i {POST[k]:=i;k:=k+1} 例：输入串a+b+c的分析和翻译 POST： a b + c + … 国防科技大学计算机系602教研室

8 图表示法 图表示法 DAG 抽象语法树 国防科技大学计算机系602教研室

9 7.1.2 图表示法 无循环有向图(Directed Acyclic Graph，简称DAG)
图表示法 无循环有向图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 国防科技大学计算机系602教研室

10 a:=b*(-c)+b*(-c)的图表示法
assign a + * b uminus c 抽象语法树 assign a + * b uminus c DAG 国防科技大学计算机系602教研室

11 assign a + * b uminus c 抽象语法树
抽象语法树对应的代码： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 国防科技大学计算机系602教研室

12 DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 抽象语法树对应的代码： assign a + * b
uminus c DAG DAG对应的代码： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5 国防科技大学计算机系602教研室

13 产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’,
产 生 式 语义规则 S→id:=E S.nptr:=mknode(‘assign’, mkleaf(id,id.place),E.nptr) E→E1+E2 E.nptr:=mknode(‘+’,E1.nptr,E2.nptr) E→E1*E2 E.nptr:=mknode(‘*’,E1.nptr,E2.nptr) E→-E E.nptr:=mknode(‘uminus’,E1.nptr) E→ (E1) E.nptr:=E1.nptr E→id E.nptr:=mkleaf(id,id.place) 国防科技大学计算机系602教研室

14 7.1.3 三地址代码 三地址代码 三地址代码可以看成是抽象语法树或DAG的一种线性表示 x:=y op z
三地址代码 三地址代码 x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示 国防科技大学计算机系602教研室

15 a:=b*(-c)+b*(-c)的图表示法
assign a + * b uminus c 抽象语法树 assign a + * b uminus c DAG 国防科技大学计算机系602教研室

16 T1:=-c T1:=-c T2:=b*T1 T2:=b*T1 T3:=-c T5:=T2+T2 T4:=b*T3 a:=T5
对于抽象语法树的代码 对于DAG的代码 国防科技大学计算机系602教研室

17 三地址语句的种类 x:=y op z x:=op y x:=y goto L if x relop y goto L或if a goto L
param x和call p,n，以及返回语句return y x:=y[i]及x[i]:=y的索引赋值 x:=&y, x:=*y和*x:=y的地址和指针赋值 国防科技大学计算机系602教研室

18 生成三地址代码时，临时变量的名字对应抽象语法树的内部结点 id:=E
对表达式E求值并置于变量T中值 id.place:=T 国防科技大学计算机系602教研室

19 非终结符号S有综合属性S.code，它代表赋值语句S的三地址代码。 非终结符号E有如下两个属性：
E.place表示存放E值的名字。 E.code表示对E求值的三地址语句序列。 函数newtemp的功能是，每次调用它时，将返回一个不同临时变量名字,如T1,T2,…。 国防科技大学计算机系602教研室

20 为赋值语句生成三地址代码的S-属性文法定义
产生式 语义规则 S→id:=E S.code:=E.code || gen(id.place ‘:=’ E.place) E→E1+E2 E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘+’ E2.place) E→E1*E2 E.place:=newtemp; gen(E.place ‘:=’ E1.place ‘*’ E2.place) E→-E1 E.place:=newtemp; E.code:=E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place) E→ (E1) E.place:=E1.place; E.code:=E1.code E→id E.place:=id.place; E.code=‘ ’ 国防科技大学计算机系602教研室

21 三地址语句 四元式 一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result
(0) uminus c T1 (1) * b T1 T2 (2) uminus c T3 (3) * b T3 T4 (4) + T2 T4 T5 (5) := T5 a 国防科技大学计算机系602教研室

22 三地址语句 三元式 通过计算临时变量值的语句的位置来引用这个临时变量 三个域：op、arg1和arg2 op arg1 arg2
(0) uminus c (1) * b (0) (2) uminus c (3) * b (2) (4) + (1) (3) (5) assign a (4) 国防科技大学计算机系602教研室

23 三地址语句 x[i]:=y op arg1 arg2 (0) [ ] = x i (1) y x:=y[i] op arg1 arg2
(1) assign x (0) 国防科技大学计算机系602教研室

24 三地址语句 间接三元式 为了便于优化，用 三元式表+间接码表 表示中间代码
间接码表:一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。 优点: 方便优化，节省空间 国防科技大学计算机系602教研室

25 例如，语句 X:=(A+B)*C; Y:=D↑(A+B) 的间接三元式表示如下表所示。 国防科技大学计算机系602教研室

26 7.2 说明语句 国防科技大学计算机系602教研室

27 7.3 赋值语句的翻译 简单算术表达式及赋值语句 国防科技大学计算机系602教研室

28 为赋值语句生成三地址代码的S-属性文法定义
产生式 语义规则 S→id:=E S.code:=E.code || gen(id.place ‘:=’ E.place) E→E1+E2 E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘+’ E2.place) E→E1*E2 E.place:=newtemp; gen(E.place ‘:=’ E1.place ‘*’ E2.place) E→-E1 E.place:=newtemp; E.code:=E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place) E→ (E1) E.place:=E1.place; E.code:=E1.code E→id E.place:=id.place; E.code=‘ ’ 国防科技大学计算机系602教研室

29 产生赋值语句三地址代码的翻译模式 S→id:=E { p:=lookup(id.name); if pnil then
S→id:=E S.code:=E.code || gen(id.place ‘:=’ E.place) E→E1+E2 E.place:=newtemp; E.code:=E1.code || E2.code ||gen(E.place ‘:=’ E1.place ‘+’ E2.place) E→E1*E2 E.place:=newtemp; E.code:=E1.code || E2.code || gen(E.place ‘:=’ E1.place ‘*’ E2.place) 产生赋值语句三地址代码的翻译模式 S→id:=E { p:=lookup(id.name); if pnil then emit(p ‘:=’ E.place) else error } E→E1+E2 { E.place:=newtemp; emit(E.place ‘:=’ E1.place ‘+’ E2.place)} E→E1*E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘*’ E 2.place)} 国防科技大学计算机系602教研室

30 产生赋值语句三地址代码的翻译模式 E→-E1 { E.place:=newtemp;
E.code:=E1.code || gen(E.place ‘:=’ ‘uminus’ E1.place) E→ (E1) E.place:=E1.place; E.code:=E1.code E→id E.place:=id.place; E.code=‘ ’ 产生赋值语句三地址代码的翻译模式 E→-E1 { E.place:=newtemp; emit(E.place‘:=’ ‘uminus’E 1.place)} E→(E1) { E.place:=E1.place} E→id { p:=lookup(id.name); if pnil then E.place:=p else error } 国防科技大学计算机系602教研室

31 数组元素的引用 数组元素地址的计算： 国防科技大学计算机系602教研室

32 设A为n维数组，每个元素宽度为w， lowi 为第i维 的下界，ni 是为第i维 可取值的个数, base为A的第一个元素相对地址
元素A[i1,i2,…,ik]相对地址公式 ((…i1 n2+i2)n3+i3)…)nk+ik)×w + base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w C= base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w 国防科技大学计算机系602教研室

33 id出现的地方也允许下面产生式中的L出现
L → id [ Elist ] | id Elist→Elist,E | E 为了便于处理，文法改写为 L→Elist ] | id Elist→Elist, E | id [ E 国防科技大学计算机系602教研室

34 引入下列语义变量或语义过程: Elist.ndim ：下标个数计数器
Elist.place ：表示临时变量，用来临时存放已形成的Elist中的下标表达式计算出来的值 limit(array，j) ：函数过程，它给出数组array的第j维的长度 国防科技大学计算机系602教研室

35 每个代表变量的非终结符L有两项语义值 L.place： 若L为简单变量i, 指变量i的符号表入口
若L为下标变量，指存放CONSPART的 临时变量的整数码 L.offset ： 若L为简单变量，null， 若L为下标变量，指存放VARPART的临时变量的整数码 国防科技大学计算机系602教研室

36 (1) S→L:=E (2) E→E+E (3) E→(E) (4) E→L (5) L→Elist ] (6) L→id
(7) Elist→ Elist, E (8) Elist→id [ E 国防科技大学计算机系602教研室

37 { if L.offset=null then /*L是简单变量*/ emit(L.place ‘:=’ E.place)
(1) S→L:=E { if L.offset=null then /*L是简单变量*/ emit(L.place ‘:=’ E.place) else emit( L.place ‘ [’ L.offset ‘]’ ‘:=’ E.place)} (2) E→E1 +E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘+’ E 2.place)} 国防科技大学计算机系602教研室

38 (3) E→(E1) {E.place:=E1.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 } 国防科技大学计算机系602教研室

39 { Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place }
A[i1,i2,…,ik] ((…i1 n2+i2)n3+i3)…)nk+ik)×w + base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w (8) Elist→id [ E { Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place } 国防科技大学计算机系602教研室

40 emit(t ‘:=’ Elist1.place ‘*’ limit(Elist1.array,m) );
A[ i1,i2,…,ik ] ( (…i1 n2+i2)n3+i3)…)nk+ik)×w + base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w (7) Elist→ Elist1, E { t:=newtemp; m:=Elist1.ndim+1; emit(t ‘:=’ Elist1.place ‘*’ limit(Elist1.array,m) ); emit(t ‘:=’ t ‘+’ E.place); Elist.array:= Elist1.array; Elist.place:=t; Elist.ndim:=m } 国防科技大学计算机系602教研室

41 emit(L.place ‘:=’ Elist.array ‘－’ C); L.offset:=newtemp;
A[i1,i2,…,ik] ((…i1 n2+i2)n3+i3)…)nk+ik) ×w + base-((…((low1 n2+low2)n3+low3)…)nk+lowk)×w (5) L→Elist ] { L.place:=newtemp; emit(L.place ‘:=’ Elist.array ‘－’ C); L.offset:=newtemp; emit(L.offset ‘:=’ w ‘*’ Elist.place) } (6) L→id { L.place:=id.place; L.offset:=null } 国防科技大学计算机系602教研室

42 类型转换 用E.type表示非终结符E的类型属性 对应产生式EE1 op E2的语义动作中关于E.type的语义规则可定义为：
{ if E1.type=integer and E2.type=integer E.type:=integer else E.type:=real } 算符区分为整型算符int op和实型算符real op， 国防科技大学计算机系602教研室

43 其中x、y为实型；i、j为整型。这个赋值句产生的三地址代码为： T1:=i int* j T3:=inttoreal T1
T2:=y real+ T3 x:=T2 国防科技大学计算机系602教研室

44 关于产生式E→E1 ＋E2 的语义动作 { E.place:=newtemp;
if E1.type=integer and E2.type=integer then begin emit (E.place ‘:=’ E 1.place ‘int+’ E 2.place); E.type:=integer end else if E1.type=real and E2.type=real then begin emit (E.place ‘:=’ E 1.place ‘real+’ E 2.place); E.type:=real 国防科技大学计算机系602教研室

45 else if E1.type=integer and E2.type=real then begin u:=newtemp;
emit (u ‘:=’ ‘inttoreal’ E 1.place); emit (E.place ‘:=’ u ‘real+’ E 2.palce); E.type:=real end else if E1.type=real and E1.type=integer then begin emit (u ‘:=’ ‘inttoreal’ E 2.place); emit (E.place ‘:=’ E 1.place ‘real+’ u); else E.type:=type_error} 国防科技大学计算机系602教研室

46 记录中域的引用 符号表表项之中保存记录中的域的类型和相对地址信息 国防科技大学计算机系602教研室

47 E→E or E | E andE |  E | (E) | i rop i | i
7.4 布尔表达式的翻译 布尔表达式的两个基本作用: 用于逻辑演算,计算逻辑值; 用于控制语句的条件式. 产生布尔表达式的文法: E→E or E | E andE |  E | (E) | i rop i | i 国防科技大学计算机系602教研室

48 计算布尔表达式通常采用两种方法: 1. 如同计算算术表达式一样,一步步算 1 or (not 0 and 0) or 0
=1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true 国防科技大学计算机系602教研室

49 第二种翻译法适合于作为条件表达式的布尔表达式使用.
两种不同的翻译方法: 第一种翻译法： A or B and C=D翻译成 (1) (=, C, D, T1) (2) (and, B, T1, T2) (3) (or, A, T2, T3) 第二种翻译法适合于作为条件表达式的布尔表达式使用. 国防科技大学计算机系602教研室

50 7.4.1 数值表示法 a or b and not c 翻译成 a<b的关系表达式可等价地写成 T1:=not c
数值表示法 a or b and not c 翻译成 T1:=not c T2:=b and T1 T3:=a or T1 a<b的关系表达式可等价地写成 if a<b then 1 else 0 ，翻译成 100: if a<b goto 103 101: T:=0 102: goto 104 103: T:=1 104: 国防科技大学计算机系602教研室

51 关于布尔表达式的数值表示法的翻译模式 过程emit将三地址代码送到输出文件中 nextstat给出输出序列中下一条三地址语句的地址索引
国防科技大学计算机系602教研室

52 关于布尔表达式的数值表示法的翻译模式 E→E1 or E2 {E.place:=newtemp;
emit(E.place ‘:=’ E 1.place ‘or’ E2.place)} E→E1 and E2 {E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘and’ E2.place)} E→not E {E.place:=newtemp; emit(E.place ‘:=’ ‘not’ E 1.place)} E→(E1) {E.place:=E1.place} 国防科技大学计算机系602教研室

53 关于布尔表达式的数值表示法的翻译模式 Eid1 relop id2 { E.place:=newtemp;
a<b 翻译成 100: if a<b goto 103 101: T:=0 102: goto 104 103: T:=1 104: 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→id { E.place:=id.place } 国防科技大学计算机系602教研室

54 布尔表达式a<b or c<d and e<f的翻译结果
100: if a<b goto 103 101: T1:=0 102: goto 104 103: T1:=1 104: if c<d goto 107 105: T2:=0 106: goto 108 107: T2:=1 108: if e<f goto 111 109: T3:=0 110: goto 112 111: T3:=1 112: T4:=T2 and T3 113: T5:=T1 or T4 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→id { E.place:=id.place } E→E1 or E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘or’ E2.place)} E→E1 and E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘and’ E2.place) } 国防科技大学计算机系602教研室

55 7.4.2 作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true
作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true E.code To E.false E.true: S1.code goto S.next E.false: S2.code …… S.next 国防科技大学计算机系602教研室

56 例：把语句: if a>c or b <d then S1 else S2 翻译成如下的一串三地址代码
if a>c goto L2 “真”出口 goto L1 L1: if b<d goto L2 “真”出口 goto L “假”出口 L2: (关于S1的三地址代码序列) goto Lnext L3: (关于S2的三地址代码序列) Lnext: 国防科技大学计算机系602教研室

57 每次调用函数newlabel后都返回一个新的符号标号 对于一个布尔表达式E，引用两个标号
E.true是E为‘真’时控制流转向的标号 E.false是E为‘假’时控制流转向的标号 国防科技大学计算机系602教研室

58 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→E1 or E2 E1.true:=E.true;
产生式 语义规则 E→E1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code || gen(E1.false ‘:’) || E2.code E1.code To E.true To E1.false E2.code To E.false 国防科技大学计算机系602教研室

59 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→E1 and E2 E1.true:=newlabel;
产生式 语义规则 E→E1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code || gen(E1.true ‘:’) || E2.code E1.code To E. false To E1. true E2.code To E.true To E.false 国防科技大学计算机系602教研室

60 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→not E1 E1.true:=E.false;
产生式 语义规则 E→not E E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E→ (E1) E1.true:=E.true; E1.false:=E.false; 国防科技大学计算机系602教研室

61 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→id1 relop id2 E.code:=gen(‘if ’ id1.place
产生式 语义规则 E→id1 relop id E.code:=gen(‘if ’ id1.place relop.op id2.place ‘goto’ E.true) || gen(‘goto’ E.false) E→true E.code:=gen(‘goto’ E.true) E→false E.code:=gen(‘goto’ E.false) 国防科技大学计算机系602教研室

62 考虑如下表达式： a<b or c<d and e<f 假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：
if a<b goto Ltrue goto L1 L1: if c<d goto L2 goto Lfalse L2: if e<f goto Ltrue 国防科技大学计算机系602教研室

63 布尔表达式的翻译 两遍扫描 一遍扫描 为给定的输入串构造一棵语法树； 对语法树进行深度优先遍历，进行语义规则中规定的翻译。
国防科技大学计算机系602教研室

64 一遍扫描实现布尔表达式的翻译 采用四元式形式 把四元式存入一个数组中，数组下标就代表四元式的标号 约定
四元式(jnz, a, -, p) 表示 if a goto p 四元式(jrop, x, y, p)表示 if x rop y goto p 四元式(j, -, -, p) 表示 goto p 国防科技大学计算机系602教研室

65 有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地址作为E的语义值保存,待机"回填"。
国防科技大学计算机系602教研室

66 例如:假定E的四元式中需要回填"真"出口的p，q，r三个四元式，则E.truelist为下列链: (p) (x， x，x，0) …
为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填"真"出口的p，q，r三个四元式，则E.truelist为下列链: (p) (x， x，x，0) … (q) (x，x，x，p) (r) (x，x，x，q) 链尾 E. truelist =r 国防科技大学计算机系602教研室

67 为了处理E.truelist和E.falselist ，引入下列语义变量和过程:
变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之后，nextquad将自动增1。 函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。 函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。 过程backpatch(p, t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。 国防科技大学计算机系602教研室

68 布尔表达式的文法 (1) E→ E1 or M E2 (2) | E1 and M E2 (3) | not E1 (4) | (E1)
(5) | id1 relop id2 (6) | id (7) M→ 国防科技大学计算机系602教研室

69 布尔表达式的翻译模式 (7) M→ { M.quad:=nextquad } 国防科技大学计算机系602教研室

70 布尔表达式的翻译模式 E1.code E1.code E2.code E2.code (1) E→E1 or M E2
To E. false To E1. true E2.code To E.true To E.false E1.code To E.true To E1.false E2.code To E.false 布尔表达式的翻译模式 (1) E→E1 or M E2 { backpatch(E1.falselist, M.quad); E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist } (2) E→E1 and M E2 { backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) } 国防科技大学计算机系602教研室

71 布尔表达式的翻译模式 (3) E→not E1 { E.truelist:=E1.falselist;
E.falselist:=E1.truelist} (4) E→(E1) { E.truelist:=E1.truelist; E.falselist:=E1. falselist} 国防科技大学计算机系602教研室

72 布尔表达式的翻译模式 (5) E→id1 relop id2 { E.truelist:=makelist(nextquad);
E.falselist:=makelist(nextquad+1); emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’　‘0’); emit(‘j, －, －, 0’) } (6) E→id { E.truelist:=makelist(nextquad); emit(‘jnz’ ‘,’ id .place ‘,’ ‘－’ ‘,’　‘0’)； emit(‘ j, -, -, 0’) } 国防科技大学计算机系602教研室

73 布尔表达式的翻译模式 作为整个布尔表达式的"真""假"出口(转移目标)仍待回填. 国防科技大学计算机系602教研室

74 a<b or c<d and e<f
100 (j<, a, b, 0) 101 (j, -, -, 102) 102 (j<, c, d, 104) 103 (j, -, -, 0) 104 (j<, e, f, 100) truelist 105 (j, -, -, 103) falselist 板书分析树的形成过程 国防科技大学计算机系602教研室

75 回顾：布尔表达式的翻译 计算布尔表达式通常采用两种方法: 1. 如同计算算术表达式一样,一步步算
1 or (not 0 and 0) or 0 =1 or (1 and 0) or 0 =1 or 0 or 0 =1 or 0 =1 2. 采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else false 把 A解释成 if A then false else true 国防科技大学计算机系602教研室

76 关于布尔表达式的数值表示法的翻译模式 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→id { E.place:=id.place } E→E1 or E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘or’ E2.place)} E→E1 and E2 { E.place:=newtemp; emit(E.place ‘:=’ E 1.place ‘and’ E2.place) } 国防科技大学计算机系602教研室

77 回顾：布尔表达式的翻译 作为条件控制的布尔式翻译 一遍扫描实现布尔表达式的翻译 国防科技大学计算机系602教研室

78 7.4.2 作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true
作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true E.code To E.false E.true: S1.code goto S.next E.false: S2.code …… S.next 国防科技大学计算机系602教研室

79 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→E1 or E2 E1.true:=E.true;
产生式 语义规则 E→E1 or E2 E1.true:=E.true; E1.false:=newlabel; E2.true:=E.true; E2.false:=E.false; E.code:=E1.code || gen(E1.false ‘:’) || E2.code E1.code To E.true To E1.false E2.code To E.false 国防科技大学计算机系602教研室

80 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→E1 and E2 E1.true:=newlabel;
产生式 语义规则 E→E1 and E2 E1.true:=newlabel; E1.false:=E.false; E2.true:=E.true; E2.false:=E.fasle; E.code:=E1.code || gen(E1.true ‘:’) || E2.code E1.code To E. false To E1. true E2.code To E.true To E.false 国防科技大学计算机系602教研室

81 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→not E1 E1.true:=E.false;
产生式 语义规则 E→not E E1.true:=E.false; E1.false:=E.true; E.code:=E1.code E→ (E1) E1.true:=E.true; E1.false:=E.false; 国防科技大学计算机系602教研室

82 产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→id1 relop id2 E.code:=gen(‘if ’ id1.place
产生式 语义规则 E→id1 relop id E.code:=gen(‘if ’ id1.place relop.op id2.place ‘goto’ E.true) || gen(‘goto’ E.false) E→true E.code:=gen(‘goto’ E.true) E→false E.code:=gen(‘goto’ E.false) 国防科技大学计算机系602教研室

83 回顾：布尔表达式的翻译 作为条件控制的布尔式翻译 一遍扫描实现布尔表达式的翻译 国防科技大学计算机系602教研室

84 布尔表达式的文法 (1) E→ E1 or M E2 (2) | E1 and M E2 (3) | not E1 (4) | (E1)
(5) | id1 relop id2 (6) | id (7) M→ 国防科技大学计算机系602教研室

85 布尔表达式的翻译模式 (1) E→E1 or M E2 { backpatch(E1.falselist, M.quad);
E.truelist:=merge(E1.truelist, E2.truelist); E.falselist:=E2.falselist } (2) E→E1 and M E2 { backpatch(E1.truelist, M.quad); E.truelist:=E2.truelist; E.falselist:=merge(E1.falselist,E2.falselist) } (3) E→not E1 { E.truelist:=E1.falselist; E.falselist:=E1.truelist} (4) E→(E1) { E.truelist:=E1.truelist; E.falselist:=E1. falselist} 国防科技大学计算机系602教研室

86 布尔表达式的翻译模式 (5) E→id1 relop id2 { E.truelist:=makelist(nextquad);
E.falselist:=makelist(nextquad+1); emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’　‘0’); emit(‘j, －, －, 0’) } (6) E→id emit(‘jnz’ ‘,’ id .place ‘,’ ‘－’ ‘,’　‘0’)； emit(‘ j, -, -, 0’) } (7) M→ { M.quad:=nextquad } 国防科技大学计算机系602教研室

87 布尔表达式的翻译模式 作为整个布尔表达式的"真""假"出口(转移目标)仍待回填. 国防科技大学计算机系602教研室

88 7.5 控制语句的翻译 考虑下列产生式所定义的语句 S → if E then S1 | if E then S1 else S2
7.5 控制语句的翻译 考虑下列产生式所定义的语句 S → if E then S1 | if E then S1 else S2 | while E do S1 其中E为布尔表达式。 国防科技大学计算机系602教研室

89 if-then语句 S → if E then S1 To E.true E.code To E.false E.true: S1.code
…… 国防科技大学计算机系602教研室

90 if-then语句的属性文法 产生式 语义规则 S→if E then S1 E.true:=newlabel;
产生式 语义规则 S→if E then S1 E.true:=newlabel; E.flase:=S.next; S1.next:=S.next S.code:=E.code || gen(E.true ‘:’) || S1.code E.code S1.code To E.true To E.false …… E.true: E.false: 国防科技大学计算机系602教研室

91 if-then-else语句 S → if E then S1 else S2 To E.true E.code To E.false
S1.code goto S.next E.false: S2.code …… S.next 国防科技大学计算机系602教研室

92 if-then-else语句的属性文法 产生式 语义规则 S→if E then S1 else S2 E.true:=newlabel;
产生式 语义规则 S→if E then S1 else S2 E.true:=newlabel; E.false:=newlabel; S1.next:=S.next S2.next:=S.next; S.code:=E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S.next) || gen(E.false ‘:’) || S2.code E.code S1.code S2.code To E.true To E.false goto S.next S.next …… E.true: E.false: 国防科技大学计算机系602教研室

93 while-do语句 S → while E do S1 S.begin: To E.true E.code To E.false
S1.code goto S.begin E.false: …… 国防科技大学计算机系602教研室

94 while-do语句的属性文法 产生式 语义规则 S→while E do S1 S.begin:=newlabel;
产生式 语义规则 S→while E do S1 S.begin:=newlabel; E.true:=newlabel; E.false:=S.next; S1.next:=S.begin; S.code:=gen(S.begin ‘:’) || E.code || gen(E.true ‘:’) || S1.code || gen(‘goto’ S.begin) E.code S1.code To E.true To E.false goto S.begin S.begin: …… E.true: E.false: 国防科技大学计算机系602教研室

95 考虑如下语句 : while a<b do if c<d then x:=y+z else x:=y-z
生成下列代码： L1: if a<b goto L2 goto Lnext L2: if c<d goto L3 goto L4 L3: T1:=y+z x:=T1 goto L1 L4: T2:=y-z x:=T2 Lnext: 板书分析树的形成过程 国防科技大学计算机系602教研室

96 一遍扫描翻译控制流语句 考虑下列产生式所定义的语句: S表示语句， L表示语句表， A为赋值语句，E为一个布尔表达式
(1) S→if E then S (2) | if E then S else S (3) | while E do S (4) | begin L end (5) | A (6) L→L;S (7) | S S表示语句， L表示语句表， A为赋值语句，E为一个布尔表达式 国防科技大学计算机系602教研室

97 if 语句的翻译 相关产生式 改写后产生式 S → if E then M S1 S → if E then S(1)
| if E then S(1) else S(2) 改写后产生式 S → if E then M S1 S → if E then M1 S1 N else M2 S2 M→ N→ 国防科技大学计算机系602教研室

98 翻译模式: 1. S→if E then M S1 { backpatch(E.truelist, M.quad);
S.nextlist:=merge(E.falselist, S1.nextlist) } 2. S→if E then M1 S1 N else M2 S2 { backpatch(E.truelist, M1.quad); backpatch(E.falselist, M2.quad); S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist) } 3. M→ { M.quad:=nextquad } 4. N→ { N.nextlist:=makelist(nextquad); emit(‘j,－,－,－’) } 国防科技大学计算机系602教研室

99 while 语句的翻译 相关产生式 S→ while E do S(1) 翻译为： 为了便于"回填"，改写产生式为:
“真”出口 E的代码 S (1)的代码 “假”出口 为了便于"回填"，改写产生式为: S→while M1 E do M2 S1 M→ 国防科技大学计算机系602教研室

100 翻译模式: 1. S→while M1 E do M2 S1 { backpatch(S1.nextlist, M1.quad);
backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(‘j,－,－,’ M1.quad) } 2. M→ { M.quad:=nextquad } 国防科技大学计算机系602教研室

101 产生式 L→L;S 改写为： L→L1; M S M→ 国防科技大学计算机系602教研室

102 1. L→L1; M S { backpatch(L1.nextlist, M.quad);
翻译模式: 1. L→L1; M S { backpatch(L1.nextlist, M.quad); L.nextlist:=S.nextlist } 2. M→ { M.quad:=nextquad } 国防科技大学计算机系602教研室

103 1. S→begin L end { S.nextlist:=L.nextlist }
其它几个语句的翻译 1. S→begin L end { S.nextlist:=L.nextlist } 2. S→A { S.nextlist:=makelist( ) } 3. L→S { L.nextlist:=S.nextlist } 国防科技大学计算机系602教研室

104 翻译语句 while (a<b) do if (c<d) then x:=y+z;
P195 S→if E then M S1 { backpatch(E.truelist, M.quad); S.nextlist:=merge(E.falselist, S1.nextlist) } M→ { M.quad:=nextquad } S→A { S.nextlist:=makelist( ) } P190 (5) E→id1 relop id2 { E.truelist:=makelist(nextquad); E.falselist:=makelist(nextquad+1); emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’　‘0’); emit(‘j, －, －, 0’) } P195 S→while M1 E do M2 S1 { backpatch(S1.nextlist, M1.quad); backpatch(E.truelist, M2.quad); S.nextlist:=E.falselist emit(‘j,－,－,’ M1.quad) } M→ { M.quad:=nextquad } P179 S→id:=E { p:=lookup(id.name); if pnil then emit(p ‘:=’ E.place) else error } E→E1+E2 { E.place:=newtemp; emit(E.place ‘:=’ E1.place ‘+’ E2.place)} 国防科技大学计算机系602教研室

105 翻译语句 while (a<b) do if (c<d) then x:=y+z;
100 (j<, a, b, 102) 101 (j, -, -, 107) 102 (j<, c, d, 104) 103 (j, -, -, 100) 104 (+, y, z, T) 105 (:=, T, -, x) 106 (j, -, -, 100) 107 国防科技大学计算机系602教研室

106 7.5.2 标号与goto语句 标号定义形式 L: S； 标号引用 goto L； 示例： 向后转移： L1: …… …… goto L1;
向前转移： goto L1; …… L1: …… 国防科技大学计算机系602教研室

107 符号表信息 名字 类型 … 定义否 地址 L 标号 r (P) (j, -, -, 0) … (q) (j, -, -, p)
(r) (j, -, -, q) 未 已 国防科技大学计算机系602教研室

108 产生式S→goto L的语义动作: { 查找符号表； IF L在符号表中且"定义否"栏为"已" THEN GEN(J，-，-，P)
{ 查找符号表； IF L在符号表中且"定义否"栏为"已" THEN GEN(J，-，-，P) ELSE IF L不在符号表中 THEN BEGIN 把L填入表中； 置"定义否"为"未"，"地址"栏为NXQ； GEN(J，-，-，0) END ELSE BEGIN Q:=L的地址栏中的编号； 置地址栏编号为NXQ； GEN(J，-，-，Q) END } 国防科技大学计算机系602教研室

109 带标号语句的产生式: S→label S label → i: label → i: 对应的语义动作:
1. 若i所指的标识符(假定为L)不在符号表中，则把 它填入，置"类型"为"标号"，定义否为"已"，"地 址"为nextquad ； 2. 若L已在符号表中但"类型"不为标号或"定义否" 为"已"，则报告出错； 3. 若L已在符号表中，则把标号"未"改为"已"，然后，把地址栏中的链头(记为q)取出，同时把nextquad填在其中，最后，执行BACKPATCH(q，nextquad )。 国防科技大学计算机系602教研室

110 7.5.3 CASE语句的翻译 语句结构 case E of C1: S1; C2: S2; … Cn-1: Sn-1;
otherwise: Sn end 国防科技大学计算机系602教研室

111 翻译法(一): 改进: T:=E L1: if TC1 goto L2 S1的代码 goto next
… Ln-1: if TCn-1 goto Ln Sn-1的代码 Ln: Sn的代码 next: 国防科技大学计算机系602教研室

112 翻译法(二): 计算E并放入T中 goto test L1: 关于S1的中间码 goto next … Ln-1: 关于Sn-1的中间码
Pi是Li在 符号表中 的位置 翻译法(二): 计算E并放入T中 goto test L1: 关于S1的中间码 goto next … Ln-1: 关于Sn-1的中间码 Ln: 关于Sn的中间码 test: if T=C1 goto L1 if T=C2 goto L2 if T=Cn-1 goto Ln-1 goto Ln next: (case, C1, P1) (case, C2, P2) … (case, Cn-1, Pn-1) (case, T, Pn) (label, NEXT, -, -) 国防科技大学计算机系602教研室

113 7.6 过程调用的处理 过程调用主要对应两种事: 传地址:把实在参数的地址传递给相应的形式参数 传递参数 转子
7.6 过程调用的处理 过程调用主要对应两种事: 传递参数 转子 传地址:把实在参数的地址传递给相应的形式参数 调用段预先把实在参数的地址传递到被调用段可以拿到的地方； 程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中； 过程体对形式参数的引用域赋值被处理成对形式单元的间接访问。 国防科技大学计算机系602教研室

114 翻译方法：把实参的地址逐一放在转子指令的前面. 例如， CALL S(A，X+Y) 翻译为: 计算X+Y置于T中的代码
par A /*第一个参数的地址*/ par T /*第二个参数的地址*/ call S /*转子*/ 国防科技大学计算机系602教研室

115 过程调用的翻译 过程调用文法: 参数的地址存放在一个队列中 最后对队列队列中的每一项生成一条par语句
(1) S → call id (Elist) (2) Elist → Elist, E (3) Elist → E 参数的地址存放在一个队列中 最后对队列队列中的每一项生成一条par语句 国防科技大学计算机系602教研室

116 翻译模式 3. Elist→E { 初始化queue仅包含E.place } 2. Elist→Elist, E
{ 将E.place加入到queue的队尾 } 1. S→call id (Elist) { for 队列queue中的每一项p do emit(‘param’ p); emit(‘call’ id.place) } 国防科技大学计算机系602教研室

117 作业 P217-1，3 ，4 ，5 ，6 ，7 ，12 国防科技大学计算机系602教研室