2.7 语义分析和中间代码产生本节要点
中间表示（后缀式、三地址代码和 DAG图）
语言中常见结构的翻译
赋值语句
声明语句
数组引用
布尔表达式
控制语句
2.7 语义分析和中间代码产生静态语义检查
类型检查
控制流检查
一致性检查
相关名字检查
名字的作用域分析语法分析器中间代码产生器静态检查器中间代码 优化器中间语言 (复杂性界于源语言和目标语言之间 )的好处：
便于进行与机器无关的代码优化工作
易于移植
使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序
Compiler
Front End
Compiler
Back End
常用的中间语言：
后缀式 (逆波兰表示 )
三地址代码
三元式
四元式
间接三元式
DAG图表示
2.7.1 中间语言
2.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
的后缀式。
逆波兰表示法不用括号 。 只要知道每个算符的目数,对于后缀式,不论从哪一端进行扫描,都能对它进行唯一分解 。
后缀式的计算
用一个栈实现 。
一般的计算过程是：自左至右扫描后缀式,每碰到运算量就把它推进栈 。 每碰到 k目运算符就把它作用于栈顶的 k个项,并用运算结果代替这
k个项 。
是语法树的后序遍历线性化把表达式翻译成后缀式的语义规则描述产生式
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表示任意二元操作符
,||”表示后缀形式的连接 。
数组 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 +?
2.7.1.2 图表示法图表示法
DAG
抽象语法树有向无环图 (Directed Acyclic Graph，简称
DAG)
对表达式中的每个子表达式,DAG中都有一个结点
一个内部结点代表一个操作符，它的孩子代表操作数
在一个 DAG中代表公共子表达式的结点具有多个父结点（允许它使用多次）
没有父节点的节点称为根节点,dag可以有多个根节点。
DAG举例与（ A+B)+(A+B)对应的 DAG
＋
A B
＋
a:=b*(-c)+b*(-c)的图表示法
assign
a +
*
b uminus
c
DAG
assign
a +
*
b uminus
c
抽象语法树
*
b uminus
c
产生赋值语句抽象语法树的属性文法产 生 式 语义规则
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)
2.7.1.3 三地址代码三地址代码的一般形式：
x:=y op z
三地址代码可以看成是抽象语法树或
DAG的一种线性表示
a:=b*(-c)+b*(-c)的代码
T1:=-c T1:=-c
T2:=b*T1 T2:=b*T1
T3:=-c T5:=T2+T2
T4:=b*T3 a:=T5
T5:=T2+T4
a:=T5
对于抽象语法树的代码 对于 DAG的代码三地址语句的种类
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的地址和指针赋值生成三地址代码时，临时变量的名字对应抽象语法树的内部结点
id:=E
对表达式 E求值并置于变量 T中值
id.place:=T
从赋值语句生成三地址代码的 S-属性文法非终结符号 S有综合属性 S.code，它代表赋值语句 S的三地址代码。
非终结符号 E有如下两个属性：
E.place表示存放 E值的名字 。
E.code表示对 E求值的三地址语句序列 。
函数 newtemp的功能是,每次调用它时,将返回一个不同临时变量名字,如 T1,T2,… 。
为赋值语句生成三地址代码的 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;
E.code:=E1.code || E2.code ||
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=‘ ’
三地址语句的实现四元式三元式间接三元式三地址语句的实现四元式
一个带有四个域的记录结构，这四个域分别称为 op,
arg1,arg2及 result
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
a:=b*(-c)+b*(-c)的四元式三地址语句的实现三元式
通过计算临时变量值的语句的位置来引用这个临时变量
三个域,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)
三地址语句的实现
x[i]:=y
op arg1 arg2
(0) [ ] = x i
(1) assign (0) y
x:=y[i]
op arg1 arg2
(0) = [ ] y i
(1) assign x (0)
三地址语句的实现间接三元式
列出指向三元式的指针,而不是三元式
间接码表,一张指示器表,按运算的先后次序列出有关三元式在三元式表中的位置 。
优点,
方便优化 (只需调整间接表 ）
节省空间 （ 同一四元式不需多重存储 ）
例如，语句
X:=(A+B)*C;
Y:=D↑(A+B)
的间接三元式表示如下表所示。
间接代码
( 1 )
( 2 )
( 3 )
( 1 )
( 4 )
( 5 )
三元式表
OP ARG1 ARG2
(1) + A B
(2) * (1) C
(3),= X (2)
(4) ↑ D (1)
(5),= Y ( 4 )
2.7.2 声明语句当考查一个过程或分程序的一系列声明语句时,便可为局部于该过程的名字分配存储空间 。
对每个局部名字,都将在符号表中建立相应的表项,并填入有关的信息如类型,在存储器中的相对地址等 。
P→ {offset:=0｝
D
D→D;D
D→id:T {enter(id.name,T.type,offset);
offset:=offset+T.width}
T→integer {T.type:=integer;
T.width:=4}
T→real {T.type:=real;
T.width:=8}
T→array[num] of T1 { T.type:=array(num.val,T1.type)
T.width:=num.val× T1.width}
T→↑T1 {T.type:=pointer(T1.type);
T.width:=4}
计算声明语句中名字的类型和相对地址
2.7.3 赋值语句的翻译
7.3.1 简单算术表达式及赋值语句产生赋值语句三地址代码的翻译模式
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 }
2.7.3.2 数组元素的引用数组元素地址的计算：
设 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在编译时可确定，可存放在符号表中 A的表项。
数组元素的引用
id出现的地方也允许下面产生式中的 L出现
L → id [ Elist ] | id
Elist→Elist,E | E
为了便于处理,文法改写为
L→Elist ] | id
Elist→Elist,E | id [ E
注：改写的主要目的是让 id与最左的 E相联系，而不是在 L
生成时与 L联系，这样在整个下标表达式的翻译过程中都可知道关于符号表中关于数组的信息。
引入下列语义变量或语义过程,
Elist.array：用来记录符号表中对应数组名项的指针
Elist.ndim,下标个数计数器
Elist.place,表示临时变量,用来临时存放已形成的 Elist中的下标表达式计算出来的值
limit(array,j),函数过程,它给出数组 array
的第 j维的长度每个代表变量的非终结符 L有两项语义值
L.place：
若 L为简单变量 i,指变量 i的符号表入口
若 L为下标变量，指存放 CONSPART的 临时变量的整数码
L.offset,
若 L为简单变量,null，
若 L为下标变量，指存放 VARPART的临时变量的整数码在赋值语句中加入数组元素后
(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
(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)}
(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 }
(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 }
(7) Elist→ Elist1,E
{ t:=newtemp;
m:=Elist.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 }
(8) Elist→id [ E
{ Elist.place:=E.place;
Elist.ndim:=1;
Elist.array:=id.place }
例 设 A为一个 10× 20的数组，即 n1=10,
n2=20,low1=1,low2=1并设 w=4。对赋值语句 x:=A[y,z]被翻译成什么三地址语句序列？
t1=elist.place* limit(Elist1.array,2)
=y*20
T1=t1+E.Place=t1+z
例 设 A为一个 10× 20的数组，即 n1=10,
n2=20,low1=1,low2=1并设 w=4。对赋值语句 x:=A[y,z]被翻译成如下三地址语句序列：
T1:=y*20
T1:=T1 +z
T2:=A-84
T3:=4*T1
T4:=T2[T3]
x:=T4
类型转换用 E.type表示非终结符 E的类型属性对应产生式 E?E1 op E2的语义动作中关于 E.type的语义规则可定义为：
{ if E1.type=integer and
E2.type=integer
E.type:=integer
else E.type:=real }
算符区分为整型算符 opi和实型算符 opr，
x:=y＋ i*j
其中 x,y为实型； i,j为整型 。 这个赋值句产生的三地址代码为：
T1:=i int* j
T3:=inttoreal T1
T2:=y real+ T3
x:=T2
关于产生式 E→E 1 ＋ 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
end
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
u:=newtemp;
emit (u ‘:=’ ‘inttoreal’ E 2.place);
emit (E.place ‘:=’ E 1.place ‘real+’ u);
E.type:=real
end
else E.type:=type_error}
2.7.3.3 记录中域的引用符号表表项之中保存记录中的域的类型和相对地址信息每个记录类型单独一张符号表，用在符号表中查找名字的方法可查找记录的域
2.7.4 布尔表达式的翻译布尔表达式的两个基本作用,
用于逻辑演算,计算逻辑值 ;
用于控制语句的条件式,
产生布尔表达式的文法,
E→E or E | E and E |? E | (E) | i rop i | i
计算布尔表达式通常采用两种方法,
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
两种不同的翻译方法,
第一种翻译法：
A or B and C=D翻译成
(1) (=,C,D,T1)
(2) (and,B,T1,T2)
(3) (or,A,T2,T3)
第二种翻译法适合于作为条件表达式的布尔表达式使用,
2.7.4.1 数值表示法
a or b and not c 翻译成
T1:=not c
T2:=b and T1
T3:=a or T2
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:
True用 1表示,False用 0表示关于布尔表达式的数值表示法的翻译模式过程 emit将三地址代码送到输出文件中
nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程 emit便把
nextstat加 1
关于布尔表达式的数值表示法的翻译模式
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 }
布尔表达式 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
7.4.2 作为条件控制的布尔式翻译条件语句 if E then S1 else S2
赋予 E 两种出口,一真一假
E.code
S1.code
S2.code
To E.true
To E.false
goto S.next
S.next ……
E.true:
E.false:
例：把语句,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:
每次调用函数 newlabel后都返回一个新的符号标号对于一个布尔表达式 E，引用两个标号
E.true是 E为 ‘ 真 ’ 时控制流转向的标号
E.false是 E为 ‘ 假 ’ 时控制流转向的标号产生布尔表达式三地址代码的语义规则产生式 语义规则
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
产生布尔表达式三地址代码的语义规则产生式 语义规则
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
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;
E.code:=E1.code
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)
考虑如下表达式：
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
goto Lfalse
布尔表达式的翻译两遍扫描
为给定的输入串构造一棵语法树；
对语法树进行深度优先遍历，进行语义规则中规定的翻译。
一遍扫描一遍扫描实现布尔表达式的翻译采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定四元式 (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所应的四元式中需回填,真,,,假,
出口的四元式的标号所构成的链表例如,假定 E的四元式中需要回填 "真 "出口的 p,q,r三个四元式,则 E.truelist为下列链,
(p) (x,x,x,0)
…
(q) (x,x,x,p)
…
(r) (x,x,x,q)
链尾
E,truelist =r
为了处理 E.truelist和 E.falselist,引入下列语义变量和过程,
变量 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) | E1 and M E2
(3) | not E1
(4) | (E1)
(5) | id1 relop id2
(6) | id
(7) M→?
布尔表达式的翻译模式
(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}
布尔表达式的翻译模式
(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);
E.falselist:=makelist(nextquad+1);
emit(‘jnz’ ‘,’ id,place ‘,’ ‘－ ’ ‘,’ ‘ 0’)；
emit(‘ j,-,-,0’) }
布尔表达式的翻译模式
(7) M→?
{ M.quad:=nextquad }
作为整个布尔表达式的 "真 ""假 "出口 (转移目标 )仍待回填,
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
2.7.5 控制语句的翻译考虑下列产生式所定义的语句
S → if E then S1
| if E then S1 else S2
| while E do S1
其中 E为布尔表达式。
if-then语句
S → if E then S1
E.code
S1.code
To E.true
To E.false
……
E.true:
E.false:
if-then语句的属性文法产生式 语义规则
S→if E then S1 E.true:=newlabel;
E.false:=S.next;
S1.next:=S.next
S.code:=E.code ||
gen(E.true ‘:’) || S1.code
if-then-else语句
S → if E then S1 else S2
E.code
S1.code
S2.code
To E.true
To E.false
goto S.next
S.next ……
E.true:
E.false:
if-then-else语句的属性文法产生式 语义规则
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
while-do语句
S → while E do S1
E.code
S1.code
To E.true
To E.false
goto S.begin
S.begin:
……
E.true:
E.false:
while-do语句的属性文法产生式 语义规则
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)
考虑如下语句,
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
goto L1
Lnext:
一遍扫描翻译控制流语句考虑下列产生式所定义的语句,
(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为一个布尔表达式
if 语句的翻译相关产生式
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→?
翻译模式,
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,－,－,－ ’ ) }
while 语句的翻译相关产生式
S→ while E do S(1)
翻译为：
E的代码
S (1)的代码
“真”出口
“假”出口为了便于 "回填 ",改写产生式为,
S→while M 1 E do M2 S1
M→?
翻译模式,
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 }
产生式
L→L;S
改写为：
L→L1; M S
M→?
翻译模式,
1,L→L1; M S
{ backpatch(L1.nextlist,M.quad);
L.nextlist:=S.nextlist }
2,M→?
{ M.quad:=nextquad }
其它几个语句的翻译
1,S→begin L end
{ S.nextlist:=L.nextlist }
2,S→A
{ S.nextlist:=makelist( ) }
3,L→S
{ L.nextlist:=S.nextlist }
翻译语句
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
2.7.5.2 标号与 goto语句标号定义形式
L,S；
标号引用
goto L；
示例：
向后转移：
L1,……
……
goto L1;
向前转移：
goto L1;
……
L1,……
产生式 S?→gotoL的语义动作,
{ 查找符号表；
IF L在符号表中且,定义否,栏为,已,/*向后转移 */
THEN GEN(J,-,-,P)
/*P为 L在符号表中定义的地址 */
ELSE IF L不在符号表中 /*第一个出现的地方 */
THEN BEGIN
把 L填入表中；
置 "定义否 "为 "未 ","地址 "栏为 NXQ；
GEN(J,-,-,0) END
ELSE BEGIN
Q:=L的地址栏中的编号；
置地址栏编号为 NXQ；
GEN(J,-,-,Q)
END /*向前转移,将所有以 L为转移地址的四元式连接起来 */
}
未定义标号的引用链带标号语句的产生式,
S→label S label → i:
label → i,对应的语义动作,
1,若 i所指的标识符 (假定为 L)不在符号表中,则把它填入,置 "类型 "为 "标号 ",定义否为 "已 ","地址 "为 nextquad ；
2,若 L已在符号表中但 "类型 "不为标号或 "定义否 "为
"已 ",则报告出错；
3,若 L已在符号表中，则把标号 "未 "改为 "已 "，然后，
把地址栏中的链头 (记为 q)取出，同时把 nextquad
填在其中，最后，执行 BACKPATCH(q，
nextquad )。
2.7.5.3 CASE语句的翻译语句结构
case E of
C1,S1;
C2,S2;
…
Cn-1,Sn-1;
otherwise,Sn
end
翻译法 (一 )
（当分支不太多，如 10个左右）
T:=E
L1,if T?C1 goto L2
S1的代码
goto next
L2,if T?C2 goto L3
S2的代码
goto next
L3,…
Ln-1,if T?Cn-1 goto Ln
Sn-1的代码
goto next
Ln,Sn的代码
next:
改进（开关表）,
C 1 S 1 的地址
C 2 S
2 的地址
… …
E S n 的地址
由编译器构造一个开关表，产生把 E的传送到末项的第一栏的指令组，并构造一个对 E值查找开关表的循环程序。
运行时循环程序对 E值查找开关表，
当匹配某个 Ci时自动执行对应的 Si。
若不存在匹配，则末项自动匹配，
执行例外语句 Sn。
当 Si不是转移指令时，最后加一个转移指令到整个 CASE语句后。
翻译法 (二 ):
计算 E并放入 T中
goto test
L1,关于 S1的中间码
goto next…
Ln-1,关于 Sn-1的中间码
goto next
Ln,关于 Sn的中间码
goto next
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,-,-)
C 1 P 1
C 2 P 2
C n- 1 P n- 1
L 1 L
1 的四元式首地址
L 2 L
2 的四元式首地址
L n-1 L
n- 1 的四元式首地址
L n L
n 的四元式首地址
Pi是 LI在符号表中的位置
7.6 过程调用的处理过程调用主要对应两种事,
传递参数
转子传地址,把实在参数的地址传递给相应的形式参数调用段预先把实在参数的地址传递到被调用段可以拿到的地方 ；
程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中 ；
过程体对形式参数的引用域赋值被处理 成 对形式单元的间接访问。
翻译方法：把实参的地址逐一放在转子指令的前面,
例如,CALL S(A,X+Y) 翻译为,
计算 X+Y置于 T中的代码
par A /*第一个参数的地址 */
par T /*第二个参数的地址 */
call S /*转子 */
过程调用的翻译过程调用文法,
(1) S → call id (Elist)
(2) Elist → Elist,E
(3) Elist → E
翻译模式
1,S→call id (Elist)
{ for 队列 queue中的每一项 p do
emit(‘param’ p);
emit(‘call’ id.place) }
2,Elist→Elist,E
{ 将 E.place加入到 queue的队尾 }
3,Elist→E
{ 初始化 queue仅包含 E.place }
中间表示（后缀式、三地址代码和 DAG图）
语言中常见结构的翻译
赋值语句
声明语句
数组引用
布尔表达式
控制语句
2.7 语义分析和中间代码产生静态语义检查
类型检查
控制流检查
一致性检查
相关名字检查
名字的作用域分析语法分析器中间代码产生器静态检查器中间代码 优化器中间语言 (复杂性界于源语言和目标语言之间 )的好处：
便于进行与机器无关的代码优化工作
易于移植
使编译程序的结构在逻辑上更为简单明确源语言程序目标语言程序中间语言程序
Compiler
Front End
Compiler
Back End
常用的中间语言：
后缀式 (逆波兰表示 )
三地址代码
三元式
四元式
间接三元式
DAG图表示
2.7.1 中间语言
2.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
的后缀式。
逆波兰表示法不用括号 。 只要知道每个算符的目数,对于后缀式,不论从哪一端进行扫描,都能对它进行唯一分解 。
后缀式的计算
用一个栈实现 。
一般的计算过程是：自左至右扫描后缀式,每碰到运算量就把它推进栈 。 每碰到 k目运算符就把它作用于栈顶的 k个项,并用运算结果代替这
k个项 。
是语法树的后序遍历线性化把表达式翻译成后缀式的语义规则描述产生式
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表示任意二元操作符
,||”表示后缀形式的连接 。
数组 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 +?
2.7.1.2 图表示法图表示法
DAG
抽象语法树有向无环图 (Directed Acyclic Graph，简称
DAG)
对表达式中的每个子表达式,DAG中都有一个结点
一个内部结点代表一个操作符，它的孩子代表操作数
在一个 DAG中代表公共子表达式的结点具有多个父结点（允许它使用多次）
没有父节点的节点称为根节点,dag可以有多个根节点。
DAG举例与（ A+B)+(A+B)对应的 DAG
＋
A B
＋
a:=b*(-c)+b*(-c)的图表示法
assign
a +
*
b uminus
c
DAG
assign
a +
*
b uminus
c
抽象语法树
*
b uminus
c
产生赋值语句抽象语法树的属性文法产 生 式 语义规则
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)
2.7.1.3 三地址代码三地址代码的一般形式：
x:=y op z
三地址代码可以看成是抽象语法树或
DAG的一种线性表示
a:=b*(-c)+b*(-c)的代码
T1:=-c T1:=-c
T2:=b*T1 T2:=b*T1
T3:=-c T5:=T2+T2
T4:=b*T3 a:=T5
T5:=T2+T4
a:=T5
对于抽象语法树的代码 对于 DAG的代码三地址语句的种类
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的地址和指针赋值生成三地址代码时，临时变量的名字对应抽象语法树的内部结点
id:=E
对表达式 E求值并置于变量 T中值
id.place:=T
从赋值语句生成三地址代码的 S-属性文法非终结符号 S有综合属性 S.code，它代表赋值语句 S的三地址代码。
非终结符号 E有如下两个属性：
E.place表示存放 E值的名字 。
E.code表示对 E求值的三地址语句序列 。
函数 newtemp的功能是,每次调用它时,将返回一个不同临时变量名字,如 T1,T2,… 。
为赋值语句生成三地址代码的 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;
E.code:=E1.code || E2.code ||
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=‘ ’
三地址语句的实现四元式三元式间接三元式三地址语句的实现四元式
一个带有四个域的记录结构，这四个域分别称为 op,
arg1,arg2及 result
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
a:=b*(-c)+b*(-c)的四元式三地址语句的实现三元式
通过计算临时变量值的语句的位置来引用这个临时变量
三个域,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)
三地址语句的实现
x[i]:=y
op arg1 arg2
(0) [ ] = x i
(1) assign (0) y
x:=y[i]
op arg1 arg2
(0) = [ ] y i
(1) assign x (0)
三地址语句的实现间接三元式
列出指向三元式的指针,而不是三元式
间接码表,一张指示器表,按运算的先后次序列出有关三元式在三元式表中的位置 。
优点,
方便优化 (只需调整间接表 ）
节省空间 （ 同一四元式不需多重存储 ）
例如，语句
X:=(A+B)*C;
Y:=D↑(A+B)
的间接三元式表示如下表所示。
间接代码
( 1 )
( 2 )
( 3 )
( 1 )
( 4 )
( 5 )
三元式表
OP ARG1 ARG2
(1) + A B
(2) * (1) C
(3),= X (2)
(4) ↑ D (1)
(5),= Y ( 4 )
2.7.2 声明语句当考查一个过程或分程序的一系列声明语句时,便可为局部于该过程的名字分配存储空间 。
对每个局部名字,都将在符号表中建立相应的表项,并填入有关的信息如类型,在存储器中的相对地址等 。
P→ {offset:=0｝
D
D→D;D
D→id:T {enter(id.name,T.type,offset);
offset:=offset+T.width}
T→integer {T.type:=integer;
T.width:=4}
T→real {T.type:=real;
T.width:=8}
T→array[num] of T1 { T.type:=array(num.val,T1.type)
T.width:=num.val× T1.width}
T→↑T1 {T.type:=pointer(T1.type);
T.width:=4}
计算声明语句中名字的类型和相对地址
2.7.3 赋值语句的翻译
7.3.1 简单算术表达式及赋值语句产生赋值语句三地址代码的翻译模式
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 }
2.7.3.2 数组元素的引用数组元素地址的计算：
设 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在编译时可确定，可存放在符号表中 A的表项。
数组元素的引用
id出现的地方也允许下面产生式中的 L出现
L → id [ Elist ] | id
Elist→Elist,E | E
为了便于处理,文法改写为
L→Elist ] | id
Elist→Elist,E | id [ E
注：改写的主要目的是让 id与最左的 E相联系，而不是在 L
生成时与 L联系，这样在整个下标表达式的翻译过程中都可知道关于符号表中关于数组的信息。
引入下列语义变量或语义过程,
Elist.array：用来记录符号表中对应数组名项的指针
Elist.ndim,下标个数计数器
Elist.place,表示临时变量,用来临时存放已形成的 Elist中的下标表达式计算出来的值
limit(array,j),函数过程,它给出数组 array
的第 j维的长度每个代表变量的非终结符 L有两项语义值
L.place：
若 L为简单变量 i,指变量 i的符号表入口
若 L为下标变量，指存放 CONSPART的 临时变量的整数码
L.offset,
若 L为简单变量,null，
若 L为下标变量，指存放 VARPART的临时变量的整数码在赋值语句中加入数组元素后
(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
(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)}
(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 }
(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 }
(7) Elist→ Elist1,E
{ t:=newtemp;
m:=Elist.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 }
(8) Elist→id [ E
{ Elist.place:=E.place;
Elist.ndim:=1;
Elist.array:=id.place }
例 设 A为一个 10× 20的数组，即 n1=10,
n2=20,low1=1,low2=1并设 w=4。对赋值语句 x:=A[y,z]被翻译成什么三地址语句序列？
t1=elist.place* limit(Elist1.array,2)
=y*20
T1=t1+E.Place=t1+z
例 设 A为一个 10× 20的数组，即 n1=10,
n2=20,low1=1,low2=1并设 w=4。对赋值语句 x:=A[y,z]被翻译成如下三地址语句序列：
T1:=y*20
T1:=T1 +z
T2:=A-84
T3:=4*T1
T4:=T2[T3]
x:=T4
类型转换用 E.type表示非终结符 E的类型属性对应产生式 E?E1 op E2的语义动作中关于 E.type的语义规则可定义为：
{ if E1.type=integer and
E2.type=integer
E.type:=integer
else E.type:=real }
算符区分为整型算符 opi和实型算符 opr，
x:=y＋ i*j
其中 x,y为实型； i,j为整型 。 这个赋值句产生的三地址代码为：
T1:=i int* j
T3:=inttoreal T1
T2:=y real+ T3
x:=T2
关于产生式 E→E 1 ＋ 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
end
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
u:=newtemp;
emit (u ‘:=’ ‘inttoreal’ E 2.place);
emit (E.place ‘:=’ E 1.place ‘real+’ u);
E.type:=real
end
else E.type:=type_error}
2.7.3.3 记录中域的引用符号表表项之中保存记录中的域的类型和相对地址信息每个记录类型单独一张符号表，用在符号表中查找名字的方法可查找记录的域
2.7.4 布尔表达式的翻译布尔表达式的两个基本作用,
用于逻辑演算,计算逻辑值 ;
用于控制语句的条件式,
产生布尔表达式的文法,
E→E or E | E and E |? E | (E) | i rop i | i
计算布尔表达式通常采用两种方法,
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
两种不同的翻译方法,
第一种翻译法：
A or B and C=D翻译成
(1) (=,C,D,T1)
(2) (and,B,T1,T2)
(3) (or,A,T2,T3)
第二种翻译法适合于作为条件表达式的布尔表达式使用,
2.7.4.1 数值表示法
a or b and not c 翻译成
T1:=not c
T2:=b and T1
T3:=a or T2
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:
True用 1表示,False用 0表示关于布尔表达式的数值表示法的翻译模式过程 emit将三地址代码送到输出文件中
nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程 emit便把
nextstat加 1
关于布尔表达式的数值表示法的翻译模式
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 }
布尔表达式 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
7.4.2 作为条件控制的布尔式翻译条件语句 if E then S1 else S2
赋予 E 两种出口,一真一假
E.code
S1.code
S2.code
To E.true
To E.false
goto S.next
S.next ……
E.true:
E.false:
例：把语句,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:
每次调用函数 newlabel后都返回一个新的符号标号对于一个布尔表达式 E，引用两个标号
E.true是 E为 ‘ 真 ’ 时控制流转向的标号
E.false是 E为 ‘ 假 ’ 时控制流转向的标号产生布尔表达式三地址代码的语义规则产生式 语义规则
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
产生布尔表达式三地址代码的语义规则产生式 语义规则
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
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;
E.code:=E1.code
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)
考虑如下表达式：
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
goto Lfalse
布尔表达式的翻译两遍扫描
为给定的输入串构造一棵语法树；
对语法树进行深度优先遍历，进行语义规则中规定的翻译。
一遍扫描一遍扫描实现布尔表达式的翻译采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定四元式 (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所应的四元式中需回填,真,,,假,
出口的四元式的标号所构成的链表例如,假定 E的四元式中需要回填 "真 "出口的 p,q,r三个四元式,则 E.truelist为下列链,
(p) (x,x,x,0)
…
(q) (x,x,x,p)
…
(r) (x,x,x,q)
链尾
E,truelist =r
为了处理 E.truelist和 E.falselist,引入下列语义变量和过程,
变量 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) | E1 and M E2
(3) | not E1
(4) | (E1)
(5) | id1 relop id2
(6) | id
(7) M→?
布尔表达式的翻译模式
(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}
布尔表达式的翻译模式
(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);
E.falselist:=makelist(nextquad+1);
emit(‘jnz’ ‘,’ id,place ‘,’ ‘－ ’ ‘,’ ‘ 0’)；
emit(‘ j,-,-,0’) }
布尔表达式的翻译模式
(7) M→?
{ M.quad:=nextquad }
作为整个布尔表达式的 "真 ""假 "出口 (转移目标 )仍待回填,
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
2.7.5 控制语句的翻译考虑下列产生式所定义的语句
S → if E then S1
| if E then S1 else S2
| while E do S1
其中 E为布尔表达式。
if-then语句
S → if E then S1
E.code
S1.code
To E.true
To E.false
……
E.true:
E.false:
if-then语句的属性文法产生式 语义规则
S→if E then S1 E.true:=newlabel;
E.false:=S.next;
S1.next:=S.next
S.code:=E.code ||
gen(E.true ‘:’) || S1.code
if-then-else语句
S → if E then S1 else S2
E.code
S1.code
S2.code
To E.true
To E.false
goto S.next
S.next ……
E.true:
E.false:
if-then-else语句的属性文法产生式 语义规则
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
while-do语句
S → while E do S1
E.code
S1.code
To E.true
To E.false
goto S.begin
S.begin:
……
E.true:
E.false:
while-do语句的属性文法产生式 语义规则
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)
考虑如下语句,
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
goto L1
Lnext:
一遍扫描翻译控制流语句考虑下列产生式所定义的语句,
(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为一个布尔表达式
if 语句的翻译相关产生式
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→?
翻译模式,
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,－,－,－ ’ ) }
while 语句的翻译相关产生式
S→ while E do S(1)
翻译为：
E的代码
S (1)的代码
“真”出口
“假”出口为了便于 "回填 ",改写产生式为,
S→while M 1 E do M2 S1
M→?
翻译模式,
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 }
产生式
L→L;S
改写为：
L→L1; M S
M→?
翻译模式,
1,L→L1; M S
{ backpatch(L1.nextlist,M.quad);
L.nextlist:=S.nextlist }
2,M→?
{ M.quad:=nextquad }
其它几个语句的翻译
1,S→begin L end
{ S.nextlist:=L.nextlist }
2,S→A
{ S.nextlist:=makelist( ) }
3,L→S
{ L.nextlist:=S.nextlist }
翻译语句
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
2.7.5.2 标号与 goto语句标号定义形式
L,S；
标号引用
goto L；
示例：
向后转移：
L1,……
……
goto L1;
向前转移：
goto L1;
……
L1,……
产生式 S?→gotoL的语义动作,
{ 查找符号表；
IF L在符号表中且,定义否,栏为,已,/*向后转移 */
THEN GEN(J,-,-,P)
/*P为 L在符号表中定义的地址 */
ELSE IF L不在符号表中 /*第一个出现的地方 */
THEN BEGIN
把 L填入表中；
置 "定义否 "为 "未 ","地址 "栏为 NXQ；
GEN(J,-,-,0) END
ELSE BEGIN
Q:=L的地址栏中的编号；
置地址栏编号为 NXQ；
GEN(J,-,-,Q)
END /*向前转移,将所有以 L为转移地址的四元式连接起来 */
}
未定义标号的引用链带标号语句的产生式,
S→label S label → i:
label → i,对应的语义动作,
1,若 i所指的标识符 (假定为 L)不在符号表中,则把它填入,置 "类型 "为 "标号 ",定义否为 "已 ","地址 "为 nextquad ；
2,若 L已在符号表中但 "类型 "不为标号或 "定义否 "为
"已 ",则报告出错；
3,若 L已在符号表中，则把标号 "未 "改为 "已 "，然后，
把地址栏中的链头 (记为 q)取出，同时把 nextquad
填在其中，最后，执行 BACKPATCH(q，
nextquad )。
2.7.5.3 CASE语句的翻译语句结构
case E of
C1,S1;
C2,S2;
…
Cn-1,Sn-1;
otherwise,Sn
end
翻译法 (一 )
（当分支不太多，如 10个左右）
T:=E
L1,if T?C1 goto L2
S1的代码
goto next
L2,if T?C2 goto L3
S2的代码
goto next
L3,…
Ln-1,if T?Cn-1 goto Ln
Sn-1的代码
goto next
Ln,Sn的代码
next:
改进（开关表）,
C 1 S 1 的地址
C 2 S
2 的地址
… …
E S n 的地址
由编译器构造一个开关表，产生把 E的传送到末项的第一栏的指令组，并构造一个对 E值查找开关表的循环程序。
运行时循环程序对 E值查找开关表，
当匹配某个 Ci时自动执行对应的 Si。
若不存在匹配，则末项自动匹配，
执行例外语句 Sn。
当 Si不是转移指令时，最后加一个转移指令到整个 CASE语句后。
翻译法 (二 ):
计算 E并放入 T中
goto test
L1,关于 S1的中间码
goto next…
Ln-1,关于 Sn-1的中间码
goto next
Ln,关于 Sn的中间码
goto next
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,-,-)
C 1 P 1
C 2 P 2
C n- 1 P n- 1
L 1 L
1 的四元式首地址
L 2 L
2 的四元式首地址
L n-1 L
n- 1 的四元式首地址
L n L
n 的四元式首地址
Pi是 LI在符号表中的位置
7.6 过程调用的处理过程调用主要对应两种事,
传递参数
转子传地址,把实在参数的地址传递给相应的形式参数调用段预先把实在参数的地址传递到被调用段可以拿到的地方 ；
程序控制转入被调用段之后，被调用段首先把实在参数的地址抄进自己相应的形式单元中 ；
过程体对形式参数的引用域赋值被处理 成 对形式单元的间接访问。
翻译方法：把实参的地址逐一放在转子指令的前面,
例如,CALL S(A,X+Y) 翻译为,
计算 X+Y置于 T中的代码
par A /*第一个参数的地址 */
par T /*第二个参数的地址 */
call S /*转子 */
过程调用的翻译过程调用文法,
(1) S → call id (Elist)
(2) Elist → Elist,E
(3) Elist → E
翻译模式
1,S→call id (Elist)
{ for 队列 queue中的每一项 p do
emit(‘param’ p);
emit(‘call’ id.place) }
2,Elist→Elist,E
{ 将 E.place加入到 queue的队尾 }
3,Elist→E
{ 初始化 queue仅包含 E.place }
