Википедия
См. также LL(1)
Синтаксический LL-анализатор (LL parser) — в информатике нисходящий синтаксический анализатор для подмножества контекстно-свободных грамматик . Он анализирует входной поток слева направо, и строит левый вывод грамматики. Класс грамматик, для которых можно построить LL-анализатор, известен как LL-грамматики .
Далее описывается анализатор, в основе которого лежит построение таблиц; альтернативой может служить анализатор, построенный методом рекурсивного спуска, который обычно пишется вручную (хотя существуют и исключения, например, генератор синтаксических анализаторов ANTLR для LL.
LL-анализатор называется LL(k)-анализатором, если данный анализатор использует предпросмотр на k токенов при разборе входного потока. Грамматика, которая может быть распознана LL(k)-анализатором без возвратов к предыдущим символам, называется LL(k)-грамматикой. Язык, который может быть представлен в виде LL(k)-грамматики, называется LL(k)o-языком. Существуют LL(k+n)-языки, которые не являются LL(k)-языками, то есть не все контекстно-свободные языки являются LL(k)-языками.
LL(1)-грамматики очень распространены, потому что соответствующие им LL-анализаторы просматривают поток только на один символ вперед при принятии решения о том, какое правило грамматики необходимо применить. Языки, основанные на грамматиках с большим значением k, традиционно считались трудными для распознавания, хотя при широком распространении генераторов синтаксических анализаторов, поддерживающих LL(k) грамматики с произвольным k, это замечание уже неактуально.
LL-анализатор называется LL-анализатором, если нет строгого ограничения для k и анализатор может распознавать язык, если токены принадлежат какому-либо регулярному множеству .
Существуют противоречия между так называемой «Европейской школой» построения языков, которая основывается на LL-грамматиках, и «Американской школой», которая предпочитает LR-грамматики. Такие противоречия обусловлены традициями преподавания и деталями описания различных методов и инструментов в конкретных учебниках; кроме того, своё влияние оказал Н. Вирт из ETHZ , чьи исследования описывают различные методы оптимизации LL(1) распознавателей и компиляторов.