当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.2 Writing a Grammar > 3.2.1 Elimination of Left Recursion
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
这一节我们来学习
编译技术中的语法分析
我们在上一章已经学习了正规式
在这一章
由于正规式的表示能力有限
我们来学习上下文无关文法
上下文无关文法
从数学上来说
它是一个四元组的表示形式
包括一组非终结符
一组终结符
一个产生式的开始符号
以及一个产生式的集合
我们看到上下文无关文法
可以用来进行推导
从而产生图形化的表示方式
产生分析树
那么到底如何来进行语法分析呢
在这节课
我们主要来学习
语法分析方法中的自上而下分析
我们来看一下
如何来进行语法分析
假设给定一个句子
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或者空串
在这样两步替换之后
我们就将一个一般的左递归的形式
改写为消除左递归之后的文法
我们可以看到
针对消除左递归的算法
可以针对上述的一般的形式
把它进行一个代换
也就是
为我们的非终结符来进行编号
在采取代入的方法
将间接左递归变为直接左递归
然后再来消除直接左递归
以上就是我们这一节所学的
消除左递归的算法
这一小节结束
谢谢大家
-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