1
§ 5.3 中间代码
一、逆波兰 ------主要用于表达式
1、表达式的逆波兰表示
后缀式, e1e2……e kθ θ是 k目运算符 (k>=1)
特点,运算量在前,运算符在后,无括号
例,a+b*c 逆波兰 a bc*+
a*(b+c/d) 逆波兰 ab cd/+*
a*(b+c) 逆波兰 a bc+*
(a+b)*(c+d) 逆波兰 ab+cd+*
2
2、后缀式的计算,利用分析栈
计算步骤,自左向右扫描后缀式
遇到运算量进栈
遇到 k目运算符则作用于栈顶的 k项
用运算结果代替这 k项,
例,计算 ab+c*
a,b + c *
b
a
t1 t2 c
t1
3
3、后缀式的推广
(1)赋值语句的后缀式
a:=e 逆波兰, ae:=
例, a:=3*(b+c) 逆波兰 a3bc+*:=
(2)条件语句的后缀式
例, if e then x else y
将 if— then — else 看成三目运算符￥
逆波兰,exy ￥
缺点,x,y 都被计值
4
改进,将后缀式放在一个一维数组 POST[n]中
运算符 后缀式 意义
无条件转移,jump p jump 转到 POST[p]
条件转移,小于转 jlt e1e2 p jlt e1<e2转 POST[p]
零转 jez e p jez e=0转 POST[p]
例,if e then x else y表示成
e’ p1 jez x’ p2 jump y’ …
5
4、语法制导生成后缀式
E·code:构成后缀式的符号串
‖,两串并置运算
Op:运算符
产生式 语义动作
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}
6
后缀式放入 POST[k]中
产生式 语义动作
E→E (1) op E(2) {POST[k]:=op; k=k+1}
E→(E (1)) { }
E →id {POST[k]:=id; k=k+1}
7
二、三元式和树
1、三元式
（ 1）表示形式
op ARG1 ARG2
其中,op：运算符
ARG1:第一运算量
ARG2:第二运算量
? 表达式及各种语句都可以表示成三元式
? 三元式出现的顺序为表达式的计值顺序
? 一目运算任选 ARG1或 ARG2
8
例,A+B*C的三元式
op ARG1 ARG2
(1) * B C
(2) + A (1)
ARG1和 ARG2,
指示器，指向符号表的某一位置或三元式表自身的某
一项。
9
例,X:=a*b+c
op ARG1 ARG2
(1) * a b
(2) + (1) c
(3),= X (2)
例,(A∧ B)∨ (?C ∨ D)
op ARG1 ARG2
(1) ∧ A B
(2) ? C _
(3) ∨ (2) D
(4) ∨ (1) (3)
10
(2)语法制导生成三元式
E·VAL,指示器，或指向符号表的某一项或三元式
自身的某一项
TRIP(op,ARG1,ARG2):语义过程，产生新的三元式
（ op,ARG1,ARG2)并回送三元式在表中的位置。
ENTRY(id):语义过程，查找标识符 id在符号表中
的位置
11
语法制导生成三元式
产生式 语义动作
E→E (1) op E(2)
{E ·VAL= TRIP(op,E(1) ·VAL,E(2) ·VAL) }
E→(E (1))
{E · VAL = E(1) · VAL }
E→ － E(1)
{E ·VAL= TRIP(@,E(1) ·VAL,_)} @代表一元负运算
E →id
{E · VAL = ENTRY(id)}
12
实现 ENTRY(i)
? 定义两个语义函数
LOOKUP(NAME),
对 NAME查符号表,若此名出现在表中,
则将其表项位置作为 LOOKUP的值 ;
否则,LOOKUP为空,
FILLSYM(NAME),
在符号表中开辟一新项,项名
为 NAME,把此项的入口作为 FILLSYM的值,
13
? ENTRY定义为,
FUNCTION ENTRY(NAME)
BEGIN
ENTRY:=LOOKUP(NAME);
IF ENTRY=NULL THEN ERROR
[ENTRY:=FILLSYM(NAME)]
END
14
2、间接三元式 去除重复三元式，便于优化
用一张间接码表辅以三元式表来表示中间代码,
间接码表按运算的先后顺序列出有关的三元式
在三元式表中的位置,
15
例, x:=(a+b)*c
y:=d*(a+b)
一般三元式,
op ARG1 ARG2
(1) + a b
(2) * (1) c
(3),= x (2)
(4) + a b
(5) * d (4)
(6),= y (5)
间接三元式
op ARG1 AGR2
(1) + a b
(2) * (1) c
(3),= x (2)
(4) * d (1)
(5),= y (4)
间接码表
(1)(2)(3)(1)(4)(5)
16
3、树
用树形数据结构来表示一个表达式或语句,
(1)树
①简单变量或常数的树就是该变量或常数本身,
② 如果表示 e1和 e2的树为 T1和 T2,
则 e1+e2,e1*e2,－ e1的树为,
+ * －
T1 T2 T1 T2 T1
17
例,A*B+C*D
树, + 三元式
op ARG1 ARG2
* * (1) * A B
(2) * C D
A B C D (3) + (1) (2)
18
(2)语法制导生成树形表示
E·VAL:指示器,指向树的一个结点,
NODE(op,LEFT,RIGHT),
建立一棵新树,根为 op,LEFT,RIGHT分别为左右
分支；从 NODE回送的值是一个指示器,指向这棵新树
的根,
UNARY(op,CHILD),
生成只有一个分支 CHILD的子树,
LEAF(i):建立一个以 i为标志的结点并回送此结点的地址,
19
产生式和语义动作
E→E (1) op E(2)
{E ·VAL= NODE(op,E(1) ·VAL,E(2) ·VAL) }
E→(E (1))
{E · VAL = E(1) · VAL }
E→ － E(1)
{E ·VAL= UNARY(@,E(1) ·VAL,_)} @代表一元负运算
E →id
{E · VAL = LEAF(id)}
20
三、四元式
1、表示 Op ARG1 ARG2 RESULT
其中,
ARG1,ARG2,RESULT(运算结果 )是用户定义的变量
或引进的临时变量,指向符号表的入口位置,
2、说明
①一目运算用 ARG1
② 四元式出现的顺序与表达式的计值顺序一致,
③ 临时变量,可以象变量名一样填入符号表,
④ 四元式之间通过临时变量联系,易于优化,
21
例,A:=－ B*(C+D)
op ARG1 ARG2 RESULT
(1) @ B _ T1
(2) + C D T2
(3) * T1 T2 T3
(4),= T3 _ A
其中,Ti 是临时变量
22
§ 5.4 自下而上分析法：简单语句的翻译
一、语句的翻译
1、语句：各种语句均有语义动作
①可执行语句 ----生成四元式
②不可执行语句 ---填写符号表
2、语句翻译的构思要点
①确定语句的目标代码结构
②中间代码
③添加语义动作
3、数据结构：符号表，四元式表，临时变量表
23
二、赋值语句和表达式到四元式的翻译
1、定义
? NEWTEMP,
函数过程，产生新的临时变量 T1,T2,…… 。
? E·PLACE,
与非终结符号 E相关的语义变量，表示存放 E值的变量
名在符号表的入口或是一个整数码。
? GEN(op,ARG1,ARG2,RESULT),
语义过程，把四元式填入四元式表中。
? ENTRY(id):语义过程，查找标识符 id在符号表中
的位置
24
2、文法
S→A
A →V:=E
E →E+T ∣ T
T → T*F ∣ F
F →(E) ∣ i
V →i
此文法为 SLR(1)文法,可以构造出 SLR(1)分析表,
25
3、产生式及语义动作
(1) S→A
{ }
(2) A →V:=E
{GEN(:=,E·PLACE,_,V·PLACE}
(3) E(1) →E (2)+T
{E(1)·PLACE:=NEWTEMP;
GEN(+,E(2)·PLACE,T·PLACE,E(1) ·PLACE}
(4)E → T
{E·PLACE:=T·PLACE}
26
(5) T(1) → T (2)*F
{T(1)·PLACE:=NEWTEMP;
GEN(*,T(2)·PLACE,F·PLACE,T(1) ·PLACE
(6) T → F
{T·PLACE:=F·PLACE}
(7) F →(E)
{F·PLACE:=E·PLACE}
(8) F → i
{F·PLACE:=ENTRY(i)}
(9)V →i
{V·PLACE:=ENTRY(i)}
27
例,分析句子 X:=B+C*D 其中 X,B,C,D为终结符
步
骤
状态栈 符号栈 输入 动
作
语义操作
1 0 # X S2
2 02 #X,= R9 VX·PLACE:=ENTRY(X)
3 03 #VX,= S4
4 034 #VX:= B S9
5 0349 #VX:=B + R8 FB·PLACE:=ENTRY(B)
6 0347 #VX:=FB + R6 TB·PLACE:=FB·PLACE
7 0346 #VX:=TB + R4 EB·PLACE:=TB·PLACE
8 0345 #VX:=EB + S10
9 034510 #VX:=EB+ C S9
28
步
骤
状态栈 符号栈 输
入
动
作
语义操作
10 0345109 #VX:=EB+C * R8 FC·PLACE:=ENTRY(C)
11 0345107 # VX:=EB+FC * R6 TC·PLACE:=FC·PLACE
12 03451013 #VX:=EB+TC * S11
13 0345101311 #VX:=EB+TC* D S9
14 03451013119 #VX:=EB+TC*D # R8 FD·PLACE:=ENTRY(D)
15 03451013117 #VX:=EB+TC*FD # R5 (*,TC·PLACE,
FD·PLACE,T1 ·PLACE)
16 03451013 #VX:=EB+TT1 # R3 (+,EB·PLACE,
T1·PLACE,T2·PLACE)
17 0345 # VX:=ET2 # R2 (:=,T2·PLACE,_,X)
18 01 #A #
29
§ 5.5 作为条件控制语句的布尔式的翻译
1、布尔式的作用
if E then S1 else S2;
E的作用,控制对 S1和 S2的选择,找到出口,E值不保留,
E的出口,真出口 ----- S1语句
假出口 ----- S2语句
F T
E的代码
S1的代码
S2的代码
30
2、布尔式的源文法
G[E],
E→E ∧ E
E→E ∨ E
E→ ?E
E→(E)
E→i rop i
E→i
其中, rop为关系运算符,>,<,=,≧,≦,≠
31
3、布尔式的四元式形式
(jnz,A,_,p),
若 A为真转第 p个四元式
(jez,A,_,p),
若 A为假转第 p个四元式
(jθ,A1,A2,p),
若的 A1 θ A2关系为真转第 p个四元式
(j,_,_,p),
无条件转第 p个四元式
32
例, if A∨ B<D then S1 else S2的四元式序列
(1) (jnz,A,_,5) A的真出口 5
(2) (j,_,_,3) A的假出口 3
(3) (j<,B,D,5) B的真出口 5
(4) (j,_,_,p+1) B的假出口 p+1
(5) (关于 S1的四元式序列 ) E的真出口
……
(p) (j,_,_,q)
(p+1) (关于 S2的四元式序列 ) E的假出口
(q) ……
问题：确定布尔式的真、假出口
确定目标地址
33
(1) 确定布尔式的真、假出口,
分情况讨论,
① E→E (1) ∨ E(2) (E(1)为真,则 E为真 )
E(1)的真出口,就是 E的真出口
E(1)的假出口,就是 E(2)的第一个四元式
E(2)的真假出口,就是 E的真假出口
34
② E→E (1) ∧ E(2) (E(1)为假,则 E为假 )
E(1)的假出口,就是 E的假出口
E(1)为真,计 E(2),
E(1)的 真出口,就是 E(2)的第一个四元式
E(2)的真假出口,就是 E的真假出口
③ E→ ? E(1)
E(1)的真出口,就是 E的假出口
E(1)的假出口,就是 E的真出口
35
(2)如何确定目标地址
①拉链 ---回填技术,
自下而上的语法分析中,一个布尔式的真假出口往往
不能在产生四元式的同时填上,需要将这些未完成的四
元式地址作为语义值保留下来,待到整个表达式的四元
式产生后回来填这个未填的转移目标,
② 对 E设两个语义值,
E·TC:表达式 E所对应的四元式序列的 真 出口链的首地址,
E·FC:表达式 E所对应的四元式序列的 假 出口链的首地址,
36
例,p,q,r三个四元式需
回填同一真出口
的目标地址
(p) (X,X,X,0)
(q) (X,X,X,0)
(r) (X,X,X,0)
拉链过程如右,
(p) (X,X,X,0)
(q) (X,X,X,p)
E.TC=r,链尾 =p
0是链尾
的标志
回填过程，设目标地址为 t
(r)(X,X,X,0) q)(r) X,X,)
t
37
③ 定义
? NXQ:指针,指向下一个将要产生但尚未产生的
四元式的地址,每执行一次 GEN过程,NXQ
值自动加 1,
? MERGE(p1,p2):函数,将以 p1为首和 p2为首的两
条链合并,并且 p1跟在 p2之后，返回合并后的链
首。
38
Procedure MERGE(p1,p2)
if p2=0 then MERG:=p1 else
begin p:= p2 ;
while 四元式 p的第四区段不为 0 do
p:=四元式 p的第四区段内容 ;
在四元式 p的第四区段填入 p1;
MERGE:= p2;
end
39
? BACKPATCH(p,t):回填过程,把 p所链接的每个四元式
的第四区段都填为 t,
Procedure BACKPATCH(p,t)
begin
Q:=p;
while Q≠0 do
begin
q:=四元式 Q的第四区段内容 ;
在四元式 Q的第四区段填入 t;
Q:=q
end
end
40
5.6 程序流控制语句的翻译
? 一般而言，程序流程控制可大致分为 顺序结构
（如复合语句）,分枝结构 （如 if条件语句和
实现多分枝的 case语句等）,循环结构 （如 for
循环,while循环,repeat循环等等）三类。另
外,GOTO语句也是一类常见改变流程的 控制
语句 。下面，将对常见的一些控制结构的翻译
进行讨论。
41
5.6.1 常见控制结构的翻译
? 程序设计理论已证明,任何程序均可由 序列结构, 条
件分枝结构 和 while循环 三种结构等价地表示。这三
类结构可用如下的文法描述,
1,S→ if E then S(1)
2,| if E then S(1) else S(2)
3,| while E do S(1)
4,| begin L end (5.8)
5,| A
6,L→ L ； S
7,| S
? S,L,A分别代表 语句, 语句序列 和 赋值语句, E代表
布尔表达式 。约定 else与其前离它最近的尚未得到匹
配的 then相匹配。为 同名文法符号 增加了 上标 。
42
条件语句 的处理方法
? 布尔表达式 E具有两个属性：
E.TC与 E.FC，用来分别指示 E
的真链和假链的链首。
? 当 E出现在条件语句 if E then
S1 else S2中时，当语法分析器
扫视到 then时,E的 真出口已
经确定，此时即可用 NXQ对 E
的 真链进行回填；而当扫视到
else时，即可用 NXQ对 E的 假
链进行回填。
T
E的代码
S1的代码
S2的代码
F
if语句的代码结构
43
while控制语句的翻译文法
S→ while E do S(1)
由于 while循环要求每次执行
完循环体之后，应无条件转
向循环判断条件 E处，因此，
需将 E的第一四元式序号记下
来，以便在翻译完 S后可产生
一个转向此处的四元式。
E的代码
S的代码
T
F
while语句的
代码结构
44
控制语句翻译应用举例
【 例 5.4】 将 语句 while (a<b) do if (c>d) then
x:=y+z 翻译成四元式序列。假定所产生的四元式
序列从编号 100开始。翻译结果如下,
100 j<,a,b,102
S.Chain→ 101 j,0,0,0
102 j>,c,d,104
103 j,0,0,100
104 +, y,z,T
105 =,T,0,x
106 j,0,0,100
NXQ→ 107
45
5.6.2 FOR循环 语句的翻译
? FOR循环语句可由如下产生式定义 (假定步长为 1),
S→ for identifier,=<循环表 > do S(1)
<循环表 >→ Expr(1) to Expr(2) (5.12)
? 假定循环控制变量 identifier为整型简单变量，
Expr(1)与 Expr(2)都是整数或整型简单表达式，且
Expr(2)的值可变。上述 FOR语句在语义上等价于
identifier = Expr(1);
LOOP,if (identifier <= Expr(2)) {
S(1);
identifier++;
goto LOOP; }
46
Expr(1)的四元式序列,结果 =>临时变量 T1
(=,T1,0,i ) (i=Entry(identifier) )
Expr(2)的四元式序列,结果 =>临时变量 T2
(p) ( j≤,identifier,T2,p+2)
(p+1) ( j,0,0,0 ) ← S.Chain
(p+2) S(1)的四元式序列
(q) (+,identifier,1,identifier)
(q+1) ( j,0,0,p)
(q+2) ← NXQ
identifier = Expr(1);
LOOP,if (identifier <= Expr(2)) {
S(1); identifier++; goto LOOP; }
47
5.6.3 语句 标号 及 GOTO语句的翻译
? 语句标号 用于标识一个语句，可以通过产生式
Statement→ label ':' Statement (5.13)
来定义。
? 通常把源程序中形如,label, Statement”的 标号 出现，
称为 定义性出现 。
? 通过执行形如 GOTO label 的转向语句，把控制无条件
地转移到由 标号 label 所标识的语句。这种出现在 GOTO
语句或其它类似语句中的 标号,称为 使用性 标号 。
? 在许多语言中，允许 标号 的 使用性出现 位于 定义性出现 之
前。
48
标号 具有的 语义属性
? 标号的语义属性,
– 名字
– 它所标识语句的四元式序列的 首地址 （序号）。
– 用于标志该 标号是否已被定义 的属性，其初值为 0
（表示尚未定义）。
? 对于一个标号而言，它在符号表中的登记项通
常有如下的内容,
NAME | [CAT] | DEF | … | ADDR
名字
[label] 0|1 四元式序号 /链
49
goto语句的翻译
? 对于 GOTO L，产生形如 （ j,0,0,p） 的四元式。
– 若此时 L表项的 DEF域为 1（即已定义），则将相应
的 ADDR域作为此四元式的转向目标 (p=ADDR);
– 若 DEF=0，利用转移四元式的 Result域将所有转向
同一目标的四元式拉成一个链，待 L有定义时回填，
链首由 L在表中 的 ADDR域指示。
源程序 四元式
goto L; (p) (j,0,0,0)
… …
goto L; (q) (j,0,0,p)
… …
goto L; (r) (j,0,0,q)
NAME
CAT
DEF
…
ADDR
…
…
…
…
…
lab 0 …
r
50
5.6.4 情况语句的翻译
多分枝的语句结构,
case Expr of
C1,S1;
C2,S2;
……
Cn-1:Sn-1; (5.17)
else Sn
end
语义,当 Expr的当前值等于
某个 Ci时, 则执行 Ci所标识的
语句 Si；若 Expr的值不等任
何一个 Ci,则执行 ELSE之后的
语句 Sn,执行完语句 Si之后,
将控制转至后继语句 。
Expr=
S1 S2 Sn …
51
CASE语句的处理方法
? 为实现 CASE语句的语义功
能, 可将 CASE语句翻译为
具有如下结构的中间代码
序列 (向前转移 )
T=Expr
goto CHECK
L1,语句 S1的代码
goto NEXT
L2,语句 S2的代码
goto NEXT
……
Ln-1,语句 Sn-1的代码
goto NEXT
Ln,语句 Sn的代码
goto NEXT
CHECK,if T=C1 goto L1
if T=C2 goto L2
……
if T=Cn-1 goto Ln-1
goto Ln
NEXT,
52
翻译 CASE语句的过程
? 上述代码结构的特点,把检测 Expr之值以及按不同结果转
向不同的代码, 集中地放在尾部, 这有利于产生效率较高
的目标代码 。 翻译 CASE语句的过程大致如下,
1.当遇到关键字 CASE时, 产生内部标号 CHECK及 NEXT，
并把填入符号表, 其 ADDR及 DEF域均填写为 0,再产生一
临时变量 T。
2.产生相应于 T=Expr的四元式 。
3.当扫视到关键字 OF时,将 NXQ的当前值填入标号 CHECK
在 符号表登记项中的 ADDR 域 。 并产生四元式
(j,0,0,0)(即 goto CHECK),其中的转移目标待回填 。 此
外,再设置一个名为 QUEUE的队列 (初值为空 ),供翻译过
程存放信息用 。
53
翻译 CASE语句的过程 (续 )
4.当扫视到每一, Ci”时, 产生相应的内部标号 Li,并把它记入符号
表, 其 ADDR域为 NXQ的当前值 (即 Si的第一四元式的序号 ),
其次,将序偶 (Ci,Pi)置入 QUEUE队列 (若 CASE语句出现嵌套, 则
不同层次的 CASE语句应有不同的 QUEUE队列 ),其中 Pi是 Li在符
号表中的序号 。
接着,产生语句 Si的四元式序列 。 其后再产生一个相应于 goto
NEXT的无条件转移四元式 (j,0,0,0),由于 NEXT地址尚未确定,
故应进行拉链 。
5.当扫视到关键字 ELSE时,产生内部标号 Ln并填入符号表,将其
ADDR域填为 NXQ当前值,在队列 QUEUE中加入序偶 (True,Pn),
然后,类似于第四步, 产生 Sn和 goto NEXT的四元式 。
54
翻译 CASE语句的过程 (续 )
6.当扫视 END时,以 NXQ当前值回填相应于 goto CHECK的链,再
从队列 QUEUE中依次取出各序偶 (Ci,Pi),构造四元式序列
(case,C1,P1,0)
(case,C2,P2,0)
… …
(case,Cn,Pn-1,0)
(case,True,Pn,0)
(label,NEXT,0,0)
其中, 四元式 (case,Ci,Pi,0)是相应于条件转移语句 if(T= Ci)
goto Li 的四元式, case是事先定义的一个内部运算符,
在产生四元式 (label,NEXT,0,0) 时, 应以 NEXT的地址回填相
应于各 goto NEXT 语句的四元式链 。
§ 5.3 中间代码
一、逆波兰 ------主要用于表达式
1、表达式的逆波兰表示
后缀式, e1e2……e kθ θ是 k目运算符 (k>=1)
特点,运算量在前,运算符在后,无括号
例,a+b*c 逆波兰 a bc*+
a*(b+c/d) 逆波兰 ab cd/+*
a*(b+c) 逆波兰 a bc+*
(a+b)*(c+d) 逆波兰 ab+cd+*
2
2、后缀式的计算,利用分析栈
计算步骤,自左向右扫描后缀式
遇到运算量进栈
遇到 k目运算符则作用于栈顶的 k项
用运算结果代替这 k项,
例,计算 ab+c*
a,b + c *
b
a
t1 t2 c
t1
3
3、后缀式的推广
(1)赋值语句的后缀式
a:=e 逆波兰, ae:=
例, a:=3*(b+c) 逆波兰 a3bc+*:=
(2)条件语句的后缀式
例, if e then x else y
将 if— then — else 看成三目运算符￥
逆波兰,exy ￥
缺点,x,y 都被计值
4
改进,将后缀式放在一个一维数组 POST[n]中
运算符 后缀式 意义
无条件转移,jump p jump 转到 POST[p]
条件转移,小于转 jlt e1e2 p jlt e1<e2转 POST[p]
零转 jez e p jez e=0转 POST[p]
例,if e then x else y表示成
e’ p1 jez x’ p2 jump y’ …
5
4、语法制导生成后缀式
E·code:构成后缀式的符号串
‖,两串并置运算
Op:运算符
产生式 语义动作
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}
6
后缀式放入 POST[k]中
产生式 语义动作
E→E (1) op E(2) {POST[k]:=op; k=k+1}
E→(E (1)) { }
E →id {POST[k]:=id; k=k+1}
7
二、三元式和树
1、三元式
（ 1）表示形式
op ARG1 ARG2
其中,op：运算符
ARG1:第一运算量
ARG2:第二运算量
? 表达式及各种语句都可以表示成三元式
? 三元式出现的顺序为表达式的计值顺序
? 一目运算任选 ARG1或 ARG2
8
例,A+B*C的三元式
op ARG1 ARG2
(1) * B C
(2) + A (1)
ARG1和 ARG2,
指示器，指向符号表的某一位置或三元式表自身的某
一项。
9
例,X:=a*b+c
op ARG1 ARG2
(1) * a b
(2) + (1) c
(3),= X (2)
例,(A∧ B)∨ (?C ∨ D)
op ARG1 ARG2
(1) ∧ A B
(2) ? C _
(3) ∨ (2) D
(4) ∨ (1) (3)
10
(2)语法制导生成三元式
E·VAL,指示器，或指向符号表的某一项或三元式
自身的某一项
TRIP(op,ARG1,ARG2):语义过程，产生新的三元式
（ op,ARG1,ARG2)并回送三元式在表中的位置。
ENTRY(id):语义过程，查找标识符 id在符号表中
的位置
11
语法制导生成三元式
产生式 语义动作
E→E (1) op E(2)
{E ·VAL= TRIP(op,E(1) ·VAL,E(2) ·VAL) }
E→(E (1))
{E · VAL = E(1) · VAL }
E→ － E(1)
{E ·VAL= TRIP(@,E(1) ·VAL,_)} @代表一元负运算
E →id
{E · VAL = ENTRY(id)}
12
实现 ENTRY(i)
? 定义两个语义函数
LOOKUP(NAME),
对 NAME查符号表,若此名出现在表中,
则将其表项位置作为 LOOKUP的值 ;
否则,LOOKUP为空,
FILLSYM(NAME),
在符号表中开辟一新项,项名
为 NAME,把此项的入口作为 FILLSYM的值,
13
? ENTRY定义为,
FUNCTION ENTRY(NAME)
BEGIN
ENTRY:=LOOKUP(NAME);
IF ENTRY=NULL THEN ERROR
[ENTRY:=FILLSYM(NAME)]
END
14
2、间接三元式 去除重复三元式，便于优化
用一张间接码表辅以三元式表来表示中间代码,
间接码表按运算的先后顺序列出有关的三元式
在三元式表中的位置,
15
例, x:=(a+b)*c
y:=d*(a+b)
一般三元式,
op ARG1 ARG2
(1) + a b
(2) * (1) c
(3),= x (2)
(4) + a b
(5) * d (4)
(6),= y (5)
间接三元式
op ARG1 AGR2
(1) + a b
(2) * (1) c
(3),= x (2)
(4) * d (1)
(5),= y (4)
间接码表
(1)(2)(3)(1)(4)(5)
16
3、树
用树形数据结构来表示一个表达式或语句,
(1)树
①简单变量或常数的树就是该变量或常数本身,
② 如果表示 e1和 e2的树为 T1和 T2,
则 e1+e2,e1*e2,－ e1的树为,
+ * －
T1 T2 T1 T2 T1
17
例,A*B+C*D
树, + 三元式
op ARG1 ARG2
* * (1) * A B
(2) * C D
A B C D (3) + (1) (2)
18
(2)语法制导生成树形表示
E·VAL:指示器,指向树的一个结点,
NODE(op,LEFT,RIGHT),
建立一棵新树,根为 op,LEFT,RIGHT分别为左右
分支；从 NODE回送的值是一个指示器,指向这棵新树
的根,
UNARY(op,CHILD),
生成只有一个分支 CHILD的子树,
LEAF(i):建立一个以 i为标志的结点并回送此结点的地址,
19
产生式和语义动作
E→E (1) op E(2)
{E ·VAL= NODE(op,E(1) ·VAL,E(2) ·VAL) }
E→(E (1))
{E · VAL = E(1) · VAL }
E→ － E(1)
{E ·VAL= UNARY(@,E(1) ·VAL,_)} @代表一元负运算
E →id
{E · VAL = LEAF(id)}
20
三、四元式
1、表示 Op ARG1 ARG2 RESULT
其中,
ARG1,ARG2,RESULT(运算结果 )是用户定义的变量
或引进的临时变量,指向符号表的入口位置,
2、说明
①一目运算用 ARG1
② 四元式出现的顺序与表达式的计值顺序一致,
③ 临时变量,可以象变量名一样填入符号表,
④ 四元式之间通过临时变量联系,易于优化,
21
例,A:=－ B*(C+D)
op ARG1 ARG2 RESULT
(1) @ B _ T1
(2) + C D T2
(3) * T1 T2 T3
(4),= T3 _ A
其中,Ti 是临时变量
22
§ 5.4 自下而上分析法：简单语句的翻译
一、语句的翻译
1、语句：各种语句均有语义动作
①可执行语句 ----生成四元式
②不可执行语句 ---填写符号表
2、语句翻译的构思要点
①确定语句的目标代码结构
②中间代码
③添加语义动作
3、数据结构：符号表，四元式表，临时变量表
23
二、赋值语句和表达式到四元式的翻译
1、定义
? NEWTEMP,
函数过程，产生新的临时变量 T1,T2,…… 。
? E·PLACE,
与非终结符号 E相关的语义变量，表示存放 E值的变量
名在符号表的入口或是一个整数码。
? GEN(op,ARG1,ARG2,RESULT),
语义过程，把四元式填入四元式表中。
? ENTRY(id):语义过程，查找标识符 id在符号表中
的位置
24
2、文法
S→A
A →V:=E
E →E+T ∣ T
T → T*F ∣ F
F →(E) ∣ i
V →i
此文法为 SLR(1)文法,可以构造出 SLR(1)分析表,
25
3、产生式及语义动作
(1) S→A
{ }
(2) A →V:=E
{GEN(:=,E·PLACE,_,V·PLACE}
(3) E(1) →E (2)+T
{E(1)·PLACE:=NEWTEMP;
GEN(+,E(2)·PLACE,T·PLACE,E(1) ·PLACE}
(4)E → T
{E·PLACE:=T·PLACE}
26
(5) T(1) → T (2)*F
{T(1)·PLACE:=NEWTEMP;
GEN(*,T(2)·PLACE,F·PLACE,T(1) ·PLACE
(6) T → F
{T·PLACE:=F·PLACE}
(7) F →(E)
{F·PLACE:=E·PLACE}
(8) F → i
{F·PLACE:=ENTRY(i)}
(9)V →i
{V·PLACE:=ENTRY(i)}
27
例,分析句子 X:=B+C*D 其中 X,B,C,D为终结符
步
骤
状态栈 符号栈 输入 动
作
语义操作
1 0 # X S2
2 02 #X,= R9 VX·PLACE:=ENTRY(X)
3 03 #VX,= S4
4 034 #VX:= B S9
5 0349 #VX:=B + R8 FB·PLACE:=ENTRY(B)
6 0347 #VX:=FB + R6 TB·PLACE:=FB·PLACE
7 0346 #VX:=TB + R4 EB·PLACE:=TB·PLACE
8 0345 #VX:=EB + S10
9 034510 #VX:=EB+ C S9
28
步
骤
状态栈 符号栈 输
入
动
作
语义操作
10 0345109 #VX:=EB+C * R8 FC·PLACE:=ENTRY(C)
11 0345107 # VX:=EB+FC * R6 TC·PLACE:=FC·PLACE
12 03451013 #VX:=EB+TC * S11
13 0345101311 #VX:=EB+TC* D S9
14 03451013119 #VX:=EB+TC*D # R8 FD·PLACE:=ENTRY(D)
15 03451013117 #VX:=EB+TC*FD # R5 (*,TC·PLACE,
FD·PLACE,T1 ·PLACE)
16 03451013 #VX:=EB+TT1 # R3 (+,EB·PLACE,
T1·PLACE,T2·PLACE)
17 0345 # VX:=ET2 # R2 (:=,T2·PLACE,_,X)
18 01 #A #
29
§ 5.5 作为条件控制语句的布尔式的翻译
1、布尔式的作用
if E then S1 else S2;
E的作用,控制对 S1和 S2的选择,找到出口,E值不保留,
E的出口,真出口 ----- S1语句
假出口 ----- S2语句
F T
E的代码
S1的代码
S2的代码
30
2、布尔式的源文法
G[E],
E→E ∧ E
E→E ∨ E
E→ ?E
E→(E)
E→i rop i
E→i
其中, rop为关系运算符,>,<,=,≧,≦,≠
31
3、布尔式的四元式形式
(jnz,A,_,p),
若 A为真转第 p个四元式
(jez,A,_,p),
若 A为假转第 p个四元式
(jθ,A1,A2,p),
若的 A1 θ A2关系为真转第 p个四元式
(j,_,_,p),
无条件转第 p个四元式
32
例, if A∨ B<D then S1 else S2的四元式序列
(1) (jnz,A,_,5) A的真出口 5
(2) (j,_,_,3) A的假出口 3
(3) (j<,B,D,5) B的真出口 5
(4) (j,_,_,p+1) B的假出口 p+1
(5) (关于 S1的四元式序列 ) E的真出口
……
(p) (j,_,_,q)
(p+1) (关于 S2的四元式序列 ) E的假出口
(q) ……
问题：确定布尔式的真、假出口
确定目标地址
33
(1) 确定布尔式的真、假出口,
分情况讨论,
① E→E (1) ∨ E(2) (E(1)为真,则 E为真 )
E(1)的真出口,就是 E的真出口
E(1)的假出口,就是 E(2)的第一个四元式
E(2)的真假出口,就是 E的真假出口
34
② E→E (1) ∧ E(2) (E(1)为假,则 E为假 )
E(1)的假出口,就是 E的假出口
E(1)为真,计 E(2),
E(1)的 真出口,就是 E(2)的第一个四元式
E(2)的真假出口,就是 E的真假出口
③ E→ ? E(1)
E(1)的真出口,就是 E的假出口
E(1)的假出口,就是 E的真出口
35
(2)如何确定目标地址
①拉链 ---回填技术,
自下而上的语法分析中,一个布尔式的真假出口往往
不能在产生四元式的同时填上,需要将这些未完成的四
元式地址作为语义值保留下来,待到整个表达式的四元
式产生后回来填这个未填的转移目标,
② 对 E设两个语义值,
E·TC:表达式 E所对应的四元式序列的 真 出口链的首地址,
E·FC:表达式 E所对应的四元式序列的 假 出口链的首地址,
36
例,p,q,r三个四元式需
回填同一真出口
的目标地址
(p) (X,X,X,0)
(q) (X,X,X,0)
(r) (X,X,X,0)
拉链过程如右,
(p) (X,X,X,0)
(q) (X,X,X,p)
E.TC=r,链尾 =p
0是链尾
的标志
回填过程，设目标地址为 t
(r)(X,X,X,0) q)(r) X,X,)
t
37
③ 定义
? NXQ:指针,指向下一个将要产生但尚未产生的
四元式的地址,每执行一次 GEN过程,NXQ
值自动加 1,
? MERGE(p1,p2):函数,将以 p1为首和 p2为首的两
条链合并,并且 p1跟在 p2之后，返回合并后的链
首。
38
Procedure MERGE(p1,p2)
if p2=0 then MERG:=p1 else
begin p:= p2 ;
while 四元式 p的第四区段不为 0 do
p:=四元式 p的第四区段内容 ;
在四元式 p的第四区段填入 p1;
MERGE:= p2;
end
39
? BACKPATCH(p,t):回填过程,把 p所链接的每个四元式
的第四区段都填为 t,
Procedure BACKPATCH(p,t)
begin
Q:=p;
while Q≠0 do
begin
q:=四元式 Q的第四区段内容 ;
在四元式 Q的第四区段填入 t;
Q:=q
end
end
40
5.6 程序流控制语句的翻译
? 一般而言，程序流程控制可大致分为 顺序结构
（如复合语句）,分枝结构 （如 if条件语句和
实现多分枝的 case语句等）,循环结构 （如 for
循环,while循环,repeat循环等等）三类。另
外,GOTO语句也是一类常见改变流程的 控制
语句 。下面，将对常见的一些控制结构的翻译
进行讨论。
41
5.6.1 常见控制结构的翻译
? 程序设计理论已证明,任何程序均可由 序列结构, 条
件分枝结构 和 while循环 三种结构等价地表示。这三
类结构可用如下的文法描述,
1,S→ if E then S(1)
2,| if E then S(1) else S(2)
3,| while E do S(1)
4,| begin L end (5.8)
5,| A
6,L→ L ； S
7,| S
? S,L,A分别代表 语句, 语句序列 和 赋值语句, E代表
布尔表达式 。约定 else与其前离它最近的尚未得到匹
配的 then相匹配。为 同名文法符号 增加了 上标 。
42
条件语句 的处理方法
? 布尔表达式 E具有两个属性：
E.TC与 E.FC，用来分别指示 E
的真链和假链的链首。
? 当 E出现在条件语句 if E then
S1 else S2中时，当语法分析器
扫视到 then时,E的 真出口已
经确定，此时即可用 NXQ对 E
的 真链进行回填；而当扫视到
else时，即可用 NXQ对 E的 假
链进行回填。
T
E的代码
S1的代码
S2的代码
F
if语句的代码结构
43
while控制语句的翻译文法
S→ while E do S(1)
由于 while循环要求每次执行
完循环体之后，应无条件转
向循环判断条件 E处，因此，
需将 E的第一四元式序号记下
来，以便在翻译完 S后可产生
一个转向此处的四元式。
E的代码
S的代码
T
F
while语句的
代码结构
44
控制语句翻译应用举例
【 例 5.4】 将 语句 while (a<b) do if (c>d) then
x:=y+z 翻译成四元式序列。假定所产生的四元式
序列从编号 100开始。翻译结果如下,
100 j<,a,b,102
S.Chain→ 101 j,0,0,0
102 j>,c,d,104
103 j,0,0,100
104 +, y,z,T
105 =,T,0,x
106 j,0,0,100
NXQ→ 107
45
5.6.2 FOR循环 语句的翻译
? FOR循环语句可由如下产生式定义 (假定步长为 1),
S→ for identifier,=<循环表 > do S(1)
<循环表 >→ Expr(1) to Expr(2) (5.12)
? 假定循环控制变量 identifier为整型简单变量，
Expr(1)与 Expr(2)都是整数或整型简单表达式，且
Expr(2)的值可变。上述 FOR语句在语义上等价于
identifier = Expr(1);
LOOP,if (identifier <= Expr(2)) {
S(1);
identifier++;
goto LOOP; }
46
Expr(1)的四元式序列,结果 =>临时变量 T1
(=,T1,0,i ) (i=Entry(identifier) )
Expr(2)的四元式序列,结果 =>临时变量 T2
(p) ( j≤,identifier,T2,p+2)
(p+1) ( j,0,0,0 ) ← S.Chain
(p+2) S(1)的四元式序列
(q) (+,identifier,1,identifier)
(q+1) ( j,0,0,p)
(q+2) ← NXQ
identifier = Expr(1);
LOOP,if (identifier <= Expr(2)) {
S(1); identifier++; goto LOOP; }
47
5.6.3 语句 标号 及 GOTO语句的翻译
? 语句标号 用于标识一个语句，可以通过产生式
Statement→ label ':' Statement (5.13)
来定义。
? 通常把源程序中形如,label, Statement”的 标号 出现，
称为 定义性出现 。
? 通过执行形如 GOTO label 的转向语句，把控制无条件
地转移到由 标号 label 所标识的语句。这种出现在 GOTO
语句或其它类似语句中的 标号,称为 使用性 标号 。
? 在许多语言中，允许 标号 的 使用性出现 位于 定义性出现 之
前。
48
标号 具有的 语义属性
? 标号的语义属性,
– 名字
– 它所标识语句的四元式序列的 首地址 （序号）。
– 用于标志该 标号是否已被定义 的属性，其初值为 0
（表示尚未定义）。
? 对于一个标号而言，它在符号表中的登记项通
常有如下的内容,
NAME | [CAT] | DEF | … | ADDR
名字
[label] 0|1 四元式序号 /链
49
goto语句的翻译
? 对于 GOTO L，产生形如 （ j,0,0,p） 的四元式。
– 若此时 L表项的 DEF域为 1（即已定义），则将相应
的 ADDR域作为此四元式的转向目标 (p=ADDR);
– 若 DEF=0，利用转移四元式的 Result域将所有转向
同一目标的四元式拉成一个链，待 L有定义时回填，
链首由 L在表中 的 ADDR域指示。
源程序 四元式
goto L; (p) (j,0,0,0)
… …
goto L; (q) (j,0,0,p)
… …
goto L; (r) (j,0,0,q)
NAME
CAT
DEF
…
ADDR
…
…
…
…
…
lab 0 …
r
50
5.6.4 情况语句的翻译
多分枝的语句结构,
case Expr of
C1,S1;
C2,S2;
……
Cn-1:Sn-1; (5.17)
else Sn
end
语义,当 Expr的当前值等于
某个 Ci时, 则执行 Ci所标识的
语句 Si；若 Expr的值不等任
何一个 Ci,则执行 ELSE之后的
语句 Sn,执行完语句 Si之后,
将控制转至后继语句 。
Expr=
S1 S2 Sn …
51
CASE语句的处理方法
? 为实现 CASE语句的语义功
能, 可将 CASE语句翻译为
具有如下结构的中间代码
序列 (向前转移 )
T=Expr
goto CHECK
L1,语句 S1的代码
goto NEXT
L2,语句 S2的代码
goto NEXT
……
Ln-1,语句 Sn-1的代码
goto NEXT
Ln,语句 Sn的代码
goto NEXT
CHECK,if T=C1 goto L1
if T=C2 goto L2
……
if T=Cn-1 goto Ln-1
goto Ln
NEXT,
52
翻译 CASE语句的过程
? 上述代码结构的特点,把检测 Expr之值以及按不同结果转
向不同的代码, 集中地放在尾部, 这有利于产生效率较高
的目标代码 。 翻译 CASE语句的过程大致如下,
1.当遇到关键字 CASE时, 产生内部标号 CHECK及 NEXT，
并把填入符号表, 其 ADDR及 DEF域均填写为 0,再产生一
临时变量 T。
2.产生相应于 T=Expr的四元式 。
3.当扫视到关键字 OF时,将 NXQ的当前值填入标号 CHECK
在 符号表登记项中的 ADDR 域 。 并产生四元式
(j,0,0,0)(即 goto CHECK),其中的转移目标待回填 。 此
外,再设置一个名为 QUEUE的队列 (初值为空 ),供翻译过
程存放信息用 。
53
翻译 CASE语句的过程 (续 )
4.当扫视到每一, Ci”时, 产生相应的内部标号 Li,并把它记入符号
表, 其 ADDR域为 NXQ的当前值 (即 Si的第一四元式的序号 ),
其次,将序偶 (Ci,Pi)置入 QUEUE队列 (若 CASE语句出现嵌套, 则
不同层次的 CASE语句应有不同的 QUEUE队列 ),其中 Pi是 Li在符
号表中的序号 。
接着,产生语句 Si的四元式序列 。 其后再产生一个相应于 goto
NEXT的无条件转移四元式 (j,0,0,0),由于 NEXT地址尚未确定,
故应进行拉链 。
5.当扫视到关键字 ELSE时,产生内部标号 Ln并填入符号表,将其
ADDR域填为 NXQ当前值,在队列 QUEUE中加入序偶 (True,Pn),
然后,类似于第四步, 产生 Sn和 goto NEXT的四元式 。
54
翻译 CASE语句的过程 (续 )
6.当扫视 END时,以 NXQ当前值回填相应于 goto CHECK的链,再
从队列 QUEUE中依次取出各序偶 (Ci,Pi),构造四元式序列
(case,C1,P1,0)
(case,C2,P2,0)
… …
(case,Cn,Pn-1,0)
(case,True,Pn,0)
(label,NEXT,0,0)
其中, 四元式 (case,Ci,Pi,0)是相应于条件转移语句 if(T= Ci)
goto Li 的四元式, case是事先定义的一个内部运算符,
在产生四元式 (label,NEXT,0,0) 时, 应以 NEXT的地址回填相
应于各 goto NEXT 语句的四元式链 。
