编译原理－何炎祥-第八章.pptVIP

第八章 语法制导翻译法 语法制导翻译法，就是在语法分析的过程中，依随分析的过程，根据每个产生式添加的语义动作进行翻译的方法。 本章介绍语法制导翻译法的基本原理及其在中间代码生成中的应用。 8.1 一般原理和树变换 8.1.1 一般原理 语法制导翻译法（SDTS）由一个源语言、一个目标语言和一组翻译规则组成，这组规则可将任何源语言符号串翻译成对应的目标语言串。SDTS的翻译规则是文法中的产生式再添加上语义动作。 什么叫SDTS？——为每个产生式配一个语义子程序，在语义分析过程中，在选用某个产生式的同时，调用配备的语义子程序来完成相应的翻译工作的一种方法。 8.1 一般原理和树变换 SDTS的形式定义为： SDTS是一个五元组T=(VT, VN, ?, R, S)， 其中，VT是一个有穷的输入字母表，包含源语言中的符号； VN是一个有穷的非终结符号集合； ?是一个有穷的输出字母表，?包含出现在翻译串或输出串中的那些符号； R是形如A?w, y的规则的有穷集合，w是由终结符和（或）非终结符组成的串，y是由VN和（或）?中的符号组成的串； S?VN是一个开始符号，其含义和用法如同CFG中的开始符号。 8.1 一般原理和树变换 翻译模式的定义如下： ① (S, S)是一个翻译模式，且这两个S是相关的（S是SDTS的开始符号）。 ② (aAb, a?Ab?)是一个翻译模式，且两个A是相关的；此外，若A?g, g?是R中的一条规则，那么(agb, a?g?b?)也是一个翻译模式。规则中g和g?的非终结符之间的相关性也必须带进这种翻译模式之中。 8.1 一般原理和树变换 8.1.2 树变换 语法制导的翻译过程可用语法树来说明，可看做从一棵树到另一棵树的变换，其变换过程如下： ① 从中剪掉终结符号结点； ② 根据适当的翻译规则，重排每个中间结点的孩子； ③ 添加对应于输出符号集?中的终结符结点。 8.2 简单SDTS和自上而下翻译器 如果每一规则的翻译成分中，非终结符出现的次序与它们在源成分出现的次序相同，则称一个SDTS是简单的（simple）。 定理8.1 如果T=(VN, VT, ?, R, S)是其基础源文法为LL(k)的简单SDTS，那么，存在一个自上而下的确定的下推翻译器PDT(Push–Down Translater)，它接收T的输入语言中的任何符号串并产生对应的输出串。 8.2 简单SDTS和自上而下翻译器 PDT P的定义如下： P的一个构形是一个四元组（q, x, y, z），其中，q是它的有穷控制器的状态，x是尚待扫描的输入串，y是下推栈，z是此时被打印出的输出符号串。于是，在某次移动中，便有 (q, ax, Yy?, z)├ (r, x, gy?, zz?) 其中，存在一条翻译器规则 ?(q, a, Y)包含(r, g, z?) 8.2 简单SDTS和自上而下翻译器 如果P满足下述两个条件，则称P是确定的： ① 对所有的状态q，输入串a和栈符号Z, ?(q, a, Z)至多只包含一个元素。 ② 若?(q, ?, Z)非空，则不存在符号a(a??)使得?(q, a, Z)非空，即对于某个状态和栈符号，在空移动和非空移动之间不应存在冲突。 如果SDTS的基础源文法是二义性的，那么就不存在确定的PDT。若SDTS的基础源文法是LL(1)，那么，它的PDT是确定的，而且对每一个可接收的输入串恰好存在一个翻译。 8.3 简单后缀SDTS和自下而上翻译器 如果一个SDTS是简单的，而且它的每个翻译规则都有下述形式：A?a0B1a1B2a2…Bkak，B1B2…Bkw 除了最右边的w之外，（输出）终结符不可能出现在翻译成分之中，那么，称这个SDTS为简单后缀的(Simple Post Fix)。 定理8.2 对其基础源文法为LR(k)的每一简单后缀的SDTS，存在一确定的LR(k) PDT, ①它接收从该基础源文法可推导出的每一句子；②它将这种句子的翻译作为输出。 8.3 简单后缀SDTS和自下而上翻译器 8.3.1 后缀翻译 8.3.2 IF–THEN–ELSE控制语句 将原来的单一产生式拆成三个产生式 引进含“then”和“else”关键字的产生式 使用空产生式来实现 8.3.3 函数调用 8.4 抽象语法树的构造 抽象语法树AST（Abstract-Syntax Tree）是某个语言结构的一种简洁的树形表示形式，它只需包含该结构尚须转换或归约的信息。任何语法结构（例如表达式、控制结构和说明）都可以用AST表示。 AST也可作为一个多遍编译程序的中间语言结构。采用AST表示法有助于代码的