当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.4 Top-Down Parsing > 3.4.1 First and Follow
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
今天我们继续来学习
语法分析中的内容
这节课我们重点来学习
First集合和follow集合
然后我们使用first集合
何方类集合
来定义L1文法
我们首先来看一下
First集合的定义
对一个串α来说
它的first集合是指
计算出来
满足α的句子所有可能的开头字符
那么first哈尔
就是一个'a'的集合
而'a'是α所能推导出来的串的首字母的集合
a属于终结符
我们看到这里有一个特殊情况
如果α经过推导之后
可以得到空串
那么空串就加入到First(α)的集合当中
接下来我们看一下
Follow集合的定义
假设有一个符号A
follow集合是只跟
在A后边所有的符号串的开头字符
同样的follow集
它也是一个终结符的集合
假设对于A来说
follow(A)等于
我们在计算语言的句型中
所有可能跟在A后边的字符
在这里仍然有一个特殊情况
假设A是我们整个文法的开头字符
也就是说A是我们的开始符号
那么我们说$
是属于follow(A)的
也就是我们在进行分析的时候
将$作为
开始符号后继的一个符号
这样我们知道
什么时候我们分析结束
所以$就作为开始符号的Follow集合中的元素
接下来我们来学习一下
First集合的求解方法
假设有一个符号X
假设X可以推导出a开头的字符串
那么a如果是一个终结符
就加入到first(X)的集合中
第二假设X可以推导为空串
那么空串就作为First(X)集合中的元素
第三假设X可以推导出以Y开头的字符串
那么我们将first(Y)去掉空串之后
加入到first(X)中
我们再来看一下第四种情况
这是前三种情况的一个一般情况
X可以产生Y1 Y2一直到Yk
那么它其实是一个总结的情况
我们可以从一般的情况开始进行推导
假设X可以产生Y1
我们需要将Y1的first集合
加入到X的first集中
假设X可以产生Y1Y2
我们将Y1的first集
去掉空串之后
加入到X的first集中
然后如果在Y1
可以推导为空串的情况下
我们需要将Y2的first集
加入到X的first集合中
假设Y1和Y2都可以推导为空串
在这种情况下
空串需要加入到X的first的集合中
接下来
如果X可以推导为Y1Y2Y3
我们首先取Y1的first集
去掉空串之后
加入到X的first集中
在Y1推导为空串的情况下
我们需要将Y2的first集取出来
去掉空串之后
加入到X的first的集合中
在Y1和Y2都可以推导为空串的情况下
我们需要将Y3的first集取出来
去掉空串之后
加入到X的first的集中
如果Y1Y2Y3都可以推导为空串
那么X的first集合中应该包含空串
接下来是一个一般的情况
X可以产生Y1 Y2一直到YK
Y1 Y2一直到Y i-1
它们都是非终结符
并且Y1Y2一直到Y i-1的first集合中
都包含空串
那么我们将first(Yj)中的所有非空串集合
加入到first(X)当中
j等于1 2 一直到i
接下来有一个特例
就是Y1~YK都包含空串产生式
那么我们才将空串加入到first(X)中
接下来我们来看一个具体的例子
S可以产生BA
A可以产生BS或者d
B可以产生aA或者bS或者c
我们来针对这个文法求解一下
这里边所有非终结符的first集合
我们可以通过第一个产生式
S可以产生BA
我们可以知道
S的first集应该等于B的first
也就是在这一步
需要将B的first集中
所有的元素加入到S的first的集合中去
根据A可以产生BS或者d
我们可以知道
first(A)应该等于
first(B)加上d这个符号
根据第三个产生式
B可以产生aA或者bS或者c
我们可以知道
First(B)应该等于a b c
这样我们就可以在先求出
First(B)的情况下
求出来first(S)和first(A)
接下来我们就可以知道
First(A)等于first(B)+d 也就是a b c d
而first(S)等于first(B) 也就是a b c
接下来我们再看另一个例子
E可以产生TE'
在这种情况下
我们知道
E的first集
应该等于T的first集
E'可以产生+TE'或者空串
那么可以计算得到
E'的first集合为+和空串
T产生FT'
所以T的first集
等于F的first集
因此first(E)和first(T)
还有F的first集合是一致的
T'可以产生×FT'
或者空串
所以first (T')等于×和空串
最后一条产生式F可以产生(E)或者id
我们可以计算得到
First(F)等于左括号( 加上id
这样我们就出求出来
产生式中
所有非终结符的first集合
接下来我们总结一下
First集合的含义
针对一个符号串α来说
α的first集合
就是从α开始
我们可以推导出来的
符号序列中的开头的终结符
也就是first集合
它是一个终结符的集合
接下来
我们来看一下follow集
follow集针对一个符号A来说
是指计算这个语言的句型中
所有可能跟在A后边的字符
接下来我们学习
follow集合的计算方法
首先针对一个文法符号的开始符号S
我们需要将$加入到S的follow集合中
第2种情况
A产生αBβ
这是一个一般的情况
我们看到B的后边跟着的是β
所以我们需要将β的first集合取出来
去调空串之后
加入到B的follow集中
第三种情况
A可以产生αB或者
A可以产生αBβ
而β经过推导之后
可以得到空串
也就是说
仍然是A可以产生αB这样的情况
如果是这样的话
我们需要将A的follow取出来
加入到B的follow集合中
我们再来看一个具体的例子
仍然是之前的这个文法
S可以产生BA
A可以产生BS或d
B可以产生aA或者bS或者c
我们可以发现
在计算follow集之前
我们需要先计算出First的集合
那么first集合
我们在上一步已经计算完成了
我们接下来需要去计算
所有非终结符的follow集
我们来看一下
这个文法计算follow集的具体步骤
首先我们将first集合写出来
然后我们观察到
S是这个文法的开始符号
所以我们将$加入到S的follow集合中
然后我们看到
第1个产生式 S产生BA
所以B的后边
跟着的是A的first集合
我们需要取出来
First(A)加入到follow(B)中
接下来我们看一下
第2个产生式
A可以产生BS
B的后边跟着的是S的第1个符号
所以我们需要取出来
First(S)加入到B的follow集中
接下来我们就可以计算出
Follow(S)中包括$
follow(B)中包括a b c d
我们观察到第三行产生式
B可以产生aA
在这种情况下
我们需要将B的follow集
加入到A的follow集合中去
接下来我们计算得到
A的follow集等于a b c d
我们观察到
还有一个产生式
B可以产生bS
根据这条产生式
我们需要将B的follow集
加入到S的follow集中去
在加完之后
我们可以得到
S的follow集等于a b c d和$
接下来我们再回头看一下
第一条产生式
S可以产生BA
我们需要将S的follow
加入到A的follow中去
这样A的follow集就变为a b c d $
根据这个文法
我们可以看出来
在计算follow集时
可能一遍是求不完整的
我们需要多次来重复计算follow集
直到所有的集合
不再膨胀为止
接下来我们看下一个例子
仍然是之前的这个文法
我们已经将first集合求出来
然后我们需要在first集合的基础上
计算所有非终结符的follow集合
首先我们看到
E作为文法的开始符号
我们将$符号取出来
加入到E的follow集中
然后我们观察到
第1个产生式
E可以产生TE'
我们需要将E的follow集
加入到E'的follow集中去
然后我们看到
T的后边跟着的是E'
所以取出E'的first集
加入到T的follow集中去
接下来我们看
第3个产生式 T产生FT'
根据这个产生式 我们可以知道
T的follow集
需要加到T'的follow集中去
然后FT'
我们可以知道
我们需要将T'的first集
加入到F的follow集中去
这是我们第1遍的计算结果
在此基础上
我们继续进行follow集的求解
我们仍然观察到
第1个产生式 E产生TE'
因为E'可以推导为空串
所以这个产生式
可以变为E产生T
我们需要将E的follow集
加入到T的follow集中去
同样的T产生FT'
由于T'可以推导为空串
所以需要将T的follow集
加入到F的follow集中去
这是我们第2遍计算的结果
我们在进行follow集合的求解的时候
需要多次重复的计算
直到所有的follow集
不再膨胀为止
这是最终的求解结果
这一小节就到这
谢谢大家
-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