当前课程知识点:Compilers Techniques > 3 Syntax Analysis > 3.4 Top-Down Parsing > 3.4.4 Nonrecursive Descent Analysis
返回《Compilers Techniques》慕课在线视频课程列表
返回《Compilers Techniques》慕课在线视频列表
各位同学大家好
我们这节课来学习语法分析中的
非递归下降分析程序
我们来看一下
对于非递归的下降分析程序
它的结构是这样的一个图示
中间是预测分析程序
最下边是我们要用到的预测分析表
上侧是输入 也就是我们的程序
程序的结尾我们使用了$作为标记
最左侧是栈 我们放了一个$符号
如果栈底的$和我们输入的$相匹配
也就意味着成功结束
我们每一次根据栈顶的符号和一个输入符号
去查我们的预测分析表 来决定下一步的动作
所以我们会发现
这里边分析表是整个预测分析程序的基础
我们使用分析表去驱动预测分析程序
我们来看一下
预测分析表是什么样的呢
我们来看一下
一个预测分析表的例子
对于之前的文法
我们画出的预测分析表是这样的
树的方向是所有的非终结符
包括E E' T T' 和F
而横向的方向
我们写的是所有的输入符号
也就是所有的终结符
包括id + * ( )以及$
然后我们会在中间这个位置
写入一些产生式
每一次我们根据一个非终结符和一个输入符号来查表
如果我们查到表里边包括一个产生式
我们就参照这个产生式来执行下一步的动作
如果查表的时候发现这个地方是空白
那也就是说明当前程序出现错误
不能向下进行
我们来看一个例子
假设有一个输入id×id加上id
我们使用刚刚看过的预测分析表来进行匹配
第1列是栈 第2列是输入 第3列是输出
首先输入是id×id加上id
在末尾我们加入$符号
我们在栈里边写入$置底
然后在上面加入产生式的开始符号E
也就是我们期望着
我们可以从E进行推导 最终得到我们的输入
自上而下构建语法分析树
那么第1步
我们取出栈顶元素和输入的第1个符号id去查表
我们看到在表中
E所在的行 id所在的列 写的是E产生TE'
所以我们在这一步
就输出我们在预测分析表中查到的内容
也就是E产生TE'
看到E产生TE'之后
我们将栈里的E弹出
将产生式的右部TE'逆序进栈
所以栈里就变成了$E'T
而输入没有发生变化
接下来我们根据栈顶元素T和输入id仍然去查表
我们发现表里边写的是T产生FT'
根据这条产生式
我们将T弹栈 FT'逆序进栈
所以栈里边就变成了$E'T'F
我们在这一步
仍然根据栈顶元素F和输入id来决定下一步的动作
去查表发现
表里边写的是F产生id
所以 我们将F弹栈 id入栈
然后输入还没有变化
在这一步
我们接下来发现
栈顶元素是id 输入是id 两个id是一样的
所以我们说匹配了id match
如果一旦匹配上之后
我们的输入指针就向后移动一位
也就是从id指向了乘号
而栈里边id弹栈
这个时候栈顶就变为T'
接下来我们就发现
有一个符号id被消耗掉了
然后我们根据栈顶元素T'和乘号来继续查表
发现表里边写的是T'产生*FT'
此时我们仍然需要
将栈里的T'弹栈, *FT'逆序进栈
所以栈顶元素就变成了乘号
和输入的乘号是一致的
仍然是进行了一次匹配
又消耗掉乘号*这个符号
所以输入这个时候就变成了id+id$
而栈里边变成了F作为栈顶
我们仍然需要去查表
根据F和id来查表
我们会发现表里边
继续写的其他内容
后边的 跟之前的过程是类似的
一直到最后一步
栈里边只剩下$ 而输入也只剩下$
就意味着成功结束
我们再来看一下
如何将预测分析表画出来
那么构造一个预测分析表
有如下的几个步骤
步骤1:每一次我们从文法的一个产生式开始
假设对于文法的一个产生式 A产生α
我们执行步骤2和3
步骤2:对于first(α)中的每一个终结符a
我们把 A产生α 加入A所在的行、a所在的列
步骤3:如果ε在first(α)中 我们需要求出来follow(A)
将follow(A)中的每个终结符b 包括$
我们把A产生α加入A所在的行、follow(A)所在的列
我们再把所有的产生式加完之后
会发现这个表中有一些地方没有填
那么没有填的地方 表示的是出错 不需要去填
我们把它总结一下
对于每一个产生式 A产生α来说
我们需要去判断ε是不是在first(α)中
如果ε不在first(α)中
我们就把first(α)中的每个a取出来
将A产生α加入到A所在的行、a所在的列
然后继续去判断这个产生式
而如果ε在first(α)中
我们需要考虑Follow(A)所在的列
我们需要将follow(A)中的b取出来 填入A产生α
其他所有没有填的 就是出错的状态
我们来看一个例子
针对一个文法
S产生ACD
A产生a或者ε
C产生c D产生d
我们首先需要将First集合和follow集合求出来
我们看到这里边还是比较容易的
对于first(D)来说 它等于d
first(C)={c}
first(A)={A, ε}
first{S)={a, c}
然后我们再来求follow集合
follow(S)={$}
follow(A)={c}
follow(C)={d}
follow(D)={$}
在求完first集和follow集之后
我们就可以来画这张预测分析表
我们将first集合和follow集合写在边上
我们每一次从我们的文法中取出一个产生式去填表
我们看到第1个产生式是S产生ACD
我们需要去求ACD的first集
所以我们将S所在的行a所在的列、c所在的列
写入S→ACD
接下来我们根据A→a填入A所在的行、a所在的列
A可以产生ε
我们需要讨论follow(A)
由于follow(A)={c}
所以将A所在的行、c所在的列写入A→ε
接下来是C→c 我们填入A所在的行、c所在的列
D→d 我们填入D所在的行、d所在的列
其他所有没有填的 其实是不需要写的
我们在这里边把它标注为出错
接下来我们再看一个if else这个文法的例子
我们看到在这里边
我们将它的文法写出来之后
可以根据第1个产生式
stmt→if expr then stmt e_part | other
根据第1条产生式
我们可以求出stmt的first集合和expr的follow集合
根据第二个产式e_part可以产生else stmt
我们可以求出来
将e_part的follow集加到stmt的follow集中
expr产生b 我们知道表达式的first集合应该包含b
所以求得的结果 First(stmt)={if, other}
这是根据第1条产生式得到的
first(e_part)={else, ε}
first(expr)={b}
而follow(stmt)包括else和$
e_part的follow集包括else和$
expr它的follow集包括then
在求完first集合和follow集合之后
我们可以发现一个问题
e_part的first集合中包括else
而它的follow其中也包括else
并且e_part的first集合中包含ε
这样我们在考虑e_part对应产生式的时候
由于e_part可以产生ε
我们就在填表的时候 需要考虑e_part的follow集
所以我们填表的结果
就变成这样了
e_part所在的行、else所在的列
我们首先将e_part→else stmt加入到其中
然后由于e_part可以产生空串
所以我们去找e_part的follow集
会发现e_part→ε也需要填在这个位置
我们知道在一个空格中
如果需要填两个产生式
实际上就意味着出现了冲突
也就是由于if else语句有二义性
会导致出现了这个问题
我们的做法是删除其中的一条
以保证它没有冲突
我们在这个地方
选择删除e_part→ε 以解决这个二义性问题
删除掉之后
我们就将原本多重定义的条目改为只有一种
这样的情况
if else语句是遵循我们程序中常用的就近原则
而LL1文法的证明可以知道
LL1文法构造出来的预测分析表中
是不包含多重定义的条目的
好
我们总结一下
我们在这节课
主要跟大家学习了LL1文法
在进行自上而下分析中
进行非递归预测的时候
如何去构造非递归的预测分析表
并且使用这个表来分析我们的输入文法
这一小节就到这
谢谢大家
-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