当前课程知识点:Compilers Techniques > 4 Syntax-Directed Translation > 4.4 Bottom-Up Parsing of L-Attributed Translation > 4.4.2 Simulate the Parsing of Inherited Properties
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
今天我们继续第4章的学习
在本章的最后
我们以之前曾经介绍过的
EQN排版语言为例
来加深大家对
模拟继承属性的理解
我们首先给出它的翻译方案
翻译方案我们之前说过
它是由文法加上语义规则
执行的指定位置来构成的
文法就是S→B
B→B1 B2
或者 B→B1 sub B2
或者 B→text
在文法中我们有两个属性
一个是ps
表示输入的一个继承属性
它表示的是
从当前位置开始
后续的文字的大小
而ht是一个综合属性
描述的是当前文本的一个高度
我们的语义规则是花括号括起来的一个动作
它的执行位置
我们把它插入到
我们产生式的指定位置
我们遵循的规则依然是
继承属性
插入到分析当前结点之前
而综合属性
放在当前产生式的末尾
例如在分析B之前
我们要设置一个初值
ps是等于10
在分析完B以后
我们S的ht高度属性
就是B的ht
类似的,在后边产生式也是
每一个产生式B都有一个
继承属性ps
它( B.ps )是从它的父结点获得的
在分析完之后
我们会返回一个ht
它可能是B1B2的高度取大
或者是针对B1B2算一个偏移值
如果说是我们的终结符
也就B→text的这样一个产生式
我们的综合属性
是由它的继承属性
乘以当前词法记号的高度
共同得到当前的text的高度
这个就是我们的翻译方案
后续我们将着重讲解
如何把当前的翻译方案
转化成对栈的操作
转化的难点
也在于我们翻译方案中
是存在继承属性的
在上一讲中
我们曾介绍过
在移进归约分析中继承属性
它是一个难点
我们需要把它转化成一个
虚拟非终结符的综合属性
例如我们考虑
直接使用栈来进行移进归约的时候
它存在的问题
在计算我们的文本字体和高度的时候
我们无法确定所依赖继承属性
在栈中的位置
例如我们可以是由text归约为B
也可以是由B text归约为BB
也可以使用B sub text归约为B sub B
如果我们不对文法进行改写的话
可能会存在一个问题
也就是在计算文字高度时候
无法确定所依赖的继承属性所在的位置
例如我们的栈顶可能是
text 归约为B 或者是B text归约为BB
或者是B sub text归约为B sub B
这三种情况中
我们的B属性的继承属性
可能会依赖于
栈中的不同位置
它的综合属性
因此我们也需要在文法中
引入一些虚拟非终结符
来消除我们的继承属性
我们的方式和前一节讲的类似
在我们的 B结点之前分别是 L,M和N
它们分别插入在第1个产生式
第3个和第五产生式中
这三个虚拟非终结符
都是推出空串
即:L,M和N都是推出空串的非终结符
并且它都是紧临在
我们最后一个B之前
在这种情况下
我们如果需要
使用B2的这个非终结符的话
我们就可以从B2的前一个位置
取得M的综合属性
把它作为我们的继承属性
这样一来
无论是第一个、
第三个和第五个产生式中
我们的B产生式的继承属性
都可以从栈顶减一的位置获得
这样的话就消除了
我们必须使用继承属性的问题
好
我们来考虑它的翻译方案
我们的产生式发生了变化
第1个条件是
原来是S→B现在变成了S→LB
其中L是我们的虚拟非终结符
B→B1 B2
原来产生式
我们在B2之前加了一个M并且
M也是推出空串的
在第3个位置
我们的 B1 sub B2
我们在B2之前也加入一个非终结符N
它也是同样推出空串
这样一来
当我们的B2或者第1个产生式中的B需要使用
继承属性的时候
我们就可以从它前一个位置获得属性
因此我们就不再需要像原来那样
使用一个继承属性
而可以使用前一个记号的综合属性
来进行代替
为了加深大家的印象
我们考虑这样的分析过程
例如我们考虑的是
L B然后B→BMB
B→B sub NB
其中L,M和N三个结点
都是推出空串的
也就是说我们当前的记号是E sub 1
这样一个记号
我们考虑每一个属性的计算顺序
例如我们的输入的基本属性是10
这个10
我们可以通过赋给L属性
并且这个属性会被传递给B作为B的ps值
在这种情况下
B的原来继承属性ps
就可以从它前一个记号的综合属性s 来进行获得
并且这个属性会被传递给B
当前B→text
所以说 B 的 ps 和 text 的 ht 值做乘积
得到B的ht属性
这是它的综合属性
接着我们的虚拟非终结符M的i属性
是从它的父结点得到
而它可以看到
也是从它的前一个位置得到的
在接下来
M的i属性
直接转化为它的综合属性s
这个综合属性就作为我们B的虚拟继承属性
也就是说
当我们需要使用
B结点的继承属性的时候
我们可以从它的前一个位置
M的综合属性来获得
这时候本质上
我们也就是从M.s到B.ps
做了一个过渡
后边的是类似的
B可以把ps传递给它的子结点
然后在B→text的时候
我们也可以使用text的h属性和ht
来计算它的综合属性
在接下来因为有sub
所以说我们N结点的话
它的综合属性要做一个变换
也就是说从它的输入i属性做一个变换
得到N.s属性
这个属性就作为
我们B的继承属性得到
也就是说,当我们需要取得
当前B结点的继承属性的时候
我们事实上是从它的前一个结点
取得它的综合属性来获得的
在计算完毕的时候
它是推出text
所以说也是使用我们的text.h乘以我们的ps
得到ht综合属性
因为当前我们已经到了树的最右下结点
所以我们会反向的把属性向上推
共同的得到我们根结点的ht属性
到此为止
我们的根结点S的ht属性
保存的就是当前句子的整个高度
通过这样一个属性传递的顺序
我们就可以更清晰的看到
通过引入L、M、N三个虚拟非终结符
我们就可以保证每一个B结点
它的继承属性都可以从
在栈中它的前一个位置、前一个位置、前一个位置
它的综合属性
来模拟我们的继承属性
在接下来我们就看
如何把我们的语义规则
翻译成我们的栈代码
理解了前面的传递顺序的话
翻译过程应该是比较容易的
例如针对第1个产生式
S→LB
因为我们在这个规则中计算的是它的综合属性
所以说我们只需要
计算一个综合属性即可
我们通过改写语法规则
为我们的栈代码的话
我们就可以得到这样的代码
第1条 S→LB
因为我们计算的是S的ht综合属性
因此我们的方式
stack[top-1].value=stack[top].value
因为我们的语义规则
是S.ht=B.ht
所以说减1,略过的就是L属性
第2个产生式
L→ε
这是一个虚拟非终结符
我们的目的是给B做一个初始的继承属性
因此我们的栈代码就是
在top+1的栈位置
给它赋一个10
这个加一
因为我们当前产生式右部是一个空串
所以说我们事实上是在栈顶压了一个值
这个位置就是top+1
再接下来
B→B1 M B2
这个位置我们事实上计算的是
产生式左部B的综合属性
因此我们目前并不需要担心
M属性计算以及B2的继承属性
我们只需要考虑
B.ht=max{B1.ht,B2.ht]
所以我们栈代码也是比较简单的
栈的top减2这个位置
它等于top-2位置的属性和top的位置取大
然后并且赋值到top-2
这个时候top位置指的是 B2的属性
top减2略过了M,就是 B1的一个属性
这两个值取大
我们保存的就是产生式左部B的位置
减二,它会覆盖掉B1的位置
在接下来M→ε
因此能推出空串这样一个产生式
这个位置就是我们需要考虑的
使用综合属性
来替代继承属性的一个例子
这个位置top+1赋值和L是类似的
因为我们右部是一个空串
因此我们需要在栈顶压入一个 记号M
所以说我们赋值的位置是top+1
并且它的赋值
我们看一下是stack[top-1].value
也就是说
M的属性是从M的前一个位置获得
M出现的位置只在这个产生式中
并且当下M应该是空串
所以说
我们的top指的是B1这个位置
top-1 再往前前一个位置
这个时候我们就可以
把M的综合属性
用来模拟后续的B2的继承属性
我们就可以通过这一行代码来实现
在接下来B→B1 sub B2
产生式和第3个是非常类似的
区别只是在于
我们计算的时候前面是取大
这个地方使用的是一个
偏移display这样一个方式
因此我们只需要对这个代码进行改写即可
我们的方式就是
stack[top-3].value等于
stack[top-3].value和stack[top].value
作为参数传递给disp函数
并且把它赋值给top-3
top-3指的就是我们当前的栈的值
应该是B1 sub N B2
我们的栈顶指的是B2
向前减三,指向的就是B1的位置
所以说这个参数
首先我们取到的是B1的综合属性
而top指的是B2的综合属性
它们两个计算以后
经过弹栈以后
我们的最终栈顶B应该是保存在B1的位置
所以说这个位置是top-3
在下一个M→ε 的时候
和前面的 L M是类似的
我们同样是
从我们的 top-2的位置取出我们的值
在这个位置
N是出现在这个产生式中
N向前我们要减两个位置
也就是说当前N是空串
我们栈底应该是sub
往前B1
再往前,就是它前一个位置
它保存的就是我们输入的ps值
这个值因为是一个下标
所以说我们要对它做一个shrink的操作
它做一个减小操作
并且把它保存在stack[top+1]的位置
和前面类似,我们说
因为它推出的是空串
因此我们要在栈顶压一个N属性
所以说在栈顶加一的位置
我们压入一个值
最后一个B→text这样一个值
这就比较简单
因为text是我们的叶结点
因此text有一个词法记号值h属性
B.ht应该等于text.h乘以B.ps
这个时候
text.h是对应的就是当前位置的栈上的值
而ps就是我们的输入的值
输入值我们前面提过
因为我们引入了L、M、N
所以我们的B.ps
总是能够从它上一个位置获得
因此我们需要改写的时候
就是这样来写
我们的B.text
就是stack[top].value
就等于两个值的乘积
第1个值stack[top].value就是text
我们的词法记号的属性值
也就是点h这个值
而对应的stack[top-1]
它的值保存的就是
我们三个虚拟非终结符 L, M和N它的综合属性
我们说这三个综合属性
事实上描述的
就是B结点的继承属性
因此把它写在这个地方和我们原来的字面值做一个乘积
得到的就是我们的 B的属性
这个属性
就作为B的综合属性出现
到此为止
我们的语义规则
就完整的被翻译成了栈代码
并且我们使用
引入三个虚拟非终结符的方式
消除了我们必须在栈中
使用继承属性的例子
好
这就是本讲的内容
谢谢大家
-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