第六章 代码生成和代码优化
第 o节 符号表
在程序中,用户用标识符定义了不少
名字来代表不同的数据对象,编译程序将
这些名字保存在符号表中。符号表除了
记录名字本身而外,还记录了与名字关联
的各种属性信息。
一, 符号表的一般形式
每个名字对应一个表项,一个表项包括
名字域和信息域。
名字 信息
其中,信息域通常设若干子域及标志位，其
内容可以是和名字有关的任何信息,
类型,种属,长度,相对地址,数组的内情
向量,记录与分量的联系,形参标志,说明
标志,赋值标志等。
因名字的长度、信息域的组成及长度
可能是各不相同的,一般采用间接表技术。
二, 常用的符号表结构
1,线性表, 用 N个数组 A1,A2,…,AN来存
放符号表的 N个子域
2,HASH表
第一节 语义分析和中间代码生成
O,概述
1,语义分析的主要工作
(1)语义检查, 如类型是否一致,数组
维数是否正确 。
(2)语义处理, 对说明语句,登记信息 ;
对可执行语句,生成中间代码 。
2,语法制导翻译
?为每个产生式配上一个语义子程序,在语
法分析过程中,当用一个产生式进行 匹配
或 归约 时,就调用相应的语义程序 。
?上述语义子程序既可能包含了语义检查,
也可能包含了语义处理,其核心是为了生
成相应的中间代码 。
例：语法分析采用自底向上的 LR分析法
X?AB
Y?CD
Z?XY
状态栈 符号栈 语义栈
B
A
?
?
?
B的语义值
A的语义值
?
?
?
状态栈 符号栈 语义栈
X
?
?
?
X的语义值
?
?
?
状态栈 符号栈 语义栈
D
C
X
?
?
?
D的语义值
C的语义值
X的语义值
?
?
?
状态栈 符号栈 语义栈
Y
X
?
?
?
Y的语义值
X的语义值
?
?
?
状态栈 符号栈 语义栈
Z
?
?
?
Z的语义值
?
?
?
语义可以是：,值”、“类型”、“种属”、“地址”等。
可见：在分析过程中必须保存语义值。
一, 四元式
?形式, (op,ARG1,ARG2,RESULT)
op— 运算符,ARG1— 第一运算量,
ARG2— 第二运算量,RESULT— 结果
如, A:=-B*(C+D) 翻译成
(@,B,_,t1)
(+,C,D,t2)
(*,t1,t2,t3)
(:=,t3,_,A)
由此可见,
?四元式出现顺序和表达式计值顺序一致 ;
?四元式之间的联系是通过临时变量实现的 。
二,简单赋值语句的翻译
1,语义变量及过程
(1)X.a:文法符 X的相应属性 a
如 i.name,E.place
(2)lookup(a):语义函数,为名字 a查符号
表 ;返回, a在符号表中的位置或 nil
(3)newtemp:语义函数,每调用一次就返
回一个可用的临时变量地址
(4)emit:语义过程,产生四元式并送到
GAM的代码存储器 ip指向位置
(5)ip:指令指针,一般设初值为 0,也可指
定一个初值,每调用一次 emit,ip自动
加 4
(6)error:语义过程,错误处理
2,翻译方案
A→i,=E { p:=lookup(i.name);
if p<> nil then
emit (,=,E.place,_,p)
else error}
E→E 1 op E2
{ E.place:=newtemp;
emit(op,E1.place,E2.place,E.place) }
E → -E1
{ E.place:=newtemp;
emit(@,E1.place,_,E.place) }
E →(E 1)
{ E.place:= E1.place }
E →i
{ p:=lookup(i.name);
if p<>nil then E.place:=p
else error }
举例, a:=-b*(c+d)的移进 -归约过程
a:=-b*(c+d)
a:=-E1*(c+d)
a:=E2*(c+d)
a:=E2*(E3+d)
a:=E2*(E3+ E4)
a:=E2*(E5)
a:=E2*E6
a:=E7
A
i
i:=
i:= -
i:= -i
i:= -E1
i:= E2
i:= E2*
i:= E2*(
i:= E2*(i
i:= E2*(E3
i:= E2*(E3+
i:= E2*(E3+i
i:= E2*(E3+E4
i:= E2*(E5
i:= E2*(E5)
i:= E2*E6
i:= E7
A
a
a_
a__
a__b
a__b
a_t1
a_t1_
a_t1__
a_t1__c
a_t1__c
a_t1__c_
a_t1__c_d
a_t1__c_d
a_t1__t2
a_t1__t2_
a_t1_t2
a_t3
a:=-b*(c+d)
:=-b*(c+d)
-b*(c+d)
b*(c+d)
*(c+d)
*(c+d)
*(c+d)
(c+d)
c+d)
+d)
+d)
d)
)
)
)
(@,b,_,t1)
(+,c,d,t2)
(*,t1,t2,t3)
(:=,t3,_,a)
符号栈 PLACE 输入 四元式
a:=-b*(c+d)的翻译过程
3,类型转换
?对表达式 E增加类型属性 E.type;
?引进类型转换指令 (itr,x,_,t)
E→E 1 op E2的语义子程序如后
t:=newtemp;
if E1.type=integer and E2.type=integer then
begin emit(opi,E1.place,E2,place,t);
E.type:=integer
end
else if E1.type=real and E2.type=real then
begin emit(opr,E1.place,E2.place,t);
E.type:=real
end
else if E1.type=integer then
begin t1:=newtemp;
emit(itr,E1.place,_,t1);
emit(opr,t1,E2.place,t);
E.type:=real
end
else begin t1:=newtemp;
emit(itr,E2.place,_,t1);
emit(opr,E1.place,t1,t);
E.type:=real
end;
E.place:=t;
第 o节 符号表
在程序中,用户用标识符定义了不少
名字来代表不同的数据对象,编译程序将
这些名字保存在符号表中。符号表除了
记录名字本身而外,还记录了与名字关联
的各种属性信息。
一, 符号表的一般形式
每个名字对应一个表项,一个表项包括
名字域和信息域。
名字 信息
其中,信息域通常设若干子域及标志位，其
内容可以是和名字有关的任何信息,
类型,种属,长度,相对地址,数组的内情
向量,记录与分量的联系,形参标志,说明
标志,赋值标志等。
因名字的长度、信息域的组成及长度
可能是各不相同的,一般采用间接表技术。
二, 常用的符号表结构
1,线性表, 用 N个数组 A1,A2,…,AN来存
放符号表的 N个子域
2,HASH表
第一节 语义分析和中间代码生成
O,概述
1,语义分析的主要工作
(1)语义检查, 如类型是否一致,数组
维数是否正确 。
(2)语义处理, 对说明语句,登记信息 ;
对可执行语句,生成中间代码 。
2,语法制导翻译
?为每个产生式配上一个语义子程序,在语
法分析过程中,当用一个产生式进行 匹配
或 归约 时,就调用相应的语义程序 。
?上述语义子程序既可能包含了语义检查,
也可能包含了语义处理,其核心是为了生
成相应的中间代码 。
例：语法分析采用自底向上的 LR分析法
X?AB
Y?CD
Z?XY
状态栈 符号栈 语义栈
B
A
?
?
?
B的语义值
A的语义值
?
?
?
状态栈 符号栈 语义栈
X
?
?
?
X的语义值
?
?
?
状态栈 符号栈 语义栈
D
C
X
?
?
?
D的语义值
C的语义值
X的语义值
?
?
?
状态栈 符号栈 语义栈
Y
X
?
?
?
Y的语义值
X的语义值
?
?
?
状态栈 符号栈 语义栈
Z
?
?
?
Z的语义值
?
?
?
语义可以是：,值”、“类型”、“种属”、“地址”等。
可见：在分析过程中必须保存语义值。
一, 四元式
?形式, (op,ARG1,ARG2,RESULT)
op— 运算符,ARG1— 第一运算量,
ARG2— 第二运算量,RESULT— 结果
如, A:=-B*(C+D) 翻译成
(@,B,_,t1)
(+,C,D,t2)
(*,t1,t2,t3)
(:=,t3,_,A)
由此可见,
?四元式出现顺序和表达式计值顺序一致 ;
?四元式之间的联系是通过临时变量实现的 。
二,简单赋值语句的翻译
1,语义变量及过程
(1)X.a:文法符 X的相应属性 a
如 i.name,E.place
(2)lookup(a):语义函数,为名字 a查符号
表 ;返回, a在符号表中的位置或 nil
(3)newtemp:语义函数,每调用一次就返
回一个可用的临时变量地址
(4)emit:语义过程,产生四元式并送到
GAM的代码存储器 ip指向位置
(5)ip:指令指针,一般设初值为 0,也可指
定一个初值,每调用一次 emit,ip自动
加 4
(6)error:语义过程,错误处理
2,翻译方案
A→i,=E { p:=lookup(i.name);
if p<> nil then
emit (,=,E.place,_,p)
else error}
E→E 1 op E2
{ E.place:=newtemp;
emit(op,E1.place,E2.place,E.place) }
E → -E1
{ E.place:=newtemp;
emit(@,E1.place,_,E.place) }
E →(E 1)
{ E.place:= E1.place }
E →i
{ p:=lookup(i.name);
if p<>nil then E.place:=p
else error }
举例, a:=-b*(c+d)的移进 -归约过程
a:=-b*(c+d)
a:=-E1*(c+d)
a:=E2*(c+d)
a:=E2*(E3+d)
a:=E2*(E3+ E4)
a:=E2*(E5)
a:=E2*E6
a:=E7
A
i
i:=
i:= -
i:= -i
i:= -E1
i:= E2
i:= E2*
i:= E2*(
i:= E2*(i
i:= E2*(E3
i:= E2*(E3+
i:= E2*(E3+i
i:= E2*(E3+E4
i:= E2*(E5
i:= E2*(E5)
i:= E2*E6
i:= E7
A
a
a_
a__
a__b
a__b
a_t1
a_t1_
a_t1__
a_t1__c
a_t1__c
a_t1__c_
a_t1__c_d
a_t1__c_d
a_t1__t2
a_t1__t2_
a_t1_t2
a_t3
a:=-b*(c+d)
:=-b*(c+d)
-b*(c+d)
b*(c+d)
*(c+d)
*(c+d)
*(c+d)
(c+d)
c+d)
+d)
+d)
d)
)
)
)
(@,b,_,t1)
(+,c,d,t2)
(*,t1,t2,t3)
(:=,t3,_,a)
符号栈 PLACE 输入 四元式
a:=-b*(c+d)的翻译过程
3,类型转换
?对表达式 E增加类型属性 E.type;
?引进类型转换指令 (itr,x,_,t)
E→E 1 op E2的语义子程序如后
t:=newtemp;
if E1.type=integer and E2.type=integer then
begin emit(opi,E1.place,E2,place,t);
E.type:=integer
end
else if E1.type=real and E2.type=real then
begin emit(opr,E1.place,E2.place,t);
E.type:=real
end
else if E1.type=integer then
begin t1:=newtemp;
emit(itr,E1.place,_,t1);
emit(opr,t1,E2.place,t);
E.type:=real
end
else begin t1:=newtemp;
emit(itr,E2.place,_,t1);
emit(opr,E1.place,t1,t);
E.type:=real
end;
E.place:=t;
