当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.6 LR Parsing > 3.6.1 LR Parsing
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这一节我们来学习语法分析中
自下而上分析当中
一类重要的文法,LR分析文法
以及LR分析器
LR分析器
可以处理的是一大类文法
这类文法我们将它称之为LR(K)文法
K是指我们每次在进行分析的时候
需要向前所查看的符号个数
K=1的时候
通常我们就省略掉
也就是LR(1)
我们可以将它直接称为LR(1)文法
或者LR(1)分析器我们将它直接称为LR分析器
LR分析器采取的是LR分析方法
LR分析方法是我们在进行编译处理的时候
也就是语法分析处理的时候
自下而上分析中的一种
也是我们最为有效、最为常用的一种分析方法
接下来我们来看一下
LR分析器的特点
LR分析器适用于LR文法
它能处理一大类的上下文无关文法
它所处理的文法
比LL(1)文法
所对应的文法要更多
它的效率同时也要更高一些
我们主要学习LR分析表的三种技术
一种我们将它称为简单的LR分析方法
也就是SLR分析方法
一种叫做规范的LR(1)分析方法
通常我们就将它称为LR(1)分析方法
还有一种是在之前的基础上
稍加改进
我们将它称为向前看的 LR分析方法
简称LALR分析方法
我们先来学习一下整个LR分析器的特点
也就是它的移进归约分析
具体的动作是什么样的
我们仍然来观察一下这个图
LR分析程序在中间的位置
在LR分析表当中
我们将整个表分为了两部分
一部分称为action表,也就是动作表
第二部分
我们将它称为goto表,也就是转移表
那么在栈里边
我们观察到
栈里边除了符号之外,还有对应的状态
在栈底是s0,也就是初始状态
在栈顶,如果符号是Xm,对应的状态就是sm
而输入跟之前是一样的
从a1~aN我们仍然在输入末尾
加入$这个符号
为了描述LR语法分析的行为
我们引入了一个新的名词
我们将它称为格局
一个格局实际就是一个状态的意思
我们使用二元组来表示LR分析器所处的一个状态
我们观察一下
使用二元组的左边表示栈的内容
右边表示
我们还没有处理的符号栈的内容
我们将它从底向上写为s0 X1 s1 一直到Xm sm
也就是
除了初始状态s0之外
在每一次我们向栈里边压入一个符号之后
我们都需要在这个符号之上增加一个状态
后边是我们所没有处理的符号串
那么如果我们使用 Xi 来表示文法符号
si来表示状态
当前栈里边所处的
是一个移进归约分析的中间状态
也就是代表着一个右句型X1X2...Xmai...an
那么我们把它从Xm和ai分开
也就是在左边是我们已经处理的部分
右边是我们需要处理的部分
我们观察到
在LR分析器中
比之前的分析器
它多了一个状态
那么实际上这个状态
会表示更多的含义
状态的含义比符号本身的含义要更多
接下来我们来观察一下
LR分析器的各种格局
也就是各种状态
那么我们从初始状态开始
我们看一下
在初始状态的时候
栈里只有一个初始状态s0
然后s0的上边没有任何的符号和状态
而输入指向第1个符号a1
同样的
我们需要决定下一步的动作
仍然要根据栈顶的状态
和输入去查表
去查表的时候
我们需要去分析
去查动作表还是去查转移表
那么当前是根据状态和输入来查动作表
也就是action表
如果动作表里写的是移进
我们就要进行移进的动作
如果写的是归约,就要进行归约
假设我们已经进行到一个中间的状态
下一步是要移进
那么当前的状态是这样的:
在栈顶的元素它是Xm
Xm这个符号之上对应的状态sm
然后输入我们假设处理到 ai 这个符号
那么根据栈顶的元素sm这个状态和输入符号
我们去查action表
也就是去查动作表
我们发现动作表中写的是移进
然后还有移进之后
进入到S这个状态
那么我们就将 ai 移入到栈中
然后再将表中写入的移入之后的状态压入到栈中
也就是现在栈顶变成了s
压入符号是ai
也就是在我们进行移进之后
我们将 ai 移入到栈里边
将我们的状态s放入到栈底
这个时候
整个LR分析器的指针指向栈顶的符号s
接下来我们仍然去查表
假设我们根据栈顶的符号sm和输入的符号ai
去查动作表的时候
发现动作表中写的是需要进行归约
那么它会写明是
按照哪一个产生式来进行归约
假设按照A→β这个产生式来进行归约
那么如果按照这个产生式归约的话
我们需要参照β长度的两倍来弹栈
因为我们的栈中
除了符号之外,还包括状态
同样需要把状态弹出栈
所以我们将β长度的两倍这些符号弹出栈
在弹出栈之后
我们需要将整个产生式的左部A移入到栈中
我们将A移入到栈中之后
需要在E之上
填加归约之后的状态
这个时候需要去查对应的转移表
我们观察到
对于当前的状态
s(m-r)这个状态所对应的行、A所对应的列
如果写的状态是S
那么我们就将S压入到A之上
我们再看第3个状态
也就是接受的状态
我们根据栈顶的符号S和输入的符号$
我们去查表
发现在这个情况下
动作表中写的是接受这个状态
那么整个的输入
也已经处理到最后一个符号
而我们的栈里边也只剩X1
那么它应该是文法的开始符号
这个情况下
在我们的动作表中
如果写的是接受
我们就认为当前已经成功结束
当然还有第4种状态
也就是我们在进行查表的时候
发现动作表中
没有任何定义
也就是一个空白
那么意味着出错了
也就是当前的输入串
不满足我们当前的文法
这一小节就到这
谢谢大家
-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