当前课程知识点:Compilers Techniques > 4 Syntax-Directed Translation > 4.2 Bottom-Up Calculation of S Attribute > 4.2.1 Bottom-Up Calculation of S-Attributed
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
我们继续第4章的学习
在上一讲中
我们着重介绍了
属性计算的顺序
在本讲中
我们将介绍如何具体进行属性计算
首先我们来回顾一下
第3章的内容
以递归下降预测分析为例
我们曾经讲过
每一个非终结符
可以对应一个分析过程
在进行递归下降预测分析的时候
每当遇到一个非终结符
我们就调用它的分析过程
来匹配当前的句子
当遇到一个终结符的时候
我们就调用match方法
来判断当前句子的首字母
和我们预期的首字母是否匹配
而当我们加入了属性以后
我们可以把这两种属性
附加到我们的分析过程中
具体的 针对综合属性
由于它是由产生式右部所有属性计算而来的
并且它是在完成整个产业式分析之后得到
因此很直观的
我们就可以联想到
综合属性可以对应到
我们过程的返回值
而另一种继承属性
在分析树中
它是依赖于
当前结点的父结点或者兄弟结点
因此它可以对应到
我们过程的参数
也就是
当我们希望分析某一个非终结符的时候
我们把对应的继承属性
传递给
当前记号的分析过程
以表示我们把对应的属性
传递给当前结点
这样一个语义
我们考虑之前提到过的
变量声明的例子
针对int id , id , id这样的句子
我们可以使用如下的产生式
以及对应的语义规则
来进行匹配
我们可以写出这样的伪代码
例如针对综合属性
例如T的type
它是由子结点来返回的
对应的我们就可以写出
左上这样的和左下这样的一个分析过程
在左下的分析过程中
T函数对应的就是
我们 T → int 或 T → real
这样一个分析过程
在分析过程中
我们T函数的返回值
就是当前结点的一个属性
这个属性会针对
我们当前句子的首字母
例如 lookahead 这个值
来判断它具体返回
应该是int类型还是real类型
在这个例子中
就可以很明显的看到
我们的综合属性
是以函数的返回值来表示的
对应的,针对继承属性
我们前面提到过
它是由参数来表示的
例如在L的分析过程
我们的L.in属性
就是通过参数
传递给当前的分析过程
下边也是类似
针对L→id这个产生式
我们构造这样一个分析过程
把L.in属性
传递给当前过程
这个属性会进一步的传递给addtype
来表示我们当前的id
给它添加一个属性类型信息
这个就是我们分析的一个方法
简而言之
综合属性对应我们的函数返回值
而继承属性
对应我们函数的参数
接着我们来介绍一个
更加实用的例子
也就是语法树的构造
我们知道在编译器中
分析树是一个非常重要的数据结构
在中间代码生成、代码优化等等阶段
都非常重要
而语法树是分析树的一个浓缩表示
它们的区别在于
在分析树中
我们的叶结点是终结符
而中间结点是非终结符
而在我们的语法树中
所有的结点都是终结符
在这种时候
它的空间要求
就比我们的分析树要更小
并且在很多场景下
分析起来也更加有用
然而值得注意的是
我们的语法制导的翻译方案
既可以针对分析树
也可以针对我们的语法树来实现
因为它们在语义上是等价的
例如考虑我们之前的
四则运算的例子
我们可以构造出如下的一些原语
这些原语都是用于
生成我们的分析树
例如我们可以使用如下三个方法
mknode和mkleaf
其中mkleaf 有两种
分别对应我们的树结点
和我们的标识符结点
而mknode的方法
是用来构造一个运算符结点
其中包括三个字段
分别是op, left, right
op代表我们的算符
例如加法和乘法
而两个字段
Left和right分别对应我们运算的两个子树
也就是我们两个运算数
给定如下原语以后
我们就可以把这些原语
用在我们的语义规则计算上
例如针对我们的产生式
每一个产生式
我们可以添加一个语义规则
在语义规则中
我们就可以使用刚才定义的
几种原语
例如从下往上看的话
在叶结点 F→digit 和 F→id
这两个产生式
我们分别使用 mkleaf() 的方法
来构造出这样一个叶结点
再向上的话
针对F→(E)的函数
我们可以直接把E的语法树结点
赋给F的结点
这个原因在于在语法树中
我们可以通过树的层次结构
来构造出一个优先级
而不需要括号来显示的标识
类似的针对T→F和E→T
我们也是直接把子结点的属性
赋给父结点
而针对第3个和第1个产生式
我们就使用mknode()的方法
前面提到过
它有三个域
分别是运算符、第1个运算数和第2个运算数
通过这种方法
我们就可以把两个子结点的
语法树结点
拼接到它的父结点上
构造出一个更高层的运算符
通过这种方式
我们就可以从叶结点
一直到根结点
构造出整个产生式它的语法树
需要值得注意的是
同样是产生附带语义规则
不同的语义规则
可能产生不同的作用
对于算符结点
一个域我们用来存放算符
并为该结点做一个标记
其余的两个域
用来指向运算对象的指针
基本运算对象结点
一个域存放我们的对象类型
定义域用来存放值
也可以用于存放其它的一些属性值
下面我们就针对我们的混合运算
来作为一个例子
我们来看这是刚才的产生式
以及对应的语义规则
下面我们针对一个表达式
来具体来看
如何构造我们的语法树
针对我们的表达式
A+5×B这样一个算式
我们来看如何的
同我们的分析树
构造出语法树
我们采用一个自下而上的方式
来进行表达
首先是我们的叶结点
我们考虑我们的叶结点a变量
在 F→id的时候
我们可以构造出id的符号表项
并且可以把它传递给F结点
接着在T→F产生式中
我们可以把 F结点的
它的指针传递给它的父结点F
这个过程还会继续向上
一直传递给E的nptr结点
在这个时候
我们的E的nptr属性
就保存了一个符号表项
它指向我们的id
同样的,在我们的右边子树
也是类似的
针对F→num这样一个产生式
我们可以构造出
num的一个符号表项
并且在T→F这样一个尝试中
我们可以把F的nptr向上
传递给它的父结点
同理针对最右边的子树
我们F→id构造出id的表项
并且把它赋给F
再向上一层的话
我们就可以构造出T×F它的一个符号表项
针对我们的右边这棵子树
在完成了两个运算数 T和F的属性计算以后
我们就可以再向上一层计算
T×F它的语法树结点
具体做法就是我们可以
构造出一个结点
它包含三个域
分别是乘号、第一个运算数
以及第二个运算数
我们把前面两个子结点
T和F的结点
分别添加到我们指定的域
就可以构造出我们的 T的nptr属性
它会指向左边这个子树
也就是T×F
对应的就是5×B
再继续向上
就可以构造出我们的根结点
也就是我们的加法
它的方式和乘法是类似的
只不过我们的第1个域
是一个加号
而它对应的两个运算数
分别是整个树的最左边一棵子树
也都是我们的a
而右边这个域
对应的就是5×B这个子树
把它添加到
我们加法三个域中的最后一个域
到这个地方为止
我们的E结点
它的nptr属性
就会指向我们整个语法树的根结点
到此为止
我们的整个语法树
也就各自完成了
再接下来
我们看一个相似的例子
同样还是一个运算
在这个例子中
我们考虑的是加减混合运算
使用的原语
依然是mknode()和mkleaf()
例如我们考虑如下的产生式
以及每个产生式对应的语义规则
我们可以看到
针对我们的叶结点
我们使用的是mkleaf()原语
来构造一个叶结点
针对括号
同样的是
直接把E结点的属性
传递给它的父结点
而在加法和减法
我们分别使用mknode()
并且把第一个域
分别设为加号或减号
来构造出一个结点
我们给出一个
自下而上的语法树的构造过程
首先从叶结点开始
我们首先构造第1个运算数
它的一个符号表项
并且把它向上传递给它的父结点
也就是T
T在接下来一步
把它传递给它的父结点
也就是E
再接下来是第2个算数
也就是我们的4
它会把4的符号表项
传递给它的父结点
也就是T.nptr会指向4的一个符号表项
再接下来又是第1个运算
也就是a-4这个部分
我们会构造出一个E.nptr
它会指向一个结点
这个结点三个元素
分别是减号、
第1个算术指向a、
第2个算术指向4
再接下来右边这棵子树
依然是自底向上的
首先我们构造出
c的符号表项
把它向上传递给它的父结点
也就是T
再接下来
我们就可以构造出加法的结点
这个方式和前面减法是类似的
首先是算符加号
第1个运算数
指向我们刚才的a+4这个结点
第2个算数
指向我们刚才的c结点
到这个地方为止
我们的根结点
也就是E结点
就可以有一个属性nptr
指向我们当前构造出的
语法树的根结点
至此我们这个句子
它对应的语法树就构造完成
在刚才的例子中
如果我们抛开分析树
只是看按照顺序执行的原语的话
其实它就是一个
构造语法树的步骤
它总共有5步
分别是mkleaf、mkleaf、mknode、mkleaf
和最后一个mknode
如果按顺序来看的话
它其实就是我们构造
整棵语法树的一个方式
例如第1个原语
我们构造出p1
它是a结点的语法树
第2步
我们构造另一个结点
也就是第2个算符
p3 构造出减法的语法树
它分别是减号
第1个算符和第2个算
第4个原语
就是构造出c的语法树
最后第5步
我们构造出根结点
也就是加法的结点
它分别有三个域:
加法
第1个算符
就是我们的a-4这样一个语法树
第3个域是我们第3个算符
也就是c对应的一个语法树
到这地方为止
我们的p5指向的
就是整棵语法树的结构
这个时候
我们就可以构造出
一个完整的语法树
这就是本讲的主要内容
谢谢大家
-1.1 Overview of Compilers Techniques
--Chapter 1 Overview of Compilers Techniques
--Overview of Compilers Techniques
-2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
--2.1 Lexical Tokens, Strings and Language
-2.2 Regular form
--2.2 Regular form
-2.3 Finite automata
--2.3 Finite automata
-2.4 DFA construction, Subset construction, Simpleset DFA
--2.4 DFA construction, Subset construction, Simpleset DFA
-2.5 Lex
--2.5 Lex
-3.1 Context-free Grammars
--3.1.1 The Role of the Parser
--3.1.2 The Formal Definition of a Context-free Grammar
-3.2 Writing a Grammar
--3.2.1 Elimination of Left Recursion
--3.2 Top-Down Parsing
-3.3 Languages and Grammars
--3.3 Language and Grammars
-3.4 Top-Down Parsing
--3.4.3 Recursive Descent Analysis
--3.4.4 Nonrecursive Descent Analysis
-3.5 Bottom-up Parsing
--Bottom-up Parsing
-3.6 LR Parsing
--3.6.6 Characteristics of LR Parsing
--3.6.7 Non Ambiguous and Not LR Context-Free Grammars
-4.1 Syntax-Directed Definitions
--4.1.2 Attribute Dependency Graphs and Ordering the Evaluation of Attributes
--Syntax-Directed Definitions
-4.2 Bottom-Up Calculation of S Attribute
--4.2.1 Bottom-Up Calculation of S-Attributed
-4.3 L-Attributed Definitions
--4.3.1 L-Attributed Definitions
--4.3.3 Design of Predictive Translator
--L-Attributed Definitions
-4.4 Bottom-Up Parsing of L-Attributed Translation
--4.4.1 Bottom-Up Parsing of L-Attributed Translation
--4.4.2 Simulate the Parsing of Inherited Properties
--Bottom-Up Parsing of L-Attributed Translation
-5.1 Overview
--Overview
-5.2 Global Stack Storage
-5.3 Calling Sequences
-5.4 Non Local Names
--5.4 Non Local Names and dynamic scope
--Non Local Name
-6.1 Overview of Intermediate Code Generation
--6.1 Overview of Intermediate Code Generation
-6.2 Declaration Statements
-7.1 Issues in the Design of Code Generator
--7.1 Issues in the Design of Code Generator
-7.2 Target Machine
--Target Machine
-7.3 Basic Blocks and Flow Graphs
--7.3 Basic Blocks and Flow Graphs
-7.4 A Simple Code Generator
-8.1 Demonstration of Compiler Framework based on Python
--8.1 Demonstration of Compiler Framework based on Python
-8.2 Basic
--8.2.4 SA
-8.3 SimpleJava