编译原理

第五章 语法制导的翻译

2020-03-17 10:00 CST
2020-04-02 15:40 CST
CC BY-NC 4.0

使用上下文无关语法(CFG)引导语言的翻译:

  • CFG的非终结符号代表了语言的某个构造
  • 程序设计语言的构造由更小的构造组合而成
  • 一个构造的语义可以由更小构造的含义综合而来(如x + y),也可以从附近的构造继承而来(如int x

语法制导定义:将文法符号和某些属性相关联,并通过语义规则来描述如何计算属性的值。

语法制导翻译:在产生式体中加入语义动作,并在适当时候执行动作。

语法制导的定义(SDD)

Syntax-Directed Definition (SDD)是对上下文无关文法和属性/规则的结合。

  • 属性和文法符号相关联,按照需要来确定各个文法符号需要哪些属性
  • 规则和产生式相关联

对于文法符号$X$和属性$a$,我们用$X.a$表示语法分析树中某个标号为$X$的节点的值。

  • 一个分析树节点和它的分支对应一个产生式规则
  • 对应的语义规则确定了这些节点上属性的取值和计算

分析树和属性值

综合属性(Synthesized Attribute):

  • 节点$N$的属性值由$N$的产生式所关联的语义规则来定义
  • 通过$N$的子节点或$N$本身的属性值来定义

继承属性(Inherited Attribute):

  • 节点$N$的属性值由$N$的父节点所关联的语义规则来定义
  • 依赖于$N$的父节点、$N$本身和$N$的兄弟节上的属性值

几条约束:

  • 不允许$N$的继承属性通过$N$的子节点上的属性来定义,但允许$N$的综合属性依赖于$N$本身的继承属性
  • 终结符号有综合属性(来自词法分析),但无继承属性

语法分析树上的SDD求值

注释语法分析树:包含了各个节点的各属性值的语法分析树。

计算顺序:S属性的SDD一定可以按照自底向上的方式求值。

我们可以用依赖图来表示计算顺序,这些图的计算顺序形成一个偏序关系,如果依赖图中出现了环,表示属性值无法计算。各个属性值需要按照依赖图的拓扑顺序计算。

S属性的SDD

只包含综合属性的SDD称为S属性的SDD。

  • 每个语义规则都根据产生式体中的属性值来计算头部非终结符号的属性值

语义规则不应该有复杂的副作用。

  • 要求副作用不影响其他属性的求值
  • 没有副作用的SDD称为属性文法

S属性的SDD可以和LR语法分析器一起实现。

  • 栈中的状态/文法符号可以附加相应的属性值
  • 规约时,按照语义规则计算规约得到的符号的属性值

S属性的SDD在依赖图中总是通过子结点的属性值来计算父结点的属性值,可以和自底向上或自顶向下的语法分析过程一起计算。

  • 自底向上:在构造分析树结点的同时计算相关的属性;
  • 自顶向下:在递归子程序法中,在过程调用的最后计算属性。

L属性的SDD

每个属性要么是综合属性(S)或继承属性(I),且继承属性满足:$A \rightarrow X_1X_2\dots X_n$中计算$X_i.a$的规则只用$A$的继承属性以及$X_i$左边的文法符号的继承属性或综合属性。

依赖图中的边:

  • 综合属性从下到上
  • 继承属性从上到下,或从左到右

在递归子程序法中实现L属性:对于每个非终结符号$A$,其所对应过程的参数为继承属性,返回值为综合属性。

具有受控副作用的语义规则

属性文法没有副作用,但增加了描述的复杂度。

  • 如果语法分析没有副作用,标识符表就必须作为属性传递。
  • 可以把标识符表作为全局变量然后通过函数来添加新的标识符。

受控的副作用:

  • 不会对属性求值产生约束,即可以按照任何拓扑顺序求值,不会影响最终结果;
  • 或者对求值过程添加简单的约束。

SDD的应用

构造抽象语法树的SDD

抽象语法树:

  • 每个结点代表一个语法结构,对应于运算符
  • 结点的每个子结点代表其子结构,对应于运算分量
  • 表示这些子结构按照特定的方式组成了较大的结构,忽略一些标点符号等非本质的东西

抽象语法树的表示方法:

  • 每个结点用一个对象表示
  • 对象有多个域
    • 叶子结点中只存放词法值
    • 内部结点中存放了OP值和参数

语法制导的翻译方案(SDT)

语法制导的翻译方案(SDT)是在产生式体中嵌入语义动作的上下文无关文法。

SDT的基本实现方法:

  • 建立语法分析树
  • 将语义动作看作是虚拟节点
  • 从左到右、深度优先地遍历分析树,在访问虚拟节点时执行对应的语义动作

用SDT实现两类重要的SDD:

  • 基本文法是LR的,SDD是S属性的
  • 基本文法是LL的,SDD是L属性的

可在语法分析过程中实现的SDT

实现SDT时,实际上并不会真的构造语法分析树,而是在分析过程中执行语义动作。

即使基础文法可以应用某种分析技术,仍可能因为动作的缘故导致次技术不可应用。

判断SDT是否可在分析过程中实现:

  • 将每个语义动作替换为一个独有的非终结符号$M_i$,其产生式为$M_i \rightarrow \varepsilon$
  • 如果新的文法可以由某种方法进行分析,那么这个SDT就可以在这个分析过程中实现。

后缀SDT的语法分析栈实现

后缀SDT可以在LR语法分析的过程中实现:

  • 规约时执行相应的语义动作
  • 定义用于记录各文法富符号属性的union结构
  • 栈中的每个文法符号(状态)都附带一个这样的union类型的值
  • 按照产生式规约时,可以在栈顶找到最后一个元素的属性值,弹出后找到倒数第二个元素的属性值……

产生式内部带有语义动作的SDT

动作左边的所有符号(以及动作)处理完成后,就立刻执行这个动作。

  • 对一般的SDT,都可以先建立分析树(语义动作作为虚拟节点),然后进行前序遍历并执行动作。
  • 不是所有的SDT都可以在分析过程中实现。后缀SDT以及L属性对应的SDT可以在分析时完成。

消除左递归时SDT的转换

如果动作不涉及属性值,可以把动作当作终结符号进行处理,然后消除左递归。

如果动作设计属性值的计算,则有通用的解决方案。

假设:

  • $A \rightarrow A_1\ Y\ \lbrace A.a = g(A_1.a, Y.y) \rbrace$
  • $A \rightarrow X\ \lbrace A.a = f(X.x) \rbrace$

那么

  • $A \rightarrow X\ \lbrace R.i = f(X.x) \rbrace\ R\ \lbrace A.a = R.s \rbrace$
  • $R \rightarrow Y\ \lbrace R_1.i = g(R.i, Y.y) \rbrace\ R_1\ \lbrace R.s = R_1.s \rbrace$
  • $R \rightarrow \varepsilon\ \lbrace R.s = R.i \rbrace$

L属性的SDT

L属性的SDT可以在自顶向下的分析过程中实现:将赋值语义动作放到相应产生式的适当位置。

对于产生式$A \rightarrow X_1\ X_2\ \dots\ X_n$:

  • 计算$X_i$继承属性的动作插入到产生式体中$X_i$的左边;
  • 计算产生式头$A$的综合属性的动作放在产生式的最右边。

边扫描边生成属性

当属性值的体积很大,对其进行运算效率很低。可以逐步生成属性的各个部分,并增量式的添加到最终的属性中。

使用这种方法的三个条件:

  • 存在一个主属性,且其为综合属性
  • 在产生式中,主属性是通过产生式体中各非终结符号的主属性连接而得到
  • 各个非终结符号的主属性的连接顺序与它们在产生式体中的顺序相同

基本思想:在适当的时候“发出”元素,并拼接到适当的地方。