3.6.1 LR Parsing慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

这一节我们来学习语法分析中

自下而上分析当中

一类重要的文法，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种状态

也就是我们在进行查表的时候

发现动作表中

没有任何定义

也就是一个空白

那么意味着出错了

也就是当前的输入串

不满足我们当前的文法

这一小节就到这

谢谢大家

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

3.6.1 LR Parsing在线视频

3.6.1 LR Parsing课程教案、知识点、字幕

Compilers Techniques课程列表：

1 Overview of Compilers Techniques

2 Lexical Analysis

3 Syntax Analysis

4 Syntax-Directed Translation

5 Organization and Management of Run-Time Storage Space

6 Intermediate Code Generation

7 Code Generation

8 Design and Implementation of a Simple Compiler

3.6.1 LR Parsing笔记与讨论

也许你还感兴趣的课程: