3.6.7 Non Ambiguous and Not LR Context-Free Grammars慕课视频播放-Compilers Techniques-MOOC慕课视频教程-柠檬大学

各位同学大家好

这节课

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

我们首先看一下

什么样的文法是LR文法？

我们在进行自左向右

进行扫描分析串的时候

如果我们进行移进归约分析

总是能及时识别出栈顶是否出现了句柄

那么对应的文法就是LR文法的

但是还有一些文法

是非LR的上下文无关文法结构

我们来看几个例子

首先针对一个语言

假设L=wwR

wR用来表示w的逆

那么 w是一个ab的串

但是我们要求w和wR必须是逆的关系

我们可以把它写为上下文无关文法的结构

S可以产生aSa或者bSb或者空串

这样可以保证前后的 w是轴对称的

这个文法不是LR（文法）

因为我们看一下

比如说一个串

ababbbbaba

我们没有办法及时找到一个中间的位置

从而使它变成一个轴对称的结构

所以这个语言它不是LR的

也就是它是一个非LR的上下文无关文法结构

然后我们再看下一个例子

跟刚才的语言很类似

L=wcwR

我们在w和w的逆中间加了一个符号c

有了这个c之后

它就可以标志出什么时候

我们到达了一个中间位置

也就是我们可以找到

整个w和wR对称结构中间的一个轴

我们将它写为对应的文法

S可以产生aSa或者bSb或者c

有了这个c可以作为一个标志位出现

所以我们在进行移进归约分析串的时候

总是可以碰到c之后将c归为S

然后再继续进行移进归约分析

也就是每一次都可以准确的识别

哪些是句柄

准确的知道什么时候移进、什么时候归约

所以这个文法是LR（文法）

我们再来看一个例子

假设我们有一个语言 L=ambn

我们要求n的个数>m>=0

那么也就是说 b的个数始终是比a多的

我们要为语言来写三个文法

他们分别是LR(1)的、二义的

以及非二义并且非LR(1)的文法

我们来看一下

我们所写的第1个方法LR(1)文法

我们将它看成两部分

S可以产生AB

A可以产生aAb或者空串

B可以产生Bb或者b

写为了上下文无关文法之后

我们判断这个文法是LR(1)文法

因为每一次我们在进行移进归约的时候

可以准确的知道

什么时候移进、什么时候归约

也就是说

我们再看一下

底下串的例子，aaabbbbb

每一次看见a，我们就继续移进

一直看到第1个b之后

我们将空串归为A

然后我们得到A之后

我们在每一次碰见a和b之后

将aAB归为A

然后我们将A归约好之后

剩下的每一次一个B碰到一个b之后将它归为B

这样我们就可以准确的知道

每一步是移进还是归约

所以它是LR(1)文法

也就是它可以准确的找到活前缀

可以准确的找到句柄

假设仍然是这个语言

我们采取另一种文法

S可以产生aSb或者B

B可以产生Bb或者b

这文法是一个非二义的文法

并且它不是LR(1)文法

也就是说

我们没有办法准确的识别句柄

我们不知道什么情况下

把bB归约为B或者把b归约为B

没有办法找到合适的位置

我们看一下匹配的方式

我们看到所有的a之后，当然是移进

但是你看到第1个b之后

由于不知道后边有多少个b

没有办法判断什么时候把b归约为B

什么时候把bB归为B

第3种方法

我们仍然是利用这个文法

我们采取第3种二义性文法

将它写为S可以产生aSB或者Sb或者b

也就是说它其实可以有多种的匹配方式

比如说仍然对这个串，三个a和5个b

我们可以采取上边的匹配方式

也可以采取下边的匹配方式

它都可以按照二义文法

来进行一个合适的推导

这样的话

我们就没有办法知道

到底按照哪种方法来进行推导

也就是没有办法准确的知道

什么时候移进、什么时候归约

不知道什么时候产生合适的句柄

所以它是一个二义的文法

接下来我们讨论一下二义的文法

二义的文法首先它肯定不是LR文法

但是二义文法简洁自然

是符合我们正常人类的认知的

比如说我们看一下二义的文法和非二义的文法的对比

上面是二义的文法

E可以产生E+E或者E×E或者(E)或者id

它和我们一直的四则运算的写法是类似的

很容易理解

假设给它改写成非二义的文法

我们就观察到，其实是比较难理解

E可以产生E加T或者T

T可以产生T×F或者F

由于乘法是优先级更高

所以在这里边

改写成这种形式之后

它是一个非二义的（文法）

但是不是那么自然简洁

我们其实可以针对这些二义的文法

采取文法以外的信息去消除这种二义性

从而仍然可以让这样的文法使用LR分析方法

有二义的文法

它的语法分析效率比较高

因为你消除二义性之后，文法要更复杂

所以它得到的分析表会更大一些

我们看一下

如何使用文法以外的信息

来消除二义性

比如说对于二义文法来说

我们可以人工规定

乘法的优先级更高

也就是乘法的优先级高于加法的优先级

那么两者都是左结合的

我们在进行LR0项目级的计算的时候

假设得到I8

I8中包括E产生E*E点

E产生E点+E

E产生E点*E

那么我们在面临加号的时候

要进行归约

在面临右括号和$的时候

要进行归约

我们看到假设栈里是id×id

输入剩下的是加id

那么我们需要进行归约

如果栈里边是id×id

输入是乘id

那么我们仍然要进行归约

我们再看一个特殊的情况引起的二义性

比如说对于文法

E可以产生 E sub E sup E

E可以产生 E sub E

E可以产生 E sup E

E可以产生带括号的E

以及E可以产生c

其实我们观察到

第1条产生式

其实可以由后边的两条产生式合成得到

那么第1条产生式不是多余的呢？

从定义形式语言的角度来说

第1条产生其实是多余的

但是我们联想到语义

第1个产生其实是必要的

为什么呢？

我们来看一下这个例子

假设 a sub i sup 2

我们知道这个意思是说

第 i 个 a 来取平方

也就是

我们应该写为如下的三种形式中哪一种呢？

我们看一下

最后一种肯定是错的

这个平方应该是在 ai 之上，而不是在a之上

那么中间的一种这样的写法

其实也是不好看的

整个的平方它落在了ai作为一个整体之上

而第1种写法是我们最想要的

a 的下标是i，它的上标是2

而且 i 和 2 是在同一个竖线的纵列上

这样是最好看

所以我们在进行LR的分析中

假设碰到 I11

我们得到的 E 产生 E sub E sup E 点

E 产生 E sup E 点

这个时候

我们需要按照第1个产生式（归约）

它的优先级别更高

这一小节就到这

谢谢大家

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.7 Non Ambiguous and Not LR Context-Free Grammars在线视频

3.6.7 Non Ambiguous and Not LR Context-Free Grammars课程教案、知识点、字幕