3.4.4 Nonrecursive Descent Analysis在线视频

各位同学大家好

我们这节课来学习语法分析中的

非递归下降分析程序

我们来看一下

对于非递归的下降分析程序

它的结构是这样的一个图示

中间是预测分析程序

最下边是我们要用到的预测分析表

上侧是输入 也就是我们的程序

程序的结尾我们使用了$作为标记

最左侧是栈 我们放了一个$符号

如果栈底的$和我们输入的$相匹配

也就意味着成功结束

我们每一次根据栈顶的符号和一个输入符号

去查我们的预测分析表 来决定下一步的动作

所以我们会发现

这里边分析表是整个预测分析程序的基础

我们使用分析表去驱动预测分析程序

我们来看一下

预测分析表是什么样的呢

我们来看一下

一个预测分析表的例子

对于之前的文法

我们画出的预测分析表是这样的

树的方向是所有的非终结符

包括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文法

在进行自上而下分析中

进行非递归预测的时候

如何去构造非递归的预测分析表

并且使用这个表来分析我们的输入文法

这一小节就到这

谢谢大家