语法制导翻译及中间代码生成.ppt
《语法制导翻译及中间代码生成.ppt》由会员分享,可在线阅读,更多相关《语法制导翻译及中间代码生成.ppt(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、语法制导翻译及中间代码生成现在学习的是第1页,共30页5.1 引言引言词法分析与语法分析仅仅是编译程序的一小部分。在早期的一些编译程序中,是在语法分析的基础上根据源程序中各语法成份的语义,直接产生机器语言或汇编语言形式的目标代码目标代码。现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码中间语言代码,然后再将其翻译为目标代码。优点优点优点优点:使编译程序各组成部分功能更单一;使得编译程序的逻辑结构更为清晰,从而使编译程序更易于编写与调整;同时为代码优化和程序的可移植性提供了条件 现在学习的是第2页,共30页5.1 引言引言(续续)本章要讨论的中间代码生成中间代码生成,是指
2、把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示。目前常见的中间语言有逆波兰表示逆波兰表示、三元式三元式、四元式四元式等等。遗憾的是,中间代码生成与语言的语义密切相关,而语义的形式化描述是一个非常困难的;存在一种称为语法制导翻译的模式,这种模式实际上是对前后文无关文法的一种扩充。方法方法:对文法中的每个产生式都附加一个语义动作或语义子程序,在语法分析过程中,每当需要使用一个产生式进行推导或归约,语法分析程序除执行相应的语法分析动作外,还要执行相应的语义动作或调用相应的语义子程序。现在学习的是第3页,共30页5.1 引言引言(续续)这种模式既把语法分析与语义处理分开,
3、又令其平行地进行,让其在同一遍扫描中同时完成语法分析和语义处理两项工作。由此可见,抽象文法符号的具体语义信息,是在与语法分与语法分析同步的语义处理过程中获取和加工的析同步的语义处理过程中获取和加工的。文法符号X的语义信息我们称之为语义属性语义属性或简称为属属性性(Attributes)。我们用形如X.ATTR的记号来表示文法符号X的相关语义语义属性属性。如果一个文法符号X在一产生式中多次出现,为了在语义上能够对其进行区分,可添加不同的上标。现在学习的是第4页,共30页文法符号及其语义属性例如,文法GEGE:产生式产生式 语义子程序语义子程序EE(1)+TE.Val=E(1).val+T.val
4、;ETE.Val=T.Val;TdigitT.Val=digit;为了能在语法分析过程中平行地进行语义处理,可在语法分析栈旁边并行地设置一个语义信息栈语义信息栈语义信息栈语义信息栈 语法分析栈语义分析栈TT.Val+E#现在学习的是第5页,共30页本章内容简介本章,我们首先介绍一种适用于定义语义的一种特殊文法属性文法,并进一步介绍适用于语义翻译的文法属性翻译文法的相关知识。在第三小节中我们将介绍几种常见的中间语言;在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术。现在学习的是第6页,共30页5.2 属性文法与属性翻译文法 语法制导翻译方法语法制导翻译方法的实质,就是根据文法中每个产
5、生式所蕴含的语义,为其配备一个(或多个)处理语句或子程序,对所要完成的功能进行描述。语义子程序的编写质量决定了语义翻译的准确性和有效性。所以,产生式相应语义子程序的正确性是能够进行正确语义翻译的先决条件。产生式的语义产生式的语义是由组成该产生式的文法符号的语义文法符号的语义所决定的。我们可将这些语义以“属性属性”的形式附加到各个文法符号上,再根据产生式所蕴含的语义,给出每个文法符号的属性的求值求值规则规则,从而形成一种附带有语义属性语义属性的前后文无关文法,即属性文法属性文法。现在学习的是第7页,共30页5.2.1 语义属性与属性文法语义属性与属性文法 定义 5.1 一一文法符号的语义性质称为
6、该文法符号的语义语义属性属性(AttributesAttributes),简称为属性属性。我们用A(X)表示X的所有属性的集合。每个属性表示X的一个特定性质,并可任意指定其取值范围。我们用X.a表示A(X)中的属性a。属性属性可表征诸如数、符号串、类型、存储空间和其它需表征的实体。终结符终结符至少有一种属性属性,即词文。当然,它还可能具有其它属性,例如无符号数123123,单词“123”就是它的词文,而其数值以及它的类型(整型)是它的其它两个属性。终结终结符的属性是其符的属性是其内在性质内在性质.非终结符非终结符的属性属性是从其它符号的属性属性经计算而得的,即由其它符号的属性属性定义的。现在学
7、习的是第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 ak
8、mkm属性计算而得的。现在学习的是第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
9、Xi i.a.a是继 承 属 性(Inherited AttributesInherited Attributes)。现在学习的是第10页,共30页加注语法树加注语法树在语法树中,将每个结点均视为由若干个域组成的结构结构,则可将其中的一些域用来存放相应文法符号诸属性之值,并可用属性属性来为这些域命名。通常我们将每个结点都标注相应属性值的语法树称为加注语法树加注语法树(AnnotatedSyntaxTree)或装饰树装饰树(DecoratedSyntaxTree书中有错!)。由定义定义5.35.3可知:在加注语法树加注语法树中,一个文法符号X X在相应结点的综合属性之值,由其子结点的属性和(或)
10、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
11、和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简
12、单赋值语句文法的属性文法现在学习的是第14页,共30页现在学习的是第15页,共30页属性文法中的一些限制在属性文法中,由于每个非终结符号的属性都由若干文法符号的属性通过相应的属性规则来定义,所以,就不能排除某文法符号的属性由其自身定义的可能性。为避免这种情况的发生,我们需对属性文法作一定的限制。定定定定义义义义5.55.55.55.5 对于L(G)中每个句子所对应的语法树T,若其每个结点标记符号的所有属性之值均可有效地计算,则称相应属性文法AG是良良良良定定定定义义义义的。此外,若所有条件B(p)均取true值,则称L(G)中的这个句子是正正正正确确确确赋赋赋赋予予予予属属属属性性性性的的的的
13、(或称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.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语法 制导 翻译 中间 代码 生成
限制150内