LL分析器是一种处理某些上下文无关文法的自顶向下分析器。因为它从左（Left）到右处理输入，再对句型执行最左推导出语法树（Left derivation，相对于LR分析器）。能以此方法分析的文法称为LL 文法。 本文中将讨论表格驱动的分析器，而非通常由手工打造（非绝对，参看如ANTLR等的 LL(*) 递归下降分析器生成器）的递归下降分析器。 一个 LL 分析器若被称为 LL("k") 分析器，表示它使用 "k" 个词法单元作向前探查。对于某个文法，若存在一个分析器可以在不用回溯法进行回溯的情况下处理该文法，则称该文法为 LL("k") 文法。这些文法中，较严格的 LL(1) 文法相当受欢迎，因为它的分析器只需多看一个词法单元就可以产生分析结果。那些需要很大的 "k" 才能产生分析结果的编程语言，在分析时的要求也比较高。 概览. 对于给定的上下文无关文法，分析器尝试寻找该文法的最左推导。例如，给定一个文法formula_1： 对formula_5的最左推导如下： formula_6 通常, 选择一条规则来展开给定的（最左的）非终结符时，有多个选择的可能。前一个关于最左推导的例子中， 在第2步： formula_7 我们有两条规则可以选择： 为了提高分析的效率，分析器必须能够尽可能确切地、无回溯地进行规则的选择。对于一些文法，它可以透过偷看不回推（即读取之后不将它退回输入流）的输入符号来做到这点。在我们的例子中，如果分析器知道下一个无回推符号是 formula_8 ，那么唯一正确可用的就是规则 2。 通常，formula_9 分析器可以向前探查 formula_10 个符号。然而，给定一个文法，若存在一个能识别该文法 formula_9 分析器，则其 formula_10 值的确定问题是不可判定的。也就是说，无法判定需要向前探查多少个符号才能识别它。对于每一个 formula_10 的取值，总存在无法被 formula_9 分析器识别的语言，而 formula_15 分析器却可以识别它。 通过上述梗概，下面我们给出 formula_15 的形式化定义： 设 formula_1 是一个上下文无关文法，且 formula_18。对于任意两个最左推导，当且仅当满足下述条件时，我们称 formula_1 是 formula_9 文法： 以下条件成立：串 formula_23 中长度为 formula_10 的前缀等价于串 formula_25 中长度为 formula_10 的前缀，表明 formula_27. 在该定义中， formula_28 文法的开始符号， formula_29 是任意非终结符。之前取得的输入 formula_30，以及还没回推的 formula_23 和 formula_25 均为终结符串。希腊字母 formula_33, formula_34 和 formula_35 代表任意终结符和非终结符组成的串（也可能是空串）。前缀长度与用于保存向前探查结果的缓冲区尺寸一致，并且该定义表明了，缓冲区足以区分任意两个不同单词的推导。 本分析器可以处理特定形式文法的符号串。 本分析器由以下部件组成： 分析器根据分析栈的栈顶符号（行）以及当前输入流中的符号（列）来决定使用哪一条规则。 当分析器一开始执行时，分析栈中已经有两个符号： [ S, $ ] '$'时一个特殊的终结符，用于表示分析栈的栈底或者输入的结束；而'S'则时文法的开始符号。分析器会尝试根据它在输入流中看到的符号来改写分析栈中的数据，但只会将仍需修改的数据存回分析栈中。 实际的例子. 设定. 为解释LL剖析器的工作方式，我们创造了以下这个小语法： 并处理以下输入： ( 1 + 1 ) 这个语法的剖析表如下： （注意到有一列特殊终端符号，在这里表示为$，是用来标示输入结束的。） 剖析流程. 剖析器先从输入资料流中读到第一个 '('，以及堆叠中的'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"的时候应该选用哪一条文法规则。我们可以轻松的发现到这种规则应该有"A" → "w"一类的格式，并且语言中的"w"应至少有一个字串由"a"开头。为了这个目的，我们设定 "第一个集合"(first set)的"w"，记作Fi（"w"），表示可以在"w"中找到的所有字串的集合，如果空字串也属于"w"的话还要再加上ε。而透过文法规则"A"1 → "w"1, ..., "A""n" → "w""n"，就可以使用以下方法演算每条规则的Fi("w""i")及Fi("A""i")了： 不幸的是，第一集合还不够用来产生出剖析表。由于规则中右手边的"w"可能无限制的被覆写成空字串，所以剖析器也在ε位于Fi（"w"）并且输入资料流中的符号可以符合"A"的时候套用"A" → "w"。所以还需要一个记作Fo（"A"）的"A"的"跟随集合"(follow set)，表示可以由开始的符号衍生出"αAaβ"字串的终端符号"a"的集合。非终端符号的跟随集合可以用以下方法得出： 现在我们可以清楚定义每条规则要放在剖析表的哪里了。若"T"["A","a"]用以表示表格中代表非终端符号"A"及终端符号"a"的规则，则 "T"["A","a"]包含"A" → "w"规则，若且唯若 "a"在Fi（"w"）之中，或 ε在Fi（"w"）之中，且"a"在Fo（"A"）之中。 若表格的每格中都仅包含一个规则，则剖析器总是知道该套用什么规则，所以可在不用回溯的前提下剖析字串。在此情形下，这个语法可以称为"LL(1)语法"。 建构LL("k")剖析表格. 剖析表格可能（一般来说，在最差状况下）必须有"k"次的指数复杂度的观念在1992年左右PCCTS发表后改观，它示范了许多程式语言可以用LL("k")来有效率的处理，而不会触发剖析器的最差状况。再者，在某些必须无限前瞻的状况下，LL剖析也是合理的。相反的，传统剖析器产生器，如yacc使用LALR(1)剖析表格建立被限制的LR剖析器，这种剖析器只能向后看固定的一个语汇符号。