LL(1)文法分析

自顶向下

自顶向下是一种从开始符号推导出输入符号所对应的语法的过程,举个例子:

上面便是个从开始符号S出发,推导出aabb语法情况的过程,可以通过这个信息产生语法树。

那么如何推导呢?下面是通过一个栈来做的穷举推导过程,这种推导是需要回溯的:

上面的例子里面,出栈一个非终结符的时候,便从这个终结符的几个产生式里找一个做尝试,如果此路不通,就回退到尝试的路口,然后换一个产生式继续努力,直到找到一条看起来可以走下去的路继续重复以上的步骤(如果所有产生式都不能走通,就判断为语法有问题)。

可以想象,如果从A开始就选错了产生式,然后B尝试了所有产生式都没走通,那么回溯的层次就不仅仅是B自己一层了。这就好像一条路有X个岔路,然后每个岔路又有各自Y个岔路,而每个子岔路下面仍然有可能有Z个岔路,而目的地是X5Y2Z8,这种做法好像赌博碰运气一样,看天吃饭。有没有其他好的方法呢?

目前的问题是如何选择一个合适的产生式,如果我们可以快速选择到合适的产生式,效率必然会有很明显的提升。因为上面的例子并不是LL(1),我们重新举个例子,同时这个例子还免费赠送了一个叫做预测表的东西,我们还加了一个$符号作为结束符号:

可以看到,使用预测表的情况下,推导上并没有做回溯,那么如何创建预测表呢?

创建预测表

创建预测表之前,需要先明确三个概念:

  • Nullable(α):如果α*=>ε,α就是Nullable的;
  • First(α):这个函数返回的是α*=>cγ中的终结符c的集合(其中γ可能为为空);
  • Follow(A):函数返回的是S=>αAaβ中的终结符a的集合(其中α和β可能为空)。

通俗的说,一个产生式能推导出空串,那么产生式左部的非终结符就是Nullable的;First(α)集合中的终结符出现的时候,就可以推测出可能要产出α了;Follow(A)是推出A以后,后面出现的终结符应该是在Follow(A)中的。

然后,通过Frist,Follow和Nullable构造表:

  1. 构造一个空表M
  2. 遍历每个产生式A->α:
    1. 每个Frist(α)中的终结符a添加A->α到M[A, a]中;
    2. 如果Nullable(α),每个Follow(A)中的终结符a添加A->α到M[A, a]中。

因为这个预测表预测的是当前非终结符是A的时候,读入a时可能用到的产生式,所以当A的产生式的First集合里a对应的产生式是最可能的嫌疑人,不过当Nullable(α)的时候,A也有可能因为推出空,所以Follow(A)中有a的产生式也有嫌疑。

根据上面的表格构造过程,考虑当M[A, a]是否有可能有很多对应的产生式呢?如果出现这种情况,LL(1)文法是不支持的,这被称为有二义性。那么我们反推一下上面情况下会有二义性:

  1. 产生式A->α中,A和First(α)相同的情况,比如A -> xM | xN;
  2. 如果Nullable(α),Follow(A)和First(α)有交集,比如A->xC | B, B-> ε, D-> yAx

那么我们回头来看Nullable,First集和Follow集怎么计算:

Nullalble

下面是一段计算所有产生式是否为Nulalble的伪代码:

也就是说产生式里面所有符号都是Nullable的,或者干脆直接就产生空串,左部的非终结符就是Nullable的,这个计算过程可能会是个递归的过程。

First集

First集就是对一个符号推导的时候,第一个可能出现的终结符的集合。

下面我们分情况讨论:

  • 终结符的First集合包含的就是它自己
  • 非终结符计算的时候要分情况
    • A->aXYZ:明显First(A)应该有终结符a,First(A) = First(A) ∪  First(a),这里First(a)自然就是a自己的集合
    • A->XYZ这种第一个符号是非终结符的情况,First(A)自然就是First(XYZ),为什么不是First(X)呢,因为X有可能为空。
      • 当X不为空的时候,自然First(A) = Frist(A) ∪ First(X)
      • 当X为空的时候,First(A) = First(A) ∪ First(X) ∪ First(YZ),这里First(YZ)是什么,和First(XYZ)是一样的推导方式

以下是相关逻辑的伪代码,要注意的是求First的过程中会有递归求解的过程。

Follow集

Follow集的求解过程大概分几种情况:

  • 如果是开始符号S,那么实际上其后面是什么都没有的
  • 对于非终结符
    • X -> αAβ,Follow(A) = Follow(A) ∪ First(β)
    • X -> aAβ,如果Nullable(β) = true,Follow(A) = Follow(A) ∪ Follow(X)
    • X -> aA,Follow(A) = Follow(A) ∪ Follow(X)

以下是求Follow集的伪代码,同样也要注意求解过程中存在递归情况:

LL(1)文法要求

LL(1)文法的要求不是二义性的,也不包含左递归。如果G是LL(1)文法,那么可以通过文法G的任意两个不同的产生式A->α | β 满足下面几个条件:

  1. 不存在终结符a,使得α和β导出的串都以a开始;
  2. α和β中至多有一个能导出空串;
  3. 如果β*=>ε,那么α不能导出FOLLOW(A)中的终结符开始的任何串(也就是FOLLOW(A)和FIRST(α)不能有交集)。

读入一个终结符(或者空串)的时候,不应该存在产生式无法判断选择哪个产生式的情况(也就是二义性,情况一的时候有两个相同的FIRST可以选择;情况二都可以推出空串;情况三则会导致不知道选择A这个FIRST的产生式,还是选择A为空,预测表会有冲突。

所以实际上,上面三个条件就是用来判断两个相同或者不相同的非终结符的产生式有没有二义性的检查方法。

至于为什么要求没有左递归呢?假设有一个左递归A -> Aα,A -> AAa,  A->AAAa,那么可以想象推导会一直堵在这里变成一个死循环,毕竟这是一个自顶向下推导的过程,这样的左递归形式会导致推导过程无法结束。还有些左递归比较难发现,A -> Ba, B -> Ab,这种构成了循环的引用左递归A -> Aba了。左递归是可以想办法消除的,比如:

上面是消除左递归的大概方法,至于具体消除的原理和实现,因为没深究,就不写在这里了。

当文法中存在相同的左因子的时候,也是可以通过提取公因式来消除的:

消除后也就去除了这一类冲突。

发表评论

电子邮件地址不会被公开。 必填项已用*标注