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

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

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

7.1.1 后缀式 一个表达式E的后缀形式可以如下定义： 后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。 7.1.1 后缀式 后缀式表示法：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教研室

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

把表达式翻译成后缀式的语义规则描述 产生式 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教研室

数组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： 1 2 3 4 5 a b + c + … 国防科技大学计算机系602教研室

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

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

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

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

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教研室

产生赋值语句抽象语法树的属性文法 产 生 式 语义规则 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→-E1 E.nptr:=mknode(‘uminus’,E1.nptr) E→ (E1) E.nptr:=E1.nptr E→id E.nptr:=mkleaf(id,id.place) 国防科技大学计算机系602教研室

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

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

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

三地址语句的种类 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教研室

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

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

为赋值语句生成三地址代码的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教研室

三地址语句 四元式 一个带有四个域的记录结构，这四个域分别称为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教研室

三地址语句 三元式 通过计算临时变量值的语句的位置来引用这个临时变量 三个域：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教研室

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

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

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

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

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

为赋值语句生成三地址代码的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教研室

产生赋值语句三地址代码的翻译模式 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教研室

产生赋值语句三地址代码的翻译模式 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教研室

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

设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教研室

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

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

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

(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教研室

{ 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教研室

(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教研室

{ 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教研室

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教研室

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教研室

类型转换 用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教研室

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

关于产生式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教研室

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教研室

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

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教研室

计算布尔表达式通常采用两种方法: 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教研室

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

7.4.1 数值表示法 a or b and not c 翻译成 a<b的关系表达式可等价地写成 T1:=not c 7.4.1 数值表示法 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教研室

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

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

关于布尔表达式的数值表示法的翻译模式 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教研室

布尔表达式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教研室

7.4.2 作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true 7.4.2 作为条件控制的布尔式翻译 条件语句 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教研室

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

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

产生布尔表达式三地址代码的语义规则 产生式 语义规则 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教研室

产生布尔表达式三地址代码的语义规则 产生式 语义规则 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教研室

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

产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→id1 relop id2 E.code:=gen(‘if ’ id1.place 产生式 语义规则 E→id1 relop id2 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教研室

考虑如下表达式： 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教研室

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

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

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

例如:假定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教研室

为了处理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教研室

布尔表达式的文法 (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教研室

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

布尔表达式的翻译模式 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教研室

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

布尔表达式的翻译模式 (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教研室

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

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教研室

回顾：布尔表达式的翻译 计算布尔表达式通常采用两种方法: 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教研室

关于布尔表达式的数值表示法的翻译模式 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教研室

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

7.4.2 作为条件控制的布尔式翻译 条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假 To E.true 7.4.2 作为条件控制的布尔式翻译 条件语句 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教研室

产生布尔表达式三地址代码的语义规则 产生式 语义规则 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教研室

产生布尔表达式三地址代码的语义规则 产生式 语义规则 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教研室

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

产生布尔表达式三地址代码的语义规则 产生式 语义规则 E→id1 relop id2 E.code:=gen(‘if ’ id1.place 产生式 语义规则 E→id1 relop id2 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教研室

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

布尔表达式的文法 (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教研室

布尔表达式的翻译模式 (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教研室

布尔表达式的翻译模式 (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教研室

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

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教研室

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

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教研室

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教研室

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教研室

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教研室

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教研室

考虑如下语句 : 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教研室

一遍扫描翻译控制流语句 考虑下列产生式所定义的语句: 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教研室

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教研室

翻译模式: 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教研室

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

翻译模式: 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教研室

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

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教研室

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教研室

翻译语句 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教研室

翻译语句 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教研室

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

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

产生式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教研室

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

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

翻译法(一): 改进: 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教研室

翻译法(二): 计算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教研室

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

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

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

翻译模式 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教研室

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