第五章语法制导的翻译 陈林
引言 使用上下文无关文法引导语言的翻译 CFG 的非终结符号代表了语言的某个构造 程序设计语言的构造由更小的构造组合而成 一个构造的语义可以由小构造的含义综合而来 比如 : 表达式 x+y 的类型由 x y 的类型和运算符 + 决定 也可以从附近的构造继承而来 比如 : 声明 int x; 中 x 的类型由它左边的类型表达式决定
语法制导定义和语法制导翻译 语法制导定义 将文法符号和某些属性相关联 并通过语义规则来描述如何计算属性的值 E E 1 +T E.code=E 1.code T.code + 属性 code 代表中缀表达式的逆波兰表示 ( 后缀表示法 ), 规则说明加法表达式的逆波兰表示由两个分量的逆波兰表示并置, 然后加上 + 得到 语法制导翻译 在产生式体中加入语义动作, 并在适当的时候执行这些语义动作 E E 1 +T {print + ;}
语法制导的定义 (SDD) SDD 是上下文无关文法和属性 / 规则的结合 属性和文法符号相关联, 按照需要来确定各个文法符号需要哪些属性 规则和产生式相关联 对于文法符号 X 和属性 a, 用 X.a 表示分析树中的某个标号为 X 的结点的值 一个分析树结点和它的分支对应于一个产生式规则, 而对应的语义规则确定了这些结点上的属性的取值
分析树和属性值 (1) 假设我们需要知道一个表达式的类型, 以及对应代码将它的值存放在何处, 我们就需要两个属性 :type, place 产生式规则 :E E 1 +T 语义规则 :( 假设只有 int/float 类型 ) E.type = if (E 1.type==T.type) T.type else float E.place = newtempplace(); // 返回一个新的内存位置 ; 产生式规则 :F id F.type = lookupidtable(id.lexvalue)->type; F.place = lookupidtable(id.lexvalue)->address;
分析树和属性值 (2) E E.Type = FLOAT E.Place = &tmp2 E.Type = FLOAT E.Place = &a E + T T.Type = INT T.Place = &tmp T.Type = FLOAT T.Place = &a F.Type = FLOAT F.Place = &a T F T F * F id F.Type = INT F.Place = &c id.lexvalue=c 假设 a,b,c 是已经声明的全局变量,a 的类型为 FLOAT,b,c 的类型为 INT id.lexvalue=a id id id.lexvalue=b 中间未标明的 T 和 F 的 type 和 address 都是 INT 和 &b; a+b*c 的语法分析树以及属性值
继承属性和综合属性 综合属性 (synthesized attribute): 在分析树结点 N 上的非终结符号 A 的属性值由 N 对应的产生式所关联的语义规则来定义 通过 N 的子结点或 N 本身的属性值来定义 继承属性 (inherited attribute): 结点 N 的属性值由 N 的父结点所关联的语义规则来定义 依赖于 N 的父结点 N 本身和 N 的兄弟结点上的属性值 不允许 N 的继承属性通过 N 的子结点上的属性来定义, 但是允许 N 的综合属性依赖于 N 本身的继承属性 终结符号有综合属性 ( 由词法分析获得 ), 但是没有继承属性
SDD 的例子 目标 : 计算表达式行 L 的值 ( 属性 val) 计算 L 的 val 值需要 E 的 val 值 E 的 val 值又依赖于 E 和 T 的 val 值 终结符号 digit 有综合属性 lexval
S 属性的 SDD 只包含综合属性的 SDD 称为 S 属性的 SDD 每个语义规则都根据产生式体中的属性值来计算头部非终结符号的属性值 S 属性的 SDD 可以和 LR 语法分析器一起实现 栈中的状态可以附加相应的属性值 在进行归约时, 按照语义规则计算归约得到的符号的属性值 语义规则不应该有复杂的副作用 要求副作用不影响其它属性的求值 没有副作用的 SDD 称为属性文法
语法分析树上的 SDD 求值 (1) 实践中很少先构造语法分析树再进行 SDD 求值 但在分析树上求值有助于翻译方案的可视化, 便于理解 注释语法分析树 包含了各个结点的各属性值的语法分析树 步骤 : 对于任意的输入串, 首先构造出相应的分析树 给各个结点 ( 根据其文法符号 ) 加上相应的属性值 按照语义规则计算这些属性值即可
语法分析树上的 SDD 求值 (2) 按照分析树中的分支对应的文法产生式, 应用相应的语义规则计算属性值 计算顺序问题 : 如果某个结点 N 的属性 a 为 f(n 1.b 1,N 2.b 2,,N k.b k ), 那么我们需要先算出 N 1.b 1,N 2.b 2,,N k.b k 的值 如果我们可以给各个属性值排出计算顺序, 那么这个注释分析树就可以计算得到 S 属性的 SDD 一定可以按照自底向上的方式求值 下面的 SDD 不能计算 A B A.s=B.i; B.i=A.s+1;
注释语法分析树的例子 3*5+4n
适用于自顶向下分析的 SDD 左递归文法无法直接用自顶向下方法处理
适用于自顶向下分析的 SDD 计算 3*5 所用注释语法树 消除左递归之后, 我们无法直接使用属性 val 进行处理 比如规则 :T FT T *FT T 对应的项中, 第一个因子对应于 F, 而运算符却在 T 中 需要继承属性来完成这样的计算
适用于自顶向下分析的 SDD 注意 :T 的属性 inh 实际上继承了相应的 * 号的左运算分量
3*5 的注释分析树 注意观察 inh 属性是如何传递的
SDD 的求值顺序 在对 SDD 的求值过程中, 如果结点 N 的属性 a 依赖于结点 M 1 的属性 a 1,M 2 的属性 a 2, 那么我们必须先计算出 M i 的属性, 才能计算 N 的属性 a 使用依赖图来表示计算顺序 显然, 这些值的计算顺序应该形成一个偏序关系 如果依赖图中出现了环, 表示属性值无法计算
依赖图 描述了某棵特定的分析树上各个属性实例之间的信息流 ( 计算顺序 ) 从实例 a 1 到实例 a 2 的有向边表示计算 a 2 时需要 a 1 的值 ( 必须先计算 a 2, 再计算 a 1 ) 对于标号为 X 的分析树结点 N, 和 X 关联的每个属性 a 都对应依赖图的一个结点 N.a 结点 N 对应的产生式的语义规则通过 X.c 计算了 A.b 的值, 且在分析树中 X 和 A 分别对应于 N 1 和 N 2, 那么从 N 1.c 到 N 2.b 有一条边
依赖图的例子 3*2 的注释分析树 ; T FT {T.val = T.syn; T.inh = F.val;} 边 e1 e2 可能的计算顺序 : 1,2,3,4,5,6,7,8.9 1,3,5,2,4,6,7,8,9
属性值的计算顺序 各个属性的值需要按照依赖图的拓扑顺序计算 如果依赖图中存在环, 则属性计算无法进行 给定一个 SDD, 很难判定是否存在一棵分析树, 其对应的依赖图包含环 怎样的 SDD 可以和以前所介绍的语法分析结合在一起?
属性值的计算顺序 特定类型的 SDD 一定不包含环, 且有固定排序模式 S 属性的 SDD L 属性的 SDD 对于这些类型的 SDD, 我们可以确定属性的计算顺序, 且可以把不需要的属性 ( 及分析树结点 ) 抛弃以提高效率 这两类 SDD 可以很好地和我们已经研究过的语法分析相结合
S 属性的 SDD 每个属性都是综合属性 都是根据子构造的属性计算出父构造的属性 在依赖图中, 总是通过子结点的属性值来计算父结点的属性值 可以和自顶向下 自底向上的语法分析过程一起计算 自底向上 在构造分析树的结点的同时计算相关的属性 ( 此时其子结点的属性必然已经计算完毕 ) 自顶向下 递归下降分析中, 可以在过程 A() 的最后计算 A 的属性 ( 此时 A 调用的其他过程 ( 对应于子结构 ) 已经调用完毕 )
在分析树上计算 SDD 按照后序遍历的顺序计算属性值即可 postorder(n) { for( 从左边开始, 对 N 的每个子结点 C) postorder(c); // 递归调用返回时, 各子结点的属性计算完毕对 N 的各个属性求值 ; } 在 LR 分析过程中, 我们实际上不需要构造分析树的结点
L 属性的 SDD 每个属性 要么是综合属性 要么是继承属性, 且产生式 A X 1 X 2 X n 中计算 X i.a 的规则只能使用 A 的继承属性 X i 左边的文法符号 X j 的继承属性或综合属性 X i 自身的继承或综合属性, 且这些属性之间的依赖关系不形成环 特点 依赖图的边 继承属性从左到右, 从上到下 综合属性从下到上 在扫描过程中, 计算一个属性值时, 和它相关的依赖属性都已经计算完毕
具有受控副作用的语义规则 属性文法没有副作用, 但增加了描述的复杂度 比如语法分析时如果没有副作用, 标识符表就必须作为属性传递 可以把标识符表作为全局变量, 然后通过副作用函数来添加新标识符 受控的副作用 不会对属性求值产生约束, 即可以按照任何拓扑顺序求值, 不会影响最终结果 或者对求值过程添加简单的约束
受控副作用的例子 L E n print(e.val) 通过副作用打印出 E 的值 总是在最后执行, 而且不会影响其它属性的求值 变量声明的 SDD 中的副作用 addtype 将标识符的类型信息加入到标识符表中 只要标识符不被重复声明, 标识符的类型信息总是正确的
语法制导翻译的应用例子 抽象语法树的构造 基本类型和数组类型的 L 属性定义
构造抽象语法树的 SDD 抽象语法树 每个结点代表一个语法结构 ; 对应于一个运算符 结点的每个子结点代表其子结构 ; 对应于运算分量 表示这些子结构按照特定方式组成了较大的结构 可以忽略掉一些标点符号等非本质的东西 语法树的表示方法 每个结点用一个对象表示 对象有多个域 叶子结点中只存放词法值 内部结点中存放了 op 值和参数 ( 通常指向其它结点 )
构造简单表达式的语法树的 SDD 属性 E.node 指向 E 对应的语法树的根结点
表达式语法树的构造过程 输入 : a-4+c 步骤 : p1=new Leaf(id, entry_a) p2=new Leaf(num, 4); p3=new Node( -, p1,p2); p4=new Leaf(id, entry_c); p5=new Node( +, p3,p4);
自顶向下方式处理的 L 属性定义 (1) 在消除左递归时, 按照规则得到此 SDD
自顶向下方式处理的 L 属性定义 (2) 对于这个 SDD, 各属性值的计算过程实际上和原来 S 属性定义中的计算过程一致 继承属性可以把值从一个结构传递到另一个并列的结构 ; 也可把值从父结构传递到子结构 抽象语法树和分析树不一致时, 继承属性很有用 计算 a-4+c 的依赖图
不同的语法分析树与抽象语法树 a-4+c
类型结构 简化的类型表达式的语法 T B C B int float C [num]c ε 生成类型表达式的 SDD
类型的含义 类型包括两个部分 :T B C 基本类型 B 分量 C 分量形如 [3][4] 表示 3X4 的二维数组 int [3][4] 数组构造算符 array array(3,array(4,int)) 表示抽象的 3X4 的二维数组
类型表达式的生成过程 输入 :int [2][3]
SDD 实例 E E 1 +T { E.type = if (E 1.type==INT && T.type==INT) then INT else FLOAT } E T {E.type = T.type} T num {T.type = INT} T num.num {T.type = FLOAT} 假设只考虑两种类型 :int 和 float, 写出利用上述文法进行类型检查的 SDD 改写文法, 消除了左递归后,SDD 又是怎样的?
E TE {E.inh=T.type; E.type=E.type} E +TE 1 { E 1.inh=(T.type==INT && E.type==INT)?INT:FLOAT; E.type=E 1.type } E ε {E.type=E.inh} T num {T.type=INT} T num.num {T.type=FLOAT}
语法制导的翻译方案 语法制导的翻译方案 (SDT) 是在产生式体中嵌入程序片断 ( 语义动作 ) 的上下文无关文法 SDT 的基本实现方法 建立语法分析树 将语义动作看作是虚拟的结点 从左到右 深度优先地遍历分析树, 在访问虚拟结点时执行相应动作
例子 E T 3 A2 语句 3*4*5 的分析树如右 DFS 可知动作执行顺序 A7 1,A5, A7 2, A4 1, A7 3, A4 2, A2 注意, 一个动作的不同实例所访问的属性值属于不同的结点 T 1 F * T 2 A5 * F A4 1 digit:4 F A4 2 digit:5 A7 3 A7 2 digit:3 A7 1
可在语法分析过程中实现的 SDT 实现 SDT 时, 实际上并不会真的构造语法分析树, 而是在分析过程中执行语义动作 即使基础文法可以应用某种分析技术, 仍可能因为动作的缘故导致此技术不可应用 用 SDT 实现两类重要的 SDD 基本文法是 LR 的,SDD 是 S 属性的 基本文法是 LL 的,SDD 是 L 属性的
可在语法分析过程中实现的 SDT 判断是否可在分析过程中实现 将每个语义动作替换为一个独有的标记非终结符号 ; 每个标记非终结符号 M 的产生式为 M ε 如果新的文法可以由某种方法进行分析, 那么这个 SDT 就可以在这个分析过程中实现 注意 : 这个方法没有考虑变量值的传递等要求
判断 SDT 可否用特定分析技术实现例子 L E n M 1 E E+T M 2 E T M 3 M 1 ε M 2 ε M 3 ε
后缀翻译方案 后缀 SDT: 所有动作都在产生式最右端的 SDT 文法可以自底向上分析且 SDD 是 S 属性的, 必然可以构造出后缀 SDT 构造方法 将每个语义规则看作是一个赋值语义动作 将所有的语义动作放在规则的最右端
后缀翻译方案的例子 实现桌上计算器的后缀 SDT 注意动作中对属性值的引用 我们允许语句引用全局变量, 局部变量, 文法符号的属性 文法符号的属性只能被赋值一次
后缀 SDT 的语法分析栈实现 可以在 LR 语法分析的过程中实现 归约时执行相应的语义动作 定义用于记录各文法符号的属性的 union 结构 栈中的每个文法符号 ( 或者说状态 ) 都附带一个这样的 union 类型的值 在按照产生式 A XYZ 归约时,Z 的属性可以在栈顶找到, Y 的属性可以在下一个位置找到,X 的属性可以在再下一个位置找到
分析栈实现的例子 假设语法分析栈存放在一个被称为 stack 的记录数组中, 下标 top 指向栈顶 stack[top] 是这个栈的栈顶 stack[top-1] 指向栈顶下一个位置 如果不同的文法符号有不同的属性集合, 我们可以使用 union 来保存这些属性值 归约时能够知道栈顶向下的各个符号分别是什么, 因此我们也能够确定各个 union 中究竟存放了什么样的值
后缀 SDT 的栈实现 注意 :stack[top-i] 和文法符号的对应 这个 SDT 中没有局部变量, 不会产生和局部变量有关的问题
产生式内部带有语义动作的 SDT 动作左边的所有符号 ( 以及动作 ) 处理完成后, 就立刻执行这个动作 B X{a}Y 自底向上分析时, 在 X 出现在栈顶时执行动作 a 自顶向下分析时, 在试图展开 Y 或者在输入中检测到 Y 的时刻执行 a
产生式内部带有语义动作的 SDT 不是所有的 SDT 都可以在分析过程中实现 后缀 SDT 以及 L 属性对应的 SDT 可以在分析时完成 对于一般的 SDT, 可以先建立分析树 ( 语义动作作为虚拟的结点 ), 然后进行前序遍历并执行动作 移入 / 规约冲突 : M 2 ε M 4 ε 移入数字
消除左递归时 SDT 的转换 如果动作不涉及属性值, 可以把动作当作终结符号进行处理, 然后消左递归 原始的产生式 E E 1 +T {print( + );} E T 转换后得到 E T R R + T {print ( + );} R R ε
消除左递归时 SDT 的一般转换形式 假设只有单个递归产生式, 且该左递归非终结符只有单个属性 消除左递归
消除左递归时 SDT 的一般转换形式
L 属性的 SDT 将 L 属性的 SDD 转换为 SDT 将每个语义规则看作是一个赋值语义动作 将赋值语义动作放到相应产生式的适当位置 计算 A 的继承属性的动作插入到产生式体中对应的 A 的左边 如果 A 的继承属性之间具有依赖关系, 则需要对计算动作进行排序 计算产生式头的综合属性的动作在产生式的最右边
L 属性的 SDT 实例 SDD 继承属性 : next: 语句结束后应该跳转到的标号 true false:c 为真 / 假时应该跳转到的标号 综合属性 code 表示代码
将 SDD 转换为 SDT 语义动作 (a) L1=new( );L2=new( ): 计算临时值 (b) C.false = S.next; C.true = L2: 计算 C 的继承属性 (c) S 1.next = L1: 计算 S 1 的继承属性 (d) S.code= : 计算 S 的综合属型 根据放置语义动作的规则得到如下 SDT (b) 在 C 之前 ;(c) 在 S1 之前 ;(d) 在最右端 (a) 可以放在最前面
L 属性的 SDD 的实现 使用递归下降的语法分析器 每个非终结符号对应一个函数 函数的参数接受继承属性 返回值包含了综合属性 在函数体中 首先选择适当的产生式 使用局部变量来保存属性 对于产生式体中的终结符号, 读入符号并获取其 ( 经词法分析得到的 ) 综合属性 对于非终结符号, 使用适当的方式调用相应函数, 并记录返回值
递归下降法实现 L 属性 SDD 的例子
边扫描边生成属性 (1) 当属性值的体积很大时, 对属性值进行运算的效率很低 比如 code( 代码 ) 可能是一个上百 K 的串, 对其进行并置等运算会比较低效 可以逐步生成属性的各个部分, 并增量式添加到最终的属性值中 条件 : 存在一个主属性, 且主属性是综合属性 在各产生式中, 主属性是通过产生式体中各个非终结符号的主属性连接 ( 并置 ) 得到的, 同时还会连接一些其它的元素 各非终结符号的主属性的连接顺序和它在产生式体中的顺序相同
边扫描边生成属性 (2) 基本思想 只需要在适当的时候 发出 非主属性的元素, 即把这些元素拼接到适当的地方 举例说明 假设我们在扫描一个非终结符号对应的语法结构时, 调用相应的函数, 并生成主属性 S while (C) S 1 S.code = Label L1 C.code Label L2 S 1.code 处理 S 时, 先调用 C, 再调用 S( 对应于 S 1 ) 如果各个函数把主属性打印出来, 我们处理 while 语句时, 只需要先打印 Label L1, 再调用 C( 打印了 C 的代码 ), 再打印 Label L2, 再调用 S( 打印 S 1 的代码 ) 对于这个规则而言, 只需要打印 Label L1 和 Label L2, 当然, 我们要求 C 和 S 的语句在相应情况下跳转到 L1 和 L2
S while ( {L1=new(); L2=new( ); C.false = S.next; C.true = L2; print( label, L1); } C ) {S 1.next = L1; print( label, L2); } S 1 前提是所有的非终结符号的 SDT 规则都这么做
边扫描边生成属性的例子