语法制导翻译及中间代码生成课件.ppt

语法制导翻译及中间代码生成第1页，此课件共30页哦5.1 引言引言词法分析与语法分析仅仅是编译程序的一小部分。在早期的一些编译程序中，是在语法分析的基础上根据源程序中各语法成份的语义，直接产生机器语言或汇编语言形式的目标代码目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码中间语言代码，然后再将其翻译为目标代码。优点优点优点优点：使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰，从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件 第2页，此课件共30页哦5.1 引言引言(续续)本章要讨论的中间代码生成中间代码生成，是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。目前常见的中间语言有逆波兰表示逆波兰表示、三元式三元式、四元式四元式等等。遗憾的是，中间代码生成与语言的语义密切相关，而语义的形式化描述是一个非常困难的;存在一种称为语法制导翻译的模式，这种模式实际上是对前后文无关文法的一种扩充。方法方法:对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中，每当需要使用一个产生式进行推导或归约，语法分析程序除执行相应的语法分析动作外，还要执行相应的语义动作或调用相应的语义子程序。第3页，此课件共30页哦5.1 引言引言(续续)这种模式既把语法分析与语义处理分开，又令其平行地进行，让其在同一遍扫描中同时完成语法分析和语义处理两项工作。由此可见，抽象文法符号的具体语义信息，是在与语法分与语法分析同步的语义处理过程中获取和加工的析同步的语义处理过程中获取和加工的。文法符号X的语义信息我们称之为语义属性语义属性或简称为属性属性（Attributes）。我们用形如X.ATTR的记号来表示文法符号X的相关语义属语义属性性。如果一个文法符号X在一产生式中多次出现，为了在语义上能够对其进行区分，可添加不同的上标。第4页，此课件共30页哦文法符号及其语义属性例如,文法GEGE:产生式产生式语义子程序语义子程序EE(1)+TE.Val=E(1).val+T.val;ETE.Val=T.Val;TdigitT.Val=digit;为了能在语法分析过程中平行地进行语义处理，可在语法分析栈旁边并行地设置一个语义信息栈语义信息栈语义信息栈语义信息栈 语法分析栈语义分析栈TT.Val+E#第5页，此课件共30页哦本章内容简介本章，我们首先介绍一种适用于定义语义的一种特殊文法属性文法，并进一步介绍适用于语义翻译的文法属性翻译文法的相关知识。在第三小节中我们将介绍几种常见的中间语言;在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术。第6页，此课件共30页哦5.2 属性文法与属性翻译文法 语法制导翻译方法语法制导翻译方法的实质，就是根据文法中每个产生式所蕴含的语义，为其配备一个（或多个）处理语句或子程序，对所要完成的功能进行描述。语义子程序的编写质量决定了语义翻译的准确性和有效性。所以,产生式相应语义子程序的正确性是能够进行正确语义翻译的先决条件。产生式的语义产生式的语义是由组成该产生式的文法符号的语义文法符号的语义所决定的。我们可将这些语义以“属性属性”的形式附加到各个文法符号上，再根据产生式所蕴含的语义，给出每个文法符号的属性的求值规则求值规则，从而形成一种附带有语义属性语义属性的前后文无关文法，即属性文法属性文法。第7页，此课件共30页哦5.2.1 语义属性与属性文法语义属性与属性文法 定义 5.1 一一文法符号的语义性质称为该文法符号的语义属语义属性性（AttributesAttributes），简称为属性属性。我们用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质，并可任意指定其取值范围。我们用X.a表示A(X)中的属性a。属性属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。终结符终结符至少有一种属性属性，即词文。当然，它还可能具有其它属性，例如无符号数123123，单词“123”就是它的词文，而其数值以及它的类型（整型）是它的其它两个属性。终结符的终结符的属性是其属性是其内在性质内在性质.非终结符非终结符的属性属性是从其它符号的属性属性经计算而得的，即由其它符号的属性属性定义的。第8页，此课件共30页哦属性依赖关系属性依赖关系各个文法符号的属属性性之间，可能存在某种依依赖赖关关系系，这种依依赖赖关系关系可用属性规则（语义规则语义规则）定义。定定义义 5.25.2设p:Xp:X0 0XX1 1X X2 2X Xn n是文法G的一个产生式，则与p相关联的属性规则集R(p)R(p)=X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm.a.akmkm)|)|X Xi i.a.aA(XA(Xi i)定义了该产生式所涉及的文法符号之属性的求求值值规规则则，它表示：X Xi i的a a属性是由的X Xk1k1的a ak1k1属性，的X Xkmkm的a akmkm属性计算而得的。第9页，此课件共30页哦综合属性与继承属性定定定定义义义义 5.35.3 对每个产生式p:Xp:X0 0XX1 1X X2 2X Xn n，设属性定义性出现的集合为AF(p)=X Xi i.a.a|X Xi i.a.a=f(=f(X Xk1k1.a.ak1k1,X,Xkmkm.a.akmkm)R(p),0kR(p),0kj jnn 若X Xi i是产生式左部的非终结符(即i=0),则称属性X Xi i.a.a是综合属性(Synthesized Synthesized AttributesAttributes);若X Xi i出现在产生式的右部(即1in),则称X Xi i.a.a是继承属性（Inherited AttributesInherited Attributes）。第10页，此课件共30页哦加注语法树加注语法树在语法树中,将每个结点均视为由若干个域组成的结构结构,则可将其中的一些域用来存放相应文法符号诸属性之值，并可用属性属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树加注语法树（AnnotatedSyntaxTree）或装饰树装饰树（DecoratedSyntaxTree书中有错!）。由定义定义5.35.3可知：在加注语法树加注语法树中，一个文法符号X X在相应结点的综合属性之值，由其子结点的属性和（或）X的其它属性，通过相关属性规则经计算而得，故综合属性的求值在语法树中是按自下而上自下而上的方式进行的；X X的继承属性之值则由X X的父结点和(或)其它兄弟结点来定义,故继承属性的求值将按自上而下自上而下的方式进行。第11页，此课件共30页哦属性文法的定义属性文法的定义定义定义定义定义5.45.45.45.4 属性文法属性文法AG是一个四元组：AG=(G,A,R,B),其中,G是已简化的CFG;A=XVA(X)是属性的有限集合;R=pPR(p)是属性定义规则的有限集;B=pPB(p)是条件的有限集合，B(p)用于描述使规则R(p)有效的条件；且同时满足：（1）对G中任意两个不同的文法符号X和Y而言，属性集合A(X)和A(Y)不相交,A(X)A(Y)=（2）在G的任意一个语法树中，对文法符号X的每一次出现，可用于计算X的每个属性之值的规则至多有一条。第12页，此课件共30页哦属性文法(续)由定义5.4可知，属属性性文文法法实际上就是对前后文无关文法的一种拓广。另外，每个产生式中的任一文法符号的属属性性计计算算规规则则只只能能是是唯唯一一的，且任一文法符号的综综合合属属性性集集与继继承承属属性性集集不不相相交交，即AS(X)AI(X)=,其中：AS(X)=X.a|p:XP,X.aAF(p)AI(X)=X.a|q:YX P,X.aAF(q)第13页，此课件共30页哦例5.1简单赋值语句文法的属性文法第14页，此课件共30页哦第15页，此课件共30页哦属性文法中的一些限制在属性文法中，由于每个非终结符号的属性都由若干文法符号的属性通过相应的属性规则来定义，所以，就不能排除某文法符号的属性由其自身定义的可能性。为避免这种情况的发生，我们需对属性文法作一定的限制。定定定定义义义义5.55.55.55.5 对于L(G)中每个句子所对应的语法树T，若其每个结点标记符号的所有属性之值均可有效地计算，则称相应属性文法AG是良良良良定定定定义义义义的。此外，若所有条件B(p)均取true值，则称L(G)中的这个句子是正正正正确确确确赋赋赋赋予予予予属属属属性性性性的的的的（或称T是可可可可加加加加注的注的注的注的）。从定义5.5可以看出，在良定义属性文法的任何语法树中，不会出现属性依赖于自身的现象。第16页，此课件共30页哦属性依赖关系属性依赖关系定义定义定义定义5.65.65.65.6 对于每个产生式p:X0X1X2XnP,直接属性依赖关系由下式给出：DDP(p)=(Xi.a,Xj.b)|Xj.b=f(,Xi.a,)R(p)若序偶(Xi.a,Xj.b)DDP(p)，则称属性Xj.b依赖于属性Xi.a，记作Xi.aXj.b。显然，若有Xi.aXj.b，则对Xj.b的计值，应在求出Xi.a的值之后进行。但若Xi.a又直接或间接地依赖于Xj.b,则称属性Xi.a和Xj.b是循环依赖循环依赖循环依赖循环依赖的。含有属性循环依赖的属性文法AG，其中的一些属性之值将不能得到有效的计算。第17页，此课件共30页哦依赖关系图定义定义定义定义5.75.75.75.7 设T是L(G)中一个句子相应的加注语法树，并设在构造T时使用过产生式p:X0X1X2Xn，对于T中由X0,X1,X2,Xn所标记的每个结点，若有(Xi.a,Xj.b)DDP(p),则在树中引一条从到的有向边，由此而得到的树称之为该句子的属性化语法树。所有这样的有向边构成的集合DT(T)，称为树T上的依赖关系。根据DT(T)所构造的关系图称为依赖关系图依赖关系图（或简称为依赖图依赖图）。例如，对于例5.1所给文法下的一个句子x:=y+zx:=y+z，相应属性化语法树的依赖关系如P191图5-3所示。第18页，此课件共30页哦属性文法的良定义性判别有了属性化的语法树及其依赖关系图，我们就可根据图中是否有回路来确定一属性文法是否是良定义的。定定定定理理理理5.15.15.15.1 一个属性文法是良定义的，当当且且仅仅当当对于它的每棵语法 树 T，相应的依赖关系图是一个无无 回回 路路 有有 向向 图图（directed acyclic graph）。从P191图5-3可以看出，该语法树相应的依赖关系DT(T)未出现回路，通过对其文法的验证，可知该属性文法是良良定定义义的。为便于设计编译程序，实际工作中我们只处理良定义的属性文法。至于有关良定义文法的判定算法，读者可参阅文献18。第19页，此课件共30页哦5.2.2 属性翻译文法属性翻译文法 由于属性文法的抽象性和属性定义的任意性，由于属性文法的抽象性和属性定义的任意性，当我们把它用于进行语义翻译时，就会发现仅当我们把它用于进行语义翻译时，就会发现仅有属性文法是不够的，有属性文法是不够的，须在属性文法的基础上须在属性文法的基础上做进一步的工作做进一步的工作。首先，我们应对文法的属性依赖关系作出限制，首先，我们应对文法的属性依赖关系作出限制，不允许出现属性的直接或间接的循环定义，即不允许出现属性的直接或间接的循环定义，即要要求属性文法是良定义的求属性文法是良定义的。其次，我们还应将属性规则改造为计算属性值的语义其次，我们还应将属性规则改造为计算属性值的语义程序，程序，即将静态的规则改写为可动态执行的语即将静态的规则改写为可动态执行的语义动作义动作。经过这样的改造后，我们就可得到一种新。经过这样的改造后，我们就可得到一种新的文法的文法属性翻译文法属性翻译文法。第20页，此课件共30页哦翻译文法的定义定义定义定义定义5.85.85.85.8 在文法产生式右部适当的位置上插入语义动作语义动作而得的新文法称为翻译文法翻译文法或增广文法增广文法(Augmented Augmented GrammarGrammar)。在一翻译文法翻译文法中，若每个产生式右部中的全部语义动作语义动作均出现在所有文法符号的右边，则称这样的翻译文法翻译文法为波兰翻译文法波兰翻译文法。为为了了区区分分文文法法符符号号与与语语义义动动作作，在在本本书书中中我我们们用用一一对对花花括括号号 及及 将将插插入入的的语语义义动动作作括括起起来来（语语义义动动作作采采用用C C语语言言格格式式书书写写）。而而且且，我我们们还还把把语语义义动动作作视视为为翻翻译译文文法法中中的的一一个个“符符符符号号号号”，称称为为动动动动作作作作符符符符号号号号。插插入入语语义义动动作作后后，翻翻译译文文法法产生式的一般形式为：产生式的一般形式为：A(A(statementstatement;);)*V V*第21页，此课件共30页哦翻译文法（续）翻译文法的作用是，在进行语法分析时，无论是用产生式进行推导还是进行归约，只要遇到其中带有语义动作的花括号，就要求编译系统自动执行花括号内指定的自动执行花括号内指定的语义动作语义动作，在执行完该动作之后才继续进行下一步的语法分析。例：ExprTerm ExprExpr+TermWriteCode(“+”);Expr|TermFactor TermTerm*Factor WriteCode(“*”);Term|Factoroperand WriteCode(yytext);|(Expr)第22页，此课件共30页哦递归下降分析中的翻译文法若用递归下降法进行语法分析，则与非终结符号Expr相对应的递归程序可扩充为：int Eprim()if(CurrentToken=+)if(Term()WriteCode(“+”);if(Eprim()return 1;else return 0;if(CurrentToken=)|CurrenToken=#)return 1;else return 0;第23页，此课件共30页哦属性翻译文法的定义定定义义5.95.9 属属性性翻翻译译文文法法（Attribute Translation Grammar，简记为ATG）是具有以下性质的翻译文法翻译文法：1每个文法符号和语义动作符X都有一个相关的有限属性集合A(X)，且每个属性都有一个允许值的集合（属性的值域，可以是无限集）。2非终结符和动作符的属性可分为继承属性继承属性与综合属性综合属性两类。3继承属性继承属性的定义规则为：开始符号的继承属性继承属性具有指定的初始值；对于给定的产生式p:YX1X2XnP,Xi的继继承承属属性性值由p中其它符号的属性值进行计算：Xi.a=f(Y.b,Xk1.ak1,Xkm.akm)i k1,km 4综综合合属属性性的定义规则为：对于给定的产生式p:YX1X2XnP，Y的综合属性综合属性值由p中某些符号的属性计算：Y.u=f(Y.v,Xk1.ak1,Xkm.akm)1 kj n；对于动作符号，其综合属性综合属性值由该动作符的其它属性计算；终结符的综合属性综合属性具有指定的初始值。第24页，此课件共30页哦对属性文法的一些限制定定义义5.105.10 一属性翻译文法称为是L-L-属属性性的，当且仅当对其中的每个产生式p:AX1X2Xn，下面的三个条件成立：1 右 部 符 号Xi(1in)的 继 承 属 性 之 值，仅 依 赖 于X1,X2,Xi-1的任意属性或A的继承属性；2左部符号A的综合属性之值仅依赖于A的继承属性或(和)右部符号Xi(1in)的任意属性；3对一动作符号而言，其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数。第25页，此课件共30页哦方法符号属性的求值顺序A的继承属性(AI(A)；X1的继承属性(AI(X1)；X1的综合属性(AS(X1),进入X1的子树后，返回时求出）；Xn的继承属性(AI(Xn)；Xn的综合属性(AS(Xn),进入Xn的子树后,返回时求出）；A的综合属性(AS(A),返回到A的上层）。第26页，此课件共30页哦表达式属性翻译文法例5.2 表达式属性翻译文法：Program|$1=$2=NewName();Expr FreeName($0);Program ExprTerm Expr Expr+$1=$2=NewName();Termprintf(“+,%s,%s,%sn”,$0,$,$0);FreeName($0);Expr|TermFactor Term Term*$1=$2=NewName();Factor printf(“*,%s,%s,%sn”,$0,$,$0);FreeName($0);Term|FactorNumberprintf(“:=,%s,-,%sn”,yytext,$);|第27页，此课件共30页哦S-属性文法的定义定义定义定义定义5.115.115.115.11 满足下面三个条件的属性文法称为S-S-属性文法属性文法：所有非终结符只具有综合属性综合属性；在一个产生式中，每一个符号的各个综综合合属属性性的定义互不依赖；在一个产生式中，若某个文法符号X具有继继承承属属性性，则此继继承承属属性性之值仅依赖于该产生式右部且位于X左边的符号之属性。显然，S-S-属属性性文文法法也满足L-L-属属性性文文法法的条件，这就是说，S-S-属属性性文文法法一定是L-L-属属性性文文法法，而且还要求每个非终结符只具有综合属性综合属性。第28页，此课件共30页哦S-属性文法的例子例例5.35.3 简单算术表达式的S-S-属性文法属性文法：ProgramExpr printf(“%dn”,$1);Expr Expr+Expr$=$1+$3;|Expr*Expr$=$1*$3;|(Expr)$=$2;|Number$=ToIntValue(yytext);上面的语义子程序采用了YACCYACC工具中的表示方法,其中$,$1,$2$,$1,$2分别表示产生式左部符号,右部的第一个,第二个符号(余类推)的语义属性语义属性语义属性语义属性.第29页，此课件共30页哦波兰翻译文法与S-属性文法在定义5.8所引入的波波兰兰翻翻译译文文法法，是将语义动作放在每个产生式的最右边，对应的属性翻译文法一定是S-S-属属性文法性文法。例 5.3文法中的语义动作均在各产生式最右侧，所以，该文法是S-S-属性波兰翻译文法属性波兰翻译文法。在本章的后几节，我们将以S-S-属属性性波波兰兰翻翻译译文文法法和自底向上的语法分析为基础，研究常见程序设计语言各类语法结构的语义翻译方法及语义子程序的设计技术。第30页，此课件共30页哦