WikiSort.ru - Не сортированное

LL(1) — LL-анализатор, нисходящий алгоритм синтаксического разбора. Цифра 1 говорит, что для определения пути разбора нужна всего одна лексема.

Прост в написании вручную без использования автоматических генераторов. Используется для разбора кода в ряде языков программирования, таких, как Pascal.

Очень быстр в исполнении и имеет характерное сообщение об ошибке вида «ожидался такой-то символ».

Направляющие символы правила

Для каждого нетерминала A в грамматике генерируется множество терминалов First(A), определенное следующим образом:

• если в грамматике есть правило с A в левой части и правой частью, начинающейся с терминала, то данный терминал входит в First(A)
• если в грамматике есть правило с A в левой части и правой частью, начинающейся с нетерминала (обозначим B), то First(B) строго входит в First(A)
• никакие иные терминалы не входят в First(A)

Для каждого правила генерируется множество направляющих символов, определенное следующим образом:

• если правая часть правила начинается с терминала, то множество направляющих символов состоит из одного этого терминала
• иначе правая часть начинается с нетерминала A, тогда множество направляющих символов есть First(A)

Возможны обобщения этих определений для случая наличия правил вида A → null.

Понятно, что First(A) есть объединение множеств направляющих символов для всех правил с A в левой части.

Грамматика разбираема по LL(1), если для любой пары правил с одинаковой левой частью множества направляющих символов не пересекаются.

Описание анализатора

Используется стек, где находятся номера терминалов и нетерминалов, входной (терминалы) и выходной (номера правил) потоки.

Сначала в стек заносится E — начальный символ грамматики.

Далее для каждого нового символа из входного потока, пока он не закончился:

• если на вершине стека терминал, и он совпадает с символом входного потока — то а) вытолкнуть терминал из стека и б) потребить символ входного потока.
• если на вершине стека терминал, и он не совпадает с символом входного потока — то это синтаксическая ошибка «ожидался такой-то символ» (тот, что на стеке).
• иначе на вершине стека нетерминал, обозначим его A. Ищутся все правила с ним в левой части, для каждого правила просматриваются множества направляющих символов на предмет нахождения символа входного потока, он не может найтись там более одного раза. Иначе грамматика не разбираема по LL(1).
• если символ нашелся, то осуществляется применение этого правила: номер правила выводится в выходной поток, со стека выталкивается один символ (это A) и взамен вталкивается все правая часть правила, крайне левый символ правой части — последним. Символ входного потока не потребляется.
• иначе символ не нашелся вовсе. Тогда, если есть правило вида A → null — то A выталкивается с вершины стека. Символ входного потока не потребляется.
• иначе это синтаксическая ошибка, сообщение может быть выведено в виде «ожидалось одно из» и далее списком множество First(A).

Языки

• Язык математических формул
• Паскаль
• Python

См. также

• LR-анализатор

Примечания

Литература

• Grune, D. and van Reeuwijk, K. and Bal, H.E. and Jacobs, C.J.H. and Langendoen, K. Modern Compiler Design. — Springer, 2012. — 843 p. — ISBN 9781461446996.
• Mogensen, T. Æ. Introduction to Compiler Design. — Springer, 2011. — 225 p. — ISBN 9780857298294.
• Mozgovoy, M. Algorithms, Languages, Automata, and Compilers: A Practical Approach. — Jones & Bartlett Learning, 2009. — 345 p. — ISBN 9780763782948.

Ссылки

• Larry Ruzzo. CSE401: LL(1) Parsing Example, UW CSE, 2004.
• Build LL(1) Parse Table, JFLAP Tutorial
• https://www.cs.bgu.ac.il/~comp151/wiki.files/ps6.html

Для улучшения этой статьи желательно: Проставив сноски, внести более точные указания на источники. Викифицировать статью. Добавить иллюстрации.