当前课程知识点: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》慕课在线视频课程列表

4.4.2 Simulate the Parsing of Inherited Properties在线视频

下一节:5.1 Overview

返回《Compilers Techniques》慕课在线视频列表

4.4.2 Simulate the Parsing of Inherited Properties课程教案、知识点、字幕

各位同学大家好

今天我们继续第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的综合属性出现

到此为止

我们的语义规则

就完整的被翻译成了栈代码

并且我们使用

引入三个虚拟非终结符的方式

消除了我们必须在栈中

使用继承属性的例子

这就是本讲的内容

谢谢大家

Compilers Techniques课程列表:

1 Overview of Compilers Techniques

-1.1 Overview of Compilers Techniques

--Chapter 1 Overview of Compilers Techniques

--Overview of Compilers Techniques

2 Lexical Analysis

-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.2 Regular form

-2.3  Finite automata

--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 Syntax Analysis

-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.1.3 Derivations

--3.1.4 Ambiguity

-3.2 Writing a Grammar

--3.2.1 Elimination of Left Recursion

--3.2.2 Left Factoring

--3.2 Top-Down Parsing

-3.3 Languages and Grammars

--3.3 Languages and Grammars

--3.3 Language and Grammars

-3.4 Top-Down Parsing

--3.4.1 First and Follow

--3.4.2 LL(1) Grammers

--3.4.3 Recursive Descent Analysis

--3.4.4 Nonrecursive Descent Analysis

-3.5 Bottom-up Parsing

--3.5.1 Reductions and Handle

--3.5.2 Shift- Reduce Parsing

--Bottom-up Parsing

-3.6 LR Parsing

--3.6.1 LR Parsing

--3.6.2 Viable Prefixes

--3.6.3 Simple LR

--3.6.4 LR(1)

--3.6.5 LALR

--3.6.6 Characteristics of LR Parsing

--3.6.7 Non Ambiguous and Not LR Context-Free Grammars

4 Syntax-Directed Translation

-4.1 Syntax-Directed Definitions

--4.1.1 Attribute Grammars

--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.2.2 Stack Code

-4.3 L-Attributed Definitions

--4.3.1 L-Attributed Definitions

--4.3.2 Translation Schemes

--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 Organization and Management of Run-Time Storage Space

-5.1 Overview

--5.1 Overview

--Overview

-5.2 Global Stack Storage

--5.2 Global Stack Storage

-5.3 Calling Sequences

--5.3 Calling Sequences

-5.4 Non Local Names

--5.4 Non Local Names and dynamic scope

--Non Local Name

6 Intermediate Code Generation

-6.1 Overview of Intermediate Code Generation

--6.1 Overview of Intermediate Code Generation

-6.2 Declaration Statements

--6.2 Declaration Statements

7 Code Generation

-7.1 Issues in the Design of Code Generator

--7.1 Issues in the Design of Code Generator

-7.2 Target Machine

--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

--7.4 A Simple Code Generator

8 Design and Implementation of a Simple Compiler

-8.1 Demonstration of Compiler Framework based on Python

--8.1 Demonstration of Compiler Framework based on Python

-8.2 Basic

--8.2.1 Scanner

--8.2.2 Parser -1LRItem

--8.2.3 Parser-2ActionGoto

--8.2.4 SA

-8.3 SimpleJava

--8.3 SimpleJava

4.4.2 Simulate the Parsing of Inherited Properties笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。