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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,编译原理 长春工业大学计算机科学与工程学院,语义分析与中间代码生成,复习：编译程序的逻辑过程,按照编译程序的逻辑工作过程，语法分析后，接下来就要进行语义分析了，语义分析后，再生成中间代码。实际应用中，往往在语法分析的同时，进行语义分析并生成中间代码，这就是语法制导翻译法。,语法制导翻译过程中，需要借助于属性文法进行语义描述和语义处理。,本章内容：,属性文法有关概念；,语法制导翻译基本思想；,中间代码形式；,简单算术表达式、布尔表达式、赋值语句、条件语句、循环语句的翻译。,属性文法,表达式文法 ET+T|T or T Tn|b,E,T,1,+T,2,T,1,.type=int,T,2,.type=T,1,.type E.type=int,E,T,1,or T,2,T,1,.type=bool,T,2,.type=T,1,.type,E.type=bool,T,n T.type=int,T,b T.type=bool,属性文法,对于某个压缩了的文法，当把每个文法符号和一组属性相关联，并把产生式附加以语义规则的时候，就得到属性文法。,语法制导的翻译过程：由于属性文法的规则和产生式是一一对应的关系，所以，由属性文法确定的语义分析可以在语法分析的过程中进行。这个过程称为语法制导的翻译。,属性文法,(attribute grammar),A=(G,V,F),其中,G:一个CFG,属性文法的基础。,V:有穷的属性集,每个属性与一个文法符号相关联,这些属性代表与文法符号相关的语义信息,如类型、地址、值、代码、符号表内容等等,属性与变量一样，可以进行计算和传递,属性加工的过程即是语义处理的过程,属性加工与语法分析同时进行,属性的表示：,标识符（或数），写在相应文法的下边,点记法：E.Val,E.Place,E.Type,F:关于属性的属性断言或一组属性的计算规则(称为语义规则).,断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相关的属性.,语义规则描述的工作,属性计算,静态语义检查,符号表操作,代码生成,继承属性和综合属性,两类属性：,综合属性(Synthesized Attribute)：归约型属性,用于“自下而上”传递信息,继承属性(Inherited Attribute)：推导型属性,用于“自上而下”传递信息。,属性的计算：A,X1 X2 Xn,A的综合属性,计算 S(A)=f(A(X1),A(Xn),Xj的继承属性,计算 I(Xj)=f(A(A),.A(Xn),文法符号属性的说明：,非终结符既可有综合属性也可有继承属性，但文法开始符号没有继承属性.,终结符只有综合属性,.,通常规定：,文法符号的综合属性与继承属性无交。,综合属性的例子,非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。,与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，可认为这条规则定义了L的一个虚属性。,某些非终结符加上标是为了区分一个产生式中同一非终结符多次出现,语 义 规 则,L,E,E E,1,+T,ET,T T,1,*F,TF,F(E),Fdigit,Print(E.val),E.val=E,1,.val+T.val,E.val=T.val,T.val=T,1,.val,F.val,T.val=F.val,F.val=E.val,F.val=digit.lexval,产 生 式,综合属性的自下而上定值,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4,的带注释的分析树,设表达式为35+4，则语义动作打印数值19,继承属性的例子,继承属性L.in,产 生 式,语 义 规 则,D,TL,T,int,T,real,L,L,1,id,L,id,L.in=T.type,T.type=integer,T.type=real,L,1,.in=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in,),继承属性的自上而下定值,D,L.in=real,L.in=real,L.in=real,T.type=real,real,id,2,id,1,id,3,Real id1,id2,id3,，,，,语法制导翻译的基本思想,为每条产生式配上一个翻译子程序（称为语义动作或语义子程序）；,语义动作的工作,指明符号串的意义；,按照这种意义规定了对应的动作：,查添各种表格,改变变量之值,诊察与报告源程序错误,产生中间代码,在语法分析的同时，当一个产生式获得匹配（对于自上而下分析）或用于归约（对于自下而上分析）时，就执行相应产生式的语义子程序。,中间代码,中间代码（Intermediate code）：,源程序的一种内部表示，不依赖目标机的结构，易于机械生成目标代码的中间表示。,几种中间语言,后缀式（逆波兰表示法）,三地址代码,四元式,三元式,间接三元式,树,后缀式,表达式的一种表示形式,运算符直接跟在运算量后面,又称为逆波兰表示法,定义：设E是表达式，那么,如果E是变量或者常量，E的逆波兰表示为E,E1 OP E2=E1 E2 OP，其中E1,E2 为 E1,E2的逆波兰表示。,(E)=E,其中E为E 的逆波兰表示。,后缀式的生成,设置一个操作符栈，当扫描到操作数时，输出该操作数。当遇到操作符时，与栈顶操作符比较优先级，若栈顶操作符优先级高于栈外操作符，则输出该栈顶操作符；反之，则栈外操作符入栈。,后缀表达式的计值,自左向右扫描表达式，每遇到运算量就把它推进栈，每遇到k目算符就把它作用于栈顶的k个项，并把运算结果来代替这k个项,逆波兰表示的例子,A+B*(C-D)+E/(C-D)N,=,A B C D-*+E C D N /+,a+b*c/(d+e),=,abc*de+/+,逆波兰表示方法的扩充,赋值语句：V=e=Ve=,例子：t=(a+b)*c/(d-e)=tab+c*de-/=,转向语句：goto=jump,条件语句：,If then else =,jumpfjump,e,L1,jumpf,x,L2,jump,y,L1,L2,三地址代码,一般形式：,X=y op z,例子,x+y*z 可表示为 T1=y*z T2=x+T1 T1、T2为编译时产生的临时变量,三地址语句的种类,三地址代码的具体实现四元式三元式间接三元式,四元式,一般形式：,例子：,a+b*c,*bct1,+a t1t2,单目运算的处理：为空。,一般来讲，四元式的运算符都有对应的机器指令，或者对应的子程序，因此从四元式生成指令代码是容易的。,四元式之间的联系是通过临时变量实现的，便于进行代码优化。,四元式表示的例子,A+B*(C-D)+E/(C-D)N,（1）(-C D T1),（2）(*B T1 T2),（3）(+A T2 T3),（4）(-C D T4),（5）(T4 N T5),（6）(/E T5 T6),（7）(+T3 T6 T7),三元式,如果我们不明显给出四元式的结果部分，而是用四元式的编号来表示结果，那么我们可以得到三元式。形式如下：,例子：a+b*c=,*b c,+a ,三元式的出现顺序与表达式的计值顺序一致。,和四元式的比较：,无须临时变量；,占用存储空间少；,相互引用太多，使得难以进行代码优化。,三元式表示的例子,A+B*(C-D)+E/(C-D)N,(1)(-C D ),(2)(*B (1),(3)(+A (2),(4)(-C D ),(5)(4)N ),(6)(/E (5),(7)(+(3)(6),间接三元式,间接三元式：,为了便于代码优化处理，用一张,间接码表,辅以,三元式表,的办法来表示中间代码。,间接码表是一张指示器表，它将按运算的先后顺序列出有关三元式在三元式表中的位置。,当在代码优化过程中需要调整运算顺序时，只需重新安排间接码表即可。,例子：X=(A+B)*C,Y=D,(A+B),间接三元式表示的例子,A+B*(C-D)+E/(C-D)N,(1)(-C D )(1),(2)(*B (1)(2),(3)(+A (2)(3),(4)(1)N )(1),(5)(/E (4)(4),(6)(+(3)(5)(5),(6),树形表示（抽象语法树AST）,采用树形表示作为一种中间代码形式，有助于代码的产生和优化。,树形表示的定义：,简单变量或常数的树就是该变量或常数自身；,如果表示e1和e2的树为T1和T2，那么，e1+e2,e1*e2,-e1的树分别是：,显然，树形表示是三元式表示的翻版。,抽象语法树（Abstract Syntax Tree）,在语法树中去掉那些对翻译不必要的信息，获得更有效的源程序中间表示,AST可以拓广，用来表示数组元素、过程调用、控制结构、说明等。,+,e1,e2,-,e1,*,e1,e2,由语法树到AST,步骤：,去掉单非产生式子树，上提终结符结点；,运算符上提，取代其父结点；,去掉括号，运算符上提。,例子：a*(a+a),简单算术表达式和赋值句的翻译,文法：,A,i:=E,EE+E|E*E|-E|(E)|i,引入的语义属性：E.place,与非终结符E相联系，表示存放E值的变量名在符号表的入口或整数码（对临时变量）,语义过程：,newtemp(),:函数过程。每次调用，回送一个代表新临时变量名的整数码作为函数值。,lookup(i.name),:函数过程。对i所代表标识符查找符号表以获知它在符号表中位置（入口）。,emit,():语义过程。,产生一个三地址代码并填入中间代码,表中。,产生式的语义描述,（1）A,i:=E ,p=lookup(i.name)；,if(p=NULL)error();,else emit(p=E.place),（,2,）,EE,(1),+E,(2),E.place=newtemp();,emit(E.place=E,(1),.place+E,(2),.place),（3）EE,(1),*E,(2),E.place=newtemp();,emit(E.place=E,(1),.place*E,(2),.place),（4）E-E,(1),E.place=newtemp();,emit(E.place=uminus E,(1),.place),（5）E(E,(1),)E.place=E,(1),.place,（6）Ei p=lookup(i.name)；,if(p=NULL)error();else E.place=p,布尔表达式的翻译,布尔表达式基本作用：,用作计算逻辑值；,用作控制条件。,布尔表达式文法：,EEE|EE|E|(E)|id relop id|id,结合性和优先级：,relop ；,左结合。,布尔表达式的翻译,计算布尔表达式的值：,逐步计算；,利用布尔表达式的性质采取优化措施：,AB if A then true else B,AB if A then B else false,B if B then false else true,布尔表达式的翻译,逐步计算的例子:,ABC=D(=,C,D,T1),(,B,T1,T2),(,A,T2,T3),布尔表达式的翻译,优化计算引入的三地址代码：,(if i.place goto l):若i为真，转向第l个三地址代码,(if i,(1),.place relop.op i,(2),.place goto l):若i,(1),relop.op i,(2),为真，转向第l个三地址代码,(goto l):无条件转向第l个三地址代码,布尔表达式的翻译,逻辑计值,EE,(1),or E,(2),E.place=newtemp();,emit(E.place=E,(1),.