编译原理语义分析与中间代码生成

S.PO.P语义分析、生成中间代码生成目标程序代码优化语法分析程序词法分析程序错误处理符号表管理第8章语义分析与中间代码生成要求明确语义分析的任务明确属性文法和语法制导翻译的含义明确自底向上和自顶向下语法制导翻译的区别和特点明确生成中间代码的目的，中间代码的几种形式

教学目标8.1语义分析的任务8.2语法制导翻译8.3中间代码8.4简单赋值语句的翻译8.5布尔表达式的翻译教学内容词法分析，语法分析：解决单词和语言成分的识别及词法和语法结构的检查。语法结构可形式化地用一组产生式来描述。给定一组产生式，我们能够很容易地将其分析器构造出来。本章要介绍的是语义分析和中间代码生成技术。程序语言中间代码目标代码翻译翻译根据语义规则对识别出的各种语法成份分析其含义，进行初步翻译，生成相应的中间代码或直接生成目标代码。（1）确定数据类型（2）语义检查动态语义检查：在运行时刻进行静态语义检查：在编译时完成（3）识别含义，进行真正的翻译8.1语义分析的任务①类型检查。②控制流检查，确保控制语句有合法的转向点。例如，C语言中的break语句使控制跳离包括该语句的最小的switch，while或for语句。如果不存在包括它的这样的语句，则应报错。静态语义检查静态语义检查③一致性检查。很多情况下要求对象只能被定义一次。例如，Ｃ语言中规定一个标识符在同一作用域中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等。④相关名字检查。有的语言中有时规定，同一名字必须出现两次或多次。例如，Ada语言中，循环或程序块可以有一个名字，它出现在这些结构的开头和结尾，如同语句括号一般，编译程序必须检查它们的配对情况。实际应用中比较流行的语义分析方法：基于属性文法的语法制导翻译方法

8.2语法制导翻译属性文法是Knuth在1968年提出的属性文法的特点是一种接近形式化的语义描述方法长于描述静态语义、短于描述动态语义每个语法符号有相应的属性符号每个产生式有相应计算属性的规则属性变量:=属性表达式8.2.1属性文法附加了一组属性和运算（语义）规则的文法

文法符号X的属性t常用X.t来表示语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关不同的产生式对应不同的语义规则不同的分析目标也对应不同的语义规则

1.属性的表示2.语义规则的表示语义信息属性之间的关系静态语义检查、符号表操作、代码生成及打印各种错误信息

非终结符E、T及F都有一个综合属性val,符号i有一个综合属性，它的值由词法分析器提供。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现语义规则EE1+TETTT1*FTFF(E)Fi

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.valT.val=F.valF.val=E.valF.val=i.lexval产生式例8.1根据文法符号的语义，为文法符号设置属性，用来表示文法符号的语义终结符使用单词的属性（id.val）保留字：if,begin,function,……常数：40.12,232,80,“TCP/IP”标识符：sum,tcc,id语法变量根据实际需要设定属性表达式E：E.type，E.val属性的设定8.2.2语法制导翻译的过程语法制导翻译：将语义规则与语法规则相结合，在语法分析的过程中通过执行语义动作，计算语义属性值，从而完成预定的翻译工作。Yacc利用的就是语法制导翻译方法，它使用符号$$表示产生式左端的属性，$n表示存取产生式右端第n个文法符号相联的属性expr:expr'+'expr {$$=$1+$3;}自底向上语法制导翻译自顶向下语法制导翻译语法制导翻译的实现语法制导翻译分为两种处理方法：（1）语法制导定义（自底向上）：对每个产生式编制一个语义子程序，在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译。这种实现方案隐藏了其中语义规则的计算次序等实现细节，不必规定翻译顺序。（2）翻译方案（自顶向下）：在产生式右部的适当位置，插入相应的语义动作，按照分析的进程，执行遇到的语义动作。这是一种动作与分析交错的实现方案。输入符号串

分析树

执行语义规则

翻译结果翻译步骤（２）从分析树得到描述结点属性间依赖关系的依赖图，由依赖图得到语义规则的计算次序

（1）分析输入符号串，建立分析语法树（３）进行语义规则的计算，得到翻译结果

8.2.3语法制导定义对每个产生式编制一个语义子程序在进行语法分析的过程中，当一个产生式获得匹配时，就调用相应的语义子程序实现语义检查与翻译综合属性继承属性自底向上传递信息自顶向下（自左向右）传递信息1、文法非终结符既有综合属性，也可有继承属性；2、开始符号没有继承属性；3、终结符只有综合属性，由词法分析器提供。几点说明：

print(E.val)打印由E产生的算术表达式的值，可认为这条规则定义了L的一个虚属性。

LEEE1+TETTT1*FTFF(E)Fiprint(E.val)

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.val

T.val=F.valF.val=E.valF.val=i.lexval例8.２综合属性语义规则产生式一个结点的综合属性值是其子结点的某些属性来决定的２+3*4的注释分析树通常使用自底向上的分析方法在每个结点处使用语义规则来计算综合属性值当一个产生式获得匹配时，就调用相应的语义子程序从叶结点到根结点进行计算只含有综合属性的语法制导定义称为S属性定义8.2.4S属性定义与自底向上翻译LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算LR分析器增加属性值（语义）栈

步骤状态栈符号栈属性值栈剩余符号串分析动作10#−2+3*4#移进205#2−+3*4#用F→i归约303#F−2+3*4#用T→F归约402#T−2+3*4#用E→T归约501#E−23*4#移进6016#E+−2−*4#移进70165#E+3−2−−*4#用F→i归约80163#E+F−2−3*4#用T→F归约90169#E+T−2−3*4#移进1001697#E+T*−2−3−4#移进11016975#E+T*4−2−3−−#用F→i归约120169710#E+T*F−2−3−4#用T→T*F归约130169#E+T−2−(12)#用E→E+T归约1401#E−(14)#acc产生式语义规则DTLTintTfloatLL1,idLidL.in=T.typeT.type=intT.type=floatL1.in=L.inenter(id.entry,L.in)enter(id.entry,L.in)例8.3继承属性L.inintid1,id2,id3DL.in=intL.in=intL.in=intT.type=intintid2id1id3.，，一个结点的继承属性值是由其父结点或兄弟结点的某些属性决定的DTLintLid2，id1图示：属性信息传递情况8.2.5L-属性定义(L-属性文法)包含综合属性和继承属性的属性文法（语法制导定义）如：算术表达式求值的属性文法、说明语句的属性文法翻译思想将语义动作插入到产生式的某个位置特征规定在语法分析中使用语义规则进行计算的次序保证当动作使用某属性时，该属性必须是有效的——最左派生表示形式：{……}例8.4：建立说明语句的翻译方案将语义动作中继承属性的计算前移，使它出现在其相应文法符号之前D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}realid1,id2的处理过程DT{L.in:=T.type}Lreal{T.type:=real}{L.in:=T.type}Lreal{L.in=real}L

real{L.in=real}{L1.in:=L.in}L1,id2{addtype(id2.entry,L.in)}real{L1.in=real}L1,id2{addtype(id2.entry,L.in)}real{L1.in=real}id1{addtype(id1.entry,L1.in)},id2{addtype(id2.entry,L.in)}realid1{(id1.entry,real)},id2{(id2.entry,real)}D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}生成中间代码的目的(1)便于优化(2)便于移植常见的中间代码形式：后缀式三地址代码（四元式、三元式和间接三元式）图形（抽象语法树、有向无环图）

中间代码：一种介于源语言和目标语言之间的中间语言形式8.３中间代码.java

java源程序文件.class

二进制字节码文件Java虚拟机（JVM)本地计算机系统编译Java语言.NET框架

GCC

中缀表示后缀表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特点1、运算对象出现的顺序和原有顺序（从左到右）相同2、运算符按实际计算顺序（从左到右）出现3、运算符紧跟在运算对象的后面出现，且没有括号优点：简明、便于计值8.3.1后缀式分别给出下列表达式的后缀表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c∧b=d4.a≤b+c∧a>d∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=∧abc+≤ad>∧ab+e≠∨8.3.2三地址代码１．种类（1）x=yopz形式的赋值语句，其中op是二元运算符。（2）x=opy形式的赋值语句，其中op是一元运算符。（3）x=y形式的赋值语句。（4）无条件转移语句gotoL，表示下一个要执行的语句是标号为L的语句。（5）条件转移语句ifxropygotoL中，rop为关系运算符，如果x和y满足关系rop，就转而执行标号为L的语句，否则顺序执行下一个语句。2．具体实现四元式操作符操作数1操作数2结果结果：通常是由编译引进的临时变量例:X=(A+B)*(C+D)-E+,A,B,T1+,C,D,T2*,T1,T2,T3-,T3,E,T4=,T4,一,XT1,T2,T3,T4为临时变量，由四元式优化比较方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4操作符左操作符数右操作数表达式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)

第三个三元式中的操作数(1)(2)表示第(1)和第(2)条三元式的计算结果。三元式例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代码优化：删除某些三元式后可能需作一系列的修改

三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)间接三元式执行顺序(1)(2)(3)(4)(1)(5)三元式的执行次序用另一张表表示,优化时三元式可以不变，仅仅改变其执行顺序表例：x=y+yz+yz

抽象语法树8.3.3图形表示有向无环图8.4表达式及赋值语句的翻译简单表达式的文法如下：Ai=EEE+E|E*E|-E|(E)|i非终结符A代表“赋值语句”，语义子程序所涉及到语义变量、语义过程及函数说明如下：（1）对非终结符的E定义语义变量E.place，即E.place表示存放Ｅ值的变量名在符号表中的入口地址或临时变量名的整数码。（２）定义语义函数newtemp()，即每次调用newtemp()时都要回送一个代表新临时变量的整数码。临时变量按产生的次序为Ｔ１，Ｔ２，。（３）定义语义过程emit(op,arg1,arg2,result)，其中的emit是产生一个四元式并填入四元式的表中。arg1、arg2是操作数，result是运算结果。（4）定义语义函数lookup(),其功能是审查是否出现在符号表中，是则返回在符号表中的入口指针，否则返回空。使用上述的语义变量、过程和函数，可以写出文法每个产生式的语义子程序。（1）Ai=E{p=lookup() if(p==NULL)error(); elseemit(=,E.place,_,P);}（2）EE(1)+E(2){E.place=newtemp(); Emit(+,E(1).place,E(2).place,E.place)}（3）EE(1)*E(2){E.place=newtemp(); emit(*,E(1).place,E(2).place,E.place)}（4）E-E(1) {E.place=newtemp();} emit(uminus,E(1).place,_,E.place)}（5）E(E(1)) {E.place=E(1).place}（6）Ei {p=lookup() if(p!=NULL)E.place=p; elseerror();}在上面的语义分析过程中，没有考虑到静态语义检查。在实际应用中，要全面考虑语句的翻译。例如：EE(1)*E(2)该语句的语义子程序的翻译可以写成：EE(1)*E(2){E.place=newtemp(); ifE(1).type=intANDE(2).type=intthen begin emit(E.place,=,E(1).place,*i,E(2).place); E.type=int end elseifE(1).type=realANDE(2).type=realthen begin emit(E.place,=,E(1).place,*r,E(2).place); E.type=real end elseifE(1).type=int/*andE(2).type=real*/then begint=newtemp; emit(t,=,itr,E(1).place); emit(E.place,=,t,*r,E(2).place);E.type=realendelse/*E(1).type=realANDE(2).type=int*/ begint=newtemp; emit(t,=,itr,,E(2).place); emit(E.place,=,E(1).place,*r,t); E.type=real end; } 例题8.7试分析赋值语句X=-B*(C+D)的语法制导翻译解答：赋值语句X=-B*(C+D)#的语法制导翻译过程如表8-2所示。输入串归约产生式符号栈语义栈（place）四元式X=-B*(C+D)##_=-B*(C+D)#（6）#i_X-B*(C+D)##i=_X_B*(C+D)##i=_X__*(C+D)#（6）#i=i_X__B*(C+D)#（4）#i=E_X__B(uminus,B,_,T1)*(C+D)##i=E_X_T1(C+D)##i=E*_X_T1__C+D)##i=E*（_X_T1_______+D)#（6）#i=E*（i_X_T1___

C+D)##i=E*（E_X_T1__

_CD)##i=E*（E+_X_T1__C_)#（6）#i=E*E+i_X_T1__C_D)#（2）#i=E*(E+E_X_T1__C_D(+,C,D,T2))##i=E*（E_X_T1__T2#（5）#i=E*(E)_X_T1__T2_#（3）#i=E*E_X_T1_T2(*,T1,T2,T3)#（1）#i=E_X_T3(=,T3,_,X)##A_X8.4.2布尔表达式的翻译布尔表达式的文法为：EE∧E|E∨E|E|(E)|i|iropi其中的rop为，<，==，!=，>=，运算符。1．布尔表达式值的计算计算布尔表达式的值通常有两种方法。第一种方法和算术表达式的计算方法一样，根据顺序和优先级一步步计算出来。例如：1∨（0∧0）∨0=1∨（1∧0）∨0=1∨0∨0=1∨0=1另一种方法就是根据布尔表达式的特点实施某种优化。即不必一步一步地计算布尔表达式中所有运算对象的值，而是省略不影响结果的运算。例如：在计算A∨B时，若计算出A的值为1，则B的值就无须再计算；在计算A∧B时，若A的值为0，则B的值无须要再计算，因为A∧B的值一定为02．布尔表达式的翻译方法给出布尔表达式ifa<bthen1else0，根据布尔表达式的第一种计算方法，写出该表达式的四元式为：（1)ifa<bgoto(4)（2）t=0（3）goto(5)（4）t=1（5）…翻译方法如下：E(1)∨E(2)：E(1)为TRUE，则整个表达式为TRUE，转向条件为“真”的出口。E(1)为FALSE，则转向E(2)的判断，若E(2)为TRUE，则整个表达式为TRUE，转向条件为“真”的出口，用E.true指针代表真的出口；若E(1)为FALSE，则转向E(2)的判断，若E(2)为FALSE，则整个表达式为 FALSE，则转向条件为“假”的出口，用E.false代表假的出口。E(1)∧E(2)：E(1)为FALSE，则整个表达式为FALSE，转向条件为“假”的出口。E(1)为TRUE，则转向E(2)的判断，若E(2)为TRUE，则整个表达式为TRUE，转向条件为“真”的出口；若E(1)为TRUE，则转向E(2)的判断。若E(2)为FALSE，则整个表达式为FALSE，转向条件为“假”的出口。根据上述的思想将布尔表达式翻译成四元式的描述，其中nextstat给出输出序列中下一个四元式序号，emit过程每被调用一次，nextstat增加1。EE(1)∨E(2) {E.place=newtemp; emit(E.place=E(1).place∨E(2).place) }EE(1)∧E(2) {E.place=newtemp; emit(E.place=E(1).Place∧E(2).place) }EE(1){E.place=newtemp; emit(E.place=

E(1).place) }E(E(1)){E.place=E(1).place}Eid1ropid2{E.place=newtemp; emit(ifid1.placeropid2.placegotonextstat+3) emit(E.Place=0) emit(gotonextstat+2) emit(E.place=1) }Etrue {E.place=newtemp; emit(E.place=

1) }Etrue {E.place=newtemp; emit(E.place=

0)}8.4.3在控制语句中布尔表达式的翻译E的代码S1的代码（a）ifEthenS1代码结构TFE的代码S1的代码（b）ifEthenS1elseS2

代码结构jumpoutS2的代码TFout:E的代码S1的代码（c）whileEdoS1

代码结构jumpbeginTFbegin:图8-5控制语句的代码结构56S→ifEthenS1

的翻译代码结构S1.beginE.trueS.nextE.codeS1.codeE.false57例：ifa>bthena=a+a

ifa>bgotoC.true (S1.begin) gotoC.false (S.next)S1.begin: t1:=a+a a:=t1S.next:（1）EE(1)VE(2){backpatch(E(1).false,E(2).codebegin)；

E.codebegin=E(1).codebegin E.true=merge(E(1).true,E(2).true) E.false=E(2).false }

（2）EE(1)∧E(2){backpatch(E(1).true,E(2).codebegin); E.codebegin=E(1).codebegin E.true=E(2).true E.false=merge(E(1).false,E(2).false) }

（3）EE(1) {E.true=E(1).False; E.codebegin=E(1).Codebegin E.false=E(1).true }（4）E(E(1)) { E.true=E(1).true; E.false=E(1).false E.codebegin=E(1).codebegin }

（5）Eid1ropid2 {E.true=nextstat; E.codebegin=nextstat; E.false=nextstat+1; emit(ifid1.placeropid2.placegoto—); emit(goto—); }（6）Etrue {E.true=nextstat; E.codebegin=nextstat;

emit(goto—) }（7）Efalse{E.false=nextstat; E.codebegin=nextstat;

emit(goto—)}代码结构E.codeS1.beginE.trueS.nextS1.codeE.falsegotoS.nextS2.codeS2.beginS2.nextS1.nextS→ifEthenS1elseS2

的翻译例题8.8给出布尔表达式ifa<b∨c<d∧e>fthenS1elseS2，它翻译成四元式序列为：（1)ifa<bgotoE.true（2）goto（3）（3）ifc<dgoto(5)（4）gotoE.false （5）ife<fgotoE.true（6）gotoE.falseE.true为S1语句目标代码的首地址，E.false为S2语句目标代码的首地址。E为a<b∨c<d∧e>f例题8.8给出布尔表达式ifa<b∨c<d∧e>fthenS1elseS2，它翻译成四元式序列为：（1）ifa<bgotoE.true（2）goto（3）（3）ifc<dgoto(5)（4）gotoE.false

（5）ife<fgotoE.true（6）gotoE.false（7）S1的四元式（p）goto(q)（p+1）关于S2的的四元式（q）（7）（p+1）（7）（p+1）通过上面的例子可以看出:（7）是该条件语句的真出口，(p+1)是该条件语句的假出口。而E.true和E.false必须是在翻译到S1或S2时才能确定它的语句编号是什么，所以需要回填。并且需要回填的语句很多，如四元式（1）和（5）需要回填E.true的值，（4）和（6）需要回填E.false的值。这些要回填的四元式标号需要记住。因此就采用“拉链”的技术，如果不能记住，则无法回填了。把需要回填E.true的值作为真链，把需要回填E.false的值作为“假“链。65拉链回填一遍扫描先产生暂时没有填写目标标号的转移指令；对于每一条这样的指令作适当的记录；一旦转移的目标“标号”被确定下来，再将它“回填”到相应的指令中布尔表达式E设属性E.turelist和E.falselistE.truelist——对应真出口EtrueE.falselist——对应假出口Efalse两遍扫描n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)E.Turelistn366拉链回填翻译模式用到如下两个函数：

1．merge(p1，p2)：将由p2指向的表接在p1所指向的链表后，返回p1

2．backpatch（p，i）：把i作为目标标号回填到p所指向的链表中的每一个转移指令中去。此处的“链表”都是为“回填”作准备的67拉链回填举例——拉链n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)P2:n3P1:n4(j,,,0)……n5(j<,a,b,n4)……n6(j=,c,d,n5)n5n6n42023/1/3168拉链回填举例——并链n1(j,,,0)……n2(j<,a,b,n1)……n3(j=,c,d,n2)P2:n3n4(j,,,)……n5(j<,a,b,n4)……n6(j=,c,d,n5)P1:n60n32023/1/3169n4n2n3n5n6拉链回填——回填n1(j,,,)……n2(j<,a,b,)……n3(j=,c,d,

)n4(j,,,)……n5(j<,a,b,)……n6(j=,c,d,)P1:backpatch（p，i）n5n4n3n2n1i0iiiiin10拉链的技术如下：（100）…gotoE.true …(200)…gotoE.true …(300)…gotoE.true …则链成：（100）…goto（0）

…（200)…goto（100）

…（300)…goto（200）

…把地址300作为链首，地址（100）为链尾，0为链尾标志。根据上面的翻译思想，我们给出将布尔表达式翻译成四元式的描述，其中（1）nextstat为给出序列中的下一个四元式的序号。emit过程每调用一次，nextstat的值就增加1。（2）merge(p1,p2)：把以p1和p2为链首的两条链合并为一条以p2为链首的链。（3）backpatch(p,t)：把链首p所链接的每个四元式的第四区段（即result）都改写为地址t。（4）语义值E.codebegin与非终结符E相连，表示表达式E的第一个四元式语句的序号。merge()函数如下：merge(p1,p2){if(p2==0)return（p1）；else{p=p2;while(四元式p的第四区段内容不为0)