当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.6 LR Parsing > 3.6.3 Simple LR
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这节课
我们来学习语法分析中
自下而上的分析方法中
SLR分析表的构造
为了来构造SLR分析表
我们需要来构造识别活前缀的DFA
为了构造识别活前缀的DFA
我们需要来学习
如何来计算LR0项目集
然后我们才能够造出识别活前缀的DFA
我们先来看一下LR分析表
它的主要作用
LR分析表是用来进行LR分析的
也就是LR分析的核心动作
它主要有两点
我们根据LR0项目
来构造识别活前缀的DFA
然后我们根据DFA来构造
对应的分析表
我们首先回顾一下活前缀是指
我们在分析栈里边出现的那些串
活前缀可以使用一个DFA来进行识别
比如说
我们给出大家一个如下的文法
S可以产生V=E
S可以产生E
V可以产生星号E
V可以产生id
E可以产生V
那么怎么把这个文法
对应的识别活前缀的DFA画出来呢?
这其实是一件很难的事情
想要直接来画是不可能的
我们需要去构造LR0项目集
然后才能来根据LR0项目集
构造识别活前缀的DFA
我们首先来看一下LR0项目集
LR0项目集是指一些由LR0项目组成的集合
那么什么是LR0项目呢?
LR0项目是指在产生式的右部某个合适的位置加点之后的产生式
我们可以通过一个例子来学习一下
假设有一个产生式A产生XYZ
我们可以在它的右部合适的位置加入点
比如说把它写为A产生点XYZ
A产生X点YZ
A产生XY点Z
A产生XYZ点
点的意思表示的是希望
在点的左边是指我们已经看到的部分
在点的右边表示我们希望看到的部分
比如说对于第1个项目,A产生点XYZ
此时我们什么都没有看到
我们接下来希望看到的是XYZ
对于第2个项目,A产生X点YZ
我们当前已经看到了X
接下来我们期望看到的是Y和Z
对于第3个项目,A产生XY点Z
我们当前已经看到了XY
接下来我们希望看到Z
对于最后一个项目A产生XYZ点
我们当前已经看到了XYZ
我们接下来不需要再看到其它的符号
我们其实可以想到
针对最后一个情况
A产生XYZ点
如果点已经出现在整个产生式的末尾
我们需要进行的是归约的动作
在这里加点的时候
有一个特殊的例子
对于A→ ε 这种情况下
我们加点之后
得到的LR0项目就是A→点
接下来我们从一个例子
来看一下如何来加点
假设有一个文法
E产生E+T或者T
T产生T×F或者F
F产生(E)或者id
那么我们观察到
这个文法当中它的开始符号是E
而E又出现在产生式的右部
所以为了加以区别
我们在整个文法的最前方
加入了一条文法
我们将它称之为拓广文法
也就是红色的这条,E'产生E
我们使用E'作为整个文法的开始符号
然后我们在进行移进归约的时候
如果归约得到了E'
我们认为整个的移进归约分析程序已经结束
那么针对id+id这个串
我们得到的最右推导动作在这里边
我们看到
对于E'→E串来说
它是宣告着整个移进归约分析动作的结束
我们来通过文法
构造LR0项目级的规范族
我们从I0这个状态出发
I0表示的是一个状态
首先我们从拓广文法这一条开始
我们将E'产生点E加入到I0当中
那么I0作为一个集合
我们需要去计算它的闭包
因为我们是来构造识别活前缀的DFA
DFA需要将所有当前状态的等价状态加进去
那么在这一步
我们实际上计算的是闭包函数
我们先来看一下
对一个闭包函数的含义
I中的每个项目加入到当前的闭包函数中
对于A产生α点Bβ
对于这个产生式来说
我们需要将B产生γ 这个产生式加入到当前的集合中
也就是B产生点γ
作为一个新出现的项目
需要加入到当前的闭包函数中
也就是这个项目
是当前项目的一个等价的状态
所以需要加入到 I0 当中去
我们观察一下
E'产生点E
点在E之前
E作为一个非终结符
它有对应的产生式
所以我们需要将 E产生点E+T、E产生点T 加入到I0当中
然后接下来我们又观察到点出现在了T之前
我们需要将T所有对应的产生式
加入到当前的状态I0当中
T产生点 T×F
T产生点F
接下来,点出现在F之前
所以我们需要将F对应的产式式加入其中
加了点之后
对应的F产生式变成了F对应的项目
F可以产生点 ( E )
F可以产生id
接下来我们继续看一下
I0是不是可以继续往其中加入更多的元素
也就是I0是不是可以继续来进行膨胀
如果I0不能继续膨胀
那么当前I0的计算就完成了
接下来我们看一下
对于I0当中,E'产生点E
这个项目是我们直接加入其中的
而剩下的6个项目
是由于点出现在产生式右部第1个非终结符号之前而加入的
也就是我们经过闭包函数计算所加入的项目
我们将这些项目称之为非核心项目
如果在计算的过程中
我们知道非核心项目是可以通过求闭包而得到
如果为了压缩空间
实际上非核心项目是可以不写的
在有了I0之后
接下来我们需要通过I0
来计算识别活前缀的DFA
也就是通过I0
我们可能碰到哪些符号
我们观察一下I0
那么在I0这个项目集中
点在E之前、T之前、F之前、左括号之前和id之前
也就是, I0应该碰到的是这些符号
是一个正确的状态转移
那么首先I0可能会碰到E
如果I0碰到E的话
我们用goto这个函数来表示这种情况
也就是goto(I0, E) 进入到 I1这个状态
goto函数的具体含义是这样的
假设我们有一个项目
A产生α点Xβ
真的碰到X之后,我们进入到一个新的状态
其中包含项目
A产生αX点β
这个项目对应的集合的闭包
也就是强调每一次
我们计算完一个集合之后
要计算当前集合对应的闭包函数
保证当前这个集合
不再膨胀了为止
那么针对 I1 来说,它从 I0 这个状态真的看到E点
从 I0 状态当中,所有E之前移动到E之后
就变为E'产生E点,E产生E点加T
接下来我们需要计算闭包函数
如果点没有出现在非终结符之前
那么当前 I1 不需要继续膨胀
也就是I1的计算完成了
接下来我们计算I2
I2是从I0出发
真的碰到了T所到达的状态
E产生T点
T产生T.×F
同样的不需要进行闭包函数的计算
然后我们来计算I3
I3是从I0出发碰到F所到达的状态
只有一条,T产生F点
接下来继续
我们要来计算I4
那么I4是从I0这个状态出发
碰到左括号所到达的状态
我们观察到 F产生左括号 点E右括号
接下来我们仍然需要去计算闭包函数
因为点出现在了非终结符E之前
所以E产生点E+T 需要加入到其中
E产生点T 需要加入到其中
而E产生点T 加入到其中之后
引起更多的闭包函数的计算
也就是T产生点T×F
T产生点F
然后点出现在了F之前
那么F对应的产生式需要继续加点之后
变为对应的项目
加入到其中
F产生点左括号E右括号
F产生点id
接下来I0还有最后的一个状态变化
也就是在它碰到id之后进入到I5这个状态
F产生id点
那么对于这个项目来说
不需要进行闭包的计算
接下来我们观察到I1这个状态
如果再碰到加号之后,进入到I6这个状态
那么I2这个状态
在碰到乘号之后,可能进入到I7这个状态
接下来I3这个状态对应的项目集
T产生F点
点出现在整个产生式的末尾
所以I3没有对应的状态转换
我们再来看I4
那么在I4碰到E之后,进入到I8这个状态
碰到T之后,进入到I2这个状态
碰到F之后,进入到I3这个状态
碰到左括号之后,进入到I4这个状态
当然回到I4这个状态
我们只写了 I4 当中的核心项目
碰到id之后,回到I5这个状态
我们把之前碰到的这些状态转换
画为对应的图
这个图就是识别活前缀的DFA
我们继续把I6、I7、I8等等
对应的状态都画出来
我们看到这是一个完整的当前文法
识别活前缀的DFA所画出来的图
我们根据这张图来构造SLR分析表
我们看一下
如何根据识别活前缀的DFA来构造SLR分析表
SLR分析表的一般过程是如下三步
首先我们观察一个文法
是不是需要进行拓广
如果需要进行拓广的话,
我们需要添加一个新的产生式 S'产生S
然后我们来构造识别活前缀的DFA
接下来根据识别活前缀的DFA来构造SLR分析表
那么在构造分析表的时候
我们分为几个大的步骤
首先我们来判断action,也就是动作表的填写
如果A产生α点aβ出现在一个状态Ii当中
并且Ii在碰到a之后
进入到 Ij 这个状态
那么在动作表中
这个状态 i 所在的行a所在的列
我们就把它填为移进这个动作
移进之后,进入到第 j 个状态
如果A产生α点 出现在 Ii 这个状态中
那么点已经出现在整个产生式的末尾
我们需要进行归约
那么参照哪些符号进行归约呢?
我们按照follow(A)中所有的元素a
我们将 i 所在的行a所在的列
写上归约这个状态
并且参照第 j 个产生式进行归约
第 j 个产生式对应的就是A产生α 这个产生式对应的编号
第3种情况
S'产生S点
如果在 Ii 这个状态中
我们知道这一条是拓广文法所在的状态
我们就将 i 所在的行$ 所在的列写为接受
在填完 action 动作表之后
如果发生了冲突
就说明当前这个文法不是SLR文法
然后接下来我们看一下goto函数
也就是转移表的构造
对于所有的非终结符A来说
如果在 Ij 这个状态
碰见A之后
进入到 Ij 这个状态
那么我们就在 i 所在的行、A 所在的列
我们填上进入到第 j 个状态
就是写上 j
我们如果在填完 action 表和goto表之后
发现有一些地方没有填写
没有填写的地方
都是置为出错的状态
分析器的初始状态是S'产生S对应的项目集所对应的状态
接下来我们来看一个例子
对于这个文法来说
它的状态I2当中包含的项目集
有E产生T点、 T产生T.×F
我们需要针对这两个项目集
来进行填写动作表和转移表
第1个项目E产生T点
点出现在整个产生式的末尾
需要进行归约
我们需要将follow(E) 取出来
假设follow(E)在求出来之后,是{ $, +, ) }
所以2所在的行
就是2这个状态所在的行
$所在的列、+加号所在的列以及 )括号所在的列
我们需要填写上进行归约
假设是参照2号产生式
E产生T来进行归约
然后第2个项目T产生T点×F
需要进行移进
碰到星号的时候移进
所以在2这个状态所在的行、星号所在的列
我们写上移进之后
进入到第7个状态,写为S7
这一小节就到这
谢谢大家
-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