编译原理-第七章

第七章语义分析和中间代码生成1、编译程序的任务是把源语言程序翻译成目标程序，有些编译程序在编译过程中，不产生中间语言，而是直接从源语言程序翻译成目标语言程序。源程序编译程序目标代码

以上编译过程省略了中间语言，它不利于编译所产生的目标代码的优化.为了产生高质量的代码，可以将源语言程序首先翻译成一种特殊形式的中间语言代码形式，并对其进行优化，然后再将它翻译成最终的目标代码。源程序语法分析中间代码优化优化后中间代码目标代码代码生成中间代码

中间代码也叫中间语言（Intermediatecode/language）是：源程序的一种内部表示，不依赖目标机的结构，复杂性介于源语言和机器语言之间。中间代码的优点1、逻辑结构清楚；2、利于不同目标机上实现同一种语言；3、利于进行与机器无关的优化；语义分析在词法分析和语法分析之后，编译程序要完成语义分析和翻译工作。由于编译器完成的分析是静态定义的，所以，语义分析也可称作静态语义分析（staticsemanticanalysis）。语义分析的具体工作1、类型检查；2、控制流检查；3、一致性检查；4、相关名字检查语法制导翻译对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或规约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应地语义动作或语义子程序。每个语义子程序都指明了相应产生式中各个符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作。由此可见：抽象文法符号的具体语义信息，是在语法分析同步的语义处理过程中获取和加工的。属性文法

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

一个文法符号X的语义信息我们称之为语义属性或简称为属性（Atrributes）X.TYPE表示为X的类型X.VAL表示为X的值例:对于文法:E

→E+T|TT→digit

例语法制导翻译的实质

根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）语句或子程序，对所要完成的功能进行描述，在语法分析过程中，当分析器使用该产生式进行语法分析时（不论是推导还是规约），除完成语法分析动作之外，还将调用为其配备的语义子程序，进行相应地语义处理，完成语义翻译工作。中间代码常见的几种形式1、后缀式2、图表示法抽象语法树、DAG图3、三地址代码三元式、四元式、间接三元式后缀式

后缀式是波兰逻辑学家卢卡西维奇（J.Lukasiewicz）提出的一种对表达式的表示方法：每一运算符都置于其运算对象之后，即操作数写在前面，算符写在后面。

它的特点是：表达式中各个运算是按运算符出现的顺序进行的，故无需用括号来指示运算顺序，因而又称为无括号式。实例

表达式（中缀式）：A+B*（C-D）+E/（C-D）

后缀式：CD-B*A+CD-E/+表达式(中缀式):（a=0∧b>3）∨（e∧x

>y）后缀式:a0=b3>xy>e∧∨∧

结论从以上两个例子我们可得出：1、在两种表示中，运算对象出现的顺序相同；2、在后缀表示中，运算符按实际计算顺序从左到右排列，且每一运算符总是跟在运算对象之后。翻译成后缀式的语义描述见P167表7.1。后缀式的推广条件语句的翻译：IfeTHENS1elseS2图表示法-抽象语法树

在语法树中去掉一些对翻译不必要的信息后，获得的更有效的源程序的中间表示，这种经过变换后的语法树称为抽象语法树。在抽象语法树中，操作符和关键字都不作为叶子节点出现，而是把它们作为内部节点，即这些叶子节点的父节点。

例1

if-then-elseBS1S2S→ifBthenS1elseS2例1

++*a*-da-bcbca+a*（b-c）+（b-c）*d翻译成抽象语法树的属性文法见P169表7.2图表示法-DAG图DAG（DirectedAcyclicGraph）有向无循环图对表达式中的每个子表达式，DAG都有一个结点，一个内部结点代表一个操作符，他的孩子代表操作数。在一个DAG中代表公共子表达式的节点具有多个父结点（与抽象语法树中公共子表达式被表示为重复的子树不同）例

++**da-bca+a*（b-c）+（b-c）*d抽象语法树的表示方法1、每一个结点用一个记录来表示，该记录包括一个运算符域和若干个指向子结点的指针域。例：a：=b*-c+b*-cassignassigna+a+***b-b-b-ccc

抽象语法树DAG方法1assign••ida+••*••idbuminus•idc*••idbUminus•idc方法2把所有的结点安排在一个记录的数组中，结点的位置或索引作为指向地点的指针。

三地址代码三地址代码最基本的用法形式:

x:=yopz其中x、y、z为名字、常数或编译时产生的临时变量；op代表运算符号。每个语句的右边只能有一个运算符。例如：x+y*z可以翻译为：

T1：=y*zT2：=x+T1T1、T2位编译时产生的临时变量三地址代码可以看成是抽象语法树一种线性表示assigna+**b-b-cc

抽象语法树

T1:=-cT2:=b*T1T3:=-cT4:=b*T3T5:=T2+T4a:=T5三地址代码三地址代码可以看成是DAG的一种线性表示assigna+*b-c

DAG

T1:=-cT2:=b*T1T3:=T2+T2a:=T3三地址代码最后看P171，表7.3三地址码的各种形式：P170x:=yopzx:=opz

x:=yGotoLifxrelopygotoL

ifagotoL

Paramxcallp,n

returnyx:=y[i]x[i]:=yx:=&y

x:=*y

*x:=y

赋值语句翻译为三地址码的属性文法P171，表7.3三地址代码—四元式四元式实际上是一种“三地址语句”的等价表示，是一个带有四个域的记录结构。它的一般形式为：（op，arg1，arg2，result）需要指出的是：每个四元式只能有一个运算符，所以，一个复杂的表达式只能由多个四元式构成的序列表示。例

a：=b*-c+b*-c三地址代码-三元式

三元式顾名思义就是带有三个域的记录结构，他的一般形式为（i）（op，arg1，arg2）其中，（i）为三元式的编号，也代表了该式的运算结果，op，arg1，arg2的含义与四元式类似，区别在于arg可以是某三元式的序号，表示用该三元式的结果作为运算对象。例a：=b*-c+b*-c三元式和四元式的比较1、无论在一个三元式序列还是四元式序列中，各个三元式或四元式都是按相应表达式的实际运算顺序出现的；相同点：2、对同一表达式而言，所需的三元式或四元式的个数一般都是相同的。三元式和四元式的比较1、由于三元式没有result字段，且不需要临时变量，故三元式比四元式占用的存储空间少；不同点：2、在进行代码优化处理时，常常需要挪动一些运算的位置，这对于三元式序列来说是很困难的，但对于四元式来说，由于四元式之间的相互联系是通过临时变量来实现的，所以，更改其中一些四元式给整个系列带来的影响就比较小。三地址代码-间接三元式

建立两个与三元式有关的表格，一个称为三元式表，用于存放各三元式本身；另一个称为执行表，它按照三元式的执行顺序，依次列出相应各三元式在三元式表中的位置，也就是说我们用一个三元式表连同执行表来表示中间代码。通常我们称这种表示方法为间接三元式。例x：=（a+b）*cb：=a+by：=c*（a+b）三元式x：=（a+b）*cb：=a+by：=c*（a+b）

（1）（+，a，b）（5）（+，a，b）（2）（*，（1），c）（6）（*，c，（5））（3）（：=，x，（2））（7）（：=，y，（6））（4）（：=，b，（1））

间接三元式x：=（a+b）*c

b：=a+b

y：=c*（a+b）执行表三元式表（1）（1）（+，a，b）（2）（2）（*，（1），c）（3）（3）（：=，x，（2））（4）（4）（：=，b，（1））（1）（5）（：=，y，（2））（2）（5）三元式与间接三元式之间的区别1、由于间接三元式在执行表中已经依次列出每次要执行的那个三元式，若其中有相同的三元式，则仅需在三元式表中保存其中之一，即三元式的项数一般比执行表的项数少；2、当进行代码优化需要挪动运算顺序时，则只需对执行表进行相应地调整，而不必再改动三元式本身，这样，就避免了前面讲到的因改变三元式的顺序所引起的麻烦。四元式：一般形式:(Op，arg1，arg2，result)arg1、arg2为参加运算的两个分量result为运算结果若为单目运算，arg2为空，用“-”表示举例说明：1.表达式的四元式：例1.a*b+c/d(*,a,b,T1)(/,c,d,T2)(+,T1,T2,T)例2.-(a*b-c)(*,a,b,T1)(-,T1,c,T2)(@,T2,-,T)@表示单目运算减2.赋值语句的四元式：把赋值看成一种运算，arg2为空例1：x:=10(:=,10,-,x)例2：x:=-(a*b-c)(*,a,b,T1)

(-,T1,c,T2)

(@,T2,-,T)

(:=,T,-,x)3.转向语句的四元式：有以下三种跳转四元式：(jnz,a,-,p)表示ifagotop；(jrop,x,y,p)表示ifxropygotop；(j,-,-,p)表示gotop；rop为：=，<>，<=<，>=，>

4.条件语句的四元式：例1：ifa<bthenx:=a+belsex:=a-b对应的四元式为：(1)(j<,a,b,

)(2)(j,-,-,

)(3)(+,a,b,T1)(4)(:=,T1,-,x)(5)(j,-,-,

)(6)(-,a,b,T2)(7)(:=,T2,-,x)(8)……685.循环语句的四元式

待讨论循环语句的翻译时介绍。回填回填回填3例2：ifa<bande＞dthenx:=a+belsex:=a-b例3：ifa<bore＞dthenx:=a+belsex:=a-b

语法制导的翻译方法：

就是对文法中的每个产生式都附加一个语义动作或语义子程序，且在语法分析过程中，每当需要使用一个产生式进行推导或归约时，语法分析程序除执行相应的语法分析动作之外，还要执行相应地语义动作或语义子程序。每个语义子程序都指明了相应产生式中各个符号的具体含义，并规定了使用该产生式进行分析时所应采取的语义动作。翻译过程见P171表7。3。这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。一.过程中的说明语句说明语句的翻译，主要工作是填符号表、分配地址说明语句的文法产生式及语义动作如下：T→integer {T.type:=integer;T.width:=4}T→real {T.type:=real;T.width:=8}T→array[num]ofT1 {T.type:=array(num.val,T1.type); T.width:=num.val*T1.width}T→↑T1 {T.type:=pointer(T1.type); T.width:=4}D→D;DD→id:T {enter(,T.type,offset);offset:=offset+T.width}P→MD {offset:=0}M→ε{offset:=0}offset为存储空间分配指针，每个过程均从0开始。enter为填符号表过程7.2说明语句的翻译

例：a:integer;b:real7.3赋值语句的翻译S→id:=E{p:=lookup();ifp<>nilthenemit(id.place,‘:=’,E.place)elseerror }E→(E1){E.place:=E1.place;}E→-E1{E.place:=newtemp;emit(E.place,‘:=’,‘uminus’,E1.place)}E→E1*E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘*’,E2.place)}E→E1+E2{E.place:=newtemp; emit(E.place,‘:=’,E1.place‘+’,E2.place)}7.3.1简单算术表达式及赋值语句的翻译简单算术表达式及赋值语句的产生式及语义动作如下：Lookup为查符号表过程Emit过程用于生成三地址码指令语句并送往输出文件E→id{p:=lookup();ifp<>nilthenE.place:=pelseerror}掌握1、2、lookup()3、

emit(…)的含义7.3.2数组元素的引用一、数组元素的地址计算1、一维数组设数组A[low..n],每个元素占w个单元，则LOC(A[i])=base+(i-low)*w

=i*w+(base-low*w)其中varpart=i*wC=low*wconspart=base-C即地址D=varpart+conspart7.3.2数组元素的引用一、数组元素的地址计算2、二维数组(按行存放）设i1,i2的下界为low1,low2,数组是n1×n2,每个元素占w个单元，则LOC(A[i1,i2])=base+((i1-low1)*n2+i2-low2)*w

=((i1*n2)+i2)*w+(base-((low1*n2)+low2)*w)其中varpart=((i1*n2)+i2)*w

C=((low1*n2)+low2)*w)conspart=base-C即地址D=varpart+conspart推广到k维数组(按行存放）LOC(A[i1,i2，…,ik])=(…(i1*n2+i2)n3+i3)…)nk+ik)*w+base-(…(low1*n2+low2)n3+low3)…)nk+lowk)*w对C或varpart的计算，可用递归公式e1=i1em=em-1*nm+im当m=k时，ek*w7.3.2数组元素的引用一、数组元素的地址计算例：A[x]

地址可变部分为x*W,应生成指令：

(T’:=X*W)A[x,y]地址可变部分为(x*n2+y)*W,应生成指令：

(T1:=X*n2)

(T1:=T1+y)

(T’:=T1*W)A[x,y,z]地址可变部分为((x*n2+y)*n3+z)*W,应生成指令：(T1:=X*n2)

(T1:=T1+y)(T2:=T1*n3)

(T3:=T2+z)

(T’:=T3*W)地址不变部分的指令为:

(T=A-C)地址结果指令为:

(T’’=T[T’])二、赋值语句中数组元素的翻译赋值语句的文法：S→id:=EE→E1+E2E→E1*E2E→-E1E→(E1)E→id

增加L→id[Elist]|idElist→Elist,E|E为便于语义处理，再改为L→Elist]|idElist→Elist,E|id[ELL含数组元素的赋值语句的文法p181-183(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.Elist.array2.Elist.ndim3.limit(array,j)4.Elist.place5.L.place,L.offset

含有数组的赋值语句文法产生式如下： (1)S→L:=E

(2)E→E+E

(3)E→(E)

(4)E→L

(5)L→id

(6)Elist→id[E

(7)Elist→Elist,E

(8)L→Elist]例：x:=A[y,z]的语法树如右图：xSL:=ELE]ElistEElist,Lz[LAy（3）L→Elist]

{L.place:=newtemp;emit(L.place‘:=’Elist.array‘-’C);

L.offset:=neswtemp;

emit(L.offset‘:=’w‘﹡’Elist.place)}（1）Elist

→id[E

{Elist.place:=E.place;Elist.ndim:=1;

Elist.array:=id.place}（2）Elist→Elist1，E

{t:=newtemp; m:=Elist1.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}（4）L→id

{L.place:=id.place;L.offset:=null}其相应的语义动作如下：计算：Em=Em-1*nm+im赋初值：(E1=i1)例见P183（7）E

→E1+E2

{E.place:=newtemp;

emit(E.place‘:=’E1.place‘+’E2.place)}（6）E

→(E1)

{E.place:=E1.place}（5）E→L

{ifL.offset=nullthenE.place:=L.place

elsebeginE.place:=newtemp;

emit(E.place‘:=’L.place‘[’L.offset‘]’)

end}（8）S→L:=E

{ifL.offset=nullthen/*L是简单变量*/

emit(L.place‘:=’E.place)

elseemit(L.place‘[’L.offset‘]’‘:=’E.place)}7.4布尔表达式的翻译文法：E→EorE|EandE|notE|(E)|idrelopid|id

布尔表达式是由布尔运算符作用于布尔变量或关系表达式组成。布尔运算符：notandor关系表达式：E1ropE27.4布尔表达式的翻译布尔表达式的计算通常有两种方法：

1.严格按计算规则进行：例：1or(not0and0)or0=1or(1and0)or0=1or0or0=1or0=12.采取优化措施，省略计算步骤：即：AorB→ifAthen1elseBAandB→ifAthenBelse0notA→ifAthen0else1在程序中布尔表达式的作用有两个方面：计算逻辑值；控制程序流程；因此讨论布尔表达式的两种翻译方式：逻辑值计算：Ex1.aorbandnotc翻译为：T1:=notcT2:=bandT1T3:=aorT2Ex2.a<b翻译为:100:ifa<bgoto103101:T:=0102:goto104103:T:=1104:Ex3.a<borc<dande<f的三地址代码100)ifa<bgoto103105)T2:=0110)goto112101)T1:=0106)goto108111)T3:=1102)goto104107)T2:=1112)T4:=T2andT3103)T1:=1108)ife<fgoto111113)T5:=T1orT4104)ifc>dgoto107109)T3:=0则计算逻辑值的布尔表达式的语义动作为：P186E→id{E.place:=id.place}E→id1relopid2{E.place:=newtemp;emit(‘if’id1.placerelop.Opid2.Place‘goto’nextstat+3); emit(E.place‘:=’‘0’); emit(‘goto’nextstat+2);emit(E.place‘:=’‘1’)}E→(E1) {E.place:=E1.place}E→notE1 {E.place:=newtemp;emit(E.place‘:=’‘not’E1.place)}E→E1andE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘and’E2.place)}E→E1orE2 {E.place:=newtemp; emit(E.place‘:=’E1.place‘or’E2.place)}二、作为条件控制的布尔式翻译

由于条件语句：if

E

thenS1elseS2中

E的作用仅在于控制对

S1或S2

的选择，而E的值无须保留,因此赋予E两个新的语义值:

E.true(真出口,出向S1)

E.false(假出口,出向S2)其含义及作用见图：E.codeS1.codeGotos.nextS2.code…

E.true

E.falseE.true：E.false：

S.next:ifEthenS1elseS2Ex1:ifa>corb<dthens1elses2翻译：ifa>cgotoL2gotoL1L1:ifb<dgotoL2gotoL3L2:S1的代码

gotoSnextL3:S2的代码Snext:二、作为条件控制的布尔式翻译思路对布尔表达式E,引入标号E.ture和E.falseE形如a<bE形如E1orE2E形如E1andE2E形如notE1seeP188table7.7Ex2.a<borc<dande<f的三地址代码设整个表达式的真假出口为Etrue和Efalse,则代码：Ifa<bgotoEturegotoL1L1:ifc<dgotoL2gotoEfalseL2:ife<fgotoEturegotoEfalse

seeP188table7.71、四元式形式表示三地址码（jnz,a,,p)(jrop,x,y,p)(j,,,p)2、关于拉链回填问题写出以下语句的四元式形式：Ex1:a<borc<dande<fEx2:Aor(Bandnot(CorD))seeP190二.作为条件控制的布尔表达式的翻译（一遍扫描）

对于条件语句：if

E

thenS1elseS2翻译分析到

E

时，S1、S2并未进行翻译，既使计算出E的结果也不知跳转到何处，因此赋予E两个新的语义值:

E.true

(真出口,记录跳往S1的语句号,待回填)

E.false(假出口,记录跳往S2的语句号,待回填)其含义及作用见图：E.codeS1.codeGotos.nextS2.code…

E.true

E.false[E.true][E.false]

S.next

另外：当E自身较复杂时，跳往S1、S2的语句可能为多条，为记录这多条语句，可以将这些语句建一链表:并改：E.true为

E.truelist(记录跳往S1的语句链表表头)

E.false为E.falselist(记录跳往S2的语句链表表头)

(※,※,※,0)0为链尾标识

……(q)(※,※,※,P)……(r)(※,※,※,q)←链表表头为r此外：为记录下一条即将产生的四元式号，以便及时回填跳往该四元式的语句，我们在文法中插入非终结符M，用于在翻译分析时遇见M即记录四元式号，则布尔表达式文法修改为：

(1)M→ε

(2)E→E1orME2|E1and

ME2|notE1|(E1)|id1relopid2|id上述文法的语义动作如下：(1)M→ε

{M.quad:=nextquad}(7)E→id {E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘jnz’‘,’id.place‘,’‘-‘‘,’‘0’);emit(‘j,-,-,0’)}(6)E→id1relopid2{E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(‘j’relop.op‘,’id1.place‘,’id2.place‘,’‘0’);emit(‘j,-,-,0’)(5)E→(E1)

{E.truelist:=E1.truelist;E.falselist:=E1.falselist}

(4)E→notE1{E.truelist:=E1.falselist;E.falselist:=E1.truelist}(2)

E→E1orME2{backpatch(E1.falselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist}(3)

E→E1andME2{backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist)}即将产生的四元式号（地址）将M.quad回填至E1.truelist为表头的链表上各四元式中将E1.falselist和E2.falselist为表头的两条链合并创建一条新链表nextquad为该链中唯一一个四元式的地址写出以下语句的四元式形式：Ex1:a<borc<dande<f7.5控制语句的翻译一.控制流语句S→ifEthenS1|ifEthenS1elseS2|whileEdoS1上述的红色跳转语句相当于S的出口，在对S语句进行翻译分析时，其跳转目标并不确定，因此赋予S语义值:S.next。E.falselistE.codeS1.code…E.truelist[E.truelist][E.falselist]E.codeS1.codeGotos.nextS2.code…E.truelistE.falselist[E.truelist][E.falselist]S.nextE.codeS1.codegotoS.begin…E.truelistE.falselist[E.truelist][E.falselist]S.begin此外，考虑到语句可以嵌套等因素，S的出口语句可能有多条，也需要建立链表，因此将S.next改为S.nextlist。S.nextlist：记录S的出口语句链表表头,待回填。S.next：S的出口,记录跳出S的语句号,待回填。例：

ifE1then

{ifE2thenS1}

elseS2E1.codeE2.codeS1.codeGotoS.nextlistS2.code…E2.truelistE2.falselist[E2.truelist]S.nextlist

[E2.falselist]E1.truelistE1.falselist[E1.truelist][E1.falselist]更为完整的控制语句文法产生式如下：

(1)S→ifEthenS(6)L→L;S(2)|ifEthenSelseS(7)

|S(3)