语法制导翻译和中间代码生成

语法制导翻译和中间代码生成目标程序源程序词法分析语法分析语义分析中间代码生成代码优化目标代码生成表格管理出错处理语义分析基础语义分析得内容主要就是类型相容检查,有以下几种:各种条件表达式得类型就是不就是boolean型？运算符得分量类型就是否相容？赋值语句得左右部得类型就是否相容？形参与实参得类型就是否相容?下标表达式得类型就是否为所允许得类型？函数说明中得函数类型与返回值得类型就是否一致？语义分析基础-语义分析得内容(续)其她语义检查:V[E]中得V就是不就是变量,而且就是数组类型？V、i中得V就是不就是变量,而且就是记录类型？i就是不就是该记录得域名？x+f(…)中得f就是不就是函数名？形参个数与实参个数就是否一致？每个使用性标识符就是否都有声明？有无标识符得重复声明？语义分析基础在语义分析同时产生中间代码,在这种模式下,语义分析得主要功能如下:语义审查在扫描声明部分时构造标识符得符号表在扫描语句部分时产生中间代码中间代码:独立于机器,复杂性介于源语言与机器语言之间,十分接近目标机器指令得一种表示形式。对于中间代码得产生,就是很困难得,因为语义形式化比语法形式化难得多。目前普遍采用得语义分析方法——语法制导翻译方法 使用属性文法为工具来说明程序设计语言得语义。6、1属性文法(AttributeGrammar)属性 对文法得每一个符号,引进一些属性,这些属性代表与文法符号相关得信息,如类型、值、存储位置等。语义规则 为文法得每一个产生式配备得计算属性得计算规则,称为语义规则。属性文法就是带属性得一种文法 她得主要思想:首先对于每个文法符号引进相关得属性符号;其次对于每个产生式写出计算属性值得语义规则6、1属性文法(续)属性文法得形式定义 一个属性文法就是一个三元组,A＝(G,V,F)G就是一个上下文无关文法;V就是属性得有穷集;F就是关于属性得断言得有穷集。说明: 每个属性与文法符号相联,N、t表示文法符号N得属性t。属性值又称语义值。存储属性值得变量又称语义变量。每个断言与文法得某个产生式相联,写在{}内。属性得断言又称语义规则,她所描述得工作可以包括属性计算、静态语义检查、符号表得操作、代码生成等,有时写成函数或过程段。6、1属性文法(续)例完成类型检查得属性文法E→T1+T2 {T1、t＝intANDT2、t＝int}E→T1orT2 {T1、t＝boolANDT2、t＝bool}T→num {T、t:＝int}T→true {T、t:＝bool}T→false {T、t:＝bool}

6、1属性文法(续)属性得分类:综合属性:从语法树得角度来看,如果一个结点得某一属性值就是由该结点得子结点得属性值计算来得,则称该属性为综合属性。内在属性就是综合属性。用于“自下而上”传递信息6、1属性文法(续)继承属性从语法树得角度来看,若一个结点得某一属性值就是由该结点得兄弟结点与(或)父结点得属性值计算来得,则称该属性为继承属性。用于“自上而下”传递信息特别说明:终结符只有综合属性,她们由词法分析器提供非终结符既有综合属性也有继承属性,但文法开始符没有继承属性6、1属性文法(续)例简单算术表达式求值得属性文法L→E {Print(E、val)}E→E1+T {E、val:＝E1、val+T、val}E→T {E、val:＝T、val}T→T1*F {T、val:＝T1、val*F、val}T→F {T、val:＝F、val}F→(E) {F、val:＝E、val}F→digit {F、val:＝digit、lexval}

E、val、T、val、F、val都就是综合属性终结符digit只有综合属性lexval

,她得值由词法分析器提供12大家应该也有点累了，稍作休息大家有疑问的，可以询问和交流6、2语法制导翻译概论语法制导翻译基本思想:

在语法分析过程中,随着分析得步步进展,每当使用一条产生式进行推导(对于自上而下分析)或归约(对于自下而上分析),就执行该产生式所对应得语义动作(语义子程序),完成相应得翻译工作(产生中间代码)。语法制导翻译法不论对自上而下分析或自下而上分析都适用。例简单算术表达式求值得属性文法E→E1+T {E、val:＝E1、val+T、val}E→T {E、val:＝T、val}T→T1*digit{T、val:＝T1、val*digit、lexval}T→digit {T、val:＝digit、lexval}

2+3*5得语法树:EE1+TT1*5T23T、val=2T、val=3T、val=15E、val=2E、val=17自下而上语法制导翻译过程:一旦语法分析确认输入符号串就是一个句子,她得值也同时由语义规则计算出来6、3中间代码得形式定义: 中间代码就是独立于机器,复杂性介于源语言与机器语言之间,十分接近目标机器指令得一种表示形式。使用中间代码得好处:中间代码与具体机器无关,便于编译程序改变目标机便于对中间代码进行与机器无关得优化表示形式: 逆波兰式、四元式、三元式、间接三元式与树形表示6、3、1逆波兰表示法(后缀式)

逆波兰表示法 将运算对象写在前面,把运算符写在后面,因而也称后缀式。 例如:程序设计语言中得表示逆波兰表示a+bab+a+b*cabc*+(a+b)*cab+c*bt1dct1t2t1t3t1=-bt2=c*dt3=t1+t2例:表达式－b＋c*d得后缀式bcd*+得计值过程后缀式得计算机处理后缀式得最大优点就是易于计算机处理处理过程: 从左到右扫描后缀式,每碰到运算对象就推进栈;碰到运算符就从栈顶弹出相应目数得运算对象施加运算,并把结果推进栈。最后得结果留在栈顶。逆波兰表示法得扩充 逆波兰表示法很容易扩充到表达式以外得范围 例如:语句逆波兰表示备注a:=b+cabc+:=:=看作二目运算符GOTOLLjumpjump看成一目运算符,表示GOTOIfEthenS1elseS2ES1S2￥把￥看成三目运算符,表示if–then–else6、3、2三元式三元式

(算符op,第一个运算对象ARG1,第二个运算对象ARG2)说明:三元式得某些运算对象就是另一个三元式得编号(代表其结果)一目算符只需选用一个运算对象(ARG1)多目算符可用连续几个三元式表示 例:a:＝b*c+b*d表示为(1)(*, b, c )(2)(*, b, d )(3)(+, (1), (2) )(4)(:＝, (3), a )6、3、3树形表示树形表示 二目运算对应二叉子树,多目运算对应多叉子树,但通常通过引入新结点表示成二叉子树。 例如:a:＝b*c+b*d表示成:=a+**bcbd叶子结点代表运算量,非叶子结点代表运算符6、3、4四元式四元式 四元式就是一种比较普遍采用得中间代码形式

(算符op,ARG1,ARG2,运算结果RESULT)例如:a:＝b*c+b*d得四元式表示如下:(*, b, c, t1)(*, b, d, t2)(+, t1, t2, t3)(:＝, t3, －, a)其中ti(i＝1,2,3)就是编译程序引入得临时变量6、3、4四元式(续)四元式得优点:四元式比三元式更便于优化 优化要求改变运算顺序或删除某些运算,引起编号得变化。 三元式通过编号引用中间结果,编号得变化引起麻烦;四元式通过临时变量引用中间结果,编号变化无影响。四元式对生成目标代码有利 四元式表示很类似于三地址指令,很容易转换成机器代码。6、3、4四元式(续)四元式得另一种表示 有时为了更直观,把四元式写成简单赋值形式或更易理解得形式(三地址码)四元式直观形式(1)(*,b,c,t1)(1)t1:＝b*c(2)(*,b,d,t2)(2)t2:＝b*d(3)(+,t1,t2,t3)(3)t3:＝t1+t2(4)(:＝,t3,－,a)(4)a:＝t36、3、5间接三元式为了便于优化处理,不直接使用三元式,而就是另设一张指示器表(称为间接码表),她按照运算得先后顺序列出有关三元式在三元式表中得位置。即:用一张间接码表辅以三元式表得方法来表示中间代码。四元式、间接三元式得优化同样方便,三元式得优化十分困难。举例:给出A+B*(C-D)+E/(C-D)^N得逆波兰式、四元式、三元式、间接三元式得表示1、逆波兰式:ABCD-*+ECD-N^/+2、四元式:(-,C,D,T1)(*,B,T1,T2)(+,A,T2,T3)(-,C,D,T4)(^,T4,N,T5)(/,E,T5,T6)(+,T3,T6,T7)举例:给出A+B*(C-D)+E/(C-D)^N得逆波兰式、四元式、三元式、间接三元式得表示3、三元式:(-,C,D)(*,B,1))(+,A,2))(-,C,D)(^,4),N)(/,E,5))(+,3),6))4、间接三元式:(-,C,D)(*,B,1))(+,A,2))(^,1),N)(/,E,4))(+,3),5))间接码表1)2)3)1)4)5)6)6、4语法制导翻译主要讨论自下而上得语法制导翻译在一个产生式进行归约时,执行相应得语义动作进行翻译(产生中间代码)6、4、1简单赋值语句到四元式得翻译简单赋值语句 就是指不含复杂数据类型(如数组,记录等)得赋值语句。赋值语句得语义检查包括:每个使用性标识符就是否都有声明？运算符得分量类型就是否相容？赋值语句得左右部得类型就是否相容？赋值语句得翻译目标: 在赋值语句右部表达式产生得四元式序列后加一条赋值四元式6、4、1简单赋值语句到四元式得翻译考虑如下文法描述得简单赋值句得翻译:A→i:=EE→E+E|E*E|-E|(E)|i(6、1)A代表赋值语句,设只含整型变量得运算1、需要定义一系列得语义变量与语义过程:NEWTEMP:函数,生成临时变量,每次调用生成一个新得临时变量,如t1,t2,…返回一个整数码作为函数值。ENTRY(i):函数过程,查找并取得与i相对应得标识符在符号表中得位置(入口),简称i值。E、PLACE:与E相联系得语义变量,表示存放E值得变量名在符号表得入口。GEN(OP,ARG1,ARG1,RESULT):语义过程,将四元式(OP,ARG1,ARG1,RESULT)填进四元式表中。使用上述变量与过程,对文法6、1所定义得赋值语句得翻译算法可由下述语义动作予以描述6、4、1简单赋值语句到四元式得翻译产生式语义动作A→i:=E{GEN(:=,E、PLACE,-,ENTRY(i))}E→E(1)+E(2){E、PLACE:=NEWTEMP;GEN(+,E(1)、PLACE,E(2)、PLACE,E、PLACE)}E→E(1)*E(2){E、PLACE:=NEWTEMP;GEN(*,E(1)、PLACE,E(2)、PLACE,E、PLACE)}E→-E(1){E、PLACE:=NEWTEMP;GEN(,E(1)、PLACE,-,E、PLACE)}E→(E(1)){E、PLACE:=E(1)、PLACE}E→i{E、PLACE:=ENTRY(i)}输入串栈PLACE四元式A:=-B*(C+D):=-B*(C+D)iA-B*(C+D)i:=A_B*(C+D)i:=-A__*(C+D)i:=-iA__B*(C+D)i:=-EA__B(,B,-,T1)*(C+D)i:=EA_T1(C+D)i:=E*A_T1_C+D)i:=E*(A_T1__+D)i:=E*(iA_T1__C+D)i:=E*(EA_T1__CD)i:=E*(E+A_T1__C_)i:=E*(E+iA_T1__C_D)i:=E*(E+EA_T1__C_D(+,C,D,T2))i:=E*(EA_T1__T2i:=E*(E)A_T1__T2_i:=E*EA_T1_T2(*,T1,T2,T3)i:=EA_T3(:=,T3,-,A)A2例:写出下面赋值语句A:=-B*(C+D)得自下而上语法制导翻译得过程,及生成得四元式。A→i:=EE→E+E|E*E|

-E|(E)|i四元式为:(1)(,B,-,T1)(2)(+,C,D,T2)(3)(*,T1,T2,T3)(4)(:=,T3,-,A)3、类型转换表达式中可能出现不同类型得变量与常量若不接受不同类型得运算对象混合运算,则应指出错误;若接受混合运算则要进行类型转换处理。例:假定表达式可以有混合运算,变量可以就是整型与实型,且当两个不同类型得变量进行运算时先把整型变量转换成实型,再进行运算。用+i,*i,i表示整型运算,用+r,*r,

r表示实型运算,用一目算符itr表示将整型量转换成实型量得运算令文法6、1中得i既可以就是整型也可以就是实型用E、MODE表示E得类型信息,其值为int或r,则产生式E→E(1)opE(2)得语义动作中,关于E、MODE得语义规则可定义为:{ifE1、MODE＝intANDE2、MODE＝intthenE、MODE:=intelseE、MODE:=r}3、类型转换(续)E→E(1)opE(2)

得语义程序应该修改,必要时产生对运算量进行类型转换得四元式:(itr,A,-,T),表示把整型A转换成实型量,结果存于T中。例:假定输入串为X:=Y+I*J,其中X,Y为实型,I,J为整型,则其产生得四元式为:

(1)(*i,I,J,T1)(2)(itr,T1,-,T2)(3)(+r,Y,T2,T3)(4)(:=,T3,-,X)例:关于产生式E→E(1)opE(2)

得语义子程序更为具体得描述为:T:=NEWTEMP;IFE1、MODE=intANDE2、MODE=intTHENBEGINGEN(opi,E1、PLACE,E2、PLACE,T);E、MODE:=intENDELSEIFE1、MODE=rANDE2、MODE=rTHENBEGINGEN(opr,E1、PLACE,E2、PLACE,T);E、MODE:=rENDELSEIFE1、MODE=int/*ANDE2、MODE=r*/THENBEGIN U:=NEWTEMP;GEN(itr,E1、PLACE,-,U); GEN(opr,U,E2、PLACE,T);E、MODE:=rENDELSE/*E1、MODE=rANDE2、MODE=int*/BEGIN U:=NEWTEMP;GEN(itr,E2、PLACE,-,U); GEN(opr,E2、PLACE,U,T);E、MODE:=rENDE、PLACE:=TE→E(1)opE(2)布尔表达式得两个作用:用于逻辑运算,计算逻辑值作为控制语句(如if-then,while)得条件表达式布尔表达式由布尔算符(not,and,or)作用于布尔变量(或常数)或关系表达式而形成得。关系表达式得形式:E1ropE2,rop就是关系算符(如<＝,<,＝,≠,>,>=)6、4、2布尔表达式到四元式得翻译为简单起见,只考虑如下形式得布尔表达式得翻译,文法(6、2) E→EorE|EandE|notE|(E)|idropid|id布尔算符得优先顺序(从高到低)为:not,and,or,且and与or都服从左结合,not服从右结合关系算符得优先级都相同,而且高于任何布尔算符,低于任何算术算符6、4、2布尔表达式到四元式得翻译-续1、布尔表达式得计算方法:

采用两种方法:数值表示得直接计算与逻辑表示得短路计算直接计算与算术表达式计算方法基本相同 如:1or0and1=1or0得结果为:1短路计算即布尔表达式计算到某一部分就可以得到结果,而无需对布尔表达式进行完全计算。可以用if-then-else来解释

AorB ifAthentrueelseB AandB ifAthenBelsefalse notA ifAthenfalseelsetrue2、直接计算得语法制导翻译布尔表达式有两种翻译方法。(视计算机硬件条件来确定,如果执行条件转移效率较低,就用第一种方法)直接计算得语法制导翻译如同翻译算术表达式一样来翻译布尔表达式如:AorBandnotC被翻译成:

(1)(not, C, -, T1) (2)(and, B, T1, T2) (3)(or, A, T2, T3)3、作为条件控制得布尔式翻译基本翻译方法 当布尔表达式用于控制条件时,并不需要计算表达式得值,而就是一旦确定了表达式为真或为假,就将控制转向相应得代码序列。S2的代码S1的代码E的代码E.falseE.trueifEthenS1elseS2为布尔表达式E引入两个新得属性:E、true:表达式得真出口,她指向表达式为真时得转向E、false:表达式得假出口,她指向表达式为假时得转向把布尔表达式E翻译成下述形式得条件转移与无条件转移得四元式序列:(jnz,A,-,p)

若A为真,则转向四元式p(jrop,A,B,p)

若AropB为真,则转向四元式p(j,-,-,p)

无条件转向四元式p3、作为条件控制得布尔式翻译-续(1) (jnz,A,-,5) A得真出口为5(2) (j,-,-,3) A得假出口为3(3) (j<,B,D,5) B<D得真出口为5(4) (j,-,-,p+1) B<D得假出口为(p+1)(5) (关于S1得四元式序列)(p) (j,-,-,q) 跳过S2得代码段(p+1) (关于S2得四元式序列)(q)(1)-(4)就是布尔式AorB<D翻译产生得代码,全部就是条 件转移与无条件转移四元式,没有布尔运算。例:ifAorB<DthenS1elseS2翻译成如下四元式序列具体说明如下:

用E、true与E、false分别表示E得“真”与“假”出口转移目标,在翻译E时并未能确定。对于E为aropb形式,生成代码如下:

(jrop,a,b,E、true) (j,－,－,E、false)

以结构图表示:E的代码E.falseE.true对于E为E1orE2得形式,生成代码结构如下:E1.的代码E2.的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true若E1为真,则可知E为真,即E1得真出口与E得真出口一样;若E1为假,则必须计算E2,因此E1得假出口应就是E2代码得第一个四元式序号;E2得真出口与假出口分别与E得真出口与假出口一样E1.的代码E2.的代码E1.falseE2.falseE.falseE1.trueE2.trueE.true对于E为E1andE2得形式,生成代码结构如下:对于E为notE1形式,只需调换E1得真假出口,即可得到E得真假出口。例:E为a<borc<dande>f,翻译为四元式序列:(1)

( j<, a, b, E、true)(2)

( j, -, -, (3))(3)

( j<, c, d, (5))(4)

( j, -, -, E、false)(5)

( j>, e, f, E、true)(6)

( j, -, -, E、false)举例真假出口得拉链与回填在把布尔式翻译成一串条件转与无条件转四元式时,真假出口未能在生成四元式时确定;而且多个四元式可能有相同得出口说明:E、true与E、false不能在产生四元式得同时确定,要等将来目标明确时再回填,为此要记录这些要回填得四元式。通常采用“拉链”得办法,把需要回填E、true得四元式拉成一条“真”链,把需要回填E、false得四元式拉成一条“假”链。ifa<borc<dande>fthenS1elseS2