语义分析和中间代码产生课件

第七章

语义分析和中间代码产生第七章

语义分析和中间代码产生17．1中间代码

7．1中间代码27.1.1逆波兰表示法

逆波兰表示法是波兰逻辑家Lukasiewicz发明的一种表示表达式的方法。该方法是将运算量写在前面，算符写在后面，用这种方法表示的表达式称为后缀式，如a+b可写成ab+。一般而言，若θ是K目算符，它对后缀式e1，e2，...，ek作用的结果将被表示为e1e2...ekθ。7.1.1逆波兰表示法

逆波兰表示法是波兰逻辑家Lukas3后缀式的计算：一个后缀式的计算过程是使用一个栈，然后自左向右扫描后缀式，每遇到运算量就将它推进栈中，每遇到K目运算符就把它作用于栈顶部的K个项，并用运算结果来替代这K个项。可以看出表达式的后缀式表示法对进行表达式的计算而言具有很强的方便性。后缀式的计算：一个后缀式的计算过程是使用一个栈，然后自左向右4后缀式的推广：后缀式这种表示法可以比较方便的推广到其它的描述地方，例如对条件算术表达式ifethenxelsey（含义为，若e=0，此式为y，否则等于x）而言，可以将if-then-else看成一个三目算符@，则该条件表达式的后缀式可写为exy@，考虑一下该表示法的缺点，和解决该缺点的方法。后缀式的推广：后缀式这种表示法可以比较方便的推广到5语法制导生成后缀式：E→E（1）+E（2）{E.CODE:=E（1）.CODE||E（2）.CODE}E→(E（1）){E.CODE:=E（1）.CODE}E→i {E.CODE:=i}语法制导生成后缀式：67.1.2三元式和树

三元式的形式为:(OP,ARG1,ARG2)；OP是运算符，ARG1、ARG2分别为第一运算量和第二运算量。表达式A+B*C可以表示为：(1)(*，B，C)(2)(+，A，（1）)其中三元式（2）是表达式A+B*C的最终代表，三元式（2）中的（1）指第一个三元式的结果。7.1.2三元式和树

三元式的形式为:(OP,ARG1,A7为产生中间代码，现定义几个相关的函数，这些函数主要是为使用符号表和保存中间代码而定义的。LOOKUP（NAME）：对NAME查找符号表。若此名出现在表中，则将其表项位置（入口）作为LOOKUP的值；否则，LOOKUP取值为null。FILLSYM（NAME）：在符号表中开辟一新项，项目名为NAME，把此项的入口作为FILLSYM的值。为产生中间代码，现定义几个相关的函数，这些函数主要是为使用符8TRIP（OP，ARG1，ARG2）：产生一个新三元式（OP，ARG1，ARG2），该过程将新的三元式放入三元式代码区中，并返回在三元式表中的位置。ERTRY(i)：对i所代表的标识符查找符号表以获得它在表中的位置TRIP（OP，ARG1，ARG2）：产生一个新三元式（OP9通常的表达式翻译成三元式的语义动作如下：（1）E→E（1）opE（2）{E.VAL:=TRIP(op,E（1）.VAL,E（2）.VAL}（2）E→-E（1）

{E.VAL：=TRIP(@,E（1）.VAL,-)}（3）E→（E（1））{E.VAL：=E（1）.VAL}通常的表达式翻译成三元式的语义动作如下：10（4）E→i {E.VAL：=ENTRY(i)}试将下面语句序列给出其相应的三元式代码序列：

X：=（A+B）*C； Y：=D↑（A+B）；（4）E→i {E.VAL：=ENTRY(11三元式序列如下：<1>（+，A，B）<2>（*，①，C）<3>（:=，X，②）<4>(+，A，B)<5>(↑，D，④)<6>(:=，Y，⑤)三元式序列如下：12可以看出，该三元式序列是可以优化的，但是优化过程需要调整运算顺序，例如三元式（4）与（1）是相同的，可去掉（4），此时三元式（5）和（6）都需要修改，为解决三元式优化修改的困难，可辅助以一张间接码表加以解决，这种表示法称为间接三元式。可以看出，该三元式序列是可以优化的，但是优化过程需要调整运算13<1>（+，A，B）<2>（*，①，C）<3>（:=,X,②）<4>(↑,D,①)<5>(:=,Y,④)间接码表：①②③①④⑤<1>（+，A，B）147.1.3 四元式四元式有四个部分：（OP，ARG1，ARG2，RESULT）

OP一般代表确定运算符的整数码，ARG1，ARG2，RESULT或者是一个指向符号表的某一个入口的指示器，或者是一个代表临时变量的整数码，7.1.3 四元式四元式有四个部分：（OP，ARG1，ARG15临时变量的表达可有两种处理方法：（1）将临时变量与用户自定义的变量同等看待添入符号表中，在四元式的运算量或运算结果位置通过指向符号表该临时变量的入口指示器来使用该临时变量。（2）使用某种整数编码来表示临时变量，这样就不用将其放入符号表中。

请思考一下三元式与四元式在中间代码优化时哪种代码形式便于优化？

以下各节有关翻译的讨论均基于四元式代码的翻译

临时变量的表达可有两种处理方法：167.2简单算术表达式和赋值语句到四元式的翻译 增加几个翻译中需要的几个函数：

NEWTEMP：是一个函数过程，每次调用回送一个代表新临时变量名的整数码。以下我们用Ti表示相应产生的临时变量。 ENTRY（i）：定义同前。

7.2简单算术表达式和赋值语句到四元式的翻译 增加几个翻译17GEN（OP，ARG1，ARG2，RESULT）：将四元式（OP，ARG1，ARG2，RESULT）填入四元式表中，并将添入的位置返回。

E．PLACE：它是和非终结符E相联系的语义变量，表示存放E值的变量在符号表的入口或整数码（若此变量是一个临时变量）。

GEN（OP，ARG1，ARG2，RESULT）：将四元式（18设只含整型变量的简单赋值语句的文法如下：

A→i:=E

E→E+E|E*E|-E|(E)|i

设只含整型变量的简单赋值语句的文法如下：

19翻译算法由如下的语义动作描述:

(1)A→i:=E {GEN(:=，E.PLACE，，ENTRY（i）)}

(2)E→E（1）+E（2）

{E.PLACE:=NEWTEMP;GEN(+，E（1）.PLACE，E（2）.PLACE，E.PLACE)}

(3)E→E（1）*E（2）{E.PLACE:=NEWTEMP;

GEN(*，E（1）.PLACE，E（2）.PLACE，E.PLACE)}

翻译算法由如下的语义动作描述:

(1)A→i:=E 20(4)E→（E（1））{E.PLACE:=E（1）.PLACE}(5)E→-E（1）

{E.PLACE:=NEWTEMP;

GEN(@，E（1）.PLACE，，E.PLACE)}

(6)E→i{E.PLACE:=ENTRY(i)}

(4)E→（E（1））217.3布尔表达式的翻译布尔表达式的翻译可以仿照算术表达式的翻译过程，但是布尔表达式的运算有自己的特点，即布尔表达式的运算结果可能只需要运算一部分即可得到，这就是短路运算。对于布尔表达式这种计算方法可以用条件语句的形式加以表示。7.3布尔表达式的翻译布尔表达式的翻译可以仿照算术表达式的22例如：

A∨B对应于ifAthentrueelseB

A∧B 对应于ifAthenBelsefalse

╗A对应于ifAthenfalseelsetrue

A∨（B∧（╗C∨D））可按此法翻译成：

ifAthentrueelse

ifBthen

ifCthenDelsetrue

elsefalse

例如：

A∨B对应于ifAthentruee23布尔表达式E一般出现在控制语句中，我们不需要保留布尔表达式的结果，而只需要在计算E的代码中，当发现E的结果为真时（称为E的真出口）就转向到某个地方，或发现为假时（称为E的假出口）跳转到另一个地方继续执行控制体中相应的计算。可以看出这种想法也可以运用到布尔表达式E的计算过程中。布尔表达式E一般出现在控制语句中，我们不需要保留布尔表达式的24例如对于产生式E→E1∨E2，E1为真，则E必为真，E1的真出口为E的真出口，E1为假则E的真假出口取决于E2的真假出口，此时E1的假出口应转向到E2的相应四元式代码的第一条四元式。

现定义几种转移四元式：

（jnz，A，，P）A为真（非0）时转到第P条四元式。

（jrop，A1，A2，P）A1ropA2成立时，转到第P条四元式。

（j，，，P）无条件转向到第P条四元式。

例如对于产生式E→E1∨E2，E1为真，则E必为真，E1的25例7.1：ifA∨B〈CthenS1ELSES2

可翻译成如下四元式序列：

1．（jnz，A，，5）

2．（j，，，3）

3．（j<，B，C，5）

4．（j，，，P+1）

.....S1的代码序列

p.(j，，，q)

P+1....S2的代码序列

q.例7.1：ifA∨B〈CthenS1ELSES226为描述布尔表达式的翻译现定义：NXQ：表示将要产生的下一条四元式的地址。GEN（op，arg1，arg2，result）：同前面的描述，GEN每调用一次NXQ增加1。为描述布尔表达式的翻译现定义：27MERGE（P1，P2）：P1，P2两条链和并，返回链头P2。BACKPATCH（P，T）：将四元式序号T填入以P为链头的四元式链中的所有四元式的RESULT域。MERGE（P1，P2）：P1，P2两条链和并，返回链头P228设布尔表达式的文法为：E→E∨E|E∧E|╗E|（E）|i|iropi为便于构造语义子程序将该文法加以改造：E→E∨E2

{E.FC:=E2.FC;E.TC:=MERGE(E∨.TC,

E2.TC)｝E→E∧E2 {E.TC:=E2.TC;E.FC:=MERGE(E∧.FC,

E2.FC)｝设布尔表达式的文法为：29E→╗E1

{E.TC:=E1.FC;E.FC:=E1.TC}E→（E1） {E.TC:=E1.TC;E.FC:=E1.FC}E→i {E.TC:=NXQ;E.FC:=NXQ+1;GEN(jnz,ENTRY(i),,0);GEN(j,,,0);}E→╗E1 30E→i1ropi2

{E.TC:=NXQ;E.FC:=NXQ+1;GEN(jrop,ENTRY(i1),ENTRY(i2),0); GEN(j,,,0);}E∨→E1∨ {BACKPATCH(E1.FC,NXQ);E∨.TC:=E1.TC}E→i1ropi231E∧→E1∧ {BACKPATCH(E1.TC,NXQ);E∧.TC:=E1.TC}语义分析和中间代码产生课件327.4控制语句的翻译

7.4.1语句标号与GOTO语句的翻译 标号在程序中分定义性出现和使用性出现。 标号定义性出现的形式为：L：S；L是标号，S是语句。 标号使用性出现的形式为：GOTOL；

标号可先定义后使用，也可先使用后定义。7.4控制语句的翻译

7.4.1语句标号与GOTO语句的33

GOTO语句可翻译成无条件转移四元式，其转移地址为GOTO语句中出现的标号的定义性出现位置。为在翻译中记载标号定义的位置以供翻译GOTO语句时使用，应将标号和其定义位置存放入符号表中。翻译GOTO语句时应该用标号查找符号表得到定义位置，若没有查到该标号，应该将标号存入符号表中注明为未定义并将使用该标号的四元式的地址记载下来。问题:多个GOTO语句使用该标号，而该标号还没定义，那么这多个GOTO语句的地址该如何保留。 GOTO语句可翻译成无条件转移四元式，其转移地址为GOTO34符号表的形式为：

NAMETYPE......DEFADDR设标号定义性出现的文法描述为：L->i:使用该产生式归约时的动作为:若i不在符号表中则将i添入符号表并将DEF填为未定义。地址栏ADDR填写NXQ的值。符号表的形式为：35若i已在符号表中但类型不为标号或虽然是标号但DEF栏填的是已定义,则程序语义有错误.若i已在符号表中但DEF栏填的是未定义,则将DEF栏改为已定义,ADDR栏填NXQ,并执行BACKPATCH(q,NXQ).q为ADDR栏原保留的需要回填同一转移地址的四元式链的链头.若i已在符号表中但类型不为标号或虽然是标号但DEF栏填的是36设GOTO语句的产生式为S->GOTOL;语义动作为: {lookup:=LOOKUP(L);iflookup=nullthenbeginENTRY(L);ENTER.TYPE:=L;ENTER.DEF:=0;ENTER.ADDR:=NXQ;GEN(j,,,0);END设GOTO语句的产生式为S->GOTOL;37ELSEiflookup.def=1then GEN(j,,,lookup.ADDR) else beginn:=NXQ; GEN(j,,,lookup.ADDR) lookup.ADDR:=n; end如果考虑标号的作用域,语义动作应该如何表示?ELSEiflookup.def=1387.4.2用于组织控制流程的一些语句的翻译

考虑if语句,while语句和复合语句的翻译.

7.4.2用于组织控制流程的一些语句的翻译

考虑if语句,39一般使用如下的文法描述这些语句:

G[S]: 1.S->ifEthenS|ifEthenSelseS |whileEdoS|beginLend|A L->L;S|S

各非终结符的含义是:S--语句, L--语句串,

A--赋值句,E--布尔表达式一般使用如下的文法描述这些语句:40 为方便翻译现将文法改造如下:

S->CS1

{S.CHAIN:=MERGE(C.CHAIN,S1.CHAIN)} S->TPS2

{S.CHAIN:=MERGE(TP.CHAIN,S2.CHAIN)}

S->WDS3

{BACKPATCH(S3.CHAIN,WD.QUAD)GEN(J,,,WD.QUAD);S.CHAIN:=WD.CHAIN} 为方便翻译现将文法改造如下:41S->beginLend{S.CHAIN:=L.CHAIN}S->A {S.CHAIN:=0}L->LSS1

{L.CHAIN:=S1.CHAIN}L->S {L.CHAIN:=S.CHAIN}S->beginLend42C->ifEthen{BACKPATCH(E.TC,NXQ);C.CHAIN:=E.FC}TP->CS1ELSE {q:=NXQ;GEN(J,,,0);BACKPATCH(C.CHAIN,NXQ);TP.CHAIN=MERGE(S1.CHAIN,q)}W->while {W.QUAD:=NXQ}WD->WEdo{BACKPATCH(E.TC,NXQ);WD.CHAIN:=E.FC; WD.QUAD:=W.QUAD}LS->L; {BACKPATCH(L.CHAIN,NXQ)}C->ifEthen{BACKPATCH(E.TC43例7.2:按上述语义动作将语句

while(A<B)do if(C<D)thenＸ:=Y+Z翻译成四元式序列。例7.2:按上述语义动作将语句447.4.3循环语句的翻译循环语句的文法描述形式为：S->fori:=E1stepE2untilE3doS1

7.4.3循环语句的翻译循环语句的文法描述形式为：45假定步长为正,则上述循环语句等价与下列程序片段:

i:=E1;

goto

OVER;AGAIN:i:=i+E2;OVER:ifi<=E3then beginS1;gotoAGIANend;按循环语句的这个实现模型进行翻译,我们改写文法并写出各产生式相应的语义动作如下:假定步长为正,则上述循环语句等价与下列程序片段:46F1->fori:=E1

{GEN(:=,E1.PLACE,,ENTRY(i)); F1.PLACE:=ENTRY(i); F1.CHAIN:=NXQ; GEN(j,,,0); F1.QUAD:=NXQ;}F1->fori:=E1 47F2->F1stepE2

{F2.QUAD:=F1.QUAD;F2.PLACE:=F1.PLACE; GEN(‘+’,F1.PLACE,E2.PLACE,F1.PLACE); BACKPATCH(F1.CHAIN,NXQ);}F2->F1stepE248F3->F2untilE3

{F3.QUAD:=F2.QUAD; q:=NXQ; GEN(j<=,F2.PLACE,E3.PLACE,q+2); F3.CHAIN:=NXQ GEN(j,,,0)}F3->F2untilE349S->F3doS1

{GEN(j,,,F3.QUAD); BACKPATCH(S1.CHAIN,F3.QUAD); S.CHAIN:=F3.CHAIN}S->F3doS1 507.5数组元素的引用

假定每个数组元素只占用一个机器字并以行为序存放，目标机器以字编址，数组说明的形式为：arrayA[l1：u1，l2：u2，...，ln：un]。A数组的某个元素的引用为A[i1，i2，...,in]。

7.5数组元素的引用

假定每个数组元素只占用一个机器字并以行51令di=ui-li+1则,i=1,2,...,n。则该元素的存储地址为：D=CONSPART+VARPART，其中：CONSPART=a-C，a为数组存储区域的起点地址，即A[l1，l2，...，ln]的地址。C=(...((l1d2+l2)d3+l3)d4+...+ln-1)dn+lnVARPART==(...((i1d2+i2)d3+i3)d4+...+in-1)dn+in令di=ui-li+1则,i=1,2,...,n。则该52CONSPART部分在数组说明时就可得到，我们可以在数组说明时将其算出并放入符号表中。VARPART部分则需要程序运行时才可算出，也就是我们在翻译时要翻译出执行计算VARPART的代码。我们可以将VARPART的结果放入某个临时变量T中而CONSPART的结果放入另一个临时变量T1中，同时用T1[T]表示数组元素的地址。对应“数组元素引用”和“对数组元素赋值”有两个相应的四元式：CONSPART部分在数组说明时就可得到，我们可以在数组说明53“变址取数”->（=[],T1[T],,X）/*相当于X:=T1[T]*/；“变址存数”->([]=,X,,T1[T])/*相当于T1[T]:=X*/。“变址取数”->（=[],T1[T],,X）/*相当54设描述赋值语句中数组元素使用的文法如下：A->V:=E V->i[elist]|i elist->elist,E|EE->E+E|(E)|V为便于翻译,文法改写:

V->elist]|i elist->elist,E|i[E设描述赋值语句中数组元素使用的文法如下：55定义几个语义变量与过程:elist.ARRAY:保留数组在符号表中的位置.eLIST.PLACE:保留已形成的VARPART的中间结果单元位置.elist.DIM:数组维数计数器.LIMIT(ARRAY,K):从符号表中取数组ARRAY的第K维的长度.ARRAY为符号表中的某个地址.定义几个语义变量与过程:56V.PLACE,V.OFFSET:

若V为简单变量名i归约所的,则V.PLACE存放i在符号表中的地址,V.OFFSET则为NULL;若V为下标变量名,则V.PLACE存放保存CONSPART的临时变量名的整数码,V.OFFSET则指存放保存VARPART的临时变量名的地址.V.PLACE,V.OFFSET:57A->V:=E {if(V.OFFSET=NULL)thenGEN(:=,E.PLACE,,V.PLACE) ELSEGEN([]=,E.PLACE,V.PLACE[V.OFFSET])}E->E1+E2 {T:=NEWTEMP;GEN(+,E1.PLACE,E2.PLACE,T);E.PLACE:=T}A->V:=E 58E->(E1){E.PLACE:=E1.PLACE}E->V {if(V.OFFSET=NULL)thenE.PLACE:=V.PLACE elsebeginT:=NEWTEMP; GEN(=[],V.PLACE[V.OFFSET],,T) E.PLACE:=T; end }E->(E1){E.PLACE:=E1.PLACE59V->elist] {T:=NEWTEMP; GEN(-,elist.ARRAY,C,T); V.PLACE:=T;V.OFFSET:=elist.PLACE}/*假设通过elist.ARRAY可以获得相应数组的常数C*/V->i {V.OFFSET:=NULL;V.PLACE:=ENTRY(i)}V->elist] 60elist->elist1,E{T:=NEWTEMP;K:=elist.DIM+1; dk:=LIMIT(elist1.ARRAY,K); GEN(*,elist1.PLACE,dk,T) GEN(+,E.PLACE,T,T); elist.ARRAY:=elist1.ARRAY; elist.PLACE:=T; elist.DIM:=K }elist->i[E {elist.PLACE:=E.PLACE;elist.DIM:=1