LL分析器

对于给定的上下文无关文法，分析器尝试寻找该文法的最左推导。例如，给定一个文法${\displaystyle G}$ ：

1. ${\displaystyle S\to E}$ 
2. ${\displaystyle E\to (E+E)}$ 
3. ${\displaystyle E\to i}$ 

对${\displaystyle w=((i+i)+i)}$ 的最左推导如下：

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)}$ 

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

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}$ 

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

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

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

通过上述梗概，下面我们给出 ${\displaystyle LL(k+1)}$  的形式化定义：

设 ${\displaystyle G}$  是一个上下文无关文法，且 ${\displaystyle k\geq 1}$ 。对于任意两个最左推导，当且仅当满足下述条件时，我们称 ${\displaystyle G}$  是 ${\displaystyle LL(k)}$  文法：

1. ${\displaystyle S\ \Rightarrow \ \dots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \dots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \dots \ \Rightarrow \ wx}$ 
2. ${\displaystyle S\ \Rightarrow \ \dots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \dots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \dots \ \Rightarrow \ wy}$ 

以下条件成立：串 ${\displaystyle x}$  中长度为 ${\displaystyle k}$  的前缀等价于串 ${\displaystyle y}$  中长度为 ${\displaystyle k}$  的前缀，表明 ${\displaystyle \beta \ =\ \gamma }$ .

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

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

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

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

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

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

[ 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 )

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

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

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

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

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

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

1. 将每个Fo(A_i)初始成空集合
2. 若存在A_j → wA_iw' 格式的规则，则
   • 若终端符号a存在Fi（w' ）中，则将a加入Fo(A_i)
   • 若ε存在Fi（w' ）中，则将Fo(A_j)加入Fo(A_i)
3. 重复步骤2直到所有Fo集合固定下来

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

T[A,a]包含A → w规则，当且仅当

a在Fi（w）之中，或

ε在Fi（w）之中，且a在Fo（A）之中。

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

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

• 编译器分析器比较表
• 抽象语法树
• 由上而下分析
• 自底向上分析

• An easy explanation of First and Follow Sets （页面存档备份，存于互联网档案馆）（使用一种比c较直观的方法解释产生First与Follow集合的过程）
• A tutorial on implementing LL(1) parsers in C#