编译原理课程教案第5章：中间代码生成.ppt

语义分析和中间代码生成,第五章,本章要求,主要内容：语义分析和中间代码的功能，中间代码的形式，属性文法及语法制导的翻译程序，各种语句的语法制导的翻译过程重点掌握：属性文法，语义分析与处理的方法,中间代码的表示形式，各种语句的代码结构，各种语句的翻译方法,语义分析和中间代码生成所处的位置：,5.1 概述,.语义分析和中间代码生成在编译器中的位置：,静态语义检查：如：类型、运算、数组维数、越界等的检查语义处理：如：变量的存储分配、表达式的求值、语句的翻译(中间代码的生成)总目标：生成等价的中间代码,.功能及任务：P166,输入-语法分析单位,输出-用中间代码形式表示的文本-出错处理:定位、继续编译,3.为什么要此阶段?逻辑结构清楚；利于不同目标机上实现同一种语言；利于进行与机器无关的优化，这些内部形式也能用于解释。4.什么是中间代码(Intermediate code)源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。5.中间代码的几种形式逆波兰、三元式、间接三元式、四元式、树,1、逆波兰式：运算对象写在前，运算符写在后(后缀表示形式)例：a+b ab+(a+b)*c ab+c*a+b*c abc*+a:=b*c+b*d abc*bd*+:=,5.2中间代码的几种形式,优点：易于计算机处理 利用栈，将扫描到的运算对象入栈，碰到运算符：若是双目运算符，则对栈顶的两个运算对象实施该运算并将运算结果代替这两个运算对象进栈；若是单目运算符，对栈顶元素，执行该运算，将运算结果代替该元素进栈，最后结果即栈顶元素。,练习,写出下列算式的逆波兰表示a+b*(c+d/e)a:=b*(-c)+b*(-34)not A or not(C or not D),abcde/+*+a b c-*b 34-*+:=A not C D not or not or,后缀式的推广,(1)赋值语句A:=E，后缀式为：AE:=(2)转向语句GOTO L的后缀式为：Ljmp(3)条件语句if xy then m:=x else m:=y,2、三元式编号（运算符，第一运算数，第二运算数）如：a：=b*c+b*d(1)（*，b，c）(2)（*，b，d）(3)（+，(1)，(2)）(4)（：=，(3)，a）对于单目运算符，只有一个运算对象，另一个为空注意：在三元式中的编号既代表了序号，又代表了结果的存放位置。,3、四元式P172 是目前最常用的中间代码形式:(运算符，第一运算数，第二运算数，结果)例：a:=b*c+b*d(1)(*,b,c,t1)(2)(*,b,d,t2)(3)(+,t1,t2,t3)(4)(:=,t3,a)也可以写成赋值语句形式：(1)t1:=b*c(2)t2:=b*d(3)t3:=t1+t2(4)a:=t3,练习,求-B+C*D 的逆波兰表示形式、三元式和四元式,到目前为止，已知 输入的语法单位，又知道 要翻译的结果的形式，翻译的方法是什么？,语义分析和翻译的方法：语义表示较流行的方法仍然是属性文法，翻译方法是语法制导的翻译。,属性文法,属性文法:是在上下文无关文法的基础上，为每个文法符号(含终结符和非终结符)配备若干个属性值，对文法的每个产生式都配备了一组属性计算规则(称为语义规则)。在语法分析过程中，完成语义规则所描述的动作，从而实现语义处理。属性：代表与文法符号相关的信息，如类型、值、代码序列、符号表的内容等。与变量一样，可以进行计算和传递，属性的加工过程就是语义的处理过程。,属性分两类：综合属性：用于自下而上传递信息继承属性：用于自上而下传递信息注意：终结符只有综合属性，它由词法分析器提供；非终结符可有综合属性，也可有继承属性，它由词法分析器提供；文法的开始符号的所有继承属性作为属性计算前的初始值,产生式右边的文法符号的继承属性可以继承左边的文法符号的继承属性产生式左边的文法符号可以通过综合右边的文法符号的综合属性而得到但必须提供一个计算规则：计算规则中只能使用相应产生式中的文法符号的属性。实际应用中，一个结点的综合属性的值由其子结点的综合属性值决定(产生式右边)。一个结点的继承属性由此结点的父结点和/或兄结点的某些属性决定(产生式左边)。但产生式左边的继承属性和右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性计算规则提供。,digitlexval:=3,Fval:=3,Tval:=3,Fval:=5,Tval:=15,*,Eval:=15,+,digitlexval:=4,Fval:=4,Tval:=4,Eval:=19,L,n,digitlexval:=5,若输入符号串为：3*5+4n,例：综合属性的计算,C语言中变量定义：int id1,id2,id3,综合属性的传递,继承属性的传递,例：继承属性的计算,语法制导的翻译方法,基于属性文法的处理过程通常是：,对单词符号串进行语法分析；,构造语法树；,根据需要遍历语法树；,在语法树的各结点处按语义规则进行计算。,语义规则描述的工作：属性计算、静态语义检查、符号表的操作、代码生成等，通常写成过程和函数调用，称为语义子程序。,语法制导翻译的基本思想：在语法分析过程中，根据语言的语义定义，随时翻译已识别的那部分语法成分的全部含义。,语法制导的翻译方法：如果遍历语法树的操作和建立语法树的操作同时进行，称为语法制导的翻译方法。,语法制导翻译的两种方法,（1）在自下而上的语法分析中，使用和语法分析栈同步操作的语义栈进行语法制导翻译；（2）在自上而下的语法分析中（如递归下降分析），利用隐含的堆栈存储各递归子程序中的局部变量所表示的语义信息。,自下而上分析的语法制导翻译,语法分析是自下而上的情况时，语义计算的时机是：在用某一产生式进行规约的同时，执行相应的语义动作。在分析完一个句子时，这个句子的“值”也就同时产生了。,例：属性文法如下，输入串为：3*5+4，其语法树如下图：,E,E1,+,T,T,T,*,F,F,3,5,F,4,在第一步规约时使用产生式6，执行的语义动作是将F.val的值置为单词digit的值3。把语法树中每个结点得语义值写在结点后的括号中，则第一步完成规约后的情形如右图所示：,E1,+,T,T,T,*,F,F（3）,5,F,4,E,第一步规约,继续进行分析，逐步向上规约，得到下图所示的情形，最后用E E1+T规约到E时，它的值19就计算出来了。,E1（15）,+,T（4）,E,在自下而上的LR语法分析过程中，首先把它的分析栈进行扩充，使得每个文法符号都带有语义值。修改后栈的结构如下图所示：,同时把LR分析器的能力扩大，使它不仅执行语法分析任务，且能在用某个产生式进行规约的同时进行相应的语义处理，完成属性文法中定义的语义动作。每步工作后的语义值保存在扩充的语义栈中。,例：在3*5+4的LR分析过程中增加了语义栈后的语法制导的实现过程。,LR分析表,文法,启示：,在刚才的翻译过程中有如下特点：句柄归约在先，语义动作在后。归约时，栈内句柄各符号的语义信息与该句柄同时出栈，整个句柄所表示的语义信息则赋给相应产生式左部非终结符的语义变量，并让该非终结符及其语义变量同时入栈。为了在某处调用语义动作，就必须先归约，因此，有时需要改写文法。,常见语句的语法制导翻译,高级语言的两大类语句：说明语句：用于定义各种形式的有名实体及其 属性，如常量、变量、数组、记录（结构）、过程、子程序等。可执行语句：用于完成程序指定的功能。语义处理也按两大类处理：（1）说明语句的处理：把说明语句中定义的名字和属性登记在符号表中，用以检查名字的引用和说明是否一致，以便在翻译可执行语句时使用。一般说明语句的语义处理不生成目标代码，过程说明和动态数组的说明有相应的代码。（2）可执行语句：首先根据各源语句的语法结构和语义设计它的目标代码结构，找出源与目标的对应关系，然后根据语义规则进行翻译，生成四元式序列。,语义翻译过程中涉及的数据结构,语义翻译过程中涉及的数据结构有符号表、四元式表和临时变量区。符号表：语义翻译过程中，在产生四元式时，通常不使用变量的名字，而是使用它们在符号表中的入口位置，一般用ENTRY(i)表示变量i在符号表中的入口。因此语义子程序需要查阅符号表，而在翻译说明语句时需要填写符号表中的相关项。四元式表：四元式表是按翻译过程中四元式产生的顺序组成的。通常设置一个专门的过程GENCODE(OP,ARG1,ARG2,Ti)来产生一个四元式，将该四元式输出到四元式列表中，并使四元式的编号加1。临时变量区：用于存放翻译过程中建立的临时语义变量。假设过程newt用来生成临时变量，每调用一次，生成一个新的临时变量，第一次调用生成的是T1，第二次调用生成T2,说明语句的翻译,说明语句的作用：就是说明类型等属性信息，在翻译时主要是填符号表说明语句分多种，此处举例两种的翻译：变量说明语句的翻译常量说明语句的翻译,变量说明语句的翻译,.变量说明语句的文法描述,.变量说明语句的翻译,例如：var a,b,c:integer;,策略：先翻译第，产生式，再翻译，产生式，以便记录的类型，即在写程序时，读完一个说明语句，开始归约，再开始翻译，变量的类型朝前传递。,.翻译的语义动作,符号表：,FILL(entry(i),Type)表示将类型Type填入符号表中,entry(i)表示变量名i在符号表中的入口,VAR id1,id2,id3:integer;的归约过程,常量说明语句的翻译,.常量说明语句的文法描述,.常量说明语句的翻译,策略：和变量说明一样，先翻译后面的产生式，再翻译前面的产生式，以便在归约时，执行语义动作，将常量的值、类型、种属填入符号表。,例：,Constant A=123,.翻译的语义动作,将常量INT在符号表中的入口或值直接填入常量符号i所指符号表的VAL栏,将常数的类型填入符号表的Type栏,3，4产生式的翻译与5，6产生式的翻译相同1，2产生式没有语义动作,将常数的种属填入符号表的Kind栏,可执行语句的翻译,定义的一些语义变量和过程GENCODE(OP,ARG1,ARG2,RESULT)：语义过程，产生一个四元式，并填入四元式表，编号自动增1。NEWT：函数，返回一个临时变量序号。在翻译可执行语句的过程中，可能需要使用临时变量，假定用NEWT过程来申请临时变量Ti，每申请一次，i增1。ENTRY(i)：函数，查找变量i的入口地址；检查id.name是否在符号表中，如在则返回一指向该登陆项的指针，否则返回NULLE.PLACE：与给终结符E相联系的语义变量，可能是某变量的入口地址，或者为临时变量序号。,简单赋值语句的翻译,.简单赋值语句的文法描述,2.简单赋值语句的代码结构,例如：x:=2+3*2;,3.简单赋值语句的翻译 此处只假定是整数运算,例：赋值句A:=B+C*(-D)的自底向上分析,因此，四元式表中增加了4条四元式：,简单算术表达式和赋值语句的翻译,(1)Sid:=E p:=lookup(id,name);if pnil then emit(p:=E.place)else error(2)EE1+E2 E.place:=newtemp;emit(E.place:=E1.place+E2.place)(3)EE1*E2 E.place:=newtemp;emit(E.place:=E1.place*E2.place)(4)E-E1 E.place:=newtemp;emit(E.place:=uminus E1.place)(5)E(E1)E.place:=E1.place)(6)Eid p:=lookup(id,name);if pnil then E.place:=p else error,张素琴编编译原理（清华大学版）,布尔表达式的翻译,1.布尔表达式的基本概念布尔表达式是将布尔运算符（and、or、not）作用到布尔变量或关系表达式上组成的表达式。关系表达式形如E1 rop E2，其中E1和E2是算术表达式，rop表示关系运算符、或。Sample语言规定布尔运算符的优先级从高到低为not、and、or，and和or都是左结合。2.布尔表达式的两个基本作用用作布尔赋值语句中的布尔运算。用作控制语句如if-then、if-then-else、whiledo等之中的条件表达式，其作用是选择下一个执行点。,3.布尔表达式的文法描述,例如：x:=not a and(yz)是符合上述文法的布尔表达式,计算布尔表达式的值有两种方法：一种是像计算算术表达式那样，对布尔表达式中的每个因子都计算其布尔值，最后求得整个表达式的布尔值。另一种计算方法是根据布尔运算的特殊性采取某些优化措施，只计算部分表达式。例如要计算A or B，若计算出A的值为1，那么B的值就无需再计算了，因为不管B的值为何结果，A or B的值都为1。,如同计算算术表达式一样，步步计算出各部分的真假值，最后计算出整个表达式的值。例如，用数值1表示true，用0表示false。那么布尔表达式 1 or(not 0 and 0)or 0的计算过程是：1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1,4.用于布尔赋值语句中布尔表达式的翻译,使用这种翻译方法，可以参照算术表达式的赋值语句文法的语义动作，为布尔表达式文法配上合适的语义动作。张素琴编编译原理（清华大学版）给出的方案如下：,(1)EE1 or E2 E.place:=newtemp;emit(E.place:=E1.place or E2.place)(2)EE1 and E2 E.place:=newtemp;emit(E.place:=E1.place and E2.place)(3)Enot E1 E.place:=newtemp;emit(E.place:=not E1.place)(4)E(E1)E.place:=E1.place(5)Eid1 rop id2 E.place:=newtemp;emit(ifid1.placeropid2.place)gotonextstat+3);emit(E.place:=0);emit(gotonextstat+2);emit(E.place:=1);(6)Etrue E.place:=newtemp;emit(E.place:=1);(7)Efalse E.place:=newtemp;emit(E.place:=0);,布尔量的代码结构每个布尔量(布尔变量或关系表达式)的目标结构有两个出口，真出口指向布尔量为真时应跳转的位置；假出口指向布尔量为假时应跳转的位置。,5.控制语句中布尔表达式的翻译,布尔量翻译为两条四元式：(jnz,A,_,P):真出口，当A为真时跳转到四元式P；(j,_,_,Q):假出口，无条件跳转到四元式Q。转移四元式的第4个分量表示转移去向（即P、Q为某个四元式的编号）。关系表达式也翻译为两条四元式：(jrop,i1,i2,P):真出口，当i1 rop i2为真时转四元式P；(j,_,_,Q):假出口，无条件跳转到四元式Q。,问题：在翻译布尔表达式时，后面的语句未翻译，P，Q如何知道？,解决方法：回填技术 在由多个因子组成的布尔表达式中，可能有多个因子的真出口或假出口的转移去向相同，但又不知道具体转向位置。在这种情况下，需要把这些转移方向相同的出口链在一起，形成真/假出口链，以便后续知道转移地址后再回填。对于给定的控制语句中的布尔表达式，翻译方法如下：若已知转移地址就直接填入；若不知道，时先填0，等知道后再返填。如果多个因子的转移去向相同，但又不知道具体位置，应该用链将这些未知且出口相同的四元式链在一起。,例：写出布尔表达式:A and B and CD 的四元式序列。当扫描到A后的and时，对A进行规约，产生两个四元式(1)和(2)，四元式(1)的第4分量表示真出口，由于A为真时应计算B，因此A的真出口的值为3（即A为真时转向3）；四元式(2)的第4个分量表示假出口，目前其值未知，先填入0。当扫描到B后的and时，对B进行规约，产生四元式(3)、(4)，四元式(3)的第4分量表示真出口，由于B为真时应计算CD，因此B的真出口的值为5（即B为真时转向5）；四元式(4)的第4个分量表示假出口，目前其值未知，但可以知道它与A的假出口相同，因此需将它与四元式(2)链接起来，即将(4)的第4个分量填入2；当扫描到最后，对关系表达式CD进行规约，产生两个四元式(5)、(6)，此时(5)的第4个分量表示真出口，其值未知（即暂时不知道CD时转向哪里），填入0；(6)的第4个分量表示假出口，其值未知，但它与A和B的假出口相同，因此需将它与四元式(4)链接起来，即将(6)的第4个分量填入4。,假出口未知，填入0,当扫描到and时，对A进行归约，产生两个四元式1，2，其中真出口已知，为3,当扫描到B后的and时，对B进行归约，又产生两个四元式3，4，其中真出口已知，为5,假出口仍未知，但它与A的假出口相同，则链接起来，填2,当扫描到最后，对CD进行归约，又产生两个四元式5，6，此时真出口未知，填0,假出口仍未知，但它与上两个布尔量的假出口相同，则链接起来，填4,生成了真、假出口两个链，其中(1)、(3)、(5)形成一条真出口链；(6)、(4)、(2)形成一条假出口链。每个链尾的四元式的第4个分量都为0，为结束标记，同时也是待填部分，等到以后翻译到后面再填入。一旦出现具体的转向目标，即把转向的目标四元式编号回填到链上对应四元式的第4个分量处。,最后的四元式列表如下：,控制语句中布尔表达式的语义处理,Sample语言中，在为布尔表达式设计语义动作时，提供了以下语义变量和语义过程：（1）为每个非终结符X设置两个出口：真出口X.TC和假出口X.FC，它们同时分别表示真、假出口链的链首。例：对于E1 or T的目标代码结构，只要E1为真，后面的表达式就不必计算，就知道E1 or T为真；只有当E1 为假，才读取T，E1 or T的值由T值决定，目标结构如下图(a)所示。对于E1 and T的目标代码结构，只要E1为假，后面的表达式就不必计算，就知道E1 and T为假；只有当E1 为真，才读取T，E1 and T的值由T值决定，目标结构如下图(b)所示。,（2）变量NXQ，指代下一个即将形成的四元式编号。NXQ的初值为1，每执行一次GENCODE过程，产生一条新的四元式，NXQ就自动加1。,（3）函数MERG(P1,P2)。将P1,P2为链首两个真出口链或假出口链合并在一起，返回合并后的链首。,MERG(P1，P2)if(P2=0)return(P1);else P:=P2;while(四元式P的第4分量内容不为0)P:=四元式P的第4分量内容；把P1填进四元式P的第4分量；return(P2);,（4）函数BACKPATCH(P，t)。把以P为链首的真出口链或假出口链中每个四元式的第4分量都改写为已知地址t。（回填）,BACKPATCH(P，t)Q:=P;while(Q!=0)do m:=四元式Q的第4分量内容；把t填进四元式Q的第4分量；Q:=m;,布尔表达式文法的改造为语义翻译服务,分析E1 or T和E1 and T的目标代码结构：,从上图(a)可以看出，E1的假出口应转向布尔表达式T的第一个四元式的位置，由于语法分析程序分析到运算符 or 时才能知道E1已分析完毕，开始生成T的四元式。这样，当分析程序扫描到or时，应执行一个语义动作，把下一个四元式的编号（即T的入口）回填给E1的假出口。为此，产生式 or 应改造为：oror or这样，当用产生式oror进行规约时，就能立即执行回填动作，及时把的第一个四元式的编号回填给的假出口链。类似的产生式 and 也应改造为下面两个产生式：andand and这样，当用产生式andand进行规约时，就能及时把的第一个四元式的编号回填给的真出口链。,布尔表达式的文法改造方案：,改造后的文法,改造前的文法,布尔表达式文法的语义翻译方案：,NXQ表示当前产生的四元式的编号,单个的布尔量,关系运算,Not逻辑运算,带算术运算的关系运算,产生式6:，3:的翻译与7相似，都是将右边的真假出口直接赋值到左边,(5)(4)构成and逻辑运算,(2)(1)构成or逻辑运算,控制语句的翻译,控制语句包括：if 语句While 语句Repeat 语句For 语句,IF语句的翻译,1.IF语句的文法(S是开始符号),产生式(1),(4)生成无else 的IF语句结构产生式(1),(2),(3)生成if then else 的语句结构,（1）SC S(1)（2）Cif E then（3）ST S(2)（4）TC S(1)else,2.IF语句的目标结构及其翻译无else的结构,C.Chain的作用：由于在用第一个产生式进行归约时，只生成了条件式E的代码，then时可以回填E.TC,E.FC必须向后传递到下一各产生式中。,if ab then x:=3;,2.IF语句的目标结构及其翻译有else的结构,if ab then x:=3 else x:=5;,例：将下面的IF语句翻译为四元式序列,if A and B and(CD)then if AB then F:=1 else F:=0else G:=G+1,1.(jnz,A,_,3)/*A的四元式*/2.(j,_,_,13)3.(jnz,B,_,5)/*B的四元式*/4.(j,_,_,13)5.(j,C,D,7)/*CD的四元式*/6.(j,_,_,13)7.(j,A,B,9)/*AB的四元式*/8.(j,_,_,11)9.(:=,1,_,F)/*F:=1的四元式*/10.(j,-,-,15)11.(:=,0,_,F)/*F:=0的四元式*/12.(j,_,_,15)13.(+,G,1,T)/*G:=G+1的四元式*/14.(:=,T,_,G)15.,练习:将下面的语句翻译为四元式序列,if(AC)and(BD)then if A=1 then C:=C+1 else if AD then A:=A+2;,1.(j,A,C,3)2.(j,-,-,14)3.(j,B,D,5)4.(j,-,-,14)5.(j=,A,1,7)6.(j,-,-,10)7.(+,C,1,T1)8.(:=,T,-,C)9.(j,-,-,14)10.(j=,A,D,12)11.(j,-,-,14)12.(+,A,2,T2)13.(:=,T2,-,A)14.,REPEAT语句的翻译,1.文法描述,2.目标结构,例：repeat x:=x+1until x10;,3.翻译,将下面的语句翻译为四元式序列,If w1 then a:=b*c+delse repeat a:=a-1 until a0;,1.(j,w,1,3)2.(j,7)3.(*,b,c,t1)4.(+,t1,d,t2)5.(:=,t2,a)6.(j,11)7.(-,a,1,t3)8.(:=,t3,a)9.(j,a,0,11)10.(j,7),FOR语句的翻译,1.文法描述,2.目标结构,例：for i:=1 to a+b do x:=x+I;,FOR语句的翻译,for i:=1 to a+b do x:=x+I;,将下面的语句翻译为四元式序列,for i:=a+b*2 to c+d+10 do if hg then p:=p+1;,自顶向下的语法制导翻译,优点：不需要改造文法在需要的任何位置调用语义动作自顶向下的语法分析有两种：递归下降分析LL(1)分析,递归下降的语法制导翻译,例：对如下文法进行递归下降的分析，并增加语义,只包含两个语句：赋值句和REPEAT语句,需要翻译布尔表达式,主程序：,增加的语义部分,增加的语义部分,用C语言实现repeat(),int*repeats()/*repeat语句的语法制导的翻译过程*/r_head=nxq;/*记录repeat语句开头的四元式编号*/token=getnexttoken();/*读取下一个token字*/s1_chain=st_sort(token);/*处理repeat后的语句*/token=getnexttoken();if(!strcmp(token,;)/*读到;*/token=getnexttoken();if(strcmp(token,until)error(缺少 until);/*应为until*/backpatch(/*返回真出口，即repeat语句的下一个语句的四元式编号*/,