当前课程知识点:Compilers Techniques >  3 Syntax Analysis >  3.2 Writing a Grammar >  3.2.1 Elimination of Left Recursion

返回《Compilers Techniques》慕课在线视频课程列表

3.2.1 Elimination of Left Recursion在线视频

下一节:3.2.2 Left Factoring

返回《Compilers Techniques》慕课在线视频列表

3.2.1 Elimination of Left Recursion课程教案、知识点、字幕

各位同学大家好

这一节我们来学习

编译技术中的语法分析

我们在上一章已经学习了正规式

在这一章

由于正规式的表示能力有限

我们来学习上下文无关文法

上下文无关文法

从数学上来说

它是一个四元组的表示形式

包括一组非终结符

一组终结符

一个产生式的开始符号

以及一个产生式的集合

我们看到上下文无关文法

可以用来进行推导

从而产生图形化的表示方式

产生分析树

那么到底如何来进行语法分析呢

在这节课

我们主要来学习

语法分析方法中的自上而下分析

我们来看一下

如何来进行语法分析

假设给定一个句子

id+id×id

我们需要从语法上进行分析

这个句子

是不是满足语法分析的要求

如何来完成语法分析呢?

方法有两种

一种是自上而下

一种是自下而上

我们看到针对这个句子

我们可以为这个句子

建立以文法的开始符号

为根节点的语法树

这样两种分析方法

去构造语法分析树

我们在进行自上而下

进行语法分析的时候

可能会碰到的问题有两个

首先 如果一个文法存在

左递归怎么办

我们看一下这样的情况是说

对一个文法 E 产生 E+E

那么如果 E 产生 E+E

我们在进行自上而下分析的时候

建立语法分析树的时候

就会出现这样的情况

我们将E推导为E+E

然后最左边的大E继续推导为E+E

最左边的大E

继续推导为E+E

也就是说E产生E+E

这个产生式它存在左递归

如果存在左递归的文法

我们一直进行推导

就会导致这个递归

一直向下进行

没有尽头

在进行自上而下分析中

我们碰到的第2个问题是

如果一个文法

在一步的推导中

存在着多个选择

怎么来完成这个任务呢

我们看一个例子

假设对于一个文法

S产生aCb

C可以推导为cd或者c

我们在为一个输入串W等于acb建立语法树

第1步

我们将S推导为aCb

第2步

我们在推导C的时候

我们就要考虑是将C推导为cd

还是将C推导为c

也就是说

在这一步

我们存在着两个选择

这种两个选择

会导致我们在这一步

如果一旦匹配错误

就会出现回溯

而回溯就会导致

我们整个

之前做过的工作需要重来

难以报告出错的位置

我们看到刚才这两个问题

如果想要避免这两个问题

我们就需要解决上述两个问题

也就是说文法

它不能够一直进行左递归

也就是我们要求文法

不允许存在所递归

第2步

我们要求每一步的推导中

只能有一个选择

也就是不允许存在多个选择

那么消除左递归

我们会考虑到每一步的推导

不能由于左递归的存在

而陷入死循环

所以为了采取自上而下的分析

必须消除左递归

每一步的推导

我们可能出现的产生式

也必须是唯一的

我们需要在文法存在左因子的时候

采取提取左因子的方法

去消除这一步出现的多个选择

接下来我们学习一下

如何消除左递归

假设存在着一个文法

A可以产生Aα

那么这是一个明显包含左递归的产生式

我们把这种左递归的情况

进行总结一下

对于一个一般的产生式

我们可以总结为

A可以产生Aα 或者β

如果A可以产生Aα 或者β

那么A产生的串的特点

就是一个以β开头αα...结尾的这样的一个串

我们针对这个串的特点

可以对它来进行改写

我们可以将文法改写为

A产生βA'

A'用来表示N个α

所以A'可以产生αA'或者空串

这样我们就可以通过改写文法

将左递归消除掉

我们来看一个例子

假设我们有一个算术表达式

E可以产生E+T或者T

T可以产生T×F或者F

F可以产生带括号的E或者id

我们看到第1个产生式

E产生E+T或者T

它就是一个包含左递归的产生式

那么这个产生式串的特点

E可以生成

T+T+T+T...这样的串

所以经过改写之后

就可以变成E产生TE'

而E'用来表示那些N个+T的串

所以E'可以产生+TE'或者空串

第2个产生式T产生T×F或者F

在这个产生式中

T可以生成的串是

以F开头、×F×F...结尾的串

所以根据这个串的特点

我们仍然可以套用之前的公式

将它改写为T产生FT'

用T'来表示那些×F的串

所以T'可以产生成×FT'或者空串

最后F的产生式

不需要发生变化

我们就可以将消除

左递归之后的文法

跟原来的文法进行比较

在消除左递归之后

我们再进行自上而下推导时

就不会出现无限递归的情况

接下来我们来看一下

消除左递归之后的文法

如何来避免左递归

假设有一个输入的串id+id×id

我们从根节点开始进行推导

首先E只有一个选择

E可以推导为TE'

然后我们按照自上而下

从最左推导的原则

推导T

T可以推导为FT'

然后F可以推导为id

因为我们是向着成功的方向去努力

所以将F推导为id

接下来是T'

我们看到T'实际上有两个选择

一个是×FT'

一个是空串

在这一步为了成功

我们将T'推导为空串

接下来是E'

我们将它推导为+TE'

然后我们继续推导T

将T推导为FT'

接下来F推导为id

然后T' 我们将他推导成×FT'

接下来这个F我们把它推导为id

这个T'推导为空串

最后一个E'推导为空串

我们看到这样一个

自上而下的构建过程

由于消除了左递归

它可以顺利的进行每一步的选择

最终得到一个正确的语法分析树

我们再来看一个例子

间接左递归如何来进行消除

假设我们给定一个文法

S可以产生Ac或C

A可以产生Bb或b

B可以产生Sa或者a

我们发现

其实这里不包含直接左递归

但是是包含间接左递归的

所以我们在消除左递归时

需要进行代换

代换完成之后

将间接左递归变为直接左递归

然后再来进行消除

我们把B的定义

带入A的产生式中

这样我们就得到

A产生Sab或者ab或者b

然后

我们再将A的定义带入到S的产生式中

最终我们就得到

S产生Sabc或者abc或者bc或者c

然后我们根据这个S产生式

来消除左递归

S可以产生abcS'或者bcS'或者cS'

S'可以产生abcS'或者空串

在变为直接左递归之后

我们将多余的产生式删掉

最终我们就可以得到

我们想要的结果

接下来我们看一下

消除左递归的一般方法

我们对一个产生式A产生

Aα1或者Aα2或者AαN

后边跟着的串是β1或者β2一直到βm

对于这个产生式

我们可以使用如下的产生式

来进行替换

A产生β1B或者β2B一直到βmB

我们在这里

使用B来替代之前写过的A'

B可以产生α1B

或者α2B一直到αnB或者空串

在这样两步替换之后

我们就将一个一般的左递归的形式

改写为消除左递归之后的文法

我们可以看到

针对消除左递归的算法

可以针对上述的一般的形式

把它进行一个代换

也就是

为我们的非终结符来进行编号

在采取代入的方法

将间接左递归变为直接左递归

然后再来消除直接左递归

以上就是我们这一节所学的

消除左递归的算法

这一小节结束

谢谢大家

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.1 Lexical Tokens, Strings and Language

-2.2  Regular form

--2.2 Regular form

--2.2 Regular form

-2.3  Finite automata

--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.2.1 Elimination of Left Recursion笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。