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

第七章第七章 语义分析和中间代码产生语义分析和中间代码产生第七章 语义分析和中间代码产生171 中间代码 71 中间代码 27.1.1 逆波兰表示法逆波兰表示法是波兰逻辑家Lukasiewicz发明的一种表示表达式的方法。该方法是将运算量写在前面，算符写在后面，用这种方法表示的表达式称为后缀式，如a+b可写成ab+。一般而言，若是K目算符，它对后缀式e1，e2，.，ek作用的结果将被表示为e1 e2.ek。7.1.1 逆波兰表示法逆波兰表示法是波兰逻辑家Lukas3后缀式的计算：一个后缀式的计算过程是使用一个栈，然后自左向右扫描后缀式，每遇到运算量就将它推进栈中，每遇到K目运算符就把它作用于栈顶部的K个项，并用运算结果来替代这K个项。可以看出表达式的后缀式表示法对进行表达式的计算而言具有很强的方便性。后缀式的计算：一个后缀式的计算过程是使用一个栈，然后自左向右4 后缀式的推广：后缀式这种表示法可以比较方便的推广到其它的描述地方，例如对条件算术表达式 if e then x else y（含义为，若e=0，此式为y，否则等于x）而言，可以将if-then-else看成一个三目算符，则该条件表达式的后缀式可写为exy，考虑一下该表示法的缺点，和解决该缺点的方法。后缀式的推广：后缀式这种表示法可以比较方便的推广到5语法制导生成后缀式：EE（1）+E（2）E.CODE:=E（1）.CODE|E（2）.CODE E(EE(E（1）)E.CODE:=E E.CODE:=E（1）.CODE.CODEEiEi E.CODE:=i E.CODE:=i语法制导生成后缀式：67.1.27.1.2三元式和树三元式和树三元式的形式为:(OP,ARG1,ARG2)；OP是运算符，ARG1、ARG2分别为第一运算量和第二运算量。表达式A+B*C可以表示为：(1)(1)(*(*，B B，C)C)(2)(2)(+(+，A A，（，（1 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）EE（1）op E（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）Ei E.VAL：=ENTRY(i)试将下面语句序列给出其相应的三元式代码序列：X：=（A+B）*C；Y：=D（A+B）；（4）Ei E.VAL：=ENTRY(11三元式序列如下：（+，A A，B B）（*，C C）（:=:=，X X，）(+(+，A A，B)B)(，D D，)(:=(:=，Y Y，)三元式序列如下：12可以看出，该三元式序列是可以优化的，但是优化过程需要调整运算顺序，例如三元式（4）与（1）是相同的，可去掉（4），此时三元式（5）和（6）都需要修改，为解决三元式优化修改的困难，可辅助以一张间接码表加以解决，这种表示法称为间接三元式。可以看出，该三元式序列是可以优化的，但是优化过程需要调整运算13（+，A，B）（*，C）（:=,X,）(,D,)(:=,Y,)间接码表：（+，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）填入四元式表中，并将添入的位置返回。EPLACE：它是和非终结符E相联系的语义变量，表示存放E值的变量在符号表的入口或整数码（若此变量是一个临时变量）。GEN（OP，ARG1，ARG2，RESULT）：将四元式（18设只含整型变量的简单赋值语句的文法如下：Ai:=E EE+E|E*E|-E|(E)|i设只含整型变量的简单赋值语句的文法如下：19翻译算法由如下的语义动作描述:(1)Ai:=EGEN(:=，E.PLACE，ENTRY（i）)(2)EE（1）+E（2）E.PLACE:=NEWTEMP;GEN(+，E（1）.PLACE，E（2）.PLACE，E.PLACE)(3)EE（1）*E（2）E.PLACE:=NEWTEMP;GEN(*，E（1）.PLACE，E（2）.PLACE，E.PLACE)翻译算法由如下的语义动作描述:(1)Ai:=E20(4)E（E（1）E.PLACE:=E（1）.PLACE(5)E-E（1）E.PLACE:=NEWTEMP;GEN(，E（1）.PLACE，E.PLACE)(6)Ei E.PLACE:=ENTRY(i)(4)E（E（1）217.3 布尔表达式的翻译布尔表达式的翻译可以仿照算术表达式的翻译过程，但是布尔表达式的运算有自己的特点，即布尔表达式的运算结果可能只需要运算一部分即可得到，这就是短路运算。对于布尔表达式这种计算方法可以用条件语句的形式加以表示。7.3 布尔表达式的翻译布尔表达式的翻译可以仿照算术表达式的22例如：AB 对应于 if A then true else BAB 对应于 if A then B else falseA 对应于 if A then false else trueA（B（CD）可按此法翻译成：if A then true else if B thenif C then D else trueelse false例如：AB 对应于 if A then true e23布尔表达式E一般出现在控制语句中，我们不需要保留布尔表达式的结果，而只需要在计算E的代码中，当发现E的结果为真时（称为E的真出口）就转向到某个地方，或发现为假时（称为E的假出口）跳转到另一个地方继续执行控制体中相应的计算。可以看出这种想法也可以运用到布尔表达式E的计算过程中。布尔表达式E一般出现在控制语句中，我们不需要保留布尔表达式的24例如对于产生式EE1E2，E1为真，则E必为真，E1的真出口为E的真出口，E1为假则E的真假出口取决于E2的真假出口，此时E1的假出口应转向到E2的相应四元式代码的第一条四元式。现定义几种转移四元式：（jnz，A，P）A为真（非0）时转到第P条四元式。（jrop，A1，A2，P）A1ropA2成立时，转到第P条四元式。（j，P）无条件转向到第P条四元式。例如对于产生式EE1E2，E1为真，则E必为真，E1的25例7.1：if ABC then S1 ELSE S2可翻译成如下四元式序列：1（jnz，A，5）2（j，3）3（ji:使用该产生式归约时的动作为:若i不在符号表中则将i添入符号表并将DEF填为未定义。地址栏ADDR填写NXQ的值。符号表的形式为：35 若i已在符号表中但类型不为标号或虽然是标号但DEF栏填的是已定义,则程序语义有错误.若i已在符号表中但DEF栏填的是未定义,则将DEF栏改为已定义,ADDR栏填NXQ,并执行BACKPATCH(q,NXQ).q为ADDR栏原保留的需要回填同一转移地址的四元式链的链头.若i已在符号表中但类型不为标号或虽然是标号但DEF栏填的是36设GOTO 语句的产生式为S-GOTO L;语义动作为:lookup:=LOOKUP(L);if lookup=null then beginENTRY(L);ENTRY(L);ENTER.TYPE:=L;ENTER.TYPE:=L;ENTER.DEF:=0;ENTER.DEF:=0;ENTER.ADDR:=NXQ;ENTER.ADDR:=NXQ;GEN(j,0);GEN(j,0);END设GOTO 语句的产生式为S-GOTO L;37ELSE if lookup.def=1 thenGEN(j,lookup.ADDR)else begin n:=NXQ;GEN(j,lookup.ADDR)lookup.ADDR:=n;end如果考虑标号的作用域,语义动作应该如何表示?ELSE if lookup.def=1387.4.2用于组织控制流程的一些语句的翻译考虑if语句,while语句和复合语句的翻译.7.4.2用于组织控制流程的一些语句的翻译考虑if语句,39一般使用如下的文法描述这些语句:GS:1.S-if E then S|if E then S else S|while E do S|begin L end|AL-L;S|S各非终结符的含义是:S-语句,L-语句串,A-赋值句,E-布尔表达式一般使用如下的文法描述这些语句:40为方便翻译现将文法改造如下:S-C S1 S.CHAIN:=MERGE(C.CHAIN,S1.CHAIN)S-TP S2 S.CHAIN:=MERGE(TP.CHAIN,S2.CHAIN)S-WD S3 BACKPATCH(S3.CHAIN,WD.QUAD)GEN(J,WD.QUAD);S.CHAIN:=WD.CHAIN 为方便翻译现将文法改造如下:41S-begin L end S.CHAIN:=L.CHAINS-AS.CHAIN:=0L-LS S1 L.CHAIN:=S1.CHAINL-S L.CHAIN:=S.CHAINS-begin L end 42C-if E then BACKPATCH(E.TC,NXQ);C.CHAIN:=E.FCTP-C S1 ELSEq:=NXQ;GEN(J,0);BACKPATCH(C.CHAIN,NXQ);TP.CHAIN=MERGE(S1.CHAIN,q)W-whileW.QUAD:=NXQWD-W E doBACKPATCH(E.TC,NXQ);WD.CHAIN:=E.FC;WD.QUAD:=W.QUADLS-L;BACKPATCH(L.CHAIN,NXQ)C-if E then BACKPATCH(E.TC43例7.2:按上述语义动作将语句while(AB)doif(Cfor i:=E1 step E2 until E3 do S1 7.4.3循环语句的翻译循环语句的文法描述形式为：45假定步长为正,则上述循环语句等价与下列程序片段:i:=E1;goto OVER;AGAIN:i:=i+E2;OVER:if ifor i:=E1 GEN(:=,E1.PLACE,ENTRY(i);F1.PLACE:=ENTRY(i);F1.CHAIN:=NXQ;GEN(j,0);F1.QUAD:=NXQ;F1-for i:=E1 47F2-F1 step E2 F2.QUAD:=F1.QUAD;F2.PLACE:=F1.PLACE;GEN(+,F1.PLACE,E2.PLACE,F1.PLACE);BACKPATCH(F1.CHAIN,NXQ);F2-F1 step E2 48F3-F2 until E3 F3.QUAD:=F2.QUAD;q:=NXQ;GEN(j F2 until E3 49S-F3 do S1 GEN(j,F3.QUAD);BACKPATCH(S1.CHAIN,F3.QUAD);S.CHAIN:=F3.CHAINS-F3 do S1507.5数组元素的引用假定每个数组元素只占用一个机器字并以行为序存放，目标机器以字编址，数组说明的形式为：array A l1：u1，l2：u2，.，ln：un。A数组的某个元素的引用为Ai1，i2，.,in。7.5数组元素的引用假定每个数组元素只占用一个机器字并以行51令di=ui-li+1则,i=1,2,.,n。则该元素的存储地址为：D=CONSPART+VARPART，其中：CONSPART=a-C，a为数组存储区域的起点地址，即Al1，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中，同时用T1T表示数组元素的地址。对应“数组元素引用”和“对数组元素赋值”有两个相应的四元式：CONSPART部分在数组说明时就可得到，我们可以在数组说明53“变址取数”-（=,T1T,X）/*相当于X:=T1T*/；“变址存数”-(=,X,T1T)/*相当于T1T:=X*/。“变址取数”-（=,T1T,X）/*相当54设描述赋值语句中数组元素使用的文法如下：A-V:=EV-ielist|ielist-elist,E|EE-E+E|(E)|V为便于翻译,文法改写:V-elist|ielist-elist,E|iE设描述赋值语句中数组元素使用的文法如下：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:=Eif(V.OFFSET=NULL)then GEN(:=,E.PLACE,V.PLACE)ELSE GEN(=,E.PLACE,V.PLACEV.OFFSET)E-E1+E2 T:=NEWTEMP;GEN(+,E1.PLACE,E2.PLACE,T);E.PLACE:=TA-V:=E58E-(E1)E.PLACE:=E1.PLACEE-Vif(V.OFFSET=NULL)then E.PLACE:=V.PLACEelse begin T:=NEWTEMP;GEN(=,V.PLACEV.OFFSET,T)E.PLACE:=T;endE-(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-elist60elist-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-iEelist.PLACE:=E.PLACE;elist.DIM:=1;elist.ARRAY:=ENTRY(i);elist-elist1,E 617.6过程调用设过程调用形实参结合采用传地址法 如果实在参数是一个变量或数组元素,就直接传递它的地址;如果实参是其它表达式，那么就将它的值计算出来并防在某个临时变量T中，然后传送T的地址，所有实在参数的地址应存放在被调用的子程序能够取得到的地方。7.6过程调用设过程调用形实参结合采用传地址法62被调用的子程序中，每一个形式参数都有一个单元（称为形式单元）用来存放相应的实在参数的地址，在子程序中对形式参数的任何引用都当作是对形式单元的间接访问。当通过转子指令进入子程序后，子程序的第一步工作就是把实在参数的地址取到对应的形式单元中，然后再开始执行本段中的语句。被调用的子程序中，每一个形式参数都有一个单元（称为形式单元）63设过程调用CALL S(A+B，Z)将被翻译成：计算A+B置于T的代码/*T：=A+B*/par T/*第一个实参地址*/par Z/*第二个实参地址*/call S /*转子指令*/按上述关于过程调用的目标结构的模式，考虑过程调用的翻译。设过程调用CALL S(A+B，Z)将被翻译成：64描述过程调用语句的文法和相应语义子程序如下：S-call(arglist)for 队列arglist.QUEUE的每一项p DOGEN(par,p);GEN(call,ENTRY(i)描述过程调用语句的文法和相应语义子程序如下：65arglist-arglist1,E把E.PLACE排在arglist1.QUEUE的末端;arglist.QUEUE:=arglist1.QUEUEarglist-E建立一个arglist.QUEUE,它只包含一项E.PLACEarglist-arglist1,E66语义分析和中间代码产生课件67语义分析和中间代码产生课件68语义分析和中间代码产生课件69语义分析和中间代码产生课件70语义分析和中间代码产生课件71语义分析和中间代码产生课件72语义分析和中间代码产生课件73语义分析和中间代码产生课件74语义分析和中间代码产生课件75语义分析和中间代码产生课件76语义分析和中间代码产生课件77语义分析和中间代码产生课件78语义分析和中间代码产生课件79语义分析和中间代码产生课件80语义分析和中间代码产生课件81语义分析和中间代码产生课件82