编译原理完整学习笔记（五）：属性文法和语法制导翻译

前言

如果你对这篇文章可感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。

属性文法和语法制导翻译

一、概述

属性文法，也称为属性翻译文法，以 “上下文无关文法” 为基础，扩充了以下两部分内容：

• 每个文法符号（终结符或非终结符）有 “值”（属性）
• 每个产生式有一组属性的语义规则，对属性进行计算和传递

属性中有两类属性，一种是综合属性，另一种是继承属性。

1.1 综合属性

• 自下而上传递信息
• 语法规则：产生式右部确定左部

• 语法树：子节点确定父节点

1.2 继承属性

• 自上而下传递信息
• 语法规则：产生式左部确定右部

• 语法树：（父节点 + 兄弟节点）确定（子节点）

1.3 语义规则

产生式 $A\to \alpha$ 对应的语义规则如下：
$$b:=f(c_1,c_2,...,c_k)$$
其中共有两种情况：

• b 是 A 的综合属性，$c_i$ 是产生式右边文法符号的属性
• b 是产生式右边文法符号的继承属性，$c_i$ 是 A 或产生式右边文法符号的属性

由此可以如下结论：

• 终结符只有综合属性，且由词法分析器提供
• 非终结符可以有综合属性、继承属性
• 文法开始符号的所有继承属性作为属性计算前的初始值

语义规则功能：

• 属性计算、静态语义检查
• 符号表操作、代码生成

二、带注释的语法树

2.1 S-属性文法

• 语法树中，一个结点的综合属性的值由其子结点和它本身的属性值确定
• 使用自底向上的办法在每一个结点处使用语义规则计算综合属性的值
• 仅使用综合属性的属性文法为 S-属性文法

• 分析过程
  

2.2 L-属性文法

语法树中，结点的继承属性由其父结点、其兄弟结点和其本身的某些属性确定。

• 继承属性，常用于表示上下文依赖关系

• 文法定义
  

三、属性计算

3.1 概述

语义规则的计算功能如下：

• 产生代码
• 在符号表中存放信息
• 给出错误信息
• 执行任何其它动作

「总结」对输入串的翻译就是根据语义规则进行计算。

3.2 语法制导翻译法

语法制导翻译法：由源程序的语法结构所驱动的处理办法

基于属性文法的处理方法有：

• 依赖图
• 树遍历
• 一遍扫描

3.3 依赖图

「功能」描述一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系

3.3.1 构建算法

3.3.2 依赖图举例

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

3.3.3 属性的计算次序

3.4 树遍历

「具体方法」通过树遍历的方法计算属性的值

• 输入时，树中已有开始符号的继承属性和终结符的综合属性
• 深度优化，从左到右的遍历

3.4.1 树遍历算法

3.4.2 树遍历举例

3.5 一遍扫描

• 在语法分析的同时计算属性值
• 适用于 S-属性文法 / L-属性文法

3.5.1 抽象语法树

3.5.2 建立抽象语法树

3.5.3 一遍扫描举例

资料来源

• 编译原理 - 国防科技大学 - MOOC