当前课程知识点:Compilers Techniques > 4 Syntax-Directed Translation > 4.2 Bottom-Up Calculation of S Attribute > 4.2.2 Stack Code
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
今天我们继续第4章的学习
在本节中
我们将介绍
如何实现综合属性的自下而上计算
特别的我们称一个
只包含综合属性的文法为S属性文法
在S属性文法的分析中
我们的综合属性
可以在分析输入串的同时
完成自下而上的分析和计算
在我们的分析器中
除了我们的状态栈
我们可以另外设置一个符号栈
这个符号栈描述的就是
每一个文法记号对应的属性
每当我们进行归约的时候
新的属性值
就可以从栈中
正在被归约的产生式中取出并且计算
计算之后
把它存储在我们的栈的指定位置
即可完成对应的语义规则
例如我们可以考虑一个LR分析器
在我们第3章讲解的时候
我们曾经讲过LR分析
在分析中
我们当时只使用了状态栈
为了进行属性计算
我们除了状态栈之外
增加了一个属性栈
用于保存每一个文法记号的属性
例如我们有一个产生式A→XYZ
假设它的语义规则是
A的A属性是由 X.x Y.y Z.c 经过一个f计算得到
很显然
A.a就是一个综合属性
这个属性如何计算呢?
我们可以这样考虑
假设当前我们
应该对当前产生式进行归约
那就意味着
在我们的状态栈中
就应该有X、Y、Z分别在栈顶
对应的X.x Y.y和Z.c
它们三个属性
也分别在栈的指定位置
我们就可以从栈的这三个位置
分别取出三个属性值
经过 f 计算以后
把它压入栈中
由于经过归约后
我们的X、Y、Z分别要进行弹栈
并且压入归约后的A
因此我们的A.a就会保存在a的指定位置
到这个地方为止
我们的属性计算就可以完成
例如我们考虑之前介绍过的
混合运算的例子
在这个例子中
我们有产生式对应的语义规则
以及我们的状态栈和属性栈
我们以之前曾经介绍过的
混合运算的例子
来介绍如何进行属性计算
具体的我们关注的是
如何将语义规则
翻译成对应的栈代码
在图中我们可以看到
我们有计算用的产生式、语义规则
以及对应的我们的状态栈和属性栈
我们就针对每一个产生式
来分别考虑
如何将语义规则转化成对栈的操作
针对第1条产生式L→En
我们的目标是打印出E的value属性
当我们使用这条产生式进行归约的时候
我们的栈顶应该是n
栈顶下一位应该是E的属性
这个时候我们就很容易看出
我们可以取出栈顶减1的位置
它的值就是E.value
我们就可以把它打印出来
这就是我们的代码栈
我们考虑第2条产生式
我们的产生式是E→E1+T
它的语义规则是E.value=E1.value+T.value
在当前的栈顶我们应该是有T
栈顶减1是加号
栈顶减2是E1
因此我们可以从
栈顶和栈顶减2的位置
取出E1和T的属性值
把它们做加法
接下来我们要做移进归约
也就是我们弹出栈领的三个元素
并且把E压入
因此我们计算后的值
应该存储在当前的 top减2位置
这就是我们的代码段的含义
从top和top减2
取出T和E1的value值做加法
并且把它保存在top减2的位置
好 第3条产生式E→T
它的语义规则是E.value=T.value
由于当前我们的栈顶元素
就是T.value
经过弹栈和压栈操作以后
我们的value值是保持不变的
因此我们的栈代码
应该是不需要做任何操作
再接下来
T→T1×F
这条产生式和第2条非常像
只不过我们把加法换成了乘法
它的操作也是类似的
从栈顶和栈顶减2的位置
取出F和T1的属性值
把它们做乘积
并且存储在栈顶减2的位置
好 接下来我们来看
T→F这个产生式
这个产生式和第3条产生式非常类似
我们的语义规则是T.value=F.value
因此我们并不需要
对属性栈做任何操作
再接下来F→(E)
这个产生式对应的语义规则
是F.value=E.value
当我们使用这条产生式进行归约的时候
我们的栈顶应该是 (E)
因此E.value
应该从栈顶的 top-1取得
并且因为我们需要弹栈三次 压栈一次
所以说计算后的属性值
应该保存在 top-2位置
因此我们的栈代码
就是value[ top-2 ]=value[ top-1 ]
最后一条 F→digit
这是一个叶结点
它的语义规则是
将词法分析得到的值赋给F.value
因此我们也不需要对栈做任何操作
到此为止
我们的所有语义规则
就已经翻译成了我们对应的栈代码
在移进归约的时候
每当需要进行归约的时候
我们就执行对应的栈操作
就可以完成对应的S属性计算
我们以一个具体的例子来看
我们考虑3×5+4
这样一个表达式
我们考虑它的移进归约分析
并且分别考虑它的
状态栈和属性栈的取值
最开始我们的输入是3×5+4n
我们的两个栈都是空的
首先我们需要移进
把3移入我们的状态栈和属性栈
这个时候我们就要使用
F→digit来进行归约
归约的时候
我们的属性栈保存的
就是它的3的值
因此不需要做任何操作
再接下来
我们使用T→F来归约
这个操作只需要对状态栈
做一个弹栈压栈操作
我们的value值
也不需要进行变化
接着我们进行移进
把乘号移进来
再接下来我们再移进,移进5
移进5以后
我们需要使用F→digit来进行归约
归约的时候
我们的栈依然不需要操作
再接下来
我们T×F需要使用 T进行归约
同时我们需要对栈顶的
top和top减2的位置
把5和3取出来做乘法
并且把它保存在top减2的位置
对应的我们得到最上面的值
我们的 value栈对应的栈顶是15
并且我们的状态栈是T
再接下来
和前面就比较类似
我们继续的移进加号
然后移进4
我们4使用F来进行归约
然后F使用T来进行替换
在这个时候
我们的栈顶就是E+T
我们需要使用E→E+T来进行归约
归约的时候
我们的栈操作就是
从栈顶和栈顶减2的位置
取出4和15
把它们做加法
并且压入在top-2的位置
经过归约的弹栈压栈以后
我们的栈顶就是19
并且我们的state栈
它的栈顶就是E
在这个时候
我们再移进n
表示我们的句子已经读完
并且我们的栈顶是19
最后我们执行打印动作
就可以把栈顶的19
这个值打印出来
到此为止
我们的3×5+4
这样一个表达式
就完成了移进归约分析
并且在移进归约分析的同时
我们完成了属性计算
得到了最终的表达式求值是19
好
我们做一个简单的小结
在本节中
我们主要关注的是自下而上分析
我们是以LR分析为例
也就是移进归约分析
首先给出了 S属性定义
也就是只包含综合属性的
这样的文法属性
然后我们给出了
如何把每一个语义规则
翻译成代码栈的操作
因此我们就构造出了
一个完整的翻译程序
针对这个过程
我们可以做一个类比
就像一个建筑
我们的语法分析就是一个框架
而在归约处
每一个归约处
我们设置一个挂钩
或者在编程的时候
我们可以把它类比成一个回调函数
每一次进行归约的时候
我们就调用我们挂钩处的一个动作
也就是调用一个回调函数
通过这种操作
我们就可以完成
在归约的同时
进行语义子程序的调用
进而完成我们的翻译任务
本节的内容处于本章的这个位置
我们在前面曾经介绍过属性
包括综合属性和继承属性
我们说基础文法加上综合属性
就是我们的S属性定义
我们是以自下而上分析为例
通过在归约的时候
执行对应的操作
来完成属性计算
在后续的过程中
我们将介绍其它的属性定义
以及对应的分析操作
好 这就是本讲的内容
谢谢大家
-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