第五章语法割导翻译 中间代码生成
第五章 语法制导翻译及 中间代码生成
5.1引言 ·词法分析与语法分析仅仅是编译程序的一小部分。 ·在早期的一些编译程序中,是在语法分析的基础上根据源 程序中各语法成份的语义,直接产生机器语言或汇编语言 形式的目标代码。 ·现在的编译系统一般都将经过语法分析的源程序先翻译为 某种形式的中间语言代码,然后再将其翻译为目标代码。 ·优点: -使编译程序各组成部分功能更单一; -使得编译程序的逻辑结构更为清晰,从而 -使编译程序更易于编写与调整;同时 一为代码优化和程序的可移植性提供了条件
5.1 引言 • 词法分析与语法分析仅仅是编译程序的一小部分。 • 在早期的一些编译程序中,是在语法分析的基础上根据源 程序中各语法成份的语义,直接产生机器语言或汇编语言 形式的目标代码。 • 现在的编译系统一般都将经过语法分析的源程序先翻译为 某种形式的中间语言代码,然后再将其翻译为目标代码。 • 优点: –使编译程序各组成部分功能更单一; –使得编译程序的逻辑结构更为清晰,从而 –使编译程序更易于编写与调整;同时 –为代码优化和程序的可移植性提供了条件
5.1引言(续) ·本章要讨论的中间代码生成,是指把单词符号串形式的源程序转换为 另一种等价的便于代码优化处理和目标代码生成表示。 ·目前常见的中间语言有逆波兰表示、三元式、四元式等等。 ·遗憾的是,中间代码生成与语言的语义密切相关,而语义的形式化描 述是一个非常困难的; ·存在一种称为语法制导翻译的模式,这种模式实际上是对前后文无关 文法的一种扩充。 ·方法:对文法中的每个产生式都附加一个语义动作或语义子程序,在语 法分析过程中,每当需要使用一个产生式进行推导或归约,语法分析 程序除执行相应的语法分析动作外,还要执行相应的语义动作或调用 相应的语义子程序
5.1 引言(续) • 本章要讨论的中间代码生成,是指把单词符号串形式的源程序转换为 另一种等价的便于代码优化处理和目标代码生成表示。 • 目前常见的中间语言有逆波兰表示、三元式、四元式等等。 • 遗憾的是,中间代码生成与语言的语义密切相关,而语义的形式化描 述是一个非常困难的; • 存在一种称为语法制导翻译的模式,这种模式实际上是对前后文无关 文法的一种扩充。 • 方法:对文法中的每个产生式都附加一个语义动作或语义子程序,在语 法分析过程中,每当需要使用一个产生式进行推导或归约,语法分析 程序除执行相应的语法分析动作外,还要执行相应的语义动作或调用 相应的语义子程序
5.1引言(续) 。 这种模式既把语法分析与语义处理分开,又令其平行地进 行,让其在同一遍扫描中同时完成语法分析和语义处理两 项工作。 ·由此可见,抽象文法符号的具体语义信息,是在与语法分 析同步的语义处理过程中获取和加工的。 ● 文法符号X的语义信息我们称之为语义属性或简称为属性 (Attributes) ·我们用形处X.ATTR的记号来表示文法符号X的相关语义属 性。 ·如果一个文法符号人在一产生式中多次出现,为了在语义 上能够对其进行区分,可冻加不同的上标
5.1 引言(续) • 这种模式既把语法分析与语义处理分开,又令其平行地进 行,让其在同一遍扫描中同时完成语法分析和语义处理两 项工作。 • 由此可见,抽象文法符号的具体语义信息,是在与语法分 析同步的语义处理过程中获取和加工的。 • 文法符号X的语义信息我们称之为语义属性或简称为属性 (Attributes)。 • 我们用形如X.ATTR的记号来表示文法符号X的相关语义属 性。 • 如果一个文法符号X在一产生式中多次出现,为了在语义 上能够对其进行区分,可添加不同的上标
文法符号及其语义属性 ·例如,文法GE: 产生式 语义子程序 E→E(1)+T E.Val=E(1).val+T.val;) 语法分 语义分 析栈 析栈 E→T{E.Val=T.Val;} T T.Val T→digit {T.Val=digit; + ·为了能在语法分析过程中平行地进行语义 处理,可在语法分析栈旁边并行地设置一 E 个语义信息栈 #
文法符号及其语义属性 • 例如,文法G[E]: 产生式 语义子程序 E→E(1)+T {E.Val=E(1) .val+T.val;} E→T {E.Val=T.Val;} T→digit {T.Val=digit;} • 为了能在语法分析过程中平行地进行语义 处理,可在语法分析栈旁边并行地设置一 个语义信息栈 语法分 析栈 语义分 析栈 T T.Val + ‘+’ E … … #
本章内容简个 ·本章,我们首先介绍一种适用于定义语义 的一种特殊文法一属性文法,并进一步介 绍适用于语义翻译的文法一属性翻泽文法 的相关知识。 ·在第三小节中我们将介绍几种常见的中向 语言; ·在第四小节中引入程序设计语言中常见语 法结构的语法制导翻译技术
本章内容简介 • 本章,我们首先介绍一种适用于定义语义 的一种特殊文法⎯属性文法,并进一步介 绍适用于语义翻译的文法⎯属性翻译文法 的相关知识。 • 在第三小节中我们将介绍几种常见的中间 语言; • 在第四小节中引入程序设计语言中常见语 法结构的语法制导翻译技术
5.2属性文法与属性翻泽女法 ·语法制导翻泽方法的实质,就是根据文法中每个产生 式所蕴含的语义,为其配备一个(或多个)处理语句 或子程序,对所要完成的功能进行描述。 ·语义子程序的编写质量决定了语义翻译的准确性和有 效性。所以,产生式相应语义子程序的正确性是能够 进行正确语义翻译的先决条件。 。 产生式的语义是由组成该产生式的文法符号的语义 所决定的。 。 我们可将这些语义以“属性”的形式附加到各个文法 符号上,再根据产生式所蕴含的语义,给出每个文法 符号的属性的求值规则,从而形成一种附带有语义属 性的前后文无关文法,即属性文法
5.2 属性文法与属性翻译文法 • 语法制导翻译方法的实质,就是根据文法中每个产生 式所蕴含的语义,为其配备一个(或多个)处理语句 或子程序,对所要完成的功能进行描述。 • 语义子程序的编写质量决定了语义翻译的准确性和有 效性。所以,产生式相应语义子程序的正确性是能够 进行正确语义翻译的先决条件。 • 产生式的语义是由组成该产生式的文法符号的语义 所决定的。 • 我们可将这些语义以“属性”的形式附加到各个文法 符号上,再根据产生式所蕴含的语义,给出每个文法 符号的属性的求值规则,从而形成一种附带有语义属 性的前后文无关文法,即属性文法
5.2.1语义属性与属性文法 ·定义5.1一文法符号的语义性质称为该文法符号的 语义属性(Attributes),简称为属性。我们用AX) 表示X的所有属性的集合。每个属性表示X的一个特 定性质,并可任意指定其取值范围。我们用X.a表示 A(闪中的属性a。 ·属性可表征诸如数、符号串、类型、存储空间和其它 需表征的实体。 。 终结特至少有一种属性,即词文。当然,它还可能具 有其它属性,例如无符号数123,单词“123”就是它 的词文,而其数值以及它的类型(整型)是它的其它 两个属性。终结符的属性是其内在性质, ·非终结特的属性是从其它符号的属性经计算而得的, 即由其它符号的属性定义的
5.2.1 语义属性与属性文法 • 定义 5.1 一文法符号的语义性质称为该文法符号的 语义属性(Attributes),简称为属性。我们用A(X) 表示X的所有属性的集合。每个属性表示X的一个特 定性质,并可任意指定其取值范围。我们用X.a表示 A(X)中的属性a 。 • 属性可表征诸如数、符号串、类型、存储空间和其它 需表征的实体。 • 终结符至少有一种属性,即词文。当然,它还可能具 有其它属性,例如无符号数123,单词“123”就是它 的词文,而其数值以及它的类型(整型)是它的其它 两个属性。终结符的属性是其内在性质. • 非终结符的属性是从其它符号的属性经计算而得的, 即由其它符号的属性定义的
属性依赖关系 各个文法符号的属性之间,可能存在某种依赖关系,这种依 赖关系可用属性规则(语义视则)定义。 定义5.2设p:X。→XX2Xn是文法G的一个产生式,则与p相 关联的属性规则集 Rp)=tK.a=f(Xkr aki,Xkmr dk)/X.a∈A(K月 定义了该产生式所涉及的文法符号之属性的求值规则,它表 示:X的a属性是由的Xk1的ak1属性,.,的Xka的akm属性计 算而得的
属性依赖关系 各个文法符号的属性之间,可能存在某种依赖关系,这种依 赖关系可用属性规则(语义规则)定义。 定义 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.X,设属性定义 性出现的集合为 AF(p)=(Xi.a Xi.a=f(Xkl.akl,....Xkm akm)E R(p),0≤k;≤n} 若X是产生式左部的非终结符(即=0),则称属性X.a 是综合属性(Synthesized Attributes);若X;出现在 产生式的右部(即1≤i≤n),则称X.a是继承属性 (Inherited Attributes)o
综合属性与继承属性 定义 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 是综合属性(Synthesized Attributes);若Xi出现在 产生式的右部 (即1≤i≤n),则 称Xi.a 是继承属性 (Inherited Attributes)