语法制导翻译概述
什么是语法制导翻译
语法制导翻译使用 CFG(上下文无关文法) 来引导对语言的翻译，是一种面向文法的翻译技术
语法制导翻译的基本思想
如何表示语义信息？
- 为 CFG 中的文法符号设置语义属性，用来表示语法成分对应的语义信息
如何计算语义属性？
将语义规则同语法规则（产生式）联系起来要涉及两个概念
SDD 是对 CFG 的推广
- 将每个文法符号和一个语义属性集合相关联
- 将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值
- 如果 X 是一个文法符号，a 是 X 的一个属性，则用 X.a 表示属性 a 在某个标号为 X 的分析树结点上的值
【例】语法制导 SDD
- 每一个产生式对应一个语义规则
- 第二个产生式的语义规则：设置非终结符 T 的语义属性 type，当产生式右部是终结符 int 时，非终结符 T 的语义属性 type 就是 int；当产生式右部是终结符 real 时，非终结符 T 的语义属性 type 就是 real
- L 和 L1 是同一个非终结符，用下角标区分 L 在不同位置的出现
- 第一个产生式的语义规则：设置非终结符 L 的语义属性 inh，它由 T 的 type 属性定义
第四个产生式的语义规则：设置非终结符 L1 的语义属性 inh，它由 L 的 inh 属性定义
语法制导翻译方案 (SDT)
SDT 是在产生式右部嵌入了程序片段的 CFG，这些程序片段称为语义动作
- 按照惯例，语义动作放在花括号内
【例】语法制导翻译方案 SDT
- 一个语义动作在产生式中的位置决定了这个动作的执行时间
第一个产生式语义动作是指，当分析出 T 之后，就可以使用 T 的 type 属性的值来计算 L 的 inh 属性值
SDD 与 SDT
SDD
- 是关于语言翻译的高层次规格说明
- 隐蔽了许多具体实现细节，使用户不必显式地说明翻译发生的顺序
SDT
语法制导定义 SDD 是对 CFG 的推广
- 将每个文法符号和一个语义属性集合相关联
- 将每个产生式和一组语义规则相关联，用来计算该产生式中各文法符号的属性值
文法符号的属性
在分析树的结点 N 上的非终结符 A 的综合属性只能通过 N 的子结点或 N 本身的属性值来定义
【例】综合属性
- E 是 E1、+、T 的父节点
- E 的 val 属性值是由它的两个子节点 E1 和 T 的属性值来定义的，因此，val 是 E 的一个综合属性
- 终结符可以具有综合属性
终结符的综合属性值是由词法分析器提供的词法值，因此在 SDD 中没有计算终结符属性值的语义规则
继承属性
在分析树结点 N 上的非终结符 A 的继承属性只能通过 N 的父结点、N 的兄弟结点或 N 本身的属性值来定义
【例】继承属性
T 和 L 互为兄弟
- L 的 inh 属性是由 T 的 type 属性定义的，因此，inh 是 L 的一个继承属性
- 终结符没有继承属性
- 终结符从词法分析器处获得的属性值被归为综合属性值
【例】带有综合属性的 SDD
- digit是一个终结符，它的lexval综合属性由词法分析器提供
- E的val综合属性由它的子节点E1和T提供
- T的val综合属性由它的子节点T1和F提供
- F的val综合属性由终结符digit提供
- 语义规则通常写成表达式的形式，用来计算文法符号的属性值，但是有时候，语义规则的目的就是产生一个副作用，比如说打印一个运算结果或者是符号表。这时，语义规则通常被写成过程调用的形式，可以把它看成是用来定义产生式左部文法符号 L 的综合属性的规则，因为它用到了子节点 E 的属性值
- 有了这个 SDD，对于输入句子的分析树，就可以根据语义规则计算树中各个节点的对应的属性值
- 假如现在输入的符号串是3*5+4n，右侧就是它的分析树
- 注释分析树 (Annotated parse tree) ：每个节点都带有属性值的分析树
- 树中标记为digit的三个节点，对应输入串中的 3 个常数，它们的综合属性值是由词法分析器提供的词法值，分别是3、5、4
- 树中标记为F的三个节点，是对第七个产生式的应用，根据第七个产生式的语义规则可以看出F的val值是由子节点digit的lexval值定义，所以它们的属性值分别为3、5、4
- 树中标记为T的两个节点，是对第五个产生式的应用，根据第五个产生式的语义规则可以看出T的val值是由子节点E的val值定义，所以它们的属性值分别为3、4
- 树中标记为T的一个节点，是对第四个产生式的应用，根据第四个产生式的语义规则可以看出T的val值是由它的两个子节点T和E的val值相乘定义，所以它的属性值分别为15
- 树中标记为E的一个节点，是对第三个产生式的应用，根据第三个产生式的语义规则可以看出E的val值是由子节点T的val值定义，所以它的属性值分别为15
- 树中标记为E的一个节点，是对第二个产生式的应用，根据第二个产生式的语义规则可以看出E的val值是由它的两个子节点E和T的val值相加定义，所以它的属性值分别为19
- 树中标记为E的一个节点，是对第一个产生式的应用，根据第一个产生式的语义规则可以看出该规则用于产生一个副作用，也就是说打印E的val值，那么，可以把它看作对产生式左部符号L的虚综合属性进行定义的规则，因为它用到了子节点E的val值
【例】带有继承属性的 SDD
- 由第一个和第四个产生式可以看出，L的inh属性由它的兄弟节点T和父节点L定义，因此，inh是L的一个继承属性
- 在第四个和第五个产生式的语义规则中，存在副作用addtype，其中终结符id的综合属性lexeme是由词法分析器提供的词法值，它表示，构成标识符id的字符序列。这个副作用的功能是在符号表中为标识符id.lexeme创建一条记录并且将标识符id的类型设置为L.inh所表示的类型。由于在这个副作用中使用了L的子节点id和它自身的属性值，因此，这个副作用可以看作是定义产生式左部符号L的虚综合属性的一条语义规则
有了这个 SDD，对于输入句子的分析树，就可以根据语义规则计算树中各个节点的对应的属性值
一个没有副作用的 SDD 有时也称为属性文法
- 属性文法的规则仅仅通过其它属性值和常量来定义一个属性值
SDD 的求值顺序
- SDD 为 CFG 中的文法符号设置语义属性
- 对于给定的输入串 x，应用语义规则计算分析树中各结点对应的属性值
按照什么顺序计算属性值？
依赖图是一个描述了分析树中结点属性间依赖关系的有向图
- 分析树中每个标号为 X 的结点的每个属性 a 都对应着依赖图中的一个结点
- 如果属性 X.a 的值依赖于属性 Y.b 的值，则依赖图中有一条从 Y.b 的结点指向 X.a 的结点的有向边
【例】注释分析树对应的依赖图
- 将继承属性放在语法分析树中对应结点的左边；将综合属性放在语法分析树中对应结点的右边
- 由第一个产生式的语义规则可以看出：L的in属性依赖T的type属性，因此，依赖图中有一条T结点的type属性指向L结点的in属性的一条有向边
由第四个产生式的第二条语义规则用来生成一个副作用，也就是说，在符号表中将id.lexme所代表的标识符的类型设置为L.in的类型，可以看作是定义产生式左部的非终结符L的一个虚综合属性的规则。在依赖图中为L设置一个虚综合属性，该属性由它的子节点id的lexeme属性和它自身的in属性，因此，在依赖图中分别从L的in属性和id的lexeme属性引出一条指向L的虚综合属性的有向边
属性值的计算顺序
可行的求值顺序是满足下列条件的结点序列 N1, N2, … , Nk ：如果依赖图中有一条从结点 Ni 到 Nj 的边 (Ni→Nj), 那么 i < j（即：在节点序列中，Ni 排在 Nj 前面）
- 这样的排序将一个有向图变成了一个线性排序，这个排序称为这个图的拓扑排序 (topological sort)
【例】拓扑排序
- 先计算出 1234，然后由 4 计算出 5，再由 53 计算出 6，由 5 计算出 7，由 72 计算出 8，……
- 因为 1234 结点互不依赖，所以内部顺序可随意调换，……
- 对于只具有综合属性的 SDD ，可以按照任何自底向上的顺序计算它们的值
- 对于同时具有继承属性和综合属性的 SDD，不能保证存在一个顺序来对各个节点上的属性进行求值
【例】同时具有继承属性和综合属性的 SDD
- s 是 A 的综合属性，s 由 A 的子节点 B 的 i 属性定义；i 是 B 的继承属性，i 由 B 的父节点 A 的 s 属性定义
- 依赖图中存在环，无法确定一个顺序来对各个节点上的属性进行求值
- 从计算的角度看，给定一个 SDD，很难确定是否存在某棵语法分析树，使得 SDD 的属性之间存在循环依赖关系
- 幸运的是，存在一个 SDD 的有用子类，它们能够保证对每棵语法分析树都存在一个求值顺序，因为它们不允许产生带有环的依赖图
不仅如此，接下来介绍的两类 SDD 可以和自顶向下及自底向上的语法分析过程一起高效地实现
仅仅使用综合属性的 SDD 称为 S 属性的 SDD，或 S - 属性定义、S-SDD
【例】S - 属性定义
- 如果一个 SDD 是 S 属性的，写就是说它的结点的属性值都依赖与它的子结点的属性值，那么，就可以按照语法分析树节点的任何自底向上顺序来计算它的各个属性值
-
L - 属性定义
L - 属性定义 (也称为 L 属性的 SDD 或 L-SDD) 的直观含义：
- 在一个产生式所关联的各属性之间，依赖图的边可以从左到右，但不能从右到左 (因此称为 L 属性的，L 是 Left 的首字母)
- L-SDD 的正式定义：
- 一个 SDD 是 L - 属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：
- 假设存在一个产生式 A→X1X2…Xn，其右部符号 Xi (1 ≤ i ≤ n) 的继承属性仅依赖于下列属性：
- 父节点 A 的继承属性
- 产生式中 Xi 左边的符号 X1, X2, … , Xi-1 的属性
- Xi 本身的属性，但 Xi 的全部属性不能在依赖图中形成环路
- 假设存在一个产生式 A→X1X2…Xn，其右部符号 Xi (1 ≤ i ≤ n) 的继承属性仅依赖于下列属性：
- 一个 SDD 是 L - 属性定义，当且仅当它的每个属性要么是一个综合属性，要么是满足如下条件的继承属性：
- 每个 S - 属性定义都是 L - 属性定义
【思考】为什么右部符号 Xi (1 ≤ i ≤ n) 的继承属性仅依赖于父节点 A 的继承属性，而不能是父节点 A 的综合属性？
- 因为父节点 A 的的综合属性 s 依赖于子节点的继承属性 i 和综合属性 s，如果子节点 Xi 的继承属性 i 再依赖于父节点的综合属性 s，就会造成循环依赖，因此，子节点的继承属性只能依赖于父节点的继承属性而不能依赖于父节点的综合属性
【例】L - 属性定义
- 第一个产生式的第一个语法规则中 T’的 inh 属性仅依赖于它左边的 F 的属性值，不违反 L-SDD 的定义中对继承属性的限制
- 第二个产生式的第一个语法规则中 T’的 inh 属性仅依赖于它的父节点 T’的 inh 属性和它左边的 F 的 val 属性，不违反 L-SDD 的定义中对继承属性的限制
【例】非 L - 属性定义
第二个产生式的第二个语法规则中 Q 的 i 属性依赖于它右边的 R 的 s 属性，违反了 L-SDD 的定义中对继承属性的限制
语法制导翻译方案 SDT
语法制导翻译方案 (SDT) 是在产生式右部中嵌入了程序片段 (称为语义动作) 的 CFG
- SDT 可以看作是 SDD 的具体实施方案
- 本节主要关注如何使用 SDT 来实现两类重要的 SDD，因为在这两种情况下，SDT 可在语法分析过程中实现
- 基本文法可以使用 LR 分析技术，且 SDD 是 S 属性的
- 基本文法可以使用 LL 分析技术，且 SDD 是 L 属性的
S-SDD 转换为 SDT
- 将一个 S-SDD 转换为 SDT 的方法：将每个语义动作都放在产生式的最后
- 因为 S-SDD 中的所有属性都是综合属性，只有当所有的子节点都分析完毕以后才可以计算父节点的综合属性，所以语义动作都放在产生式的最右边
S-SDD 的 SDT 实现
- 如果一个 S-SDD 的基本文法可以使用 LR 分析技术 (自底向上)，那么它的 SDT 可以在 LR 语法分析过程中实现
【例】S-SDD 的 SDT 实现
- 该 S-SDD 的基础文法是 LR 文法，可以用 LR 分析技术进行语法分析
- 当归约发生时执行相应的语义动作
扩展的 LR 语法分析栈：
将语义动作中的抽象定义式改写成具体可执行的栈操作：
- A 的综合属性 a 由它的子节点 X、Y、Z 的 x、y、z 属性定义
- 因为语义动作在产生式的最后，所以当把 x、y、z 归约为 A 时，该语义动作将执行
- 归约前，栈顶 top 存放 Z 对应的记录，top-1 存放 Y 对应的记录，top-2 存放 X 对应的记录；归约以后，XYZ 出栈，A 进栈，存放在 X 所在的位置，top-2 成为新的栈顶 top
【例】S-SDD 的 SDT 实现中的语法分析栈变化
- 初始时，语法分析栈中状态为 0，符号是栈底标记符 $，属性是空
- 输入指针指向输入串中的第一个符号 3，状态 0 遇到数字 digit，采取移入动作后进入状态 5，d 的 lexval 属性值是由词法分析器提供的词法值，也就是 3
- 状态 5 是一个归约状态：将 d 归约成 F，根据第七个产生式的语义规则：F 的属性值等于 digit 的属性值，所以属性栈不做操作，只将状态 5 和符号 d 出栈即可，然后将 F 进栈；状态 0 遇到 F，进入状态 3：
- 状态 3 是一个归约状态：将 F 归约成 T，属性栈不做操作，将状态 3 和符号 F 出栈，T 进栈，状态 0 遇到 T，进入状态 2：
- 输入指针指向输入串中的下一个符号，状态 2 遇到，*入栈，状态 7 入栈，无属性值：
- 输入指针指向输入串中的下一个符号 5，状态 7 遇到 digit，d 入栈、状态 5 入栈，属性值 5；归约：d 出栈、状态 5 出栈，F 入栈；状态 7 遇到 F，状态 10 入栈；
- 状态 10 归约：将 T 的属性值 3 与 F 的属性值 5 相乘作为 T 的属性值 15，状态 2、7、10 出栈，符号 T、*、F出栈，属性 5 出栈，符号 T 入栈，状态 0 遇到 T，状态 2 入栈：
- ……
- 最终结果：
L-SDD 转换为 SDT
- 将计算某个非终结符号 A 的继承属性的动作插入到产生式右部中紧靠在 A 的本次出现之前的位置上
- 将计算一个产生式左部符号的综合属性的动作放置在这个产生式右部的最右端
L-SDD 的 SDT 实现
- 如果一个 L-SDD 的基本文法可以使用 LL 分析技术 (自顶向下)，那么它的 SDT 可以在 LL(自顶向下) 或 LR(自底向上)语法分析过程中实现，LL 分析具体又分为两种清况：
- 在非递归的预测分析过程中进行语义翻译
- 在递归的预测分析过程中进行语义翻译
【例】L-SDD 的 SDT 实现
因为具有相同左部 T’的产生式 2 和 3 的 SELECT 集互不相交，所以该 S-SDD 的基础文法是 LL 文法，可以用 LR 分析技术进行语法分析
在非递归的预测分析过程中进行翻译
扩展语法分析栈：
因为继承属性是在它即将出现时计算，综合属性是当它的所有子节点都分析完毕以后才可以计算，所以将继承属性和综合属性分开存放
- A 的继承属性就存放在它本身的记录中；A 的综合属性存放在它本身的记录之下
【例】在非递归的预测分析过程中 (自顶向下) 进行翻译
- 将 6 个语义动作分别起名叫 a1-a6
- 初始时刻，语法分析栈中只有文法的开始符号 T，因为 T 没有继承属性，所以 T 记录的属性字段为空；因为 T 有综合属性，所以 T 记录的下一个字段 Tsyn 的属性字段值为 val；
- 输入指针指向输入串中的第一个符号 3，根据第一个产生式，将 T 替换成 F{a1}T’{a2}：T 出栈，因为 T 的综合属性 val 要等即将进栈的子节点 T’分析完毕才可以计算，所以 Tsyn 不出栈，F{a1}T’{a2} 进栈：
- 栈顶非终结符 F 替换成 digit{a6}，digit 的属性值由词法分析器提供，也就是 3，与当前输入指针指向的 3 匹配成功，digit 出栈；由语义动作 a6 可知，要用 digit 的属性值计算 E 的属性值，所以 digit 出栈前，要将属性值备份到 {a6} 字段中：
- 执行 {a6} 的栈操作：将 digit 的属性值给 F 的 val 属性，{a6}出栈，由语义动作 a1 可知，要用 F 的属性值计算 T’的属性值，所以 F 出栈前，要将属性值备份到 {a1} 字段中，执行 {a1} 的栈操作：将 F 的属性值给 T’的 inh 属性，{a1}出栈：
- 输入指针指向输入串中的下一个符号，选择产生式 2，栈顶非终结符 T’替换成{a3}T1’{a4}，由语义动作 a3 可知，要用 T’的属性值计算 T1’的属性值，所以 T’出栈前，要将 T’的属性值存到 {a3} 中：
- 栈顶与当前输入指针指向的匹配成功，*出栈；输入指针指向输入串中的下一个符号 5，选择产生式 4，栈顶非终结符 F 替换成 digit{a6}，digit 的属性值由词法分析器提供，也就是 5，与当前输入指针指向的 5 匹配成功，digit 出栈；由语义动作 a6 可知，要用 digit 的属性值计算 E 的属性值，所以 digit 出栈前，要将属性值备份到 {a6} 字段中，输入指针指向输入串中的下一个符号$：
- 执行 {a6} 的栈操作，……
- 最终结果：
- 分析栈中的每一个记录都对应着一段执行代码
- 综合记录出栈时，要将综合属性值复制给后面特定的语义动作
- 变量展开时（即变量本身的记录出栈时），如果其含有继承属性，则要将继承属性值复制给后面特定的语义动作
【例】一个 SDT 一旦确定，这个 SDT 中各个符号对应的执行代码也就确定
在递归的预测分析过程中进行翻译
- 为每个非终结符 A 构造一个函数，A 的每个继承属性对应该函数的一个形参，函数的返回值是 A 的综合属性值。对出现在 A 产生式中的每个文法符号的每个属性都设置一个局部变量
- 非终结符 A 的代码根据当前的输入决定使用哪个产生式
- 与每个产生式有关的代码执行如下动作：从左到右考虑产生式右部的词法单元、非终结符及语义动作
- 对于带有综合属性 x 的词法单元 X，把 x 的值保存在局部变量 X.x 中；然后产生一个匹配 X 的调用，并继续输入
- 对于非终结符 B，产生一个右部带有函数调用的赋值语句 c := B(b1 , b2 , …, bk)，其中， b1 , b2 , …, bk 是代表 B 的继承属性的变量，c 是代表 B 的综合属性的变量
- 对于每个动作，将其代码复制到语法分析器，并把对属性的引用改为对相应变量的引用
L-SDD 的自底向上翻译
- 给定一个以 LL 文法为基础的 L-SDD，可以修改这个文法，并在 LR 语法分析过程中计算这个新文法之上的 SDD
- 首先构造 SDT，在各个非终结符之前放置语义动作来计算它的继承属性， 并在产生式后端放置语义动作计算综合属性
- 对每个内嵌的语义动作，向文法中引入一个标记非终结符来替换它。每个这样的位置都有一个不同的标记，并且对于任意一个标记 M 都有一个产生式 M→ε
- 如果标记非终结符 M 在某个产生式 A→α{a}β中替换了语义动作 a，对 a 进行修改得到 a’，并且将 a’关联到 M→ε 上。动作 a’
- 将动作 a 需要的 A 或α中符号的任何属性作为 M 的继承属性进行复制
- 按照 a 中的方法计算各个属性，但是将计算得到的这些属性作为 M 的综合属性
若有收获，就点个赞吧
0 人点赞
