第八章 语义分析和中间代码生成

第一部分：中间语言

1 中间语言的特点和作用

特点：
独立于机器；
复杂性界于源语言和目标语言之间。
引入中间语言的优点：
使编译程序的结构在逻辑上更为简单明确 ；
便于进行与机器无关的代码优化工作 ；
易于移植。

中间语言的地位

中间语言的地位

2 常用的中间语言

后缀式，逆波兰表示。
图表示： 抽象语法树(AST)、有向无环图(DAG)。
三地址代码：三元式、四元式、间接三元式。

3 后缀式

后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。

一个表达式E的后缀形式可以如下定义：
如果E是一个变量或常量，则E的后缀式是E自身；
如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1‘ E2’ op，其中E1‘ 和E2’ 分别为E1 和E2的后缀式；
如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。

特点：
后缀式表示法不用括号：只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行无歧义地分解；
后缀式的计算：用一个栈实现，自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。

示例：
后缀式

4 图表示法

有向无环图(Directed Acyclic Graph，简称DAG)：
对表达式中的每个子表达式，DAG中都有一个结点；
一个内部结点代表一个操作符，它的孩子代表操作数；
在一个DAG中代表公共子表达式的结点具有多个父结点。

图表示法

图表示法

5 三地址代码

三地址代码：x:=y op z
可以看成是抽象语法树或有向无环图的一种线性表示。

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

四元式：一个带有四个域的记录结构，这四个域分别称为op, arg1, arg2及result。示例：
四元式

三元式：用三个域表示：op、arg1和arg2。

间接三元式：三元式表+间接码表。
间接码表是一张指示器表，按运算的先后次序列出有关三元式在三元式表中的位置。优点是方便优化，节省空间。

第二部分：赋值语句的翻译

6 简单算术表达式及赋值语句

赋值语句的形式：
id:=E
赋值语句的意义(功能) ：
对表达式E求值并置于变量T中，id.place:=T。

7 产生赋值语句三地址代码的翻译模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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)}

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 }

8 数组元素引用的翻译

9 类型转换

示例：
x := y＋i*j，其中x、y为实型；i、j为整型，该赋值句产生的三地址代码为： 

1
2
3
4
T1 := i  int*  j  
T3 := inttoreal  T1  
T2 := y  real+ T3  
x := T2

用E.type表示非终结符E的类型属性，产生式E→E1 op E2的语义动作中关于E.type的语义规则可定义为： 

1
2
3
{  if E1.type=integer and E2.type=integer  
       E.type:=integer  
    else E.type:=real  }

第三部分：布尔表达式的翻译

10 布尔表达式的简介

文法：
E → E or E | E and E | not E | (E) | i rop i | i

用途：
用于逻辑演算，计算逻辑值；用于控制语句的条件式。

计算布尔表达式的两种方法：
数值表示法：如同计算算术表达式一样,一步步算。
例子：

1
2
3
4
5
1 or (not 0 and 0) or 0
=1 or (1 and 0) or 0
=1 or 0 or 0
=1 or 0
=1

带优化的翻译法:
把A or B解释成 if A then true else B；
把A and B解释成 if A then B else false；
把not A解释成 if A then false else true；
适合于作为条件表达式的布尔表达式使用。

11 数值表示法的翻译模式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 }

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 }

12 产生布尔表达式三地址代码的属性文法

语义函数newlabel，返回一个新的符号标号；
对于一个布尔表达式E，设置两个继承属性：E.true是E为‘真’时控制流转向的标号，E.false是E为‘假’时控制流转向的标号；
E.code记录E生成的三地址代码序列。

E→E1 or E2：

1
2
3
4
5
E1.true:=E.true;
E1.false:=newlabel;
E2.true:=E.true;
E2.false:=E.false;
E.code:=E1.code || gen(E1.false ‘:’) || E2.code

E→E1 and E2：

1
2
3
4
5
E1.true:=newlabel;
E1.false:=E.false;
E2.true:=E.true;
E2.false:=E.fasle;
E.code:=E1.code || gen(E1.true ‘:’) || E2.code

E→not E1：

1
2
3
E1.true:=E.false;
E1.false:=E.true;
E.code:=E1.code

E→ (E1)：

1
2
3
E1.true:=E.true;
E1.false:=E.false;
E.code:=E1.code

E→id1 relop id2：

1
2
E.code:=gen(‘if ’ id1.place relop.op id2.place ‘goto’ E.true) 
        || gen(‘goto’  E.false)

E→true：

1
E.code:=gen(‘goto’  E.true)

E→false：

1
E.code:=gen(‘goto’  E.false)

13 一遍扫描翻译模式

以四元式为中间语言。
四元式存入一个数组中，数组下标代表四元式的标号。
约定：
四元式(jnz, a, -, p) 表示 if a goto p ；
四元式(jrop, x, y, p) 表示 if x rop y goto p；
四元式(j, -, -, p) 表示 goto p。

产生跳转四元式时，它的转移地址无法立即知道，需要以后扫描到特定位置时才能回过头来确定，把这些未完成的四元式地址作为E的语义值保存,待机“回填”。

为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所对应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表。

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

布尔表达式的文法：
(1) E → E1 or M E2
(2) E → E1 and M E2
(3) E → not E1
(4) E → (E1)
(5) E → id1 relop id2
(6) E → id
(7) M→𝜀

E→E1 or M E2：

1
2
3
{ backpatch(E1.falselist, M.quad);
  E.truelist:=merge(E1.truelist, E2.truelist);
  E.falselist:=E2.falselist }

E→E1 and M E2：

1
2
3
{ backpatch(E1.truelist, M.quad);
  E.truelist:=E2.truelist;
  E.falselist:=merge(E1.falselist,E2.falselist) }

E→not E1：

1
2
{ E.truelist:=E1.falselist;
  E.falselist:=E1.truelist}

E→ (E1)：

1
2
{ E.truelist:=E1.truelist;
  E.falselist:=E1.falselist}

E→id1 relop id2：

1
2
3
4
{ E.truelist:=makelist(nextquad);
  E.falselist:=makelist(nextquad+1);
  emit(‘j’ relop.op ‘,’ id 1.place ‘,’ id 2.place‘,’　‘0’);
  emit(‘j, －, －, 0’) }

E→id：

1
2
3
4
{ E.truelist:=makelist(nextquad);
  E.falselist:=makelist(nextquad+1);
  emit(‘jnz’ ‘,’ id .place ‘,’ ‘－’ ‘,’　‘0’)；
  emit(‘ j, -, -, 0’) }

第四部分：控制语句的翻译

14 常用的控制语句

S → if E then S1
S → if E then S1 else S2
S → while E do S1
其中E为布尔表达式。

15 if语句的属性文法

S→if E then S1：

1
2
3
4
E.true:=newlabel;
E.flase:=S.next;
S1.next:=S.next
S.code:=E.code || gen(E.true ‘:’) || S1.code

S→if E then S1 else S2：

1
2
3
4
5
6
7
8
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

16 while语句的属性文法

S→while E do S1：

1
2
3
4
5
6
7
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)

17 一遍扫描翻译控制语句

控制语句的文法：
(1) S → if E then S
(2) S → if E then S else S
(3) S → while E do S
(4) S → begin L end
(5) S → A
(6) L → L;S
(7) L → S

if 语句的翻译模式：
S→if E then M S1： 

1
2
{ backpatch(E.truelist, M.quad);
  S.nextlist:=merge(E.falselist, S1.nextlist) }

S→if E then M1 S1 N else M2 S2：

1
2
3
{ backpatch(E.truelist, M1.quad);
  backpatch(E.falselist, M2.quad);
  S.nextlist:=merge(S1.nextlist, N.nextlist, S2.nextlist) }

M→𝜀：

1
{ M.quad:=nextquad }

N→𝜀：

1
2
{ N.nextlist:=makelist(nextquad);
  emit(‘j,－,－,－’) }

while-do语句的翻译模式：
S → while M1 E do M2 S1：

1
2
3
4
{ backpatch(E.truelist, M2.quad);
  backpatch(S1.nextlist, M1.quad);
  S.nextlist := E.falselist;
  emit(‘j,－,－,’ M1.quad)  }

M → 𝜀： 

1
{  M.quad := nextquad  }

复合语句的翻译模式：
S → begin L end： 

1
{ S.nextlist := L.nextlist }

L → L1; M S： 

1
2
{ backpatch(L1.nextlist, M.quad);
  L.nextlist := S.nextlist }

M → 𝜀： 

1
{ M.quad := nextquad }

其它几个语句的翻译：
S → A：

1
{ S.nextlist := makelist( ) }

L → S：

1
{ L.nextlist := S.nextlist }