教学课件第八章语法制导翻译和中间代码生成

资源描述

《教学课件第八章语法制导翻译和中间代码生成》由会员分享，可在线阅读，更多相关《教学课件第八章语法制导翻译和中间代码生成（126页珍藏版）》请在金锄头文库上搜索。

1、第八章语法制导翻译和中间代码生成8.1概述8.2属性文法和语法制导翻译8.3语义分析8.4中间代码8.5一些语句的翻译概述语义处理程序设计语言的语义静态语义是对程序约束的描述，这些约束无法通过抽象语法规则来妥善地描述，实质上就是语法规则的良形式条件，它可以分为类型规则和作用域/可见性规则两大类类型相容性变量先声明后引用名称相关要求动态语义程序单位描述的计算编译程序的语义处理工作静态语义审查解释执行动态语义（计算）生成代码.语语法法分分析析后后的的源源程程序序语义处理语义处理概述语义形式化语义建模文法模型-属性文法命令式或操作式模型-操作语义学应用式模型-指称语义学公理式模型-

2、公理语义学属性文法属性文法表达式文法ET+T|TorTTn|b ET1 + T2 T1.type = int T2.type= T1.type E.type :=int E T1 or T2 T1.type = bool T2.type= T1.type E.type :=bool T n T.type := int T b T.type := bool 操作语义描述一段程序的含义是通过执行该段程序所改变的计算机（虚拟计算机）状态来反映。这个计算机的状态与程序执行时的状态相对应：包括变量的所有值，可执行程序本身，各种系统定义的内部数据结构。计算机里所有的寄存器的值和存储单元的值作为计算机的状态

3、，用一组形式定义的操作来说明执行一条指令相应的状态怎样变化。For(expr1;expr2;expr3)expr1;.Loop:ifexpr2=0goto outexpr3;gotoloopout:.公理语义一个语言的每个语法成分的含义定义为公理和演绎规则，用于推导出该成分执行的效果。公理语义概念是随着程序正确性的证明而发展的。当正确性证明能构造时表明程序执行它的规格说明所描述的计算。在一个证明中，每一个语句之前之后都有一个逻辑表达式对程序的变量进行约束,以此说明这个语句的含义。一般的记号PSQ如果在语句S执行前P为真，则在语句S执行并终止后Q为真。演绎规则的例子规则前驱后继赋值：x:=exp

4、rP(expr)x:=exprP(x)While:PBSPPwhileBdoSendP(notB)if-then-elseBPS1Q,(notB)PS2QPifBthenS1elseS2Q指称语义指称语义的基本概念是给每一段程序实体定义一个数学意义上的对象，和一个从实体实例向数学意义对象的映射的函数特点：特点：不但对全部程序赋予全文而且对程序设计语法每一个语法成分短语（表达式，命令，声明）都给予含义。每一个语法成分（短语）的含义是以它的自成分的含义的术语来定义的。即语义结构平行于语法结构。语义函数：语义函数：程序设计语言的语义利用映射函数来证明。语义函数将短语映射到它的指称。例：例：二进制数语

5、言110或10101语法实体指称（自然数）6或21语义实体二进制数文法Numeral:=0:=1:=Numeral0:=Numeral1自然数Natrual=0,1,2,3,语义函数Valuation:NumeralNaturalValuation101表示把Valuation施用于101ValuationN-把它施用于N定义定义:Valuation（用四个方程)因为有四个形式numeralValuation00Valuation11ValuationN02ValuationNValuationN12ValuationN+1所以：所以：Valuation110=2Valuation11=2(2

6、Valuation1+1)=2(21+1)=6属性文法和语法制导翻译虽然形式语义学(如指称语义学、公理语义学、操作语义学等)的研究已取得了许多重大的进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译方法属性文法属性文法(attributegrammar)是一个三元组:A=(G,V,F),其中G:是一个上下文无关文法V:有穷的属性集,每个属性与文法的一个终结符或非终结符相连,这些属性代表与文法符号相关信息，如它的类型、值、代码序列、符号表内容等等.属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。F:关于属性的属性断言或一组属性的计算规则

7、(称为语义规则).断言或语义规则与一个产生式相联,只引用该产生式左端或右端的终结符或非终结符相联的属性.属性有两种属性有两种继承的和综合的属性属性通常分为两类：综合属性和继承属性。简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由生计算器的参数提供。AX1X2XnA的综合属性,计算S(A):=f(I(X1),I(Xn)Xj的继承属性,计算T(Xj):=f(I(A),.I(Xn)1)非终结符既可有综合属性也可有继承属性，但文法开始符号

8、没有继承属性.2)终结符只有综合属性.在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1,c2ck)这里，f是一个函数，而且或者（1）b是A的一个综合属性并且c1,c2ck是产生式右边文法符号的属性;或者（2）b是产生式右边某个文法符号的一个继承属性并且c1,c2ck是A或产生式右边任何文法符号的属性。在两种情况下，我们都说属性b依赖于属性c1,c2ck。一个属性文法的例子例8.1非终结符E、T及F都有一个综合属性val,符号digit有一个综合属性，它的值由词法分析器提供。与产生式LEn对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，

9、我们可认为这条规则定义了L的一个虚属性。某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现语义规则LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.valF.valT.val:=F.valF.val:=E.valF.val:=digit.lexval产生式设表达式为35+4，则语义动作打印数值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5dig

10、it.lexval=3+*3*5+4的带注释的分析树的带注释的分析树继承属性一个结点的继承属性值是由此结点的父结点和/或兄弟结点的某些属性来决定的。例8.2继承属性继承属性L.in生产式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)DL.in=realL.in=realL.in=realT.type=realrealid2id1id3.Real id1,id2,id3，例8.3P DSD var V; D

11、| S V := E; S | V x | y | z现在使用两个属性，现在使用两个属性，name和和dl，每当一个新的变量声明时，就把它的，每当一个新的变量声明时，就把它的name属性附给它，属性附给它，name属性是综合属性。属性是综合属性。将所声明的变量都放到一个变量名字清单中（用语义函数将所声明的变量都放到一个变量名字清单中（用语义函数addlist实现），用实现），用属性属性dl综合声明块中声明的所有变量。然后这个综合声明块中声明的所有变量。然后这个dl属性又作为继承属性传属性又作为继承属性传到后面的语句部分，每个语句用到的变量都要进行审查，看它是否在变到后面的语句部分，每个语句用到

13、符号串对是源程序和目标程序。各个编译阶段定义一个翻译，词法分析：（字符串，单词串）语法分析：（单词串，语法树）代码生成（语法树，汇编语言）设是输入字母表且是输出字母表。定义由语言L1*到语言L2*的一个翻译是由*到*的一个关系T,使得T的定义域为L1且T的值域为L2。使(x,y)T的句子y叫做x的一个输出.语法制导的翻译直观地说，一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。例8.4：下列翻译模式，它定义翻译，即对每个输入x，其输出y是x的逆转。定义此翻译的规则是产生式产生式翻译规则翻译规则(1)s0s(2)s1s(3)s (1)s=s0(2)s=s1(3)s=输入输出对

14、可由(,)表示，其中是输入句子形式而是输出句子形式。(S,S)开始用产生式s0s来扩展得到(0S,S0).再用一次规则(1)，得到(00S,S00)。再用规则(2)，就得到(001S,S100).然后应用规则(3)并得到(001,100)。例8.5：把下述产生式定义的算术表达式映射到后缀波兰表示：EE+TETTTFTFF(E)FaE=ET+E=TT=TFT=FF=EF=a产生式翻译规则翻译规则确定输入a+aa的输出：(E,E)(E+T,ET+)(T+T,TT+)(F+T,FT+)(a+T,aT+)(a+TF,aFF+)(a+FF,aFF+)(a+aF,aaF+)(a+aa,aaa+)定义：定义

15、：一个语法制导的翻译模式是一个五元组一个语法制导的翻译模式是一个五元组T=(N, , ， R,S),其中其中 (1) N是非终结符的有限集。是非终结符的有限集。 (2) 是有限的输入字母表。是有限的输入字母表。 (3) 是有限的输出字母表。是有限的输出字母表。 (4) R是形如是形如A, 的规则的有限集的规则的有限集,其中其中 (N )*, (N )*且且中那组非终结符是中那组非终结符是中中那那组非终结符的置换。组非终结符的置换。 (5) S是是N中一个特别的非终结符，即开始符。中一个特别的非终结符，即开始符。定义：定义：若若T= (N, , , R,S)是是SDTS, (T)则称为语

16、法制导的则称为语法制导的翻译翻译(SDT)，文法，文法Gi=(N, ,P,S)，其中，其中P=A|A, 属于属于R)，称为，称为SDTS T的基础（或的基础（或输入）文法。文法输入）文法。文法G0=( N, ,P ,S), ，其中，其中P =A | A, 属于属于R ，称为，称为T的输出文法。的输出文法。把语法制导的翻译方法看成是将输入文法把语法制导的翻译方法看成是将输入文法Gi中的中的推导树变换成输出文法推导树变换成输出文法G0中的推导树。给了输入句子中的推导树。给了输入句子x，可以按如下方式得到，可以按如下方式得到x的一个翻译：先为推导的一个翻译：先为推导x构造构造一棵推导树，再变换该树

17、到输出文法中的一棵树，然一棵推导树，再变换该树到输出文法中的一棵树，然后取此输出树的边缘作为后取此输出树的边缘作为x的一个翻译。的一个翻译。语义制导翻译中的规则A,对应于每一个文法产生式A都有与之相关联的一套语义描述属性文法(attributegrammar)是一个三元组:A=(G,V,F)属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来语法制导翻译实现从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串分析树属性依赖

18、图语义规则的计算顺序依赖图由称为依赖图的一个有向图描述分析树中的继承属性和属性中间的相互依赖关系。依赖图的构造算法：依赖图的构造算法： for分析树中每一个结点ndofor结点的文法符号的每一个属性ado为a在依赖图中建立一个结点；for分析树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b:=f(c1,c2,ck)do fori:=1tokdo从ci结点到b结点构造一条有向边依赖图-例8.2例8.2继承属性继承属性L.in生产式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inad

19、dtype(id.entry,L.in)addtype(id.entry,L.in)例8.2Real id1,id2,id3分析树的依赖图5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1.1依赖图中的结点由数字来标识。从代表T.type的结点4有一条有向边连到代表L.in的结点5，因为根据产生式ETL的语义规则L1.in=L.in，可知L1.in依赖于L.in，所以有两条向下的有向边分别进入结点7和9。每一个与L产生式有关的语义规则addtype(id.Entry,L.in)都产生一个虚属性，结点6、8和10都是为这些虚属性构造的。良定

20、义的属性文法。很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。从事贸易如，p、c1、c2都是属性，若有下求值规则：p:=f1(c1)、c1:=f2(c2)、c2:=f3(p)时，就无法对p求值。如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。一个依赖图的任何拓扑

21、排序都给出一个分析树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点，语义规则b:=f(c1,c2,ck)中的属性c1,c2,ck在计算b以前都是可用的。属性文法属性文法说明的翻译是很精确的。最基本的文法用于建立输入符号说明的翻译是很精确的。最基本的文法用于建立输入符号串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排串的分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。义规则就得到输入符号串的翻译。例例8.2Real id1,

22、id2,id3分析树的依赖图分析树的依赖图每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖每一条边都是从序号较低的结点指向序号较高的结点。历此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用排序中我们可以得到下列程序，用an来代表依赖图中与序号来代表依赖图中与序号n的的结点有关的属性：结点有关的属性：a4: = reala5: = a4 addtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7)a9: = a7 addtype

23、 (id1,entry, a9)这些语义规则的计算将把这些语义规则的计算将把real类型填入到每个标识符对应的符号表类型填入到每个标识符对应的符号表项中。项中。属性计算方法树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）。一遍扫描的处理方法与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无无需构造实际的语法树。因为一遍扫描的处理方法与语法分析器

24、的相互作用，它与下面两个因素密切相关：（1）所采用的语法分析方法（2）属性的计算次序。例：定义定点二进制数的CFG:(1)NSS(2)SSB(3)SB(4)B0(5)B1非终结符N表示整个二进制数的数值，综合属性v附加在N上：Nv非终结符B表示一个二进制数字，它有自己的值v，但该值分配给N的值与它的位置有关，是与2成比例，比例因子f是从S继承的属性,所以：Bvf非终结符S表示一个二进制数字串，它也有值，但该值与串的位置有关，与f有关与串的长度l有关:Sfvl构造数值的属性断言可以如下:NvSf1v1l1Sf2v2l2v=v1+v2;f1=1;f2=2-l2SfvlSf1v1l1Bf2v2f1=

25、2f;f2=f;v=v1+v2;l=l1+1Bfvl=1Bfv0v=01v=fNvSi1l1“”Si2l2v=i1+2-l2i2SilSi1l1Bi2i=2i1+i2;l=l1+1Bil=1Bi“0”i=0“1”i=1在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要具体的实现希望在单遍扫描中完成翻译具体的实现希望在单遍扫描中完成翻译研究怎样实现这种翻译器。一个一般的属性文法的翻译器可能是很难建立的，然而有一大类属性文法的翻译器是很容易建立的s-属性属性适用于适用于自底向

26、上的计算自底向上的计算 L-属性属性适用于自顶向下的分析，也可用于自底向上。适用于自顶向下的分析，也可用于自底向上。 S属性文法的自下而上计算S属性文法，它只含有综合属性。综合属性可以在分析输入符号串的同时自下而上的分析器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。S属性文法的翻译器通常可借助于LR分析器实现。在S属性文法的基础上，LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。产生式语义规则）（.）1 . 1.） . .l）1* . 1. ）F . F.）（）（） . . ）i

27、i .:.LR分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。LR分析器增加语义栈增加语义栈 *的分析和计值过程步骤动作状态栈语义栈(值栈)符号栈余留输入串） 3*） 3 *） *） *） *） *） *） *） *） * ） * ）（）（） * #）（）（））（）（））接受）接受BOTTOMUPBOTTOMUP语语义义处处理理是是作作类类型型检检查查，对对二二目目运运算算符符的的运运算算对对象进行类型匹配审查。象进行类型匹配审查。(LR(LR分分析析）：增加语义栈）：增加语义栈归约归约时进行语义动作时进行语义动作. .例8.7GE:(1)ET+TT+T(2

28、) E (2) E T or TT or T(3) T (3) T n n(4) T (4) T b b E ET T1 1 + T+ T2 2 if T if T1 1. .type = type = intint and T and T2 2. .type= type= intint then E then E. .type :=type :=intint else error else error E E T T1 1 or Tor T2 2 if T if T1 1. .type = type = boolbool and T and T2 2. .type= type= boolbo

29、ol then E then E. .type :=type :=boolbool else error else error T T n T.type := int n T.type := intT T b T.type := bool b T.type := bool GE:(1)ET+TT+T(2) E (2) E T or TT or T(3) T (3) T n n(4) T (4) T b bL属性文法和自顶向下翻译一一个个属属性性文文法法称称为为L属属性性文文法法，如如果果对对于于每每个个产产生生式式AX1X2Xn，其其每每个个语语义义规规则则中中的的每每个个属属性性或或者者是是

30、综综合合属属性性，或或者者是是Xj（1jn）的的一一个个继继承承属属性性且且这这个个继继承承属属性性仅仅依赖于：依赖于：（1）产生式）产生式Xj在左边符号在左边符号X1，X2，Xj-1的属性；的属性；（2）A的继承属性。的继承属性。S属属性性文文法法一一定定是是L属属性性文文法法，因因为为（1）、（2）限限制制只只用于继承属性。用于继承属性。L属性文法允许一次遍历就计算出所有属性值。属性文法允许一次遍历就计算出所有属性值。LL（1）这这种种自自上上而而下下分分析析文文法法的的分分析析过过程程，从从概概念念上上说说可可以以看看成成是是深深度度优优先先建建立立语语法法树树的的过过程程，因因此此，我

31、我们们可可以以在在自自上而下语法分析的同时实现上而下语法分析的同时实现L属性文法的计算。属性文法的计算。例（中缀表达式翻译成相应的后缀表达式）ETRRaddopTprint(addop.Lexeme)R1|Tnumprint(num.val)翻译模式（Translationschemes）适合语法制导翻译的另一种描述形式。翻译模式给出了使用语义规则进行计算的次序，可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上。输入串95+2的语法树，每个语义动作都作为相应产生式左部符号的结点的儿子，按深度优先次序执行

32、图中的动作后，打印输出952+。ETR9print(9)-Tprint(-)R5print(5)+Tprint(+)R2print(2)L属性文法在自顶向下分析中的实现带左递归的文法的翻译模式EE1+T E.val:=E1.val+T.valEE1T E.val:=E1.valT.valETE.val:=T.valT(E)T.val:=E.valTnumT.val:=num.val消除左递归的同时考虑属性，构造新的翻译模式翻译模式ET R.i: =T.val R E.val: = R.sR + T R1.i:=R.i + T.val R1 R.s: = R1.sR- T R1.i: = R.i

33、 -T.val R1 R.s: = R1.sRR.s: = R.iT(E) T.val: =E.valTnum T.val: = num.val计算表达式9-5+2.ER.i=9T.val=5T.val=9R.i=4R.i=6T.val=2num.val=9num.val=5num.val=2_+在上页的翻译模式中，每个数都是由在上页的翻译模式中，每个数都是由T产生的，并且产生的，并且T.val的值就是由属性的值就是由属性num.val给出的数的词法值。子表达式给出的数的词法值。子表达式95中的数字中的数字9是由最左边的是由最左边的T生成的，但是减号和生成的，但是减号和5是是由根的右子结点由根

34、的右子结点R生成的。继承属性生成的。继承属性R.i从从T.val得到值得到值9。计算计算95并把结果并把结果4传递到中间的传递到中间的R结点这是通过产生结点这是通过产生式中嵌入的下面动作实现：式中嵌入的下面动作实现：R1.i: = R.iT.val类类似似的的动动作作把把2加加到到95的的值值上上，在在最最下下面面的的R结结点点处处产产生生结结果果R.i6。这这个个结结将将成成为为根根结结点点处处E.val的的值值,R的的综综合合属属性性s在在图图中中没没有有表表示示出出来来，它它用用来来向向上上复复制制这这一一结果一直到树根。结果一直到树根。对于自顶向下分析，我们假设动作是在处于相同位置上的

35、符号被展开（匹配成功）时执行的。如图中的第二个产生式中，第一个动作（对R1.i赋值）是在T被完全展开成终结符号后执行的，第二个动作是在R1被完全展开成终结符号后执行的。正如前面我们所讨论的，一个符号的继承属性必须由出现在这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它所依赖的所有属性都计算出来以后才能计算。转换左递归翻译模式的方法推广到一般假设翻译模式假设翻译模式1：AA1YA.a: = g(A1。a, Y.y)AX A.a: = f(X.x)每每个个文文法法符符号号都都有有一一个个综综合合属属性性，用用相相应应的的小小写写字字母母表表示示，g和和f是是任任意函数意函数消除左递

36、归，文法转换成：消除左递归，文法转换成：AXR RYR再考虑语义动作，翻译模式变为再考虑语义动作，翻译模式变为2AX R.i: = f(X.x) R A.a: =R.sRY R1.i: = g(R.i,Y.y) R1R.s: = R1.sRR.s: = R.i翻译模式1和翻译模式2的结果是一样的。可以给出串XY1Y2两棵带注释的语法树看出来，一棵是根据翻译模式1自下而上计算属性的。一棵是根据翻译模式2自上而下计算的。 AA1YA.a: = g(A1。a, Y.y)AX A.a: = f(X.x)A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X.x,Y1.y)Y2A.a=f(

37、X.x)Y1XAAYAYX AXR.i: = f(X.x) RY R1.i: = g(R.i),Y.y) R A.a: =R.s R1R.s: = R1.s AXR RYRAXRY1RY2RAXR.i=f(X.x)Y1R.i=g(f(X.x,Y1.y)Y2R.i=g(g(f(X.x,Y1.y),Y2.y)思考问题-把建立语法树的翻译模式变换成适合预测分析的模式EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptr)自下而上计算继承属性讨论在自下而上的分析过程中实现L属性

38、文法的方法。这种方法可以实现任何基于LL（1）文法的L属性文法，它还可以实现许多（不是所有）基于LR（1）文法的L属性文法。这种方法是S-属性文法的自下而上翻译技术的一般化自下而上分析器对产生式AXY的右部是通过把X和Y从分析栈中移出并用A代替它们。假设X有一个综合属性X.s，按照前面所介绍的方法我们把它与X一起放在分析栈中。由于X.s的值在Y以下的子树中的任何归约之前已经放在栈中，这个值可以被Y继承。也就是说，如果继承属性Y.i是由复写规则Y.i:=X.s定义的，则可以在需要y.i值的地方使用X.s的值。在自下而上分析中计算属性值时复写规则起非常重要的作用。看下面例子。假设某翻译模式为：DT

39、L.in:=T.typeLTintT.type:=integerTrealT.type:=realLL1.in:=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)回顾例8.2Real id1,id2,id3分析树的依赖图5678910T4DLLLRealtypeininin3entry2entryentryid3id2id1.1例8.2输入串realReal id1,id2,id3的的分析过程当当L的右部被归约时，的右部被归约时，T恰好在这个右部的下面恰好在这个右部的下面输入状态(符号）使用产生式Realid1,id2,id3#i

40、d1,id2,id3#realid1,id2,id3#TTreal,id2,id3#Tid1,id2,id3#TLLidid2,id3#TL,id3#TL,id2,id3#TLLLi,did3#TL,#TL,id3#TLLLi,d#DDTL用综合属性代替继承属性有时，改变基础文法可能避免继承属性。例如，一个Pascal的说明由一标识符序列后跟类型组成，如,m,n:integer。这样的说明的文法可由下面形式的产生式构成DL：TTinteger|charLL,id|id因为标识符由L产生而类型不在L的子树中，我们不能仅仅使用综合属性就把类型与标识符联系起来。事实上，如果非终结符L从第一个产生式中

42、tch (PopOperator() case ADD: PushOperand(lhs+rhs); break;case SUB: PushOperand(lhs-rhs); break;| /* empty, do nothing */ T - FTT - M F T rhs = PopOperand();lhs = PopOperand();switch (PopOperator() case MUL: PushOperand(lhs*rhs); break;case DIV: PushOperand(lhs/rhs); break;| /* empty, do nothing */ A

43、 - + PushOperator(ADD);| - PushOperator(SUB);M - * PushOperator(MUL);| / PushOperator(DIV);F - int PushOperand(intval);| (E) /* handled during parsing of E */ parse2 + 4 * 3:分析动作桥分析动作桥分析栈分析栈运算对象栈运算对象栈运算符栈运算符栈Predict E TE E#Predict T FT TE#Predict F int FTE#Match int intTE#Predict T TE# 2Predict E

44、 ATE ATE # 2Predict A + ATE# 2Match + +TE# 2Predict T FT TE# 2 +Predict F int FTE# 2 +Match int intTE# 2 +Predict T MFT TE# 4 2 +Predict M * MFTE# 4 2 +Match * *FTE# 4 2 +Predict F int FTE# 4 2 * +Match int intTE# 4 2 * +Predict T TE# 3 4 2 * +Predict E E# 12 2 +Success! # 14Yacc或或bison作为编译程序的生成工具，利

45、用的就是语法作为编译程序的生成工具，利用的就是语法制导翻译方法。它使用符号制导翻译方法。它使用符号$表示产生式左端的属性，表示产生式左端的属性，$n表示存取产生式右端第表示存取产生式右端第n个文法符号相联的属性个文法符号相联的属性如例如例8.3作为作为Yacc的输入，可写成：的输入，可写成：P DS $2.dl=$1.dlD1 var V； D$.dl=addlist($2.name，$4.dl) | $.dl=nullS1 V:=e； Scheck($1.name，$.dl)； $5.dl=$.dl |V x $.name=x |y $.name=y |z $.name=z如果数据结构如果数

46、据结构attribute定义属性定义属性name和和dl，可以具体化为：，可以具体化为：type struct_attribute char *name； struct_attribute *list； attribute；P DS $2.list=$1.listD1 var V； D$.list=add_to_list($2.name，$4.list) | $.list=nullS1 V:=e； Scheck($1.name，$.list)； $5.list=$.list |V x $.name=x |y $.name=y |z $.name=z语义分析语义分析属性文法和语法制导翻译方法和技

47、术应用于语义分析中。语义分析通常包括：（1）类型检查。验证程序中执行的每个操作是否遵守语言的类型系统的过程.，编译程序必须报告不符合类型系统的信息。（2）控制流检查。控制流语句必须使控制转移到合法的地方。例如，在C语言中break语句使控制跳离包括该语句的最小while、for或switch语句。如果不存在包括它的这样的语句，则就报错。（3）一致性检查。在很多场合要求对象只能被定义一次。例如Pascal语言规定同一标识符在一个分程序中只能被说明一次，同一case语句的标号不能相同，枚举类型的元素不能重复出现等等。（4）相关名字检查。有时，同一名字必须出现两次或多次。例如，Ada语言程序中，循环

48、或程序块可以有一个名字，出现在这些结构的开头和结尾，编译程序必须检查这两个地方用的名字是相同的。(5)名字的作用域分析类型和声明（类型和声明（Types and declarations）一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型一个类型是一组值和在这些值上的一组操作，程序设计语言中有三种类型:基本类型基本类型：int, float, double, char, bool等等等等. 也可能允许在也可能允许在基本类型基础上基本类型基础上用用户自己定义的类型，如枚举型户自己定义的类型，如枚举型.复合类型：数组复合类型：数组,指针，记录指针，记录/结构结构/联合联合,类等等类等

49、等.这些类型由基本类型构成这些类型由基本类型构成.复杂类型：链表，栈，队，树，堆，表格等等复杂类型：链表，栈，队，树，堆，表格等等.可以把它们组织成可以把它们组织成ADT. 一个语一个语言不一定支持这类高级的抽象。言不一定支持这类高级的抽象。声明是程序中的一个语句声明是程序中的一个语句,是把数据对象的名称和类型，以及生命周期信息传是把数据对象的名称和类型，以及生命周期信息传给编译，声明的地方传递生命周期信息给编译，声明的地方传递生命周期信息也有些语言允许声明初始化变量也有些语言允许声明初始化变量。如如:double calculate(int a, double b); / function

50、prototypeint x = 0; / global variables available throughoutdouble y; / the programint main() int m3; / local variables available only in mainchar *n;.强类型的-任何数据类型都可以在编译时确定弱类型的.进行类型检查的时间：编译时，运行时，或者两者结合.静态类型检查编译时进行类型检查动态类型检查，将类型信息并到运行时每个数据单元中.隐含类型转换.PD；EDD；|id:TTchar|integer|araynumofT|TEliteral|num|id

51、|EmodE|EE|EP代表程序；D代表说明；E代表表达式。如程序语句：key:integer;keymod1999语言本身提供两种基本类型：char和integer。除此之外还有缺省的基本类型type_error和void。假定所有数组都从下标1开始确定标识符类型的部分翻译模式（1）PD；E（2）DD；D（3）Did:T addtype (id. Entry, T. type)（4）Tchar T. Type:= char（5）Tinteger T. Type:= integer（6）TT1 T. Type:= pointer (T1. type)（7）Tarray numof T1 T.

52、Type: = array (num.Val, T1.type)语句的类型检查的翻译模式Sid:=E if id. Type= E. Type Then S. Type:= void else S. Type:= type_ errorSif E then S1 if E. type= boolean then S. Type:= S1. typeelseS.type:=type_errorSwhileEdoS1ifE.type=booleanThenS.type:=S1.TypeelseS.type:=type_error设计设计类型检查程序1.辨认语言中可用的类型2.辨认具有类型的语言结构

53、3.辨认语言的语义规则In Decafbasetypes：int,double,bool,stringcompoundtypes：arraysandclasses.Anarraycanbemadeofanytype(eitherabasetype,aclass,oroutofotherarrays).Classesareabitspecialinthattheclassnamemustbedeclaredbeforeitcanbeusedinadeclaration.ADTscanbeconstructedusingclasses,buttheyarenthandledinanywaydiff

54、erentlythanclasses,sowedontneedtoconsiderthemspecially.InDecaftherelevantlanguageconstructsconstants,everyconstanthasanassociatedtype.Ascannertellsusthesetypesaswellastheassociatedlexeme.variables：allvariables(global,local,andinstance)musthaveadeclaredtypeofeitherint,double,bool,string,array,orclass

55、.functions：functionshaveareturntype,andeachparameterinthefunctiondefinitionhasatype,asdoeseachargumentinafunctioncall.expressionsanexpressioncanbeaconstant,variable,functioncall,orsomeoperator(binaryorunary)appliedtoexpressions.Eachofthevariousexpressionshaveatypebasedonthetypeoftheconstant,variable

56、,returntypeofthefunction,ortypeofoperands.TheotherlanguageconstructsinDecaf(if,while,Print,assignments,etc.)alsohavetypesassociatedwiththem,becausesomewhereineachofthesewefindanexpression.Thesemanticrulesgovernwhattypesareallowableinthevariouslanguageconstructs.InDecaf,operandtoaunaryminusmusteither

57、bedoubleorint,theexpressionusedinalooptestmustbeofbooltype,generalrules,suchasallvariablesmustbedeclaredbeforeuse,allclassesareglobal,andsoon.arrays:theindexusedinanarrayselectionexpressionmustbeofintegertypeexpressions:thetwooperandsto%mustbothbeint.Theresulttypeisint.this isboundtothereceivingobje

58、ctwithinclassscope,itisanerroroutsideclassscopevariables：avariabledeclaredofclasstypemustrefertoadefinedclassnamefunctions：thetypeofeachactualargumentinafunctioncallmustbecompatiblewiththeformalparameter。ifafunctionhasavoidreturntype,itmayonlyusetheemptyreturnstatement实现实现类型检查程序.首先，将每个名字（标识符）的类型信息记录

59、在符号表中作用域检查作用域和可见性基本作用域规则（lexicalrule) int a;void Binky(int a) int a;a = 2;. 作用域检查实现：1每个作用域一个独立的符号表，这些符号表组织成作用域栈2对所有作用域的全局符号表，每个作用域有一个作用域号？各自的优缺点，PL/0用的是哪种运算符（函数）的重载多态函数重载运算符（overloading operator）根据上下文可以执行不同的运算。是重载符号，在AB中，当A和B为整数、实数、复数或者矩阵时，运算符执行不同类型的运算当出现重载运算符时，要确定它所表示的唯一的意义，称为运算符识别。检查运算符的操作数。多态函数-

60、能实现对数据结构进行操作的算法，不管数据结构的元素类型是什么多态函数的特点是，每次被调用时，传递过来的参数可以具有不同类型。. . . 何谓中间代码何谓中间代码 ( Intermediate code ) ( Intermediate representation ) ( Intermediate language ) 源程序的一种内部表示，不依赖目标机的结构，易于机械生成源程序的一种内部表示，不依赖目标机的结构，易于机械生成目目标代码的中间表示。标代码的中间表示。为什麽要此阶段为什麽要此阶段逻辑结构清楚；利于不同目标机上实现同一种语言；逻辑结构清楚；利于不同目标机上实现同一种语言；（参

61、考第参考第12章的章的275,276页页）利于进行与机器无关的优化利于进行与机器无关的优化；这些内部形式也能用于解释。；这些内部形式也能用于解释。中间代码的几种形式中间代码的几种形式逆波兰逆波兰四元式四元式三元式三元式间接三元式间接三元式树树中间代码中间代码例例 : A + B * ( C - D ) + E / ( C - D ) N例例 : A + B * ( C - D ) + E / ( C - D ) N例例 : A + B * ( C - D ) + E / ( C - D ) N简单赋值语句的简单赋值语句的(四元式）翻译四元式）翻译四元式形式四元式形式 : resul

62、t:= arg1 op arg2语义属性：语义属性：id.name, E.place 函数：函数：lookup( id.name) ; 过程：过程：emit(t := arg1 op arg2); newtemp; 产生式和语义描述：产生式和语义描述：(1) S id := E P:=lookup (id.name) ; if P nil then emit( P“ :=”E.place) else error (op ,arg1,arg2,result) 或或(2)EE1+E2 E.place:= newtemp; emit(E.place“:=” E1.place“+”E2.place)

63、(3)E - E1 E.place:=newtemp; emit(E.place“:=”“uminus” E1.place)(4)E( E1) E.place:= E1.place(5)Eid E.place:=newtemp; P:=lookup(id.name); if P nil then E.place:=P else error简单说明句的翻译简单说明句的翻译-翻译是指在符号表中登录名字和性质。最简单的说明句的语法：integernamelistrealnamelistnamelistnamelist，idid用自下而上翻译文法改写：1，idintegerid|realid(1)in

64、tegeridenter(id,int）;D.att:=int(2)realidenter(id,real）;D.att:=real(3),identer(id，att）；D.att:=att不改写文法，用自下而上翻译-请你自己设计用自上而下翻译-请你自己设计如如 i f B t h e n S 1 e l s e S 2B 的的代代码码条条件件假转假转S1的的代代码码转转移移S2的的代代码码BS1S2NY控制语句的翻译控制语句的翻译- -结构的翻译结构的翻译E.false 控制语句中布尔表达式的翻译控制语句中布尔表达式的翻译控制语句控制语句Sif E then S1 el

65、se S2 E的代码的代码 E.true E.true: S1的代码的代码 goto outE.false: S2的代码的代码out: . 把条件转移的布尔表达式把条件转移的布尔表达式E翻译成仅含翻译成仅含条件真条件真转转和和无条件无条件转转的四元式的四元式 E：a rop b if a rop b goto E.true goto E.false如如：ab or cd and ef 可可翻译成如下四元式：翻译成如下四元式：(1) if ab goto E.true(2) goto (3)(3) if cd goto (5)(4) goto E.false(5) if ef g

66、oto E.true(6) goto E.false (翻译翻译不是最优不是最优)语句语句if ab or cd and ef then S1 else S2的四元式的四元式(1) if ab goto (7) /转移至转移至(E.true ) (2) goto (3) (3) if cd goto (5)(4) goto (p+1)/转移至转移至(E.false)(5) if ef goto (7)(6) goto (p+1)(7)( S1的四元式的四元式 (p-1) ）(p) goto (q)(p+1) (S2的四元式的四元式(q-1) ）(q)/转移至转移至(E.true ) /转移至转

67、移至(E.false)/(E.false)入入口口/ (E.true ) 入口入口记录需回填地址的四元式，把需回填的四元式拉成一链，把需回填的四元式拉成一链，分别称做“真”链和“假”链（）o（）（）则链成（）（）（）（）（）（）把地址（）称作“真”链链首，为链尾标志，即地址（）为“真”链链尾。语义描述使用的变量和过程：语义描述使用的变量和过程： E.true ： “真真”链，链， E.false ： “假假”链链。 E.codebegin ： E的第一个四元式的第一个四元式 Nextstat：下一四元式地址下一四元式地址过程：过程： emit( ) 输出一条四元式，而输出一条四元式，而

68、nextstat+1 merge(p1, p2) 把把p1的链首填在的链首填在p2的链尾的链尾例：例： merge(p1, p2)(p10) goto ( 0) p1链链 (p100) goto (p10)(p1) goto (p100)(p20) goto( 0) (p100) p2链链 (p200) goto (p20)(p2) goto (p200) backpatch(p,t) 把把链首链首p 所链接的每个四元式所链接的每个四元式的第四区段都填为的第四区段都填为t自下而上分析中的一种翻译方案：自下而上分析中的一种翻译方案：(1) EE1 or E2 backpatch(E1.false

69、, E2.Codebegin); E.Codebegin:= E1.codebegin; E.true:=merge(E1.true, E2.true) E.false:= E2.false(2) EE1 and E2 backpatch(E1.true, E2.codebegin); E.Codebegin:= E1.codebegin; E.true:= E2.true; E.false:= merge(E1.false, E2false);(3) Enot E1 E.true:= E1.false; E.Codebegin:= E1.codebegin; E.false:= E1.tru

70、eGOTOGOTO语句翻译语句翻译拉链返填拉链返填（10） goto L （10）goto 0 链尾链尾（10）（20） goto L （20）goto 10 （30） goto L (30) goto 20 链头链头（30）（40）L：（40）L: .符号表nametypedefaddLlabelnotr(p)goto0(q)gotop(r)gotoq建链的方法是：若中的标号尚未在符号表中出现，则把填入表中，置的“定义否”标志为“未”，把填进的地址栏中作为新链首，然后，产生四元式（），其中为链尾标志。若已在符号表中出现（但“定义否”标志为“未”），则把它的地址栏中的编号（记为）取出，把

71、nextstat填进该栏作新链首，然后，产生四元式（）。定义标号语句的产生式：那么，当用：进行归约时，应做如下的语义动作：1.若所指的标识符（假定为）不在符号表中，则把它填入，置“类型”为“标号”，“定义否”为“已”，“地址”为nextstat。2.若已在符号表中但“类型”不为“标号”或“定义否”为“已”，则报告出错。3.若已在符号表中，则把标志“未”改为“已”，然后，把地址栏中的链首（设为）取出，同时把nextstat填在其中，最后，执行backpatch（，nextstat）。翻译语句时，还有两点必须注意第一：相同名字的标号可以在不同名字作用域中定义。如：（）（）：（）；/延迟使用（）（）

72、：（）（）第二，转移标号是非法的（）（）for =to10do（）（） begin goto；（）（） for =to 20 do（）（） begin goto；（）（） L: endfor endfor i处理到第（）行后，第（）行的goto目标得以解决。而第（）行的goto是非法的，但只有当循环关闭时才能确定。中间表示的不同层次源中层 IR 低层IRfloat a1020; t1 = j + 2 aij+2; t2 = i * 20 t3 = t1 + t2 高层 IR t4 = 4 * t3 t1 = ai, j+2 t5 = addr a t6 = t5 + t4 t7 = *t6

73、抽象语法树和DAG图语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（AbstractSyntaxTree）。在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点如产生式SifBthenS1elseS2抽象语法树表示if-then-elseBS1S2语法树和抽象语法树directed acyclic graph (DAG).b*c+b*c+*bcinDecafcompiler Three-address code (TAC)a = b * c + b *

74、d t1 = b * c;t2 = b * d;t3 = t1 + t2;a = t3;控制流if (a b + c) a = a - c;c = b * c; t1 = b + c; t2 = a t1; IfZ t2 Goto L0; t3 = a - c; a = t3;L0: t4 = b * c; c = t4;函数调用，数组访问int n;n = ReadInteger();Binky(arrn);n = LCall _ReadInteger();t1 = 4;t2 = t1 * n;t3 = arr + t2;t4 = *(t3);LCall _Binky(t4);void ma

75、in() int a;int b;int c;a = 1;b = 2;c = a + b;Print(c);main:BeginFuncWithParams;Var a;Var b;Var c;Var _t0;_t0 = 1;a = _t0;Var _t1;_t1 = 2;b = _t1;Var _t2;_t2 = a + b;c = _t2;LCall _PrintInt(c);EndFunc;void main() Print(hello world);main:BeginFuncWithParams;Var _t0;_t0 = hello world;LCall _PrintString

76、(_t0);EndFunc;void main() int a;a = 2 + a;Print(a);main:BeginFuncWithParams;Var a;Var _t0;_t0 = 2;Var _t1;_t1 = _t0 + a;a = _t1;LCall _PrintInt(a);EndFunc;void Binky(int arr) arr1 = arr0 * 2;_Binky:BeginFuncWithParams arr;Var _t0; _t0 = 1;Var _t1; _t1 = 4;Var _t2; _t2 = _t1 * _t0;Var _t3; _t3 = arr

77、+ _t2;Var _t4; _t4 = 0;Var _t5; _t5 = 4;Var _t6; _t6 = _t5 * _t4;Var _t7; _t7 = arr + _t6;Var _t8; _t8 = *(_t7);Var _t9; _t9 = 2;Var _t10; _t10 = _t8 * _t9;*(_t3) = _t10;EndFunc;int foo(int a, int b) return a + b;void main() int c;int d;foo(c, d);_foo:BeginFuncWithParams a, b;Var _t0;_t0 = a + b;Ret

78、urn _t0;EndFunc;main:BeginFuncWithParams;Var c;Var d;Var _t1;_t1 = LCall _foo(c, d);EndFunc;class Animal int height;void InitAnimal(int h) this.height = h;_Animal_InitAnimal:BeginFuncWithParams this, h;*(this + 4) = h;EndFunc;VTable Animal =_Animal_InitAnimal,；class Cow extends Animal void InitCow(i

79、nt h) InitAnimal(h);_Cow_InitCow:BeginFuncWithParams this, h;Var _t0;_t0 = *(this);Var _t1;_t1 = *(_t0);ACall _t1(this, h);EndFunc;VTable Cow =_Animal_InitAnimal,_Cow_InitCow,;void Binky(class Cow betsy) betsy.InitCow(5);_Binky:BeginFuncWithParams betsy;Var _t2;_t2 = 5;Var _t3;_t3 = *(betsy);Var _t4;_t4 = *(_t3 + 4);ACall _t4(betsy, _t2);EndFunc;

展开阅读全文

教学课件第八章语法制导翻译和中间代码生成

最新文档