当前课程知识点:Compilers Techniques > 4 Syntax-Directed Translation > 4.3 L-Attributed Definitions > 4.3.3 Design of Predictive Translator
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
今天我们继续第4章的学习
在本讲中
我们关注预测分析的设计
以及在一些场景下
如何使用综合属性来替代继承属性
首先我们来关注
如何设计自上而下的分析
如果我们的文法是满足LL(1)文法的话
我们就可以比较容易的实现边分析边计算
在这个时候
我们的函数返回值
可以作为A的综合属性
如果说我们的属性有多个的话
可以考虑使用记录或者使用某一个记录的指针
来封装若干个域
为了简单起见
在本讲中
我们假设
每一个非终结符只有一个综合属性
对于每一个函数过程中
未出现在A的产生式中的每一个文法记号
设计一个局部变量
局部变量就可以用来记录
出现的每一个记号的它的属性
再接下来
针对非终结符A对应的函数过程中
根据当前的输入符号
我们可以确定使用
哪一个产生式作为候选
这个过程就和我们在第3章讲解过的
match函数是一致的
因为LL(1)文法
它没有左递归
没有公共左因子
所以我们总是能够根据当前的
第1个记号来判断
应该使用哪一个产生式
在每个产生式对应的代码中
我们按照自左向右的顺序
对于简单的终结符、
非终结符和语义动作
做以下的工作:
第1点
对于带有综合属性 x 的终结符 X
我们可以把 x 的值
存入 X.x 这样一个局部变量中
然后产生一个匹配 X 调用
并且继续读入一个符号
第2点
针对每一个非终结符 B
产生赋值语句
c=B ( b1, b2, ..., bk )
其中 b1 到 bk 是输入参数
而 B 是非终结符 B 对应的分析过程
这样一来
我们就可以把B的综合属性保存在 c 中
这个 c 就是为了B的综合属性
所设置的一个局部变量
第3点
对于语义动作
我们把语义动作对应的代码
抄入分析器中
用代表属性的变量来代替
属性中的每一次引用
我们来看
我们的预测分析器的设计
我们的设计目标是为文法计算
其中的一个L属性值
相比前面综合属性
L属性就相对复杂一些
我们的方法是
把预测分析的构造方法
推广到翻译方案的实现
例如考虑这样一个产生式
R → +TR | ε
它的分析过程
如前所述
针对这样的产生式
我们要构造一个分析函数
我们把它命名为 R
并且针对它的一个产生式右部(进行讨论)
第1个记号是一个加号
所以说我们要首先判断
当前的第1个位置是不是加号
如果是的话,我们则匹配加号
然后分别调用 T 和 R 的分析过程
如果首字母不是加号的话
我们就应该使用
第2个产生式 R → ε 来进行匹配
在这个情况下
我们什么都不需要做
只要有一个空的else 分支即可
当我们考虑属性以后
我们就可以把当前的分析过程
进行扩展
在当前的 R 过程中
我们的参数
表示的就是我们当前 R 的继承属性
也就是从其它结点中
传入当前分析结点的属性
对应的它的返回值syntaxTreeNode
表示的就是当前属性
计算完了一个综合属性
针对我们产生式右部可能出现的所有记号
我们设置一个局部变量
并且我们针对当前输入的首字母
来进行判断
如果是加法的话
我们就匹配当前加号
调用T和R
并且使用对应的变量
来保存它们的返回值
和 R 的过程类似
T的返回值就是
T结点对应的分析过程它的综合属性
而R的返回值就是
R 这个结点它的综合属性
R的参数就是
它的一个继承属性
对于 R → +TR 这样一个过程
我们后面这个R 它的输入属性
也就是我们分析到 R 之前所构造的一个语法结点
它的构造方式是通过调用
mknode 的这样一个原语
它的参数就是:
我们在前面分析得到的一个运算符、
输入进来的一个参数、
以及我们前一个结点对应的一个属性
到此为止
我们的S就是我们的返回值
表示的就是分析完当前 R 以后
得到的一个语法树结点
对应的,如果说
我们的输入首字母不是加号的话
我们则使用第2个产生式
也就是 R → ε 来进行匹配
在这种情况下
我们需要对它的返回值做一个赋值
在 R → ε 的时候
我们知道
它已经进入到分析树的右下结点
这种时候
我们只需要把它的输入参数
作为返回值返回即可
无论哪一种情况
我们的S都表示分析完当前过程以后
得到的一个语法树的结点
最后我们只要把语法树结点
作为当前过程的返回值
也就是分析完当前产生式左部以后
得到的综合属性
那就完成了当前函数的匹配
好,接下来我们来看一个特殊的案例
也就是在一定场景下
我们可以使用综合属性
来替代继承属性
我们说综合属性分析起来
总是比继承属性要更容易一些
在一定场景下
我们可以在两个属性之间进行转换
例如我们考虑这样的例子
这是PASCAL语言它的变量声明的一个语法
和C语言、Java等等不同的是
PASCAL语言它的变量声明
我们的标志符是写在前面
然后通过冒号
来分割我们的变量声明以及类型
这个语句 m, n: integer 表示的是
我们上面有两个变量:m 和 n
它们的类型是整型
我们可以使用这样的文法来描述
D→ L : T
L代表我们的变量列表
而T代表我们的类型
T→ integer | char
表示两种类型
而L是一个列表
它是L1, id 或者 id
给定这样的语法以后
我们就可以
针对每个句子来构造它的分析树
例如从根结点D开始
D→ L : T
L是我们的参数列表
也就是 L → L , id
L→ id
T是我们的类型,是integer
在这种文法情况下
我们的分析树是长这个样子
我们需要对每一个 id
赋值它的类型
但是我们的类型是出现在分析树的右下
所以它需要
首先传递给它的父结点
并且由父结点传递给它的左边的兄弟结点
然后传递给子结点
具体传递到我们的两个 id
在这个时候
我们可以对 id 的类型进行赋值
赋值方式类似于我们前面的addtype
但是这个时候我们看到
它的赋值方式是从右向左的
和我们的分析方式是有个区别
因此不适合我们边分析边计算
在这种情况下
我们可以通过改写文法的方式
来进行变换
把我们的继承属性
变成可以使用综合属性来描述
针对上面的文法
我们可以做这样一个变换
D→id L
L→ , id L | : T
而T是我们的 integer 或者 char 两种类型
这两种文法描述的语言是一致的
都是可以推出形如 m, n : integer 这样的句子
但是它的好处在于我们可以
构造出不同的分析树
例如还是 id , id : integer 这样的一个句子
我们构造的分析树是这样的
D (作为根结点)
左边是 id 右边是 L 逗号 id
然后我们的列表结束
后边是我们的类型
类型是 : integer
在这种情况下
我们的类型是在最下边
它可以以综合属性的方式向上传递
并且传递给包含 id 的每一个 L 以后
我们可以使用
虚拟综合属性的方式
来执行我们的 addtype 操作
当完成 L 分析以后
它已经知道了它的类型是integer
并且知道了它的 id 表项
所以我们可以完成 L 分析以后
调用 addtype 操作
来给 id 赋一个类型信息
左边的 id 也是类似的
可以通过分析完 D 以后
执行 addtype 操作
在这种时候
我们既知道了 id 的信息
也知道类型信息
所以调用 addtype 是没有问题的
通过这种方式
我们就可以把原来很难分析的
一个包含继承属性的这样一个例子
变成一个只使用综合属性
就可以完成的分析
当然我们要注意
这是一个只有在特殊场景下可以使用的
因为这种文法改写
并不是总能成立的
把我们刚才描述的属性传递的过程
使用我们的翻译方案来描述的话
只需要把我们的语义规则对应的动作
写在我们的产生式指定的位置
就可以完成
我们刚才的类型传递以及 addtype 操作
这时候我们可以看到
在我们的翻译方案中只有综合属性
因为我们所有的动作
都是在产生式最右部以后来执行的
像 addtype 我们刚才也提过
因为它是一个有副作用的动作
它需要在完成当前结点分析以后来执行
所以它也是一个综合属性
在这个例子中
就是一个非常典型的
使用综合属性来描述
原来必须使用继承属性的例子
当然我们需要在合适的场景
考虑使用合适的方式来进行改写
这个需要在大家今后的工作中
进行自我摸索
好,谢谢大家
这就是本讲的内容
-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