第四章 语义分析及中间代码生成

第四章

语义分析和中间代码的表示语义分析的概念语法制导翻译方法属性文法几种常见的中间代码表示简单算术表达式和赋值语句的翻译if语句的翻译4.1概述4.1.1语义分析的概念语义分析：即审查每个语法成分的静态语义。在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码，然后再将其翻译为目标代码。优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件。

回顾：语义处理在编译程序中的逻辑位置词法分析语法分析中间代码生成中间代码优化（可选）目标代码优化（可选）目标代码生成静态语义分析语义处理

两项工作：静态语义分析，中间代码生成

静态语义分析：主要工作如类型检查、名字的作用域分析、控制流检查、一致性检查等。中间代码生成：从语法分析的结果生成中间代码（个别编译程序可能直接生成目标代码）。跨分析和综合两个阶段分析阶段：理解源程序，挖掘源程序的语义综合阶段：生成与源程序语义上等价的目标程序跨编译程序的前端和后端语法制导的语义处理

编译程序的设计中，语义分析和中间（目标）代码生成的实现采用语法制导翻译的方法。

程序设计语言的语义描述常采用属性文法。语义处理涉及到的基本技术4.1.2语法制导翻译方法对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。这种模式实际上是对上下文无关文法的一种扩充。例如,文法G[E]:

产生式

语义动作E→E(1)+T{E.Val=E(1).val+T.val;}E→T {E.Val=T.Val;}T→i {T.Val=i;}为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语义信息栈。

语法分析栈语义分析栈TT.Val+‘+’E……#

产生式的语义是由组成该产生式的文法符号的语义所决定的。

可将文法符号的语义以“属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则，从而形成一种附带有语义属性的前后文无关文法，即属性文法。4.2属性文法

属性文法=上下文无关文法+属性+求值规则

属性用来描述文法符号的语义特征，如常量的“值”、变量的类型和存储位置等。求值规则（属性计算规则）与产生式相关联的反映文法符号属性之间关系的“规则”。求值规则还可进一步扩展为语义规则（语义动作）。1、定义【例】简单表达式的属性文法。语义规则S→EE→E（1）+TE→T

T→T（1）*FT→FF→(E)F→iprint(E.val)

E.val=E（1）.val+T.val

E.val=T.val

T.val=T（1）.valF.val

T.val=F.valF.val=E.valF.val=i.lexval产生式词法分析的结果若产生式AX1X2…Xn，与之相关的属性计算规则 b=f(c1,c2,…)，其中f

是函数，b和c1,c2,…,ck

是该产生式文法符号的属性，－如果属性b是产生式左部符号A的属性，c1,c2,…,ck

是产生式右部文法符号的属性或A的其它属性,则称其为A的综合属性；－如果属性b是产生式右部符号Xi的属性，

c1,c2,…,ck

是产生式右部文法符号的属性或A的属性则称其为Xi的继承属性；－终结符仅有综合属性,如i.lex_val。通常由词法程序提供。而开始符号没有继承属性。2、属性的分类继承属性用于“自上而下”传递信息。继承属性由相应语法树中结点的父结点和/或兄弟结点属性计算得到，它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序设计语言上下文的结构关系。几点说明：几点说明（续）：综合属性用于“自下而上”传递信息。综合属性由相应语法树中结点的分枝结点属性计算得到，即沿语法树向上传递，从分枝（子）结点到根结点。思考：简单表达式文法中的属性各是什么类型的？A.bX1.c1X2.c2X…综合属性A.b的计算AX1.c1X2.c2…继承属性Xk.b的计算Xk.bX属性的计算次序用图表示如下：注释分析树在语法树中,将每个结点均视为由若干个域组成的结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为注释分析树（DecoratedSyntaxTree）。【例】给出表达式3＊(5+4)

的属性计算过程。

（综合属性的例子）语义规则S→EE→E（1）+TE→T

T→T（1）*FT→FF→(E)F→iprint(E.val)

E.val=E（1）.val+T.val

E.val=T.val

T.val=T（1）.valF.val

T.val=F.valF.val=E.valF.val=i.lexval产生式

综合属性代表自下而上传递的信息对表达式3＊(5+4)

的分析树进行自下而上（后序）遍历，并执行相应的语义规则，得到该表达式的一种求值过程TETEFTi＋()iSEFFTiFi.lexval=5i.lexval=3i.lexval=4F.val=5F.val=3T.val=3T.val=5E.val=5F.val=4T.val=4E.val=9F.val=9T.val=27E.val=27print(27)S→EE→E（1）+TE→TT→T（1）*FT→FF→(E)F→i【例】语句intx,y,z的语义分析。（继承属性）产生式

语

义

规

则

D

TL

L.in=T.type

T

int

T.type=integer

T

float

T.type=float

L

L1,

id

L1.in=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

继承属性代表自上而下传递的信息对声明语句intx,y,z的分析树进行遍历，自下而上执行综合属性相应的语义规则，自上而下执行继承属性相应的语义规则，可以得到所有属性值的一个求值过程T,LDLidintT.type=integerL.in=integer,idL.in=integeridLL.in=integeraddtype(id.entry,integer)addtype(id.entry,integer)addtype(id.entry,integer)思考：如何通过对注释分析树进行树遍历的方法计算属性值？最常用的方法是深度优先、从左到右的遍历。小结：基于属性文法的语义处理基于属性文法的语义处理即为语法制导翻译（Syntax-DirectedTranslation）处理方法分两类：

树遍历方法

通过遍历分析树进行属性计算

单遍的方法（On-the-fly方法）语法分析遍的同时进行属性计算

基于树遍历方法的语义处理

步骤

构造输入串的语法分析树。

构造依赖图（Dependencygraph）。

若该依赖图是无圈的，则按造此无圈图的一种拓扑排序（Topologicalsort）对分析树进行遍历，则可以计算所有的属性。4.3几种常见的中间语言

（中间代码形式）抽象语法树逆波兰式三地址代码（四元式、三元式、间接三元式）语法树是分析树的浓缩表示：算符和关键字作为内部结点。

语法制导翻译可以基于分析树，也可以基于语法树。在抽象语法树表示中，每一个叶结点都表示诸如常量或变量这样的运算对象（本质部分），而其他内部结点则表示运算符和关键字等（非本质部分）。1、抽象语法树语法树的例子：if-then-elseES1S2+*2582、逆波兰表示波兰逻辑学家J.Lukasiewicz于1929年提出的一种表示表达式的方法。按此方法，每一运算符都置于其运算对象之后，故称为后缀表示。表达式E的后缀表示递归定义如下：（1）如果E是变量或常数，则E的后缀表示即E自身。（2）如果E为E1opE2形式，则它的后缀表示为E1’E2’op；其中E1’、E2’分别是E1和E2的后缀表示。若op是一元运算符，则视E1和E1’为空。（3）如果E为(E1)形式，则E1的后缀表示即为E的后缀表示。特点:操作数出现的顺序与原来一致，而运算符则按运算先后的顺序放到相应的操作数之后，即运算符先后的顺序发生了变化，表达式中各个运算是按运算符出现的顺序进行的，故无须使用括号来指示运算顺序。【例】

中缀表示 后缀表示

A+B AB+ A+B*C ABC*+ (A+B)*(C+D) AB+CD+* x/y^z-d*e xyz^/de*-

程序语句的逆波兰表示见课本P116。3、三地址代码（四元式）四元式是一种更接近目标代码的中间代码形式，由于这种形式的中间代码便于优化处理，因此，在目前的许多编译程序中得到了广泛的应用。四元式是一种“三地址语句”（注：三地址语句的种类见课本P98）的等价表示。它的一般形式为：(op,arg1,arg2,result)其中，op为一个二元(也可是一元或零元)运算符;arg1,arg2分别为它的两个运算对象，它们可以是变量、常数或系统定义的临时变量名；运算的结果将放入result中。四元式还可写为类似于PASCAL语言的赋值语句的形式：result=arg1

op

arg2

种类：x=yopz双目运算(op,y,z,x)x=opy 单目运算(op,y,_,x)x=y 赋值语句(=,y,_,x)x=-y(uminus,y,_,x)ifxrelopygotol条件转移语句 (jrop,x,y,l)

gotol无条件转移(j,_,_,l)每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。例如，表达式a+b*c可写为序列 （*,b,c,t1） （+,a,t1,t2）当op为一元、零元运算（如无条件转移）时，arg2甚至arg1应缺省，即result=op

arg1或op

result；对应的一般形式为： (op,arg1,-,result)或 (op,-,-,result)。说明：【例】赋值语句a=b*(c+d)相应的四元式代码为：(1)(+,c,d,t1)(2)(*,b,t1,t2)(3)(=,t2,_,a)

除前面所述的抽象语法树、逆波兰式、四元式外，常见的中间语言还有接近PASCAL形式的P-代码，接近C格式的C-代码等等。4、其它表示法4.4简单算术表达式和赋值语句的翻译相关的语义处理说明对非终结符E定义语义变量E.place，即用E.place表示存放E值的变量名在符号表中的入口地址或临时变量名的整数码。定义语义函数newtemp()，即每次调用newtemp()时都回送一个代表新临时变量的整数码；临时变量名按产生的顺序可设为T1、T2…定义语义函数emit(op,arg1,arg2,result)，emit的功能是产生一个四元式。定义语义函数lookup()，其功能是查找是否出现在符号表中，是则返回在符号表中的入口指针，否则返回null。(1)S→i=E {p=lookup(); if(p==null)thenerror();elseemit(=,E.place,_,p);}

(2)E→E1+E2{E.place=newtemp(); emit(+,E1.place,E2.place,E.place);}

(3)E→E1*E2{E.place=newtemp(); emit(*,E1.place,E2.place,E.place);}写出每个产生式对应的语义处理过程(4)E→-E1{E.place=newtemp();emit(uminus,E1.place,_,E.place);}(5)E→(E1){E.place=E1.place;}

(6)E→i{p=lookup(); if(p!=null)thenE.place=p; elseerror();}

表达式翻译中的其它问题临时变量空间的统计了解需求、及时释放运算合法性检查利用符号表保存的名字类型类型自动转换添加专用指令两种方法：1）类似于算术表达式计算布尔表达式的值，用“1”表示“真”，用“0”表示“假”。2）“短路”计算的方法，用表达式的真、假出口表示运算后转移的地址。真假出口表示法给出两个表示语义的属性：E.tc，E为真时控制到达的位置；E.fc，E为假时控制到达的位置。思考：布尔表达式如何翻译？则有示例如下：a<bifa<bgotoE.tc（j<,a,b,E.tc）gotoE.fc（j,_,_,E.fc）E→E1

∨E2如果E1为真，则立即可知E为真，即E1.tc与E.tc相同；如果E1为假，则必须计算E2的值，令E1.false为E2的开始位置；E2的真假出口分别与E的真假出口相同(1)E→i {E.tc=nxq;E.fc=nxq+1; emit(jnz,entry(i),_,0);emit(j,_,_,0);}(2)E→i1ropi2{E.tc=nxq;E.fc=nxq+1; emit(jrop,entry(i1),entry(i2),0);emit(j,_,_,0);}

写出每个产生式对应的语义处理过程真出口，有待回填假出口，有待回填(3)E→(E1){E.tc=E1.tc;E.fc=E1.fc;}(4)E→┐E1{E.tc=E1.fc;E.fc=E1.tc;}(5)EA→E1{Backpatch(E1.tc,nxq);EA.fc=E1.fc}(6)E→EAE2{E.tc=E2.tc;E.fc=merge(EA.fc,E2.fc);}(7)EB→E1{Backpatch(E1.fc,nxq);EB.tc=E1.tc}(8)E→EBE2{E.fc=E2.fc;E.tc=merge(EB.tc,E2.tc);}什么是“回填”？（1）先产生暂时没有填写目标标号的四元式。（2）对于每一条这样的四元式作适当的记录，即可用“拉链”的方法将这些四元式链接起来。

（实现见课本P104merge(p1,p2)函数）（3）一旦目标标号（即将要转移的目标四元式的地址）被确定下来，再将它“回填”到相应的指令（四元式的第四个区段）中。

（实现见课本P104Backpatch(p,t)函数）4.5if语句的翻译条件语句的模式

if(E)S1;elseS2条件语句的代码结构

E的代码

E.tc

S1的代码

gotooutS2的代码out:E.fcE.tcE.fc相关语义处理说明对非终结符E定义语义变量E.tc和E.fc，分别表示“真”、“假”两个出口。定义语义变量nxq，始终指向下一条将要产生的四元式的地址（此处用序号表示），其初值为1。每执行一次emit语句后，nxq自动加1。所有的出口地址采用“拉链”、“回填”的方式确定。相应的定义如下两个语义函数:merge(p1,p2):把以p1和p2为链首的两条链合并为一条以p2为链首的链。Backpatch(p,t):把链首p所链接的每个四元式的第四个区段都改写为地址t。（具体实现见课本P104）一种翻译方法：为了及时回填地址，将条件语句的文法修改为如下形式:G´[S]:(1)S→CS1(2)C→if(E)(3)S→TPS2(4)TP→CS1;else

对应的语义规则C→if(E){Backpatch(E.tc,nxq);C.chain=E.fc;}S→CS1{S.chain=merge(C.chain,S1.chain);}Tp→CS1;

else{q=nxq;emit(j,_,_,0);Backpatch(C.chain,nxq);Tp.chain=merge(S1.chain,q);}S→TpS2{S.chain=merge(Tp.chain,S2.chain);}生成的四元式序列[例]将下面语句翻译成四元式：ifc<5z=x+1

elsex=y102105107100：（j<,c,5,?）101：（j,-,-,?）102：（+,x,1,t1）103：（=,t1,-,z）104：（j,-,-,?）105：（=,y,-,t2）107:106：（=,t2,-,z）控制流语句的自底向上翻译_另一种实现方法SifEthenMS1 |ifEthenM1S1

NelseM2S2 |whileM1EdoM2S1 |S1;MS2

Mε{M.q=nxq}Nε{N.chain=makechain(nxq);emit(j,_,_,0)}if-then语句的自底向上翻译SifEthenMS1{backpatch(E.tc,M.q)S.chain=merge(E.fc,S(1).chain)}E的代码S⑴的代码ifE.tcE.fcS.chainS⑴

.chainthenM.qif-then-else语句

的自底向上翻译SifEthenM1S1

NelseM2S2{backpatch