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

各位同学大家好

这节课

我们继续来学习语法分析方法

我们来学习 LL 分析方法和LR分析的特点

也就是将这两种分析方法来进行对比

我们首先看一下 LR分析方法

我们知道

在进行移进归约的过程中

栈中的文法符号总是形成一个活前缀

比如说我们给出一个最右推导的过程

我们观察到

在移进归约的分析中栈里边

它一定是形成了一个活前缀

因为移进归约分析是最右推导的逆过程

我们可以通过这个分析表来分析一下

这边是输入

第1列是栈

那么栈里的符号串

总是我们标记的这些红色的部分

也就是它始终形成一个活前缀

第2个特点

分析表的转移函数

实际上是识别活前缀的DFA

我们看到这个是动作表

这边是转移表

转移表才是对应识别活前缀的DFA

第3个特点

栈里边这个状态符号

包含了确定句柄所需要的一切的信息

那么我们为什么还要放文法符号呢？

栈里放文法符号

是为了方便大家的理解

实际上文法符号是可以省略的

可以只写状态符号

下一个特点是：

LR分析方法

是已知的最一般的没有回溯的移进归约分析方法

此外它所能分析的文法

是预测分析方法所能分析文法的真超集

还有它可以及时发现错误

但是缺点我们也知道，是很明显的

手工来构造这张分析表的工作量非常大

我们再将 LL分析方法和LR的方法进行对比

首先是建立分析树的方式

LR分析方法是自下而上建立分析树进行归约

LL分析方法是自上而下来建立分析树进行推导

那么LR分析方法用的是规范归约

也就是最右推导的逆过程

LL分析方法用的是最左推导

我们再来看第3个对比方法

也就是决定使用产生式的时机

LR分析方法当中

它在看到了整个产生式的右部之后

再决定使用哪个产生式进行归约

而LL分析方法中

它只是看到产生式的第1个终结符

就决定接下来使用哪一个产生式

我们可以看一下推导的过程

假设从S开始进行推导

我们得到 γAbω

接下来我们将A推导为 lβ

那么如果在自上而下的分析中

LL分析方法决定使用产生式的位置

是在看到 l 之后就决定是由哪个产生式

而使用自下而上的LR分析法

我们是在看见了b之后才决定

将 lβ 归约为A

当然看得越多越准确

所以LR分析方法

它能分析的文法是更多

选择的时机是更好的、更准确的

再一个是对本法的限制

我们在学LL(1)文法的时候

学习了提取左因子、消除左递归

是因为LL这种分析方法

它不允许有左递归存在

而且也不允许有公共左因子存在

那么LR分析方法中我们发现

其实对文法没有明显的限制

下一个是分析表的比较

LR分析表（的大小）是状态数目乘以文法符号的数目

也就是状态数乘以终结符和非终结符个数的总和

分析表比较大

而LL分析表

是非终结符的个数乘以终结符的个数

分析表比较小

最后我们来比较一下分析栈

LR分析方法的栈是一个状态栈

当然我们也可以把符号放入其中

但是通常状态比文法符号包含的信息更多

而LL分析方法中它是文法的符号栈

接下来我们再看一下句柄

在LL分析方法中没有句柄的概念

在LR分析方法中

我们每次根据栈顶的状态和下一个符号

决定是不是有句柄出现

以及我们要进行归约

应该使用哪一个产生式

还有关于语法错误这一部分

对于LA分析方法来说

绝对不会将出错点之后的符号移入到栈中

LL分析方法和LR分析一样

绝不会读过出错点而不会报错

也就是它一定会报错

这一小节就到这

谢谢大家

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.6 Characteristics of LR Parsing在线视频

3.6.6 Characteristics of LR Parsing课程教案、知识点、字幕