第7章 语法制导翻译和中间代码_ppt.txt

大学编译原理实用教程-杨德芳-课件PPT

收藏

资源目录
跳过导航链接。
大学编译原理实用教程-杨德芳-课件PPT.zip
编译原理实用教程-杨德芳-PPT演示文稿
教案资料.ppt---(点击预览)
编译原理实用教程-杨德芳-PPT课件文件
文稿ppt_ppt.txt---(点击预览)
文稿ppt_ppt.jpg---(点击预览)
文稿ppt.ppt---(点击预览)
编译原理实用教程-杨德芳-大学教学资料
(课件资料)《编译原理实用教程》-杨德芳-电子教案
压缩包内文档预览:
预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图 预览图
编号:21836409    类型:共享资源    大小:13.06MB    格式:ZIP    上传时间:2019-09-06 上传人:QQ24****1780 IP属地:浙江
25
积分
关 键 词:
大学 编译 原理 实用教程 杨德芳 课件 ppt
资源描述:
大学编译原理实用教程-杨德芳-课件PPT,大学,编译,原理,实用教程,杨德芳,课件,ppt
内容简介:
第7章 语法制导翻译和中间代码生成学习目标任何编译程序都可以看作是这样的一个翻译程序:它将用某种源语言写的源程序转换为等价的用某种目标语言写的程序(目标程序),其中的目标程序可以是某种中间的语言程序。语法制导翻译的基本思想是很简单的,就是先给文法中的每个产生式添加一个成分,这个成分称为语义动作或翻译子程序。在执行语法分析的同时,执行相应产生式的语义动作。这些语义动作不仅指明了该产生式所生成的符号串的意义,而且根据这种意义规定了对应的加工动作。本章要点:语法制导翻译中间代码的形式各种语句的翻译例题7.1 给出文法及其语义子程序(0)SE print valtop(1)EE(1)+E(2) valtop=valtop+valtop+2 (2) EE(1)*E(2) valtop=valtop*valtop+2(3) E(E(1) valtop=valtop+1(4) Ei valtop=lexval/*LEXVAL为i的整型内部值*/计算算术表达式7+9*5 #的语法值及各结点的值。 7.1概述如同在进行词法分析、语法分析的同时也进行着词法检查、语法检查一样,在语义分析时也必然进行语义检查。语义分析包括动态语义分析和静态语义分析两类。动态语义分析就是进行真正的翻译,即生成程序的一种中间表示形式(中间代码)或需要生成相应的目标代码,它是运行时进行的;静态语义分析是在编译时完成的,它涉及到几个方面:7.1.1 语义分析的概念(1)类型检查,如参与运算的操作数其类型应相容。(2)控制类检查,以保证控制语句有合法的转向点。如C语言中不允许goto语句转入case语句流。Break语句需要寻找包含它的最小的switch、while或for语句方可找到转向点,否则出错。(3)一致性检查,如在相同作用域中标识符只能说明一次,case语句的标识不能相同等。7.1.2 语法制导翻译语法制导翻译的方法就是为每个产生式配上一个翻译子程序(称为语义动作或语义子程序),并在语法分析的同时执行这些子程序。语义动作是为产生式赋予具体意义的手段,它一方面指出了一个产生式所产生的符号串的意义;另一方面又按照这种意义规定了生成某种中间代码应做哪些基本动作。在语法分析过程中,当一个产生式获得匹配或用于归约时,此产生式相应的语义子程序就进入工作,完成即定的翻译任务。语法制导翻译分为自底向上语法制导翻译和自顶向下的语法制导翻译。 7.2 属性文法属性是指与文法符号的类型和值等有关的信息。在编译中用属性描述处理对象的特征。随着编译的进展,对语法分析产生的语法树进行语义分析,且分析的结果用中间代码描述出来。对于一棵等待翻译的语法树,它的各个结点都是文法中的一个符号X,该X可以是终结符或非终结符。根据语义处理的需要,在用产生式AX进行归约或推导时,应能够准确而恰当地表达文法符号X在归约或推导时的不同的特征。例如,判断X的类型是否匹配,要用X的数据类型来描述;因此,在语义分析阶段引入X的属性,如X.type、X.place、X.val等分别描述变量X的类型、存储位置及值的不同特征。文法符号的属性可以分为继承属性与综合属性两大类。继承属性用于“自上而下”传递信息。继承属性由相应语法树中的结点的父结点属性计算得到,即沿语法树向下传递,由根结点到分枝结点,它反映了对上下文依赖的特性。继承属性可以很方便地用来表示程序语言上下文的结构关系。综合属性用于“自下而上”传递信息。综合属性由相应语法分析树中结点的分支结点属性计算得到,其传递方向与继承属性相反,即沿语法分析树向上传递,从分枝结点到根结点。7.2.2 属性文法属性文法是一种适应于定义语义的特殊文法,即在语言的文法中增加了属性的文法。它将文法符号的语义以“属性”的形式附加到各个文法的符号上。再根据产生式所包含的含义,给出每个文法符号属性的求值规则,从而形成一种带有语义属性的上下问无关文法,即属性文法。属性文法也是一种翻译文法,属性有助于更详细地指定文法的代码动作。例题7.2(1)SE print(E.val)(2) EE(1)+ T E.val= E(1).val+T.val(3) ET E.val= T.val(4) TT(1)* FT.val= T(1).val*F.val(5) TT(1)T.val= T(1).val(6) F(E)F.val= E.val(7) FiF.val= i.lexval例题7.3 描述说明语句中各种变量的类型信息的语义规则。(1)DTLL.in=T.type (2) TintT.type=int(3) TrealT.type=float(4) LL(1),idL1.in= L.inaddtype(id.entry,L.in)(5) Lidadtype(id.entry,L.in)该文法的功能是描述说明语句,说明语句的定义形式为:int id1,id2,idn或者为float id1,id2,idn由关键字int或float开头,后跟一标识符表,每个标识符间由逗号隔开。非终结符T有一综合属性type ,它的值由关键字决定(int或float)。与产生式DTL相联的语义规则为L.in=T.type,将L.in的属性值置为该说明语句指定的类型。显然,属性L.in是继承属性,它将被沿着语法树传递到下边的结点使用,与L产生式相连的规则使用了它,语法树的传递关系如图7-3所示:7.3 几种常见的中间代码形式所谓中间代码形式是指用来描述源程序并与之等效的一种编码方式,可根据具体情况将它设计成各种形式如汇编语言可以看作一种中间代码形式。一般来说,对于一个多遍扫描的编译程序,越到后面的阶段,所产生的中间代码越接近于机器代码。于是编译程序首先将源程序翻译成中间代码的形式,然后,再把中间代码翻译成目标代码,也就是把语义分析和代码生成分开处理。比如常用的中间代码有逆波兰式表示、四元式和树形表示等。下面介绍几种中间代码的形式。7.3 .1逆波兰式表示方法逆波兰式表示法是中间代码最简单的一种的表示形式,早在编译程序出现之前,它就用于表示算术表达式。在这种表示法中,运算符是直接跟在运算量的后面,因此,逆波兰表示法有时也称为后缀表示法。下面是逆波兰式表示方法的例子。A*B 表示为:AB*A*B +C 表示为:AB*C+A*(B +C/D) 表示为ABCD/+*A*B+C*D 表示为AB*CD*+7.3 .2逆波兰式表示方法的推广(1)考虑赋值语句,其一般的形式为:=如果把“:=”看作一个进行赋值运算的双目运算符,那么赋值运算的逆波兰表示式为:=例如A:=B*C+D可以写成:ABC*D+:=(2)用逆波兰式表示转向语句goto L变为:L jump(3)条件语句IF E S1 ELSE S2 写成为: ES1S2¥(4)数组元素A,表示成逆波兰式为, A subs例题7.4 begin integer k;k:=100;h:if ki+j then begin k:=k-1; goto h end else k:=i*2-j*2; i:=j:=0end该段程序的逆波兰式表示方法为:(1)block(2)k 100:=(5)h:(7)k i j +(23) jumpf(14)k k 1-:=h jump(32)jump(23)k i 2 * j 2 * -:=(32)i j 0 :=:=(37)blockend 其中1)block和blockend是两个无运算量的运算符,分别表示程序的开始运算和结束运算。2)左端圆括号内的数字,是其近旁那个符号相对该程序段的内部形式的开始位置的序号,例如,先设block的序号为1,则k的序号是2,数字100的序号是3,依次类推。3)源程序中的类型说明“integer k”经词法分析后已经不再存在了。例题7.5BCD*+的计算过程:(1)B进栈。(2)对栈顶元素进行一目减的运算,并将结果代替栈顶,即-B置于栈顶。(3)C进栈。(4)D进栈。(5)栈顶两个元素相乘,两元素退栈,相乘的结果置于栈顶。(6栈顶两个元素相加,两个元素退栈,相加结果进栈,现在栈顶存放的是整个表达式的值。7.3 .3四元式四元式是一种比较普遍的中间代码的形式,四元式的一般形式是:例如a=b*c+b*d 的四元式表示为:(1) (*,b,c,t1)(2)(*,b,d,t2)(3) (+,t1,t2,t3) (4)(:=,t3,a)例如,GOTO L写成四元式的格式为(jump,L)。if B rop C GOTO L写成四元式的格式为(jrop,B,C,L)。例题7.6 将下列程序begin integer k;k:=100;h: if ki+j then begin k:=k-1;goto hend else k:=i*2-j*2;i:=j:=0end表示成四元式为:(1)block(2):= 100 k(3)+ijT1(4)kT1T2(5) jumpf9T2(6)k1k(7)jump(4)(8)jump12(9)*i 2T3(10)* j 2 T4(11)T3 T4 k(12):=0j(13):=0i(14)blockend7.3 .4三元式和树型表示另一类中间代码的形式是三元式,即把表达式及各种语句表示成一组三元式。每个三元式有三个组成部分:(运算符,第一个运算对象,第二个运算对象)例如 a=b*c+b*d 的三元式表示为:(1)(*b,c)(2)(*b,d)(3)(+(1),(2)(4)(=(3),a) 与四元式不同的是,三元式对中间计算结果的显式引用是用表达式的编号而不是中间变量,树形表示是三元式表示的翻版。 7.4 表达式及赋值语句的翻译简单表达式的文法如下:Ai=EEE+E|E*E|-E|(E)|i非终结符A代表“赋值语句”,语义子程序所涉及到语义变量、语义过程及函数说明如下:(1)对非终结符的E定义语义变量E.place,即E.place表示存放值的变量名在符号表中的入口地址或临时变量名的整数码。()定义语义函数newtemp( ),即每次调用newtemp()时都要回送一个代表新临时变量的整数码。临时变量按产生的次序为,。()定义语义过程emit(op,arg1,arg2,result),其中的emit是产生一个四元式并填入四元式的表中。arg1、arg2是操作数,result 是运算结果。(4)定义语义函数lookup( ),其功能是审查是否出现在符号表中,是则返回在符号表中的入口指针,否则返回空。使用上述的语义变量、过程和函数,可以写出文法每个产生式的语义子程序。(1)Ai=E p=lookup() if(p=NULL) error();else emit(=,E. place,_,P);(2)EE(1)+E(2) E. place=newtemp( );Emit(+,E(1).place, E(2).place, E. place)(3) EE(1)*E(2) E. place=newtemp( );emit(+,E(1).place, E(2).place, E. place)(4) E-E(1) E. place=newtemp( );emit(uminus,E(1).place, , E. place)(5) E(E(1) E. place= E(1). place(6) E i p=lookup()if (p!=NULL) E.place=p;else error();在上面的语义分析过程中,没有考虑到静态语义检查。在实际应用中,要全面考虑语句的翻译。例如:EE(1)*E(2) 该语句的语义子程序的翻译可以写成:EE(1)*E(2) E. place=newtemp( );if E(1).type=int AND E(2).type=int then begin emit(E.place,= , E(1).place, *i, E(2).place);E.type=intendelse if E(1).type=real AND E(2).type=real thenbeginemit(E.place, =, E(1).place, *r, E(2).place);E.type=realend else if E(1).type=int /*and E(2).type=real*/ thenbegin t=newtemp;emit(t, =, itr, E(1).place);emit(E.place, =, t, *r, E(2).place);E.type=realendelse /* E(1).type=real AND E(2).type=int*/begin t=newtemp; emit(t,=, itr, , E(2).place); emit(E.place, =, E(1).place , *r,t); E.type=real end;例题7.7试分析赋值语句X=-B*(C+D)的语法制导翻译解答:赋值语句X=-B*(C+D)#的语法制导翻译过程如表7-2所示。7.4.2布尔表达式的翻译布尔表达式的文法为:EEE| EE|E|(E)|i|i rop i其中的rop为,=,运算符。1布尔表达式值的计算计算布尔表达式的值通常有两种方法。第一种方法和算术表达式的计算方法一样,根据顺序和优先级一步步计算出来。例如:1(00)0=1(10)0=100=10=1另一种方法就是根据布尔表达式的特点实施某种优化。即不必一步一步地计算布尔表达式中所有运算对象的值,而是省略不影响结果的运算。例如:在计算AB时,若计算出A的值为1,则B的值就无须再计算;在计算AB时,若A的值为0,则B的值无须要再计算,因为AB的值一定为0 2布尔表达式的翻译方法给出布尔表达式if ab cf then 1 else 0,根据布尔表达式的第一种计算方法,写出该表达式的四元式为:(1) if ab goto (4)(2) t=0(3) goto (5)(4)t=1(5) 翻译方法如下:E(1) E(2):E(1)为TRUE,则整个表达式为TRUE ,转向条件为“真”的出口。E(1)为FALSE,则转向E(2)的判断,若E(2)为TRUE,则整个表达式为TRUE,转向条件为“真”的出口,用E.true指针代表真的出口;若E(1)为FALSE,则转向E(2)的判断,若E(2)为TRUE,则整个表达式为FALSE,则转向条件为“假”的出口,用E.false代表假的出口。E(1) E(2): E(1)为FALSE,则整个表达式为FALSE ,转向条件为“真”的出口。E(1)为TRUE,则转向E(2)的判断,若E(2)为TRUE,则整个表达式为TRUE,转向条件为“真”的出口;若E(1)为TRUE,则转向E(2)的判断。若E(2)为FALSE,则整个表达式为FALSE,转向条件为“假”的出口。根据上述的思想将布尔表达式翻译成四元式的描述,其中nexstat 给出输出序列中下一个四元式序号,emit 过程每被调用一次,nextstat增加1。E E(1) E(2) E.place=newtemp;emit(E.place = E(1).place E(2). place)E E(1) E(2) E.place=newtemp;emit(E.place = E(1). Place E(2). place)E E(1) E.place=newtemp; emit(E.place = E(1). place)E(E(1) E.place= E(1).placeEid1 rop id2 E.place=newtemp; emit(if id1. place rop id2.pPlace goto nextstat+3 )emit(E. Place = 0)emit( goto nextstat+2)emit(E.place = 1)Etrue E.place=newtemp;emit(E.place = 1)Etrue E.place=newtemp;emit(E.place = 0)7.4.3在控制语句中布尔表达式的翻译(4) E(E(1) E.true= E(1). true; E.false= E(1).false E.codebegin= E(1). codebegin (5) E id1 rop id2 E.true= nextstat; E.codebegin= nextstat; E.false= nextstat+1; emit(if id1.place rop id2.place goto ); emit( goto );(6) Etrue E.true= nextstat; E.codebegin= nextstat;emit( goto )(7) Efalse E.false= nextstat;E.codebegin= nextstat;emit( goto )例题7.8给出布尔表达式if ab cf then S1 else S2,它翻译成四元式序列为:(1)if ab goto E.true(2) goto E.false(3) if cd goto (5)(4)goto E.false/(5)if ef goto E.true(6) goto E.false(7)S1的四元式。(p) goto (q)(p+1)关于S2的的四元式(q)E.true为S1语句目标代码的首地址,E.false为S2语句目标代码的首地址。E为ab cf通过上面的例子可以看出,(7)是该条件语句的真出口,(p+1)是该条件语句的假出口。而E.true和E.false必须是在翻译到S1 或S2时才能确定它的语句编号是什么,所以需要回填。并且需要回填的语句很多,如四元式(1)和(5)需要回填E.true的值,(2)、(4)、和(6)需要回填E.false的值。这些要回填的四元式标号需要记住。因此就采用“拉链”的技术,如果不能记住,则无法回填了。把需要回填E.true的值作为真链,把需要回填E.false的值作为“假“链。拉链的技术如下:(100)goto E.true(200) goto E.true(300) goto E.true则链成:(100)goto (0)(200) goto(100)(300) goto (200)把地址300作为链首,地址(100)为链尾,0为链尾标志。根据上面的翻译思想,我们给出将布尔表达式翻译成四元式的描述,其中(1)nextstat为给出序列中的下一个四元式的序号。emit过程每调用一次,nextstat的值就增加1。(2)merge(p1,p2):把以p1和p2为链首的两条链合并为一条以p2为链首的链。(3)backpatch(p,t):把链首p所链接的每个四元式的第四区段(即result)都改写为地址t。(4)语义值E.codebegin与非终结符E相连,表示表达式E的第一个四元式语句的序号。merge( )函数如下:merge(p1,p2)if(p2= =0) return(p1);elsep= p2;while(四元式p的第四区段内容不为0)p=四元式p的第四区段内容;把p1填进四元式p的第四区段;return(p2);backpatch(p,t)Q=p;while(Q!=0)q=四元式Q的第四区段内容;把t填进四元式Q的第四区段;Q=p;(1)EE(1) V E(2) backpatch(E(1).false, E(2).codebegin);E.codebegin= E(1). codebeginE.true= merge(E(1).true, E(2).true )E.false= E(2).false (2) EE(1)E(2) backpatch(E(1).true, E(2).codebegin);E.codebegin= E(1). codebeginE.true= E(2). trueE.false= merge(E(1).false, E(2).false ) (3) EE(1) E.true= E(1). False;E.codebegin= E(1). CodebeginE.false= E(1).true根据上述语义的动作,编译程序在进行语义分析的时候,编译程序在进行语义分析的时候,条件表达式的四元式全部都产生以后,作为整个表达式的真、假出口还是不能填上,这些真假出口需要用E.true 和E.false作为链首记住。例题7.9给出布尔表达式ab cf,假设开始的语句为100根据上面的的语义分析写出分析过程如表7-3所示。100(if ,a,b,)101(goto 102)102(if ,c,d,104)103(goto )104(if ,e,f,100)105(goto 103)“真”的链首为104,“假”的链首为105。7.5 控制语句的翻译在源程序中,控制语句用于实现程序流程的控制。一般程序的流程控制有三种基本结构:(1)顺序结构,一般用于复合语句的实现。(2)选择结构,用if和case等语句来实现。(3)循环结构,用for 、while 、do等语句来实现。下面就各种语句的翻译方案进行讲述。7.5.1控制语句的翻译设条件语句的文法为:(1)Sif E then S (2)|if E then S else S (3)|while E do S (4)| begin L end (5)| A (6) LL; S (7)|S其中非终结符的含义为:S语句L语句串A赋值语句E布尔表达式1.条件语句的if代码结构2条件语句if 的文法和语义子程序的设计条件语句if 的文法如下:(1)Sif E then S (2)|if E then S else S为了能够及时的回填四元式和便于翻译,将文法进行修改,成为如下的形式:(1)SCS(1) (2) Cif( E) (3) STPS(2) (4) TP CS(1);else假设给定语句if E then S(1) else S(2)设计出来的语法制导翻译为:(1)SCS(1) S.chain=merge(C.chain, S(1).chain)(2)Cif( E)backpatch(E.true,nextstat); C.chain=E.false; (3) STPS(2) S.chain=merge(TP.chain, S(2).chain)(4) TP C S(1);elseq=nextstat;emit(j,_,_,0)backpatch(C.chain,nextstat);TP.chain=merge(S.chain,q)条件循环语句while的文法如下:(1)SWdS(1)(2)WdW(E)(3)Wwhile假设给出while (E) do 根据while语句的扫描加工顺序,首先用产生式(3)Wwhile进行归约,这时,nextstat即为E的第一个四元式地址,我们将其保留在w.codebegin中,然后继续扫描并用(2) WdW(E)归约,即扫描完“)”后可以用backpatch(E.true,nextstat)回填E.true;而E.false则要等到S(1)语句序列全部产生后才能回填,因此E.false作为待填信息用Wd.chain=E.false传下去。文法的语义加工子程序为:(1)SWdS(1)backpatch(S(1).chain, Wd.chain);Emit(j,_,_, Wd.chain);S.chain= Wd.chain); (2) WdW(E)backpatch(E.true,nextstat);Wd.chain=E.falseWd.codebegin=W.codebegin;(3)WwhileW.codebegin=nextstat5 三种基本控制结构的翻译前面我们讲述了三种控制语句的文法为:(1)Sif E then S (2)|if E then S else S (3)|while E do S (4)| begin L end (5)| A (6) LL; S (7)|S(1)SCS1(2) STPS2(3)SWdS3(4)SL (5) SA(6) LLSS1 (7)|S2 (8) Cif( E) (9) TP C S;else(10) WdW(E)(11)Wwhile (12) LSL;(1)SCSS.chain=merge(C.chain,S(1).chain) (2) STPSS.chain=merge(TP.chain, S(2).chain)(3)SWdSbackpatch(S(1).chain, Wd.chain);emit(j,_,_, Wd.chain);S.chain= Wd.chain);(4)SL S.chain=L.chain (5) SAS.chain=0 (6) LLSSL.chain=S(1).chain (7)|S L.chain=S.chain (8) Cif( E)backpatch(E.true,nextstat); C.chain=(E.false; (9) TP C S;else q=nextstat;emit(j,_,_,0)backpatch(C.chain,nextstat);TP.chain=merge(S.chain,q) (10) WdW(E) backpatch(E.true,nextstat);Wd.chain=E.falseWd.codebegin=W.codebegin;(11)WwhileW.codebegin=nextstat(12) LSL;backpatch(L.chain,nextstat):6翻译示例例题7.10将下面的语句翻译成四元式:While(AB)If(CD) X=Y+Z按照文法及加工的子程序得到该语句对应的四元式如下:100: (j,A,B,102)101: (j,_,_,107)102: (j,C,D,104)103: (j,_,_,106)104: (+,Y,Z,T)105: (=,T,_,X)106: (j,_,_,100)1077.5.2多分支控制语句case的翻译多分支控制语句case的语法结构:Switch(E) case c1:S1;case c1:S1;case ci:Si;Case cn:SnDefault:Sn+1设E的计算值放在临时单元T中。goto testP1:S1的中间代码;goto next;P2:S2的中间代码;goto next;Pn:Sn的中间代码;goto next;default:Sn+1的中间代码goto next;test:if(T=c1) goto P1if(T=c2) goto P2if(T=cn) goto Pnif(T=default) goto Pn+1next:为了便于语法制导翻译,给出switch语句的文法和相应的语义加工子程序如下:(1)Aswitch(E)T.place=E.place;F1.chain=nextstat;emit(j,_,_,0); /*转向test*/(2) BAcase cP=1;queueP.label=c; queueP.chain=nextstat;(3) DB:S生成S的四元式序列;Backpatch(S.chain,nextstat);B.chain=nextstat;emit (j,_,_,0); /*转向next*/(4) DF:S生成S的四元式序列;Backpatch(S.chain,nextstat);B.chain=nextstat;emit (j,_,_,0);F.chain=merge(B.chain, F.chain) /*转向next的语句拉成链*/(5) FD;case cP=P+1;queueP.label=c;queueP.chain=nextstat;(6) SD;default:S生成S的四元式序列;Backpatch(S.chain,nextstat);B.chain=nextstat;emit (j,_,_,0);F.chain=merge(B.chain, F.chain) /*转向next的语句拉成链*/P=P+1;queueP.label=default;queueP.chain=nextstat;F3.chain=nextstat;m=1;doci= queuem.label;Pi= queuem.chain;m=m+1if(ci!=default) emit(case , ci, Pi,_)else emit(case,T.place,default,_)while(m=P+1);Backpatch(F1.chain,F3.chain);Backpatch(F.chain,nextstat);/*填写所有的转向 next的转移地址*/7.5.3 for循环语句除了whiledo语句外,很多程序设计语言有如下结构的循环语句:for i:=E1 STEP E2 until E3 do S1该程序的执行相当于:i:= E1goto OVER;AGAIN:i=i+ E2OVER:if i E3 thenbeginS1;goto againend;为了便于产生四元式,必须修改文法,因而产生了如下的产生式:F1for i:=E1F2F1 step E2F3F2 until E3SF3 do S1(1)F1for i:=E1emit (entry(i),:= , E1.place); F1.place:=entry(i);/*保存控制变量在符号表中的位置*/F1.chain:=nextstat;emit (goto ,_);/*goto OVER*/F1.codebegin:=nextstat;(2)F2F1 step E2F2.codebegin:= F1.codebegin /*保存AGAIN的地址*/F2.place:= F1.placeemit (F1.place,:= ,E2.place, + F1.place);backpatch(F2.chain,nextstat);(3)F3F2 until E3 F3.codebegin:= F2.codebegin;q:=nextstat;emit(if ,F2.place, E3.place GOTO q+2)/*若i E3转去执行循环体的第一个四元式*/F3.chain:=nextstat;emit (goto ,_);/*转离循环体*/(4)SF3 do S1/*这里是语句S1的相应的代码*/ emit(GOTO F3.codebegin) /*gotoAGAIN*/Backpatch(S1.chain, F3.codebegin);S.chain:= F3.chain/*转离循环的转移目标留待处理外层S时再回添*/例如,循环语句For I:=1 step 1 until N M:=M+I将被翻译成四元式序列:100: I:=1101:GOTO 103102:I:=I+1103:if IN GOTO 105104:GOTO 108105:T:=M+I106:M:=T107:GOTO 1021087.6 数组元素的翻译程序设计语言中,数组是用来存储一批同类型数据的数据结构,数组中的每个元素具有同样长度的存储空间。如果在编译时就知道一个数组存储空间的大小,则称其为静态数组.否则为动态数组。7.6.1 数组元素的地址计算及中间代码的生成数组的一般定义格式为:Al1:u1,l2:u2,ln:un其中,A是数组名,lk是数组A第k维的下界,uk是第k维的上界。为了简单起见,假定数组A中的每个元素的存储长度为l,a是数组A的首地址,则数组元素Ai1,i2,in的地址D的计算公式为:D=a+(i1-l1)d2d3dn+(i2-l2)d3d4dn+( in-1-ln-1) dn+( in-ln) 其中,di=ui-li+1(i=1,2,n-1)。整理后得到D=CONSPART+VARPART其中,CONSPART=a-(l1d2+l2) d3+l3) d4+l n-1) dn+inCONSPART中的各项在处理说明语句时就可以得到 访问数组元素Ai1,i2,i3,in可以设想为:把它的VARPART计算在某一变址寄存器的T中,将CONSPART作为“基本地址”,然后以变址的方式访问内存单元为:CONSPARTT假定所考虑的数组是静态的,因此,CONSPART=a-C中的C在处理数组说明时能够计算出来。实现数组元素的地址计算时,将产生两组四元式序列:一组计算CONSPART,其值存放在临时变量T中;另一组计算VARPART,其值存放在临时变量T1中,即用T1T表示数组元素的地址。这样,对数组元素的引用和赋值就有如下两种不同的四元式:(1)变址存数:若有T1T=X,则可以用四元式( =,X,T1T)(2)变址取数:若有X=T1T,则可以四元式(= ,T1T,X)表示。7.6.2 赋值语句中数组元素的翻译为了便于语法制导翻译,定义一个含有数组元素的赋值语句文法如下所示:(1)AV=E(2)Vielist|i(3)elistelist,E|E(4)EE+E|(E)|V为了便于翻译,将文法改为:(1)AV=Eif (V.offset=NULL) emit(=,E.place,_,V.place);/*V是简单变量*/Else emit( =,E.place,_,V.placeV.offset);/*V是下标变量*/(2)EE(1)+E(2)T=newtemp;emit(+,E(1).place, E(2).place,T)Eplace=T;(3)E(E) Eplace= E(1).place(4)E Vif(V.offset=NULL)Eplace= V.placeElseT=newtemp;Emit(=,V.placeV.offset,T);E.place=T;(5)V elistT= newtemp;Emit(_,elist.ARRAY,C,T);V.place=T;V.offset=elist.place;(6)V iV.place=entry(i);V.offset=null;(7)elistelist,ET=newtemp;k=elist.DIM+1dk=limit(elist(1).ARRAY,k);emit(*,elist(1).place,dk,T);emit(+,E.place,T,T);elist.ARRAY= elist(1).ARRAY;elist.place=T;elist.DIM=k;(8)elist iEelist.place= E.place;elist.DIM=1;elist.ARRAY=entry(i);7.6.3 数组元素翻译示例例题7.11已 知A是一个1020列的数组。且按行存放,求:(1)赋值语句X=AI,J的四元式序列;(2)赋值语句AI+2,J+1=M+N的四元式序列,给出语法制导翻译。【解】由于A是1020的数组,故d1=10,d2=20,C=d2+1.根据文法的语句加工子程序,赋值语句X=AI,J的语法制导翻译过程如表76所示:最后得到的赋制值语句的四元式序列为:100(*,I,20,T1)101 (+,J,T1,T1) 102(-,A,21,T2) 103(=,T2T1,-,T3)104(=,T3,_,X)(2)根据文法及对应的语义分析加工子程序,赋值语句AI+2,J+1=M+N的四元式序列为:100(*,I,20,T1)101 (+, J, 1, T2) 102(*,T1,20, T3) 103(+,T2 , T3, T3)104(,A,21,T4)105(+,M,N,T5)106(=,T5,T4T3)7.7高级语言中其他语句的翻译在高级语言中,我们都学过结构体类型,如C语言中的结构体类型的定义如下:struct dataint day;char month_name4;int year;描述该结构体类型的文法如下:struct f1;|int |char|pointerf1 f1 ;f |ff i| in下面是处理结构体类型说明的基本语义动作;f i:=;f.len:=type.len;FILN(,f.len)f in:=;f.len:=type.len*n.val;FILN(,f.len)f1 fFILO(, 0);/*第一个分量的相对数为0*/f1.len:= f.lenf1 f1 ;fFILO(, f1.len);f1.len:= f1.len+f.lenstruct f1;type.len f1.len chartype.len:=1 integertype.len:=4 pointertype.len:=47.7.2说明语句的翻译 程序设计语言中的说明语句就是定义各种类型的有名的实体,包括常量、变量、数组、记录、过程、子程序等,说明语句的种类也很多,如对象说明、变量说明、过程说明等。编译程序把说明语句中定义的名字和性质登记在符号表中,用以检查名字的引用和说明是否一致。下面简单介绍一下说明语句的翻译。程序设计语言中的说明语句的语法描述为:Dinteger|real,id|id对这种说明语句的翻译就是在符号表中登录该名字的性质。下面的语义翻译就是给每一个D一个语义变量D.att,用来记录说明语句所引入的名字的性质(是int还是real)。使用过程enter(id,A)把名字id和性质A登录在名字表中。(1)D integer identer(id,int);D.att:=int(2) Dreal identer(id,real);D.att:=real(3) D D 1 , identer(id, D 1 , att);D.att:= D 1 , att 7.7.3转向语句的翻译多数程序设计语言的转移是通过标号和goto语句实现的。带标号语句的形式是L:S;goto语句的形式是goto L。标号语句L:S被语句处理后,标号L是“定义”了,在标识符表中,将登录L项的“地址”栏中登上语句S的第一个四元式的地址。如果goto L是一个向上转移的语句,那么编译程序碰上这个语句,则L是定义过的了。通过对L查找符号表获得它的定义地址P,编译程序可立即产生出相应于这个goto L的四元式(j,,P)。如果goto L是一个向下转移语句,也就是说,标号L尚未定义,那么,若L是第1次出现,则把它填进符号表中并标记“未定义”。由于L尚未定义,对goto L只能产生一个不完全的四元式(goto ),它的转移目标须等L定义时再回填。在这种情况下,必须把那些以L为转移目标的
温馨提示:
1: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
提示  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:大学编译原理实用教程-杨德芳-课件PPT
链接地址:https://www.renrendoc.com/p-21836409.html

官方联系方式

2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服 - 联系我们

网站客服QQ:2881952447     

copyright@ 2020-2025  renrendoc.com 人人文库版权所有   联系电话:400-852-1180

备案号:蜀ICP备2022000484号-2       经营许可证: 川B2-20220663       公网安备川公网安备: 51019002004831号

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知人人文库网,我们立即给予删除!