编译原理Ch6

第六章 语法制导的翻译

一、属性文法

1.属性文法定义的形式

• 基础文法
• 每个文法符号都有一个属性
• 每个文法产生式$A → α$有一组形式为$b :=f(c_1, c_2, …, c_k )$的语义规则，其中$f$是函数，$b,c_1, c_2, …, c_k$ 是该产生式文法符号的属性

2.综合属性

• b是A的属性，$c_1, c_2, …, c_k$是产生式右部文法符号的属性或A的其他属性

(1)S属性定义

• 仅仅使用综合属性的语法制导定义

(2)注释分析树

• 在语法树的基础上，将文法符号的属性标明

3.继承属性

• b是产生式右部某个文法符号X的属性

(1)万能钥匙法

• 违反了“遍”的原则
• 在注释分析树的基础上，遍历每一个属性规则，若有属性之间的依赖，则引一条从决定方到被决定方的有向边
• 形成的有向图的拓扑排序为万能钥匙
• addType函数：addtype (id.entry,L.in)的意义是在符号表中找到id，将其entry属性设置为L.in
• 虚综合属性：类似addtype (id.entry,L.in)的语义规则我们会虚拟构造一个L.s=addtype，此时s就是虚综合属性

二、基于属性文法的处理方法

1.构造语法分析树

2.构造依赖树

• 在语法分析树的节点旁边再构造一个节点，表示其属性
• 虚综合属性也要构造
• 遍历每一个属性规则，若有属性之间的依赖，则引一条从决定方到被决定方的有向边

3.依赖图的构建算法

for 语法树中的每一个节点n do
    for 节点n的文法符号的每个属性a do
        为a在依赖图中建立一个节点;
for 语法树中的每一个节点n do
    for 节点n所用产生式对应的每一个语义规则 b:=f(c1,c2,...,ck) do
        for i:=1 to k do
            从节点ci到b节点构造一条有向边

4.良定义的属性文法

• 如果一属性文法不存在属性之间的循环依赖关系，则称该文法为良定义的
• 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序

5.结果

• 按照属性文法的语义规则，实现了语义分析，在符号表中登记了每个变量标识符的类别信息，对符号表的操作也是一种语义分析、翻译

三、树遍历的属性计算方法

1.过程

• 通过树遍历的方法计算属性的值
  • 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性
  • 以某种次序遍历语法树，直至计算出所有属性
  • 深度优先，从左到右的遍历，直到计算出所有的属性（也需要多遍扫描）

2.树遍历算法

先遍历所有子结点，求他们的继承属性，然后求自己的综合属性

四、一遍扫描的处理方法

1.过程

• 在语法分析的同时计算属性值
  • 所采用的语法分析方法
  • 属性的计算次序
• 所谓语法制导翻译法，直观上说就是为文法中每一个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则
• 语义规则被计算的世纪与语法分析方法有关
  • 自上而下分析，一个产生式匹配输入串成功时
  • 自下而上分析，一个产生式被用于进行规约时

2.抽象语法树（AST）

• 在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。
• 没有非终结符作为内部结点，内部结点由运算符充当，代表该节点具有该运算符作用在其子节点的对应的值之后的结果。
  
• 其中，if语句的根结点是一个三目运算符

3.建立表达式的抽象语法树

(1)mknode(op,left,right)函数

• 建立一个运算符结点，标号是op，两个域left和right分别指向左子树和右子树。

(2)mkleaf(id,entry)函数

• 建立一个标识符结点，标号为id，一个域entry指向标识符在符号表中的入口

(3)mkleaf(num,val)函数

• 建立一个数结点，标号为num，一个域val用于存放数的值

4.建立抽象语法树的语义规则

• a-4+c的抽象语法树（S属性文法，非常适合与自下而上结合在一起）
  

五、S属性文法的自下而上计算

1.思想

• S属性文法：只含有综合属性
• 在自下而上的分析器分析输入符号串的同时计算综合属性
  • 分析栈中保存语法符号和有关的综合属性值
  • 每当进行规约时，新的语法符号的属性值久游栈中正在规约的产生式右边符号的属性值来计算

2.实现

• 在分析栈中增加附加域存放综合属性值
• 假设产生式A→XYZ对应的语义规则为A.a:=f(X.x,Y.y,Z.z)
  
  
  

六、L属性文法的自上而下计算

1.L属性文法和自顶向下翻译

• 按照深度优先遍历语法树，计算所有属性值
• 与LL(1)自上而下分析方法结合
  • 深度优先建立语法树
  • 按照语义规则计算属性

2.L属性文法

• 对于每个产生式$A→X_1X_2…X_n$，其每个语义规则中的每个属性，要么是综合属性，要么是$X_j$的一个继承属性且这个继承属性仅依赖于
  • 产生式中$X_i$左边符号$X_1,X_2,…,X_{i-1}$的属性
  • A的继承属性

3.翻译模式

• 语义规则：给出了属性计算的定义，没有属性计算的次序等细节
• 翻译模式：给出了使用语义规则进行计算的次序，把实现细节表示出来
  • 在翻译模式中，和文法符号相关的属性和语义规则（语义动作），用{}括起来，插入到产生式右部的合适位置上
    

4.设计翻译模式的原则

• 设计翻译模式时，必须保证当某个动作引用一个属性时它必须是有定义的。
• L属性文法本身就能确保每个动作不会引用尚未计算出来的属性。

5.建立翻译模式

• 当只需要综合属性时，为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。
  
• 如果既有综合属性又有继承属性，建立翻译模式时必须保证：
  • 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来
  • 一个动作不能引用这个动作右边的符号的综合属性
  • 产生式左边非终结符的综合属性只有在它引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常放在产生式右端末尾
    

6.翻译模式示例

7.统一语义动作执行时机

• 把所有产生式的语义动作都放在产生式末尾
• 转换方法
  • 加入新产生式$M→\varepsilon$
  • 把嵌入在产生式中的每个语义动作用不同的非终结符M代替，并把这个动作放在产生式$M→\varepsilon$的末尾
    

8.消除翻译模式中的左递归

• 语义动作是在相同位置上的符号被展开（匹配成功）时执行的
• 为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归
• 当消除一个翻译模式的基本文法的左递归时同时考虑属性计算
  • 适合带综合属性的翻译模式
• R.i是继承属性，R.s是综合属性
  
• 推广：
  假设有翻译模式：
  $$
  A→A_1Y{A.a:=g(A_1.a, Y.y)}\
  A→X {A.a:=f(X.x)}
  $$
• 它的每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数
  
• 消之前，f计算的是A.a，消之后，A.a不止包含f，f只能算出R.i，而A.a与R.s相等
• 第二句背
• 不会了，不想写了
  

七、递归下降翻译器的设计