LL(1)分析表构造算法在线视频

同学们

在上一节关于LL(1)

分析过程的讨论当中

我们发现

分析表指挥着LL(1)分析器

今天呢我们就和大家一起来看

怎样去构建LL(1)分析表

首先要明确

对于不同的LL(1)文法

LL(1)的分析算法是相同的

不同的仅仅是它的分析表

所以

如何根据文法来构造分析表

是LL(1)分析算法它的关键

期间需要特别注意的是

如果当文法当中的

某一个非终结符

出现在栈顶的时候

根据当前程序单词指针

所扫描到的这个输入符号

分析表

应该指示出要用这个非终结符的

哪一条产生式规则

也就是说

如何进行下一步的最左推导

下面我们就给出

LL(1)分析表它的构建规则

首先

要求出

每个非终结符号它的FOLLOW集

和每个候选式的FIRST集合

然后呢

对文法G当中的每个产生式

A→α

我们按照下面的规则来确定

分析表中的元素

对于

FIRST(α)当中的每个终结符a

要注意α不是ε

那么对于M[A a]=POP PUSH(α′)

或者是M[A a]=A→α

其中α′是这个产生式右部α的倒置

如果ε∈FIRST(α)

也就是说A→ε

那么对于属于

FOLLOW(A)当中的每个符号b

b呢是终结符或者是#

我们将M[A b]=POP

或者M[A b]=A→ε

我们把M中的所有M[a a]都设置为

POP NEXTSYM

a呢是我们说到的终结符

把M[# #]=ACCEPT

表示的是句子分析结束

但是这一项呢我们等会会讲到

它是可以简化的

最后

把M当中所有不按上述规则定义的元素

均设置为空或者是ERROR

在LL(1)分析器工作的过程当中

我们发现

如果压栈的最后一个符号是终结符的话

那么下一步的分析动作

肯定是这个终结符它的出栈

我们把这个环节简化一下

这个终结符不入栈

程序的单词指针后移

扫描下一个单词符号

这样的话我们分析表当中的

所有终结符行都可以去掉了

其次

所有的过程我们都可以换成对应的产生式

当非终结符A

面临的输入符号a

a是终结符或＃时候

它所应该选用的产生式

如果没有产生式的话

那么M[A a]就为出错处理(error)

我们来总结一下

预测分析表它的构造算法

输入是文法G

输出的是分析表M

它的算法步骤是这样子的

对于文法G当中的任意一个产生式

A→α

去执行第2步和第3步

对于任意属于FIRST(α)的终结符a

将A→α

填入到分析表的A行a列

如果ε属于FIRST(α)

而且a属于FOLLOW(A)

那么就将A→ε

填入到分析表当中的A行a列

如果ε属于FIRST(α)

而且#是属于FOLLOW(A)的话

那么就将A→ε

填入到M[A #]

将所有无定义的M[A b]

我们标注为出错标志

接下来我们来看下表达式文法

它的LL(1)预测分析表的构造过程

首先

FIRST(E)= {( i}

所以我们将分析表当中

E这一行的i列和(这一列设置为E→TE'

接下来我们来看一下FIRST(E’)={+ ε}

而且呢

FIRST(+TE)={+}

所以我们就将分析表E’行+这一列

设置为E'→+TE

由于ε属于E’的FIRST集

而且呢FOLLOW(E’)={) #}

那么就将分析表E’这一行的)列

#这一列设置为E’→ε

接下来FIRST(T ) = {( i}

所以将分析表T行这一列的

(和i行列设置为T→FT'

接下来再看

FIRST(T’)={* ε}

而且是FIRST(*FT')={*}

所以就将分析表

T’行*列设置为T'→*FT'

由于ε属于T’的FIRST集的

而且FOLLOW(T’)={+ ) # }

那么将分析表T’行的

+列

)列

和#这一列

设置为T’ →ε

再来看由于

FIRST(E)= {(}

那么就将分析表的E行(这一列

设置为F→(E)

又由于

FIRST(i)= {i}

所以我们就将分析表E行i列设置为F→i

表达式文法的LL(1)分析表的构建工作就此结束

我们可以利用算法1

构造任意给定文法它的分析表

但不是所有文法都能构造出

刚才每一项仅有一个产生式

或者是Error这种形状的分析表

如果分析表当中有多个产生式的话

那么这种文法并不是LL(1)文法

LL(1)分析表是不能包含多重定义的

也就是说二义性的文法

不能是LL(1)文法

同学们

这一章我们讨论了自顶向下的文法分析

从分析的过程当中我们面临的问题入手

寻找解决这些问题的方法

并且提出了没有递归

不含回溯的文法LL(1)文法

同时讨论了两种

确定的自顶而下的语法分析方法

递归下降分析法

和LL(1)分析法

下一章呢

我们将讨论自底向上的分析方法

这一节课就到这里

谢谢大家