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

第五章语法制导翻译及中间代码生成 5 1引言 词法分析与语法分析仅仅是编译程序的一小部分 在早期的一些编译程序中 是在语法分析的基础上根据源程序中各语法成份的语义 直接产生机器语言或汇编语言形式的目标代码 现在的编译系统一般都将经过语法分析的源程序先翻译为某种形式的中间语言代码 然后再将其翻译为目标代码 优点 使编译程序各组成部分功能更单一 使得编译程序的逻辑结构更为清晰 从而使编译程序更易于编写与调整 同时为代码优化和程序的可移植性提供了条件 5 1引言 续 本章要讨论的中间代码生成 是指把单词符号串形式的源程序转换为另一种等价的便于代码优化处理和目标代码生成表示 目前常见的中间语言有逆波兰表示 三元式 四元式等等 遗憾的是 中间代码生成与语言的语义密切相关 而语义的形式化描述是一个非常困难的 存在一种称为语法制导翻译的模式 这种模式实际上是对前后文无关文法的一种扩充 方法 对文法中的每个产生式都附加一个语义动作或语义子程序 在语法分析过程中 每当需要使用一个产生式进行推导或归约 语法分析程序除执行相应的语法分析动作外 还要执行相应的语义动作或调用相应的语义子程序 5 1引言 续 这种模式既把语法分析与语义处理分开 又令其平行地进行 让其在同一遍扫描中同时完成语法分析和语义处理两项工作 由此可见 抽象文法符号的具体语义信息 是在与语法分析同步的语义处理过程中获取和加工的 文法符号X的语义信息我们称之为语义属性或简称为属性 Attributes 我们用形如X ATTR的记号来表示文法符号X的相关语义属性 如果一个文法符号X在一产生式中多次出现 为了在语义上能够对其进行区分 可添加不同的上标 文法符号及其语义属性 例如 文法G E 产生式语义子程序E E 1 T E Val E 1 val T val E T E Val T Val T digit T Val digit 为了能在语法分析过程中平行地进行语义处理 可在语法分析栈旁边并行地设置一个语义信息栈 本章内容简介 本章 我们首先介绍一种适用于定义语义的一种特殊文法 属性文法 并进一步介绍适用于语义翻译的文法 属性翻译文法的相关知识 在第三小节中我们将介绍几种常见的中间语言 在第四小节中引入程序设计语言中常见语法结构的语法制导翻译技术 5 2属性文法与属性翻译文法 语法制导翻译方法的实质 就是根据文法中每个产生式所蕴含的语义 为其配备一个 或多个 处理语句或子程序 对所要完成的功能进行描述 语义子程序的编写质量决定了语义翻译的准确性和有效性 所以 产生式相应语义子程序的正确性是能够进行正确语义翻译的先决条件 产生式的语义是由组成该产生式的文法符号的语义所决定的 我们可将这些语义以 属性 的形式附加到各个文法符号上 再根据产生式所蕴含的语义 给出每个文法符号的属性的求值规则 从而形成一种附带有语义属性的前后文无关文法 即属性文法 5 2 1语义属性与属性文法 定义5 1一文法符号的语义性质称为该文法符号的语义属性 Attributes 简称为属性 我们用A X 表示X的所有属性的集合 每个属性表示X的一个特定性质 并可任意指定其取值范围 我们用X a表示A X 中的属性a 属性可表征诸如数 符号串 类型 存储空间和其它需表征的实体 终结符至少有一种属性 即词文 当然 它还可能具有其它属性 例如无符号数123 单词 123 就是它的词文 而其数值以及它的类型 整型 是它的其它两个属性 终结符的属性是其内在性质 非终结符的属性是从其它符号的属性经计算而得的 即由其它符号的属性定义的 属性依赖关系 各个文法符号的属性之间 可能存在某种依赖关系 这种依赖关系可用属性规则 语义规则 定义 定义5 2设p X0 X1X2 Xn是文法G的一个产生式 则与p相关联的属性规则集R p Xi a f Xk1 ak1 Xkm akm Xi a A Xi 定义了该产生式所涉及的文法符号之属性的求值规则 它表示 Xi的a属性是由的Xk1的ak1属性 的Xkm的akm属性计算而得的 综合属性与继承属性 定义5 3对每个产生式p X0 X1X2 Xn 设属性定义性出现的集合为AF p Xi a Xi a f Xk1 ak1 Xkm akm R p 0 kj n 若Xi是产生式左部的非终结符 即i 0 则称属性Xi a是综合属性 SynthesizedAttributes 若Xi出现在产生式的右部 即1 i n 则称Xi a是继承属性 InheritedAttributes 加注语法树 在语法树中 将每个结点均视为由若干个域组成的结构 则可将其中的一些域用来存放相应文法符号诸属性之值 并可用属性来为这些域命名 通常我们将每个结点都标注相应属性值的语法树称为加注语法树 AnnotatedSyntaxTree 或装饰树 DecoratedSyntaxTree书中有错 由定义5 3可知 在加注语法树中 一个文法符号X在相应结点的综合属性之值 由其子结点的属性和 或 X的其它属性 通过相关属性规则经计算而得 故综合属性的求值在语法树中是按自下而上的方式进行的 X的继承属性之值则由X的父结点和 或 其它兄弟结点来定义 故继承属性的求值将按自上而下的方式进行 属性文法的定义 定义5 4属性文法AG是一个四元组 AG G A R B 其中 G是已简化的CFG A X VA X 是属性的有限集合 R p PR p 是属性定义规则的有限集 B p PB p 是条件的有限集合 B p 用于描述使规则R p 有效的条件 且同时满足 1 对G中任意两个不同的文法符号X和Y而言 属性集合A X 和A Y 不相交 A X A Y 2 在G的任意一个语法树中 对文法符号X的每一次出现 可用于计算X的每个属性之值的规则至多有一条 属性文法 续 由定义5 4可知 属性文法实际上就是对前后文无关文法的一种拓广 另外 每个产生式中的任一文法符号的属性计算规则只能是唯一的 且任一文法符号的综合属性集与继承属性集不相交 即AS X AI X 其中 AS X X a p X P X a AF p AI X X a q Y X P X a AF q 例5 1简单赋值语句文法的属性文法 属性文法中的一些限制 在属性文法中 由于每个非终结符号的属性都由若干文法符号的属性通过相应的属性规则来定义 所以 就不能排除某文法符号的属性由其自身定义的可能性 为避免这种情况的发生 我们需对属性文法作一定的限制 定义5 5对于L G 中每个句子所对应的语法树T 若其每个结点标记符号的所有属性之值均可有效地计算 则称相应属性文法AG是良定义的 此外 若所有条件B p 均取true值 则称L G 中的这个句子是正确赋予属性的 或称T是可加注的 从定义5 5可以看出 在良定义属性文法的任何语法树中 不会出现属性依赖于自身的现象 属性依赖关系 定义5 6对于每个产生式p X0 X1X2 Xn P 直接属性依赖关系由下式给出 DDP p Xi a Xj b Xj b f Xi a R p 若序偶 Xi a Xj b DDP p 则称属性Xj b依赖于属性Xi a 记作Xi a Xj b 显然 若有Xi a Xj b 则对Xj b的计值 应在求出Xi a的值之后进行 但若Xi a又直接或间接地依赖于Xj b 则称属性Xi a和Xj b是循环依赖的 含有属性循环依赖的属性文法AG 其中的一些属性之值将不能得到有效的计算 依赖关系图 定义5 7设T是L G 中一个句子相应的加注语法树 并设在构造T时使用过产生式p X0 X1X2 Xn 对于T中由X0 X1 X2 Xn所标记的每个结点 若有 Xi a Xj b DDP p 则在树中引一条从到的有向边 由此而得到的树称之为该句子的属性化语法树 所有这样的有向边构成的集合DT T 称为树T上的依赖关系 根据DT T 所构造的关系图称为依赖关系图 或简称为依赖图 例如 对于例5 1所给文法下的一个句子x y z 相应属性化语法树的依赖关系如P191图5 3所示 属性文法的良定义性判别 有了属性化的语法树及其依赖关系图 我们就可根据图中是否有回路来确定一属性文法是否是良定义的 定理5 1一个属性文法是良定义的 当且仅当对于它的每棵语法树T 相应的依赖关系图是一个无回路有向图 directedacyclicgraph 从P191图5 3可以看出 该语法树相应的依赖关系DT T 未出现回路 通过对其文法的验证 可知该属性文法是良定义的 为便于设计编译程序 实际工作中我们只处理良定义的属性文法 至于有关良定义文法的判定算法 读者可参阅文献18 5 2 2属性翻译文法 由于属性文法的抽象性和属性定义的任意性 当我们把它用于进行语义翻译时 就会发现仅有属性文法是不够的 须在属性文法的基础上做进一步的工作 首先 我们应对文法的属性依赖关系作出限制 不允许出现属性的直接或间接的循环定义 即要求属性文法是良定义的 其次 我们还应将属性规则改造为计算属性值的语义程序 即将静态的规则改写为可动态执行的语义动作 经过这样的改造后 我们就可得到一种新的文法 属性翻译文法 翻译文法的定义 定义5 8在文法产生式右部适当的位置上插入语义动作而得的新文法称为翻译文法或增广文法 AugmentedGrammar 在一翻译文法中 若每个产生式右部中的全部语义动作均出现在所有文法符号的右边 则称这样的翻译文法为波兰翻译文法 为了区分文法符号与语义动作 在本书中我们用一对花括号 及 将插入的语义动作括起来 语义动作采用C语言格式书写 而且 我们还把语义动作视为翻译文法中的一个 符号 称为动作符号 插入语义动作后 翻译文法产生式的一般形式为 A statement V 翻译文法 续 翻译文法的作用是 在进行语法分析时 无论是用产生式进行推导还是进行归约 只要遇到其中带有语义动作的花括号 就要求编译系统自动执行花括号内指定的语义动作 在执行完该动作之后才继续进行下一步的语法分析 例 Expr TermExpr Expr Term WriteCode Expr Term FactorTerm Term Factor WriteCode Term Factor operand WriteCode yytext Expr 递归下降分析中的翻译文法 若用递归下降法进行语法分析 则与非终结符号Expr 相对应的递归程序可扩充为 intEprim if CurrentToken if Term WriteCode if Eprim return1 elsereturn0 if CurrentToken CurrenToken return1 elsereturn0 属性翻译文法的定义 定义5 9属性翻译文法 AttributeTranslationGrammar 简记为ATG 是具有以下性质的翻译文法 1 每个文法符号和语义动作符X都有一个相关的有限属性集合A X 且每个属性都有一个允许值的集合 属性的值域 可以是无限集 2 非终结符和动作符的属性可分为继承属性与综合属性两类 3 继承属性的定义规则为 开始符号的继承属性具有指定的初始值 对于给定的产生式p Y X1X2 Xn P Xi的继承属性值由p中其它符号的属性值进行计算 Xi a f Y b Xk1 ak1 Xkm akm i k1 km 4 综合属性的定义规则为 对于给定的产生式p Y X1X2 Xn P Y的综合属性值由p中某些符号的属性计算 Y u f Y v Xk1 ak1 Xkm akm 1 kj n 对于动作符号 其综合属性值由该动作符的其它属性计算 终结符的综合属性具有指定的初始值 对属性文法的一些限制 定义5 10一属性翻译文法称为是L 属性的 当且仅当对其中的每个产生式p A X1X2 Xn 下面的三个条件成立 1 右部符号Xi 1 i n 的继承属性之值 仅依赖于X1 X2 Xi 1的任意属性或A的继承属性 2 左部符号A的综合属性之值仅依赖于A的继承属性或 和 右部符号Xi 1 i n 的任意属性 3 对一动作符号而言 其综合属性之值是以该动作符号的继承属性或产生式右部符号的任意属性为变元的函数 方法符号属性的求值顺序 A的继承属性 AI A X1的继承属性 AI X1 X1的综合属性 AS X1 进入X1的子树后 返回时求出 Xn的继承属性 AI Xn Xn的综合属性 AS Xn 进入Xn的子树后 返回时求出 A的综合属性 AS A 返回到A的上层 表达式属性翻译文法 例5 2表达式属性翻译文法 Program 1 2 NewName Expr FreeName 0 Program Expr TermExpr Expr 1 2 NewName Term printf s s s n 0 0 FreeName 0 Expr Term FactorTerm Term 1 2 NewName Factor printf s s s n 0 0 FreeName 0 Term Factor Number printf s s n yytext S 属性文法的定义 定义5 11满足下面三个条件的属性文法称为S 属性文法 所有非终结符只具有综合属性 在一个产生式中 每一个符号的各个综合属性的定义互不依赖 在一个产生式中 若某个文法符号X具有继承属性 则此继承属性之值仅依赖于该产生式右部且位于X左边的符号之属性 显然 S 属性文法也满足L 属性文法的条件 这就是说 S 属性文法一定是L 属性文法 而且还要求每个非终结符只具有综合属性 S 属性文法的例子 例5 3简单算术表达式的S 属性文法 Program Expr printf d n 1 Expr Expr Expr 1 3 Expr Expr 1 3 Expr 2 Number ToIntValue yytext 上面的语义子程序采用了YACC工具中的表示方法 其中 1 2分别表示产生式左部符号 右部的第一个 第二个符号 余类推 的语义属性 波兰翻译文法与S 属性文法 在定义5 8所引入的波兰翻译文法 是将语义动作放在每个产生式的最右边 对应的属性翻译文法一定是S 属性文法 例5 3文法中的语义动作均在各产生式最右侧 所以 该文法是S 属性波兰翻译文法 在本章的后几节 我们将以S 属性波兰翻译文法和自底向上的语法分析为基础 研究常见程序设计语言各类语法结构的语义翻译方法及语义子程序的设计技术