LL分析器


上下文无关文法
语法分析器
· LL分析器
· 算符优先分析器
· LR分析器
· SLR分析器
· LALR分析器

LL分析器是一种处理某些上下文无关文法自顶向下分析器。因为它从Left)到右处理输入,再对句型执行最左推导出语法树(Left derivation,相对于LR分析器)。能以此方法分析的文法称为LL 文法

本文中将讨论表格驱动的分析器,而非通常由手工打造(非绝对,参看如ANTLR等的 LL(*) 递归下降分析器生成器)的递归下降分析器

一个 LL 分析器若被称为 LL(k) 分析器,表示它使用 k词法单元向前探查。对于某个文法,若存在一个分析器可以在不用回溯法进行回溯的情况下处理该文法,则称该文法为 LL(k) 文法。这些文法中,较严格的 LL(1) 文法相当受欢迎,因为它的分析器只需多看一个词法单元就可以产生分析结果。那些需要很大的 k 才能产生分析结果的编程语言,在分析时的要求也比较高。

概览

对于给定的上下文无关文法,分析器尝试寻找该文法的最左推导。例如,给定一个文法 

  1.  
  2.  
  3.  

 的最左推导如下:

 

通常, 选择一条规则来展开给定的(最左的)非终结符时,有多个选择的可能。前一个关于最左推导的例子中, 在第2步:

 

我们有两条规则可以选择:

  1.  
  2.  

为了提高分析的效率,分析器必须能够尽可能确切地、无回溯地进行规则的选择。对于一些文法,它可以透过偷看不回推(即读取之后不将它退回输入流)的输入符号来做到这点。在我们的例子中,如果分析器知道下一个无回推符号是   ,那么唯一正确可用的就是规则 2。

通常,  分析器可以向前探查   个符号。然而,给定一个文法,若存在一个能识别该文法   分析器,则其   值的确定问题是不可判定的。也就是说,无法判定需要向前探查多少个符号才能识别它。对于每一个   的取值,总存在无法被   分析器识别的语言,而   分析器却可以识别它。

通过上述梗概,下面我们给出   的形式化定义:

  是一个上下文无关文法,且  。对于任意两个最左推导,当且仅当满足下述条件时,我们称    文法:

  1.  
  2.  

以下条件成立:串   中长度为   的前缀等价于串   中长度为   的前缀,表明  .

在该定义中,   文法的开始符号,   是任意非终结符。之前获取的输入  ,以及还没回推的    均为终结符串。希腊字母  ,    代表任意终结符和非终结符组成的串(也可能是空串)。前缀长度与用于保存向前探查结果的缓冲区尺寸一致,并且该定义表明了,缓冲区足以区分任意两个不同单词的推导。

本分析器可以处理特定形式文法的符号串。

本分析器由以下部件组成:

  • 一个输入缓冲区,存放输入符号串(由语法建立的)。
  • 一个分析栈,用于储存等待处理的终结符非终结符的。
  • 一张分析表,标记了是否存在可用于目前分析栈与下一个输入符号的语法规则。

分析器根据分析栈的栈顶符号(行)以及当前输入流中的符号(列)来决定使用哪一条规则。

当分析器一开始执行时,分析栈中已经有两个符号:

[ S, $ ]

'$'时一个特殊的终结符,用于表示分析栈的栈底或者输入的结束;而'S'则时文法的开始符号。分析器会尝试根据它在输入流中看到的符号来改写分析栈中的数据,但只会将仍需修改的数据存回分析栈中。

实际的例子

设置

为解释LL分析器的工作方式,我们创造了以下这个小语法:

  1. S → F
  2. S → ( S + F )
  3. F → 1

并处理以下输入:

( 1 + 1 )

这个语法的分析表如下:

1 + $
S 2 - 1 - -
F - - 3 - -

(注意到有一列特殊终端符号,在这里表示为$,是用来标示输入结束的。)

分析流程

分析器先从输入资料流中读到第一个 '(',以及堆栈中的'S'。从表格中他发现必须套用规则 (2);它必须将堆栈中的'S'重写为 '( S + F )',并将规则的号码输出。最后堆栈变成:

[ (, S, +, F, ), $ ]

再来它移除输入及堆栈中的 '(':

[ S, +, F, ), $ ]

现在分析器从输入资料流中抓到一个'1',所以他知道必须套用规则 (1)与规则 (3),并将结果输出。则堆栈变成:

[ F, +, F, ), $ ]
[ 1, +, F, ), $ ]

接下来的两个步骤中,分析器读到'1'及 '+',因为他们跟堆栈中的资料一样,所以从堆栈中移除。最后堆栈剩下:

[ F, ), $ ]

再接着的三个步骤中,堆栈中的'F'会'1'被取代,而规则 (3)会被输出。再来堆栈与输入资料流中的'1'与')'都会被移除。而分析器看到堆栈与输入资料流都只剩下'$'的时候,就知道自己的事情做完了。

在这个例子中,分析器接受了输入资料,并产生以下输出(规则的代号):

[ 2, 1, 3, 3 ]

这的确是从输入的左边优先推导。我们可以看出由左至右的输入顺序为:

S → ( S + F ) → ( F + F ) → ( 1 + F ) → ( 1 + 1 )

备注

由以上示例可以看出分析器根据堆栈最上层为非终端符号、终端符号、还是特殊符号$来决定采取三种不同的步骤:

  • 若堆栈最上层为非终端符号,则根据输入资料流中的符号对照分析表,决定要用语法中的哪条规则来取代堆栈中的资料,顺带输出规则的号码。若表格中并没有这么个规则,则回报错误并终止执行。
  • 若堆栈最上层为终端符号,则与输入资料流中的符号比较。若相同则移除,若不同则回报错误并终止执行。
  • 若堆栈最上层为'$',并且输入资料流中也是'$',则表示分析器成功的处理了输入,否则将回报错误。不管怎样,最后分析器都将终止执行。

这些步骤会持续到输入结束,然后分析器成功处理了一则左边优先推导,或者会回报错误。

建构LL(1)分析表格

为了要填满分析表格,我们必须决定分析器在堆栈看到非终端(nonterminal)符号A又在输入资料流看到a的时候应该选用哪一条文法规则。我们可以轻松的发现到这种规则应该有Aw一类的格式,并且语言中的w应至少有一个字符串由a开头。为了这个目的,我们设置 第一个集合(first set)的w,记作Fiw),表示可以在w中找到的所有字符串的集合,如果空串也属于w的话还要再加上ε。而透过文法规则A1w1, ..., Anwn,就可以使用以下方法演算每条规则的Fi(wi)及Fi(Ai)了:

  1. 将每个Fi(wi)及Fi(Ai)初始成空集合
  2. Fi(wi)加入每条Aiwi规则中的Fi(Ai),Fi定义如下:
    • 所有的a皆为终端符号时,Fia w' )= { a }
    • FiA)不包含ε时,相对于每个非终端符号AFiA w' )= FiA
    • FiA)包含ε时,相对于每个非终端符号AFiA w' )= FiA)\ { ε } ∪ Fiw'
    • Fi(ε) = { ε }
  3. 针对每条Aiwi规则,将Fi(wi)加入Fi(Ai)
  4. 重复步骤2与步骤3,直到所有Fi集合固定下来。

不幸的是,第一集合还不够用来产生出分析表。由于规则中右手边的w可能无限制的被改写成空串,所以分析器也在ε位于Fiw)并且输入资料流中的符号可以符合A的时候套用Aw。所以还需要一个记作FoA)的A跟随集合(follow set),表示可以由开始的符号派生出αAaβ字符串的终端符号a的集合。非终端符号的跟随集合可以用以下方法得出:

  1. 将每个Fo(Ai)初始成空集合
  2. 若存在AjwAiw' 格式的规则,则
    • 若终端符号a存在Fiw' )中,则将a加入Fo(Ai)
    • 若ε存在Fiw' )中,则将Fo(Aj)加入Fo(Ai)
  3. 重复步骤2直到所有Fo集合固定下来

现在我们可以清楚定义每条规则要放在分析表的哪里了。若T[A,a]用以表示表格中代表非终端符号A及终端符号a的规则,则

T[A,a]包含Aw规则,当且仅当
aFiw)之中,或
ε在Fiw)之中,且aFoA)之中。

若表格的每格中都仅包含一个规则,则分析器总是知道该套用什么规则,所以可在不用回溯的前提下分析字符串。在此情形下,这个语法可以称为LL(1)语法

建构LL(k)分析表格

分析表格可能(一般来说,在最差状况下)必须有k次的指数复杂度的观念在1992年左右PCCTS发表后改观,它示范了许多编程语言可以用LL(k)来有效率的处理,而不会触发分析器的最差状况。再者,在某些必须无限前瞻的状况下,LL分析也是合理的。相反的,传统分析器产生器,如yacc使用LALR(1)分析表格建立被限制的LR分析器,这种分析器只能向后看固定的一个语汇符号。

参见

外部链接