LL分析器
概览
对于给定的上下文无关文法，分析器尝试寻找该文法的最左推导。例如，给定一个文法
：
- 1.
对
的最左推导如下：
通常, 选择一条规则来展开给定的（最左的）非终结符时，有多个选择的可能。前一个关于最左推导的例子中， 在第2步：
我们有两条规则可以选择：
- 1.
为了提高分析的效率，分析器必须能够尽可能确切地、无回溯地进行规则的选择。对于一些文法，它可以通过偷看无回推（即读取之后不将它退回输入流）的输入符号来做到这点。在我们的例子中，如果分析器知道下一个无回推符号是 
，那么唯一正确可用的就是规则 2。
通常，
分析器可以向前探查 
个符号。然而，给定一个文法，若存在一个能识别该文法 
分析器，则其 值的确定问题是不可判定的。也就是说，无法判定需要向前探查多少个符号才能识别它。对于每一个 
的取值，总存在无法被 分析器识别的语言，而 
分析器却可以识别它。
通过上述梗概，下面我们给出 
的形式化定义：
设 
是一个上下文无关文法，且 
。对于任意两个最左推导，当且仅当满足下述条件时，我们称 是 
文法：
- 1.
以下条件成立：串 
中长度为 
的前缀等价于串 
中长度为 的前缀，表明 
.
在该定义中， 
文法的开始符号， 
是任意非终结符。之前获取的输入 
，以及还没回推的 和 
均为终结符串。希腊字母 
, 
和 
代表任意终结符和非终结符组成的串（也可能是空串）。前缀长度与用于保存向前探查结果的缓冲区尺寸一致，并且该定义表明了，缓冲区足以区分任意两个不同单词的推导。
本分析器可以处理特定形式文法的符号串。
本分析器由以下部件组成：
一个输入缓冲区，存放输入符号串（由语法创建的）。