语法制导翻译和中间代码(8学时)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第8章 语法制导翻译和中间代码,属性文法,语法制导翻译,中间代码的形式,逆波兰式、三元式、树形表示、四元式,一些语句的翻译,赋值语句,布尔表达式,控制语句中的布尔表达式,For,循环语句,8.1 属性文法,预备知识,源程序与目标程序，,语法结构完全不同,，但语义相同，所以,表达的结果完全相同,。,语义分析的,2,种处理方法：,1）语法分析之后，直接调用相应的,“,语义子程序,”,进行语义处理,2）语法分析之后，先生成,“,语法树,”,或其他形式，再进行语义处理,语义分析的处理结果：,1）目标代码,2）中间代码：复杂性介于源程序语言和机器语言之间,静态语义分析：审查语法结构的静态语义,确定标识符的数据类型,类型检查和转换,：检查运算对象的数据类型是否合法，必要时进行类型转换,一致性检查,：一个对象只能被声明一次,作用域检查,控制流检查,：控制语句转到合法的地方继续执行,翻译,（若静态语义分析正确后才翻译）,语义处理的任务和功能,常用的语义分析方法,语法制导翻译,语法制导翻译：,首先，使用,属性文法,为工具，描述程序设计语言的语义规则。,在语法分析时，每应用一个产生式（推导或归约），同时完成该产生式上所附的语义规则描述的动作，从而完成语义处理。,语义分析的方法,用于描述语义规则的文法。,对文法的,每个符号引入一些属性,，这些属性代表与文法符号相关的信息，例如：类型、值、代码序列、符号表内容等。,属性,值,可以在语法分析过程中进行,计算和传递,。,属性的加工过程就是语义的处理过程。,属性文法,(,attribute grammar),属性文法的组成：,一个,上下文无关文法,一系列,语义规则,（附在文法的每个产生式上）,属性文法的形式：三元组,A=(G,V,F),G,:,是一个,上下文无关文法,V,:,有穷,属性集,每个属性与文法的一个终结符或非终结符关联,F,:,关于属性的,断言或谓词集,.每个断言与一个产生式关联.而此断言只引用该产生式的终结符或非终结符相关联的属性,属性文法,(,attribute grammar),属性文法 举例,例1 说明语句中各种变量的类型信息的语义规则：,产生式语义规则,D,TL,T,char,Tint,Tfloat,LL,1,id,Lid,L.in:=T.type,T.type:=char,T.type:=int,T.type:=float,L,1,.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in),属性文法 举例,例2 表达式,类型检查,和,求值,的语义规则：,假设：类型不同的两个变量进行运算则语义错误。,产生式语义规则,L,E,E,E,1,+T,ET,TT,1,*F,TF,F(E),Fid,print(E.val);,if(E,1,.type=T.type),E.type:=E,1,.type;,E.val:=E,1,.val+T.val;,else error();,E.type:=T.type;E.val:=T.val,getType(F.type,id.entry);,F.val:=id.lexval;,语法制导翻译的,实质,：,根据每个产生式所对应的语义规则，随语法分析的每一步（推导或归约），执行相应的语义动作。,语法制导翻译的,过程,：,对单词符号串进行语法分析，构造语法分析树；,然后根据需要构造属性依赖图，遍历语法树，并在语法树的各结点处按语义规则进行计算。,8.2 语法制导翻译概论,使用,“,依赖图,”,，从依赖图的拓扑排序中得到计算语义规则的顺序，再依照顺序对输入串进行语义分析,。,依赖图,一个有向图，用于描述分析树中的属性和属性之间的相互依赖关系。,构造依赖图举例：参见,P172,图8.4,属性计算方法,树遍历,：事先建立语法树，（深度优先）遍历直至计算出所有属性值。,一遍扫描,：在语法分析的同时计算属性值。,计算语义规则,属性：,综合属性,：,可以在分析输入串的同时，,自下而上,地来计算。如：,val,继承属性,：,一个结点的继承属性值是由此结点的父结点和（或）兄弟结点的某些属性来决定的。如：,L.in,属性文法：,S-,属性,文法,：,L-,属性文法的一个特例,L-,属性文法,：,例1就是一个,L-,属性文法,属性文法的计算：,可以是普通意义上的数学运算，也可以是打印输出等动作。,属性文法的类型和计算,S-,属性文法,：,是,L-,属性文法的一个特例，只含有综合属性。例2是一个,S-,属性文法。,S-,属性文法翻译器,：,可以借助,LR,分析器实现。,实现原理,：,LR,分析器中增加一个栈（,语义值栈,）用来,存放综合属性的值,，进行归约的同时，栈中正在归约的产生式右部符号的综合属性值弹栈，并调用相应语义子程序进行相应计算（完成属性文法中的语义规则），产生的新值入语义值栈。,举例：,参见,P174,图8.7,S-,属性文法和,自下而上,翻译,L-,属性文法,：,对于,文法中的每个产生式,A,X,1,X,2,X,n,，,其每个语义规则中的每个属性要么是综合属性，要么是,X,j,(1jn),的一个继承属性且该继承属性仅依赖于：产生式中,X,1,X,2,X,j-1,的属性和,A,的继承属性。,L-,属性文法优点：,允许一次遍历就计算出所有属性值。,L-,属性文法,L-,属性文法翻译器,：,可以借助,LL,分析器实现。,实现原理,：,在自顶向下分析的过程中，每应用一个产生式进行推导，同时完成该产生式上属性文法的计算。,LL(1),分析方法的语义描述：,语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。这样的语义描述称为,翻译模式,。,举例：,P174,例8.3 例8.4,L-,属性文法在,自上而下,分析中的实现,翻译模式,：,语义动作不是附在产生式右部的末尾，而是嵌在两个符号之间。,翻译模式是适合语法制导翻译的另一种描述形式。,翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表现出来。,翻译模式,何时将属性文法改写成翻译模式？,消除左递归时，原属性文法将被改成翻译模式。,如何将属性文法改写成翻译模式？,原文法：,A,A,1,Y,A.a=g(A,1,.a,Y.y),A,X,A.a,=,f(X.x,),翻译模式：,A,X,R.i,=,f(X.x),R,A.a,=,R.s,R,Y,R,1,.i=g(R.i,Y.y),R,1,R.s,=R,1,.s,R,R.s,=,R.i,改写成翻译模式,L-,属性文法,中，如何实现,自下而上,计算继承属性？,方法,1,：去掉翻译模式中嵌入在产生式中间的动作。,方法,2,：改变原文法或,重新构造文法，,用综合属性代替继承属性。,自学（,P176,177,）,L-,属性文法在,自下而上,分析中的实现,8.3 中间代码的形式,中间代码的常见形式：,逆波兰记号,三元式,树形表示,四元式,逆波兰记号（后缀式）,特点：,将运算对象写在前面，把运算符号写在后面,标识符顺序与表达式中的一致,运算符顺序与计算顺序一致,无括号,表达式,逆波兰式,a+b,ab+,a+b*c,abc*+,(,a+b)*c,ab+c*,a=b*c+b*d,abc*bd*+=,为什么要使用逆波兰式？,更易于计算机处理，表示简洁、计算方便。,逆波兰记号的扩充用途,i-,i,Goto L,L,jump,if E then S,1,else S,2,ES,1,S,2,￥,Anm,nmA,subs,逆波兰式的复杂性：,压栈的可能是地址（如变量赋值），不是值；,栈中不一定产生结果。,逆波兰式的计算机处理方法：,自左向右扫描逆波兰式，遇到运算对象入栈，遇到算符则将相应数目的运算对象出栈计算后结果入栈。,三元式和树形表示,三元式的格式：(算符,第一运算对象,第二运算对象),如：,a=b*c+b*d,的三元式和树形表示,(1)(*,b,c)(2)(*,b,d)(3)(+,(1),(2)(4)(=,(3),a),=,a,+,*,*,b,c,b,d,四元式,四元式的格式：(算符,第一运算对象,第二运算对象,结果),如：,a=b*c+b*d,的四元式表示如下,(*,a,b,t1),(*,b,d,t2),(+,t1,t2,t3),(:=,t3,-,a),t1:=a*b,t2:=b*d,t3:=t1+t2,a:=t3,或,特点：利于代码优化和目标代码生成,特例：,goto,L,的四元式为,（,jump,-,-,L）,if B,rop,C,goto,L,的四元式为,(,jrop,B,C,L,),8.4 简单赋值语句的翻译,说明：,1）,id.name,表示,id,所表示的单词，用作语义变量,2）,lookup(id.name),审查,id.name,是否出现在符号表,是：返回指向该登录项的指针,否：返回,nil,3）,emit,将四元式输出到中间文件（或目标文件）上,4）,newtemp,生成一临时变量,5）,E.place,存放,E,值的变量名在符号表的登录项,若变量为临时变量，则直接存放一整数码,8.4 简单赋值语句的翻译,例3 将,赋值语句翻译成四元式,的语义描述：,S,id:=E,E,E,1,+,E,2,E,E,1,*,E,2,E,-E,1,E,(E,1,),E,id,S,id:=E,P:=lookup(,id.name,);if,P,nil,then emit(P,“:=”,E.place,);elseerror();,(2),E,E,1,+E,2,E.place:=newtemp;emit(E.place,“:=”,E,1,.place,“+”,E,2,.place);,(3),E,E,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,:=,-,E,1,.place);,(5),E,(E,1,),E.place=newtemp;emit(E.place,:=,E,1,.place);,(6),E,id,p:=lookup(id.name);if(p!=nil)E.place=p;else error();,8.5 布尔表达式的翻译,1、布尔表达式的作用：,计算逻辑值（返回真/假）,控制流语句中的条件表达式,if(,)then,while(,),2,、,布尔表达式的文法,E,E and E,E,E or E,E,not,E,E,id,rop,id,E,true,E,false,3,、布尔表达式的计算方法：,一步一步计算出式中各部分真假，最终算出整个表达式的值,采用优化措施，只计算部分表达式值即可,例如：,a and b/a,为,0,时，,b,无论是什么表达式的值都为,0,a or b/a,为,1,时，,b,无论是什么表达式的值都为,1,8.5 布尔表达式的翻译,例如,a or b and not c,对应的四元式,(1),(not,c,-,t1),(2),(and,b,t1,t2),(3),(or,a,t2,t3),布尔表达式的翻译,E,not,E1,E.true,:=E1.false;,E.codebegin,:=E1.codebegin;,E.false,:=E1.true;,(2)E,E1 and E2,backpatch(E1.true,E2.codebegin);,E.codebegin:=E1.codebegin;,E.true:=E2.true;,E.false:=merge(E1.false,E2.false);,(3)E,E1 or E2,backpatch(E1.false,E2.codebegin);,E.codebegin:=E1.codebegin;,E.tru