1 翻译方式有两种翻译方式有两种:第五章第五章 中中间代代码生成生成源言语源言语目的言语目的言语源言语源言语1)2)目的言语目的言语中间代码中间代码中间代码的特点中间代码的特点: 构造简单构造简单,功能明确功能明确,易于优化易于优化,易于翻译易于翻译. 第一第一节 中中间代代码简介介1) 逆波兰表示法逆波兰表示法 运算量在前运算量在前,运算符在后的后缀式表示法运算符在后的后缀式表示法.例如例如: 表达式表达式后缀式后缀式 a+bab+ (a+b)*cab+c* a*(b+c)abc+* (a+b)*(c+d)ab+cd+* 2) 三元式表示法三元式表示法 三元式就是三元组三元式就是三元组: ( 操作符操作符,操作数操作数1,操作数操作数2)例如例如: 语句语句 D:=A+B*C 可翻译为下述三元式表可翻译为下述三元式表: (1) (*,B,C) (2) (+,A,(1)) (3) (:=,D,(2)) 三元式没有明确指出结果放在何处三元式没有明确指出结果放在何处. 3) 四元式表示法四元式表示法 四元式就是四元组四元式就是四元组: ( 操作符操作符,操作数操作数1,操作数操作数2,结果结果)例如例如: 语句语句 D:=A+B*C 可翻译为下述四元式表可翻译为下述四元式表: (1) (* ,B ,C ,T1) (2) (+ ,A ,T1,T2) (3) (:= ,T2, , D ) 四元式间经过暂时变量传值四元式间经过暂时变量传值. 操作符实现的运算也非常简单操作符实现的运算也非常简单,本章主要引见各种语句到四元式的翻译本章主要引见各种语句到四元式的翻译. 第二第二节 语法制法制导翻翻译的根本思想的根本思想1 何谓语法制导翻译何谓语法制导翻译 在语法分析的每次归约或推导时在语法分析的每次归约或推导时,根据产生式的语义进展根据产生式的语义进展翻译的一种方法翻译的一种方法. 翻译时翻译时,除了产生中间代码外除了产生中间代码外,还有许多辅助任务还有许多辅助任务,包括包括: 改动语法变量的值改动语法变量的值;查填符号表查填符号表;诊查与报告源程序错误等诊查与报告源程序错误等.2 与翻译相关的假设干商定与翻译相关的假设干商定 1) 暂时变量暂时变量 在翻译中在翻译中,能够会引入许多暂时变量存放中间结果能够会引入许多暂时变量存放中间结果. 经过调用经过调用 newtemp() 前往一个暂时变量前往一个暂时变量 Ti . 2) 分析栈分析栈 分析栈中的内容为语法单位分析栈中的内容为语法单位,每个语法单位包含两个部分每个语法单位包含两个部分: (语法单位称号语法单位称号,语法单位属性语法单位属性),属性能够有多个值属性能够有多个值. 例如例如: E 为表达式的语法单位为表达式的语法单位, E.place 代表了该表达式值代表了该表达式值 存放的地方存放的地方.3) 符号表符号表 符号表用于存放变量及属性值符号表用于存放变量及属性值,由如干项构成由如干项构成,每个项为每个项为: (变量名变量名, 变量信息变量信息).4) 四元式表四元式表 四元式表用于存放翻译中产生的四元四元式表用于存放翻译中产生的四元 式式,经过过程经过过程 Gen( 操作符操作符,操作数操作数1,操作数操作数2,结果结果) 把四元式存入四元式表的把四元式存入四元式表的 NXQ 所指所指 空间中空间中, NXQ 自动加自动加 1. 四元式表四元式表NXQ 5 一些根本操作一些根本操作 •newtemp( ) 产生一暂时变量产生一暂时变量;•gen(操作符操作符,操作数操作数1,操作数操作数2,结果结果) 填入四元式表填入四元式表;•fill( i,属性属性)填入符号表填入符号表;•entry( i )查符号表查符号表,前往前往 i 在符号表中的位置在符号表中的位置;•backpatch( m,n) 把把 n 填入填入 四元式表第四元式表第 m 个四元式中个四元式中; 第三第三节 简单变量量阐明明语句的翻句的翻译 程序程序设计中中,首先首先应该对程序中运用的程序中运用的变量量进展展阐明明.其目的其目的是是规定定变量所占用空量所占用空间的大小的大小. 编译时, 对变量量阐明明语句的翻句的翻译工工作作,本本质上就是把上就是把变量名及属性登量名及属性登记在符号表中在符号表中,以便后以便后续任任务中中运用运用. pascal 言言语的的简单变量量阐明明语句句为: x,y,z:real; 语法可表示法可表示为: D → NAMELIST:T NAMELIST→ NAMELIST,i | i T → integer|real|boolean|char 该文法代表了一切该文法代表了一切非构外型变量的阐明语非构外型变量的阐明语句句. 当然当然,也可以用如下文法表示也可以用如下文法表示: D→i:T | i,D T → integer|real|boolean|char 我我们曾曾经知道用知道用该文法如何分析一个文法如何分析一个阐明明语句句,下面要下面要处理理的是的是,怎怎样在分析的在分析的过程中程中, 把把该语句表达的意思完好的翻句表达的意思完好的翻译清楚清楚. 阐明明语句的含句的含义是是: 阐明的明的变量具有量具有给定定类型型; 编译时那么翻那么翻译为:把每个把每个变量及量及类型登型登记在符号表中在符号表中. 语法制法制导翻翻译就是就是为每一条每一条产生式配一个子程序生式配一个子程序,当用某个当用某个产生式生式归约时,就就调用相用相应的子程序的子程序进展适当的翻展适当的翻译任任务. 这些子程序称些子程序称为语法法单位的位的语义子程序子程序(或或语义动作作). 下面下面讨论如下文法的各如下文法的各产生式的生式的语义子程序及翻子程序及翻译过程程 D→i:T | i,D T → integer|real|boolean|char 1) T → integer { T.att:=integer}; 2) T → real { T.att:=real}; 3) T →boolean { T.att:=boolean}; 4) T → char { T.att:=char}; 5) D→i:T { D.att:= T.att ; fill(i,T.att) }; 6) D→i:D { D.att:= D .att ; fill(i, D .att) }; 例如例如: x,y,z:real;x,y,z:realx,y,z:Tx,y,Dx,DDT.att=realD.att=real;fill(z,real)D.att=real;fill(y,real)D.att=real;fill(z,real)最终最终,符号表中包含了符号表中包含了 x,y,z 三个变量及属性三个变量及属性 real. 第四第四节 简单算算术表达式表达式 和和赋值语句的翻句的翻译 简单算算术赋值语句的文法可表示句的文法可表示为:S→i:=EE→E+E | E-E | E*E | E/E | (E) | i 该文法文法为二二义文法文法,但假但假设规定每个定每个终结符的符的优先关系先关系,并按并按优先关系先关系进展展归约,那么可以防止二那么可以防止二义性性. 赋值语句的含句的含义是是:计算出算出 E 的的值,并写入并写入变量量 i 中中. 编译中中,并不关并不关怀值是多少是多少,而关而关怀的是怎的是怎样计算算值的的过程程;也即也即,哪些哪些变量参与运算量参与运算,怎怎样运算运算? 上面文法的各上面文法的各产生式生式语义子程序如下子程序如下: E→i{ E.place:=entry(i)} //E.place 表示了表达式表示了表达式E 的的值放在什么放在什么变量中量中 E→(E1) { E.place:= E1.place}E → E1 + E2 { E.place:=newtemp( ) Gen( + , E1 .place, E2.place, E.place) }E → E1 - E2 { E.place:=newtemp( ) Gen( - , E1 .place, E2.place, E.place) }E → E1 * E2 { E.place:=newtemp( ) Gen( * , E1 .place, E2.place, E.place) }E → E1 / E2 { E.place:=newtemp( ) Gen( / , E1 .place, E2.place, E.place) }S→ i := E { Gen( := , E.place , ,entry( i ) } 四元式中的操作数及四元式中的操作数及结果果,本本质上是一指向上是一指向变量的指量的指针. 例如例如: x:=y+zx:=y+z x:=y x:=Ex:=E+zx:=E1+E2E.place=entry(y)E1.place=entry(y); E2.place=entry(z)+z +z x:=EE .place=T1 ;Gen(+,y,z, T1) S Gen(:=, T1 , , x ) 第五第五节 布布尔表达式的翻表达式的翻译 布布尔表达式文法可表示表达式文法可表示为:B→not B | B and B | B or B | (B) | i | E ROP E ROP →< | <= | = | > | >= | < > 该文法也文法也为二二义文法文法,但假但假设规定每个定每个终结符的符的优先关系先关系,并按并按优先关系先关系进展展归约,那么可以防止二那么可以防止二义性性. 各各产生式生式语义子程序如下子程序如下: ROP →< | <= | = | > | >= | < > { ROP.val= < 或或 <=或或 =或或 >或或 >=或或 < > } B→i { B.place:=entry(i)} //B.place 表示了表达式表示了表达式B 的的值放在什么放在什么变量中量中 B→(B1) { B.place:= B1.place}B →not B1 { B.place:=newtemp( ) Gen( not , B1 .place, , B.place) }B → B1 and B2 { B.place:=newtemp( ) Gen( and , B1 .place, B2.place, B.place) }B → B1 or B2 { B.place:=newtemp( ) Gen( or, B1 .place, B2.place, B.place) }B → E1 ROP E2 { B.place:=newtemp( ) Gen( ROP.val, E1 .place, E2.place, B.place) } 第六第六节 分支分支语句的翻句的翻译分支语句包括分支语句包括: ifcase(省略省略)goto1 if 语句的翻译语句的翻译 在程序设计种在程序设计种,if 语句可以表示为语句可以表示为: if B then S1 else S2; if 语句翻译后语句翻译后,将得到一组四元式将得到一组四元式,其流程可以表示为其流程可以表示为: B 的四元式的四元式B为真为真?S1 的四元式的四元式S2 的四元式的四元式F 分析是从前向后进展的分析是从前向后进展的,按四元式按四元式流程的要求流程的要求,(1)首先归约布尔表达式首先归约布尔表达式,产生产生B的四元式的四元式;(2)在归约在归约S1之前之前,应产生条件转移语句应产生条件转移语句,也即也即 当归约当归约 if B then 时时,产生条件转移语句产生条件转移语句; 由于由于 S1 S2 还未处置还未处置,因此因此,条件转移语句条件转移语句 的转移地址未知的转移地址未知,只需等到只需等到S1处置终了并处置终了并 产生了无条件转移语句产生了无条件转移语句,才干知道条件转才干知道条件转 移语句转移确实切地址移语句转移确实切地址.(3)归约归约S1;并在归约并在归约 S1 else 时时,产生无条件产生无条件 转移语句转移语句;此时此时,由于由于S2未处置未处置, 无条件转无条件转 移语句的转移地址不确定移语句的转移地址不确定;回填条件转移语句的地址回填条件转移语句的地址.(4)归约归约S2;回填无条件转移语句的地址回填无条件转移语句的地址.** 从以上分析从以上分析,可以将文法可以将文法设计为: S→TS2 T→CS1else C→if B then 语义子程序子程序为: C→if B then{ C.chain:=NXQ; Gen(Jz,B.place, ,xxxx)} T →CS1else{T.chain:=NXQ; Gen(J , , ,xxxx); backpatch(C.chain,NXQ)} S→TS2{backpatch (T.chain,NXQ)}并设并设:T C 有属性值有属性值 T.chain及及C.chain,用于用于记录条件及无条件转移记录条件及无条件转移四元式的序号四元式的序号. 例如例如: if A<1 then x:=2 else y:=4x:=2 else y:=4 C CS1elseTTS2x:=2 else y:=4 y:=4 if B then 四元式序列四元式序列(1) (<,A,1,T1)(2) (Jz,T1, ,xxxx) (5)(3) (:=,2, ,x)(4) (J , , ,xxxx) (6)(5) (:=,4, ,y)(6)y:=4 SC.chain=(2);Gen(Jz,T1, ,xxxx)T.chain=(4);Gen(J , , ,xxxx);backpatch((2),(5))backpatch((4),(6))NXQ 2 标号及号及转移移语句的翻句的翻译 处置置标号包括三个含号包括三个含义: 标号号阐明明 标号定号定义 标号援用号援用(1) 标号号阐明的翻明的翻译 标号号阐明明语句的句的语法如下法如下: Lab→label c | Lab,c 标号号阐明明语句用于句用于阐明程序中运用明程序中运用的一切的一切标号号,翻翻译时只需将一切只需将一切标号登号登记在在标号表中号表中. 标号表的内容如右号表的内容如右图所示所示: Lab→label c { fill(c,未未,0) } Lab→ Lab,c { fill(c,未未,0) }标号名标号名 定义否定义否 addrc1 未未 0c2 未未 0cn 未未 0 (2) 标号定义及援用标号定义及援用 标号定义是指标号定义是指:确定标号所代表的某个四元式地址确定标号所代表的某个四元式地址. 普通方式为普通方式为: c:S c 这一标号代表了这一标号代表了S的第一条四元式地址的第一条四元式地址. 标号援用普统统过标号援用普统统过 goto c 实现实现. 普通程序设计中普通程序设计中,允许标号的援用及定义交叉进展允许标号的援用及定义交叉进展,如下所示如下所示:goto c;goto c;c: S;goto c;因此因此,当翻译到第一个当翻译到第一个 goto 语句时语句时, 标号标号 c 还未定义还未定义, goto 语句的转移地址语句的转移地址 不确定不确定,只需翻译到标号定义时只需翻译到标号定义时,才干回才干回 过头来回填地址过头来回填地址. 可以利用可以利用标号表地址号表地址栏,当当标号已定号已定义时,地址地址栏就是就是标号号所代表的地址所代表的地址;当当标号未定号未定义时,地址地址栏用于用于衔接一切接一切转移到移到该标号的号的转移四元式移四元式,当翻当翻译到到标号定号定义时,以便回填一切以便回填一切转移到移到该标号的号的转移四元式移四元式.文法及文法及语义动作如下作如下:S→ goto c{ 假假设 c 已定已定义 那么那么 Gen(J, , , entry(c).addr) 否那么否那么 Gen(J, , , entry(c).addr); entry(c).addr:=NXQ-1 } Ldef→c:{ 令令 entry(c).定定义否否:=已定已定义; 用用 NXQ 回填回填 entry(c).addr 链中一切中一切 转移四元式移四元式 } 第七第七节 循循环语句的翻句的翻译 循环语句有三种方式循环语句有三种方式:while B do Srepeat S until Bfor i:=E1 to E2 do S1 while B do S 的翻译的翻译 该语句翻译为如右图所示的该语句翻译为如右图所示的四元式系列四元式系列. 从流程图中可以看出从流程图中可以看出,有两处有两处的四元式地址需特殊处置的四元式地址需特殊处置:B 的四元式的四元式B为真为真?S 的四元式的四元式F** while 语语句的文法及句的文法及语义语义子程序如下子程序如下:S→Wd S{ Gen(J , , , Wd .q ) backpatch(Wd .chain,NXQ) } Wd →W B do{ Wd .q := W.q //传传送送给给Wd. Wd .chain:=NXQ; Gen(Jz,B.place, , xxxx) }W→while{ W.q:=NXQ } //记记住住 B 的第一条四元式地址的第一条四元式地址 2 repeat S until B 的翻的翻译 S→R S until B { Gen(Jz, B.place, ,R.q) }R→repeat { R.q:=NXQ}**S 可以是复合可以是复合语句句S 的四元式的四元式B为真为真?B的四元式的四元式FT 3 for i:=E1 to E2 do S 的翻的翻译S→F2 do S{ Gen( inc, , , F2.place) Gen( J , , , F2.chain) backpatch(F2.chain, NXQ ) }F2→F1 to E2 { F2.chain:=NXQ; F2.place:=F1.place Gen (Jg,F1.place ,E2.place, xxxx)}F1→for i:= E1 { Gen (:= ,E1.place, ,entry(i)) F1.place :=entry(i) } E1的四元式的四元式i > E2? E2的四元式的四元式T i:=E1 S的四元式的四元式 i:=i+1 第八第八节 数数组的翻的翻译 这节讨论三个问题这节讨论三个问题:数组阐明的翻译数组阐明的翻译数组元素的翻译数组元素的翻译含数组元素的赋值语句的翻译含数组元素的赋值语句的翻译1 数组阐明语句的翻译数组阐明语句的翻译 进展数组阐明语句的进展数组阐明语句的 翻译时翻译时,要把数组名填入符号表要把数组名填入符号表,并建立一内情向量表并建立一内情向量表,记录维数记录维数,下标上下界下标上下界,类型等类型等. 简单起见简单起见,只思索如下的数组阐明只思索如下的数组阐明:A:array[L1:U1, L2:U2,....... Ln:Un ] of TYPE 文法如下文法如下:D→i:array[ LIST ] of TLIST→i(1):i(2)| LIST (1) , i(1):i(2) T→integer|real|char|boolean 语义子程序如下子程序如下:LIST→i(1):i(2){建立一个建立一个仅含含 i(1):i(2) 的的队列列LIST.Q }LIST→ LIST (1) , i(1):i(2) {把把 i(1):i(2) 插入插入队列列LIST.Q中中 }D→i:array[ LIST ] of T{ i 填入符号表并填入符号表并标志志为数数组;开辟内情向量表开辟内情向量表, 把把LIST.Q 中的上下界中的上下界对逐一取出逐一取出,计算算 di, 并将并将 i(1),i(2) , di, 放入内情向量表放入内情向量表;计算算维数数 n 及及 c, 将将 T.attr,n,c 填入内情向量表填入内情向量表. } 数数组阐明明语句不句不产生四元式生四元式. L1 u1 d1 L2 u2 d2 Ln un dn a c n type c = { ( L1 )*d2d3d4...dn + ( L2 )* d3d4...dn + ( Ln-1)* dn + ( Ln ) }*elemlength = {(...((L1d2+L2)d3+L3)d4+L4)......) dn + Ln }*elemlength 2 数组元素的翻译数组元素的翻译 设数组元素为设数组元素为: A[ E1,E2,......En], 要获得该元素值要获得该元素值,首先要计算首先要计算出该元素的地址出该元素的地址:addr=conspart+varpartconspart =a -c varpart = {(...((E1d2+E2)d3+E3)d4+E4)......) dn + En } conspart 的的 a c 曾经经过数组阐明语句的翻译登记在内曾经经过数组阐明语句的翻译登记在内情向量表中情向量表中; 而而 varpart 中含有未知数中含有未知数,只能在程序运转时经过如只能在程序运转时经过如下算法实现下算法实现: varpart:=E1;k:=1;while k