语法制导翻译和中间代码.ppt

《语法制导翻译和中间代码.ppt》由会员分享，可在线阅读，更多相关《语法制导翻译和中间代码.ppt（74页珍藏版）》请在三一办公上搜索。

1、第8章 语法制导翻译和中间代码生成,教学目的：1掌握语法制导翻译基本原理。2了解自上而下分析制导翻译基本思想和实现方法。3掌握几种常用的中间代码：四元式、三元式、逆波兰表示。4掌握简单表达式的中间代码生成。,教学重点：语法制导翻译基本思想、中间代码的形式、布尔表达式的翻译与控制结构的翻译；布尔表达式与控制结构的语义过程。,本章内容,8.1 属性文法,8.2 语法制导翻译概论,8.3 中间代码的形式,8.4 简单赋值语句的翻译,8.5 布尔表达式的翻译,8.6 控制结构的翻译,8.7 说明语句的翻译,8.8 数组和结构的翻译符号表,编译程序的任务是将汇编语言或高级语言书写成的源程序转换成等价的目

2、标代码程序。其中要求目标代码程序和源程序的语义(Semantics）必须相同。什么是语义？程序的语义就是它的“意思”。语义分析的任务包括两方面:一个是静态语义检查;一个是动态语义的解释执行（通俗地说就是计算并生成中间代码。,8.1 属性文法,一、静态语义分析或静态语义审查,语义分析的工作:,包括：（1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的

3、语句，则报错。（3）一致性检查。（4）上下文相关性检查。比如，变量名字必须先声明后引用；(5)名字的作用域分析,例,例,1、各种条件表达式的类型是不是boolean型？2、运算符的分量的类型是否相容？3、赋值语句的左右部的类型是否相容？4、形参和实参的类型是否相容？5、下标表达式的类型是否为所允许的类型？6、函数说明中的函数类型和返回值的类型是否一致？,1、每个使用的标识符是否都有声明？在同层内有无标识符被声明多次？【例如】Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。2、标号是否有声明？有无重复声明和重复定位错误？

4、有无非法转入错误？3、子界类型中的下界和上界类型是否相容？下界是否小于等于上界？,二、动态语义处理 如果静态语义正确，语义处理则执行真正的翻译（动态语义）即：生成程序的一种中间表示形式或生成实际的目标代码。中间代码(中间语言)是介于源语言和机器语言的一种表示形式。通常语义分析生成中间代码的原因：便于移植：中间代码相对独立于目标机，在编译程序移植时编译前端保持不变。利于优化：将优化分为与目标机无关的中间代码优化，以及与目标机相关的目标代码的优化，使优化更加细致有效。,语义分析的整个过程和词法及语法分析相类似。例如,在语法分析中，使用BackusNaus范式(BNF)中的上下文无关文法描述语法结构

5、，并用各种自顶向下和自底向上的分析算法实现语法结构。由于没有标准的方法(如BNF)来说明语言的静态语义，因此语义分析就没有这么简单。常采用属性文法(attribute grammar)来描述语义。,语义的形式化描述,8.1属性文法,一、属性（Attribute）,属性翻译文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规则。,二、属性文法（Attr

6、ibute Grammar）的定义,一个属性文法是一个三元组A(G,V,F)，其中：G为一上下文无关文法。V为属性的有穷集。F是关于属性的断言或一组属性的计算规则(称为语义规则)。,属性文法的表示分两部分：首先在上下文无关文法中，对于每个文法符号引进相关的属性符号；其次对于每个产生式写出计算属性值的计算规则（即语义规则）,来描述各属性间的关系。形式为：文法规则 语义规则规则1 相关的属性等式.规则n 相关的属性等式,【例】用属性文法表示简单的无符号整数文法：number number digit|digitdigit 0|1|2|3|4|5|6|7|8|9【分析】一个数最重要的属性是它的值，将

7、其命名为val。每个数字都有一个值，可以用它表示的实际数直接计算。1、文法规则：digit0 语义规则：digit.val=0 2、文法规则：number digit 语义规则：number.val=digit.val。3、文法规则number number digit,必须表示出这个文法规则左边符号的值和右边符号的值之间的关系。通过使用下标进行区分，将文法写成如下形式：number1 number2 digit语义规则：number1.val:=number2.val*10+digit.val,三、属性的分类（1）综合属性：用于“自下而上”传递信息 分析树中，如果一个结点的属性值是通过子结点

8、的属性值计算得到则称综合属性。（2）继承属性：用于“自上而下”传递信息 分析树中，如果一个结点的属性值由该结点的父结点和/或兄弟结点定义的则称继承属性。,四、语义规则 在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，f是一个函数，而且或者1）b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性，或者2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck 是A或产生式右边任何文法符号的属性。属性b依赖于属性c1,c2,ck。,说明：终结符只有综合属性，由词法分析器提供非终结符既可有综合属性也可有继承属性

9、，文法开始符号的所有继承属性作为属性计算前的初始值对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供,【例8.1】算术表达式求值的语义描述:产生式 语义规则LE print(E.val)EE1+T E.val:=E1.val+T.valET E.val:=T.val TT1*F T.val:=T1.valF.val TF T.val:=F.val F(E)F.val:

10、=E.val Fdigit F.val=digit.lexval,语义过程 L的属性为空,digit仅有综合属性 由词法分析程序提供,【例8.2】带有继承属性L.in的语义规则,产生式 语义规则 DTL Lin:=T type T int T type:=int T real T type:=real L L1,id L1 in:=L in addtype(id entry,L in)L id addtype(id entry,L in),8.2 语法制导翻译概论,语法制导翻译法 在语法分析的基础上进行边分析边翻译。注：1）语法制导翻译时会根据文法产生式右部符号串的含义，进行翻译，翻译的结果是

11、生成相应中间代码。2）语法制导翻译的依据是语义子程序。3）具体做法：为每个产生式配置一个语义子程序，当语法分析进行归约或推导时，调用语义子程序，完成一部分翻译任务。4）语法分析完成，翻译工作也结束。,语法制导翻译过程通常是这样的：1)对单词符号串进行语法分析，构造语法分析树;2)从语法分析树得到描述节点属性间依赖关系的依赖图;3)由此依赖图得到语义规则的计算次序;进行语义规则计算，得到翻译结果,可表示为：输入串语法树依赖图语义规则计算次序,在一棵语法树中结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。在为一棵语法树构造依赖图以前，为每一个包含过程调用的语义规则引入

12、一个虚综合属性b，这样把每一个语义规则都写成如下形式：b:=f(c1,c2,ck)依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。,依赖图,for分析树中每一个结点n do for 结点的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 分析树中每一个结点n do for结点n所用产生式对应的每一个语义规则 b:=f(c1,c2,ck)do for i:=1 to k do 从ci结点到b结点构造一条有向边,对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：,【例如】属性 A.a:=f(X.x,Y.y)对应于产生式 A

13、XY的语义规则,这条语义规则确定了依赖于属性X.x和Y.y的综合属性A.a。如果在语法树中应用这个产生式，那么在依赖图中会有三个结点A.a,X.x,和Y.y。由于A.a依赖X.x，所以有一条有向边从X.x到A.a.由于A.a也依赖于Y.y，所以还有一条有向边从Y.y连到A.a.如果与产生式AXY对应的语义规则还有：X.i:=g(A.a,Y.y)那么，图中还应有两条有向边，一条从A.a连到X.i，另一条从Y.y连到X.i,因为X.i依赖于A.a和Y.y.,如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,8.2.2 S-属性文法的自

14、下而上计算,1、S-属性文法仅仅使用综合属性的属性文法称S属性文法综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。,2、S-属性文法的翻译器 S-属性文法的翻译器通常可借助LR分析器来实现 在分析栈中使用一个附加的域来存放综合属性值 假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的,产生式 代 码 段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-

15、2*valtop TFF(E)valntop:=valtop-1Fdigit,产 生 式 语 义 规 则 LEn print(E.val)EE1+T E.val:=E1.val+T.val ET E.val:=T.val TT1*F T.val:=T1.val*F.val TF T.val:=F.val F(E)F.val:=E.val Fdigit F.val:=digit.lexval,输入 statesym val 用到的产生式 3*5+4n 0#-*5+4n 05#3-3*5+4n 03#F-3 Fdigit*5+4n 02#T-3 TF 5+4n 027#T*-3-+4n 0275#

16、T*5-3-5,产生式 代 码 段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit,输入 statesym val 用到的产生式+4n 0275#T*5-3-5+4n 02710#T*F-3-5 Fdigit+4n 02#T-15 TT*F+4n 01#E-15 ET 4n 016#E+-15-n 0165#E+4-15-4,产生式 代 码 段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+val

17、top ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit,输入 statesym val 用到的产生式 n 0165#E+4-15-4 n 0163#E+F-15-4Fdigit n 0169#E+T-15-4TF n 01#E-19EE+T#En-19-#L-19 LEn,产生式 代 码 段 LEnprint(valtop)EE1+Tvalntop:=valtop-2+valtop ETTT1*Fvalntop:=valtop-2*valtop TFF(E)valntop:=valtop-1Fdigit,8.2.3 L

18、-属性文法和自顶向下翻译,通过深度优先的方法对语法树进行遍历，计算属性文法的所有属性值LL(1)：自上而下分析方法，深度优先建立语法树,一个属性文法称为L-属性文法，如果对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj(1jn)的一个继承属性且这个继承属性仅依赖于：(1)产生式Xj的左边符号X1，X2，Xj-1的属性；(2)A的继承属性。S-属性文法一定是L-属性文法,【思考】非L-属性的语法制导定义,【分析】该语法制导定义不是L-属性定义，文法符号Q的继承属性依赖于它右边文法符号R的属性。,产生式,语义规则,ALMA QR,L.i:=l(A.i)M.i:=m

19、(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s),8.3 中间代码的形式,中间代码是源程序的一种内部表示复杂性介于源语言和目标机语言之间中间代码的作用使编译程序的逻辑结构更加简单明确利于进行与目标机无关的优化利于在不同目标机上实现同一种语言中间代码的形式 逆波兰式、四元式、三元式、树,1、后缀表示式Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。一个表达式E的后缀形式可以如下定义：1）如果E是一个变量或常量，则E的后缀式是E自身。2）如果E是E1 op E2形式的表达式，其中op是任何二元运算符，则E的后缀式为E1 E2 o

20、p，其中E1 和E2 分别为E1 和E2的后缀式。3）如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。,1、后缀表示式逆波兰表示法不用括号。只要知道每个算符的目数，对于后缀式，不论从哪一端进行扫描，都能对它进行唯一分解。例如：（a+b）*c 表示成ab+c*后缀式的计算用一个栈实现。一般的计算过程是：自左至右扫描后缀式，每碰到运算量就把它推进栈。每碰到k目运算符就把它作用于栈顶的k个项，并用运算结果代替这k个项。,1、后缀表示式把表达式翻译成后缀式的语义规则描述,产生式EE(1)op E(2)E(E(1)Eid,语义动作E.code:=E(1).code|E(2).code|op

21、E.code:=E(1).codeE.code:=id,E.code表示E后缀形式op表示任意二元运算符“|”表示后缀形式的连接。,数组POST存放后缀式：k为下标，初值为1上述语义动作可实现为：产生式程序段EE(1)op E(2)POSTk:=op;k:=k+1E(E(1)EiPOSTk:=i;k:=k+1例：输入串a+b+c的分析和翻译POST：1 2 3 4 5,EE(1)op E(2)E.code:=E(1).code|E(2).code|opE(E(1)E.code:=E(1).codeEidE.code:=id,a,b,+,c,+,2、图表示法DAG（无循环有向图）抽象语法树（1）

22、无循环有向图(Directed Acyclic Graph，简称DAG)对表达式中的每个子表达式，DAG中都有一个结点一个内部结点代表一个操作符，它的孩子代表操作数在一个DAG中代表公共子表达式的结点具有多个父结点,a:=b*(-c)+b*(-c)的图表示法,后缀式是抽象语法树的线性表示形式：abc-*bc-*+:=,抽象语法树对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,DAG对应的代码：T1:=-cT2:=b*T1T5:=T2+T2a:=T5,抽象语法树对应的代码：T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5

23、:=T2+T4 a:=T5,三地址代码,三地址代码x:=y op z 三地址代码可以看成是抽象语法树或DAG的一种线性表示,三地址语句的种类,x:=y op z x:=op y x:=y goto L if x relop y goto L或if a goto Lparam x和call p,n，以及返回语句return yx:=yi及xi:=y的索引赋值x:=&y,x:=*y和*x:=y的地址和指针赋值,3、四元式形式：一个带有四个域的记录结构：（Op，ARG1，ARG2，Result）注：1）ARG1，ARG2，Result可能是用户自己定义的变量，也可能是编译时引进的变量。这里Op是双目

24、运算符，若只有一个运算量，则是单目运算符。2）四元式中变量采用符号表的入口地址，而不用变量的地址，因为语义分析不仅需要变量的地址，还需要从符号表查到变量的属性、类型和地址等。,3、四元式形式：例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c，t1）（2）（*，b，d，t2）（3）（+，t1，t2，t3）（4）（:=，t3，-，a）,4、三元式形式（Op，ARG1，ARG2）注：1）这里三元式本身作为存放结果的单元。2）为了在其它三元式中利用当前三元式的结果，需要对三元式进行编号。三元式的编号就作为相应三元式的结果值。例如：a：=b*c+b*d的四元式表示如下：（1）（*，b，c）

25、（2）（*，b，d）（3）（+，（1），（2）（4）（:=，（3），a）,8.5 布尔表达式的翻译,布尔表达式的两个基本作用:用于逻辑演算,计算逻辑值;用于控制语句的条件式。产生布尔表达式的文法:EE or E|E andE|not E|(E)|i rop i|i,计算布尔表达式通常采用两种方法:1.如同计算算术表达式一样,一步步算 1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=12.采用某种优化措施 把A or B解释成 if A then true else B 把A and B解释成 if A then B else

26、 false 把not A解释成 if A then false else true,两种不同的翻译方法:第一种翻译法：A or B and C=D翻译成(1)(=,C,D,T1)(2)(and,B,T1,T2)(3)(or,A,T2,T3)第二种翻译法适合于作为条件表达式的布尔表达式使用。,8.5.1 数值表示法,a or b and not c 翻译成T1:=not cT2:=b and T1T3:=a or T1ab的关系表达式可等价地写成if ab then 1 else 0，翻译成 100:if ab goto 103101:T:=0102:goto 104103:T:=1104:,

27、关于布尔表达式的数值表示法的翻译模式,过程emit将三地址代码送到输出文件中nextstat给出输出序列中下一条三地址语句的地址索引每产生一条三地址语句后，过程emit便把nextstat加1,关于布尔表达式的数值表示法的翻译模式,EE1 or E2 E.place:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E 1.place and E2.place)Enot E1 E.place:=newtemp;emit(E.place:=not E 1.place)E(E

28、1)E.place:=E1.place,关于布尔表达式的数值表示法的翻译模式,Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place:=1)Eid E.place:=id.place,ab 翻译成100:if ab goto 103101:T:=0102:goto 104103:T:=1104:,布尔表达式ab or cd and ef的翻译结果,100:if ab goto

29、103101:T1:=0102:goto 104103:T1:=1104:if cd goto 107105:T2:=0106:goto 108107:T2:=1108:if ef goto 111109:T3:=0110:goto 112111:T3:=1112:T4:=T2 and T3113:T5:=T1 or T4,Eid1 relop id2 E.place:=newtemp;emit(if id1.place relop.op id2.place goto nextstat+3);emit(E.place:=0);emit(goto nextstat+2);emit(E.place

30、:=1)Eid E.place:=id.place EE1 or E2 E.place:=newtemp;emit(E.place:=E 1.place or E2.place)EE1 and E2 E.place:=newtemp;emit(E.place:=E 1.place and E2.place),8.5.2 作为条件控制的布尔式翻译,条件语句 if E then S1 else S2 赋予 E 两种出口:一真一假,E.code,S1.code,S2.code,To E.true,To E.false,goto S.next,S.next,E.true:,E.false:,例：把语句

31、:if ac or b c goto L2“真”出口 goto L1L1:if bd goto L2“真”出口 goto L3“假”出口 L2:(关于S1的三地址代码序列)goto LnextL3:(关于S2的三地址代码序列)Lnext:,产生布尔表达式三地址代码的语义规则,每次调用函数newlabel后都返回一个新的符号标号对于一个布尔表达式E，引用两个标号E.true是E为真时控制流转向的标号E.false是E为假时控制流转向的标号,产生布尔表达式三地址代码的语义规则,产生式语义规则 EE1 or E2 E1.true:=E.true;E1.false:=newlabel;E2.true:

32、=E.true;E2.false:=E.false;E.code:=E1.code|gen(E1.false:)|E2.code,产生布尔表达式三地址代码的语义规则,产生式语义规则EE1 and E2 E1.true:=newlabel;E1.false:=E.false;E2.true:=E.true;E2.false:=E.fasle;E.code:=E1.code|gen(E1.true:)|E2.code,产生布尔表达式三地址代码的语义规则,产生式语义规则Enot E1 E1.true:=E.false;E1.false:=E.true;E.code:=E1.code E(E1)E1.

33、true:=E.true;E1.false:=E.false;E.code:=E1.code,产生布尔表达式三地址代码的语义规则,产生式语义规则 Eid1 relop id2 E.code:=gen(if id1.place relop.op id2.place goto E.true)|gen(goto E.false)Etrue E.code:=gen(goto E.true)Efalse E.code:=gen(goto E.false),考虑如下表达式：ab or cd and ef假定整个表达式的真假出口已分别置为Ltrue和Lfalse，则按定义将生成如下的代码：,if ab go

34、to Ltruegoto L1L1:if cd goto L2goto LfalseL2:if ef goto Ltruegoto Lfalse,布尔表达式的翻译,两遍扫描为给定的输入串构造一棵语法树；对语法树进行深度优先遍历，进行语义规则中规定的翻译。一遍扫描,一遍扫描实现布尔表达式的翻译,采用四元式形式把四元式存入一个数组中，数组下标就代表四元式的标号约定 四元式(jnz,a,-,p)表示 if a goto p 四元式(jrop,x,y,p)表示 if x rop y goto p四元式(j,-,-,p)表示 goto p,有时,四元式转移地址无法立即知道,我们只好把这个未完成的四元式地

35、址作为E的语义值保存,待机回填。,为非终结符E赋予两个综合属性E.truelist和E.falselist。它们分别记录布尔表达式E所应的四元式中需回填“真”、“假”出口的四元式的标号所构成的链表 例如:假定E的四元式中需要回填真出口的p，q，r三个四元式，则E.truelist为下列链:(p)(x，x，x，0)(q)(x，x，x，p)(r)(x，x，x，q),链尾,E.truelist=r,为了处理E.truelist和E.falselist，引入下列语义变量和过程:变量nextquad，它指向下一条将要产生但尚未形成的四元式的地址(标号)。nextquad的初值为1，每当执行一次emit之

36、后，nextquad将自动增1。函数makelist(i)，它将创建一个仅含i的新链表，其中i是四元式数组的一个下标(标号)；函数返回指向这个链的指针。函数merge(p1,p2)，把以p1和p2为链首的两条链合并为一，作为函数值，回送合并后的链首。过程backpatch(p,t)，其功能是完成“回填”，把p所链接的每个四元式的第四区段都填为t。,布尔表达式的文法,(1)EE1 or M E2(2)|E1 and M E2(3)|not E1(4)|(E1)(5)|id1 relop id2(6)|id(7)M,布尔表达式的翻译模式,(1)EE1 or M E2 backpatch(E1.fa

37、lselist,M.quad);E.truelist:=merge(E1.truelist,E2.truelist);E.falselist:=E2.falselist(2)EE1 and M E2 backpatch(E1.truelist,M.quad);E.truelist:=E2.truelist;E.falselist:=merge(E1.falselist,E2.falselist),布尔表达式的翻译模式,(3)Enot E1 E.truelist:=E1.falselist;E.falselist:=E1.truelist(4)E(E1)E.truelist:=E1.trueli

38、st;E.falselist:=E1.falselist,布尔表达式的翻译模式,(5)Eid1 relop id2 E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(j relop.op,id 1.place,id 2.place,0);emit(j,0)(6)Eid E.truelist:=makelist(nextquad);E.falselist:=makelist(nextquad+1);emit(jnz,id.place,0)；emit(j,-,-,0),布尔表达式的翻译模式,(7)M M.quad:=nextquad,布尔表达式的翻译模式,作为整个布尔表达式的真假出口(转移目标)仍待回填.,ab or cd and ef,100(j,a,b,0)101(j,-,-,102)102(j,c,d,104)103(j,-,-,0)104(j,e,f,100)truelist105(j,-,-,103)falselist,