LL(1)
—
LL-анализатор
,
нисходящий алгоритм синтаксического разбора
. Цифра 1 говорит, что для определения пути разбора нужна всего одна
лексема
.
Прост в написании вручную без использования автоматических генераторов. Используется для
разбора
кода
в ряде
языков программирования
, таких, как
Pascal
и
Python
(до 3.8
).
Очень быстр в исполнении и имеет характерное сообщение об ошибке вида «ожидался такой-то символ».
Направляющие символы правила
Для каждого
нетерминала
A в
грамматике
генерируется множество терминалов First(A), определенное следующим образом:
-
если в грамматике есть правило с A в левой части и правой частью, начинающейся с терминала, то данный терминал входит в First(A)
-
если в грамматике есть правило с A в левой части и правой частью, начинающейся с нетерминала (обозначим B), то First(B) строго входит в First(A)
-
никакие иные терминалы не входят в First(A)
Для каждого правила генерируется множество
направляющих символов
, определенное следующим образом:
-
если правая часть правила начинается с терминала, то множество направляющих символов состоит из одного этого терминала
-
иначе правая часть начинается с нетерминала A, тогда множество направляющих символов есть First(A)
Возможны обобщения этих определений для случая наличия правил вида
A → null
.
Понятно, что First(A) есть объединение множеств направляющих символов для всех правил с A в левой части.
Грамматика
разбираема по LL(1)
, если для любой пары правил с одинаковой левой частью множества направляющих символов не пересекаются.
Для выяснения, разбираема ли грамматика по LL(1) или нет в общем виде, удобно пользоваться критерием LL(1)-грамматик
.
Описание анализатора
Используется стек, где находятся номера терминалов и нетерминалов, входной (терминалы) и выходной (номера правил) потоки.
Сначала в стек заносится E — начальный символ грамматики.
Далее для каждого нового символа из входного потока, пока он не закончился:
-
если на вершине стека терминал, и он совпадает с символом входного потока — то а) вытолкнуть терминал из стека и б) потребить символ входного потока.
-
если на вершине стека терминал, и он не совпадает с символом входного потока — то это синтаксическая ошибка «ожидался такой-то символ» (тот, что на стеке).
-
иначе на вершине стека нетерминал, обозначим его A. Ищутся все правила с ним в левой части, для каждого правила просматриваются множества направляющих символов на предмет нахождения символа входного потока; он не может найтись там более одного раза, иначе грамматика не разбираема по LL(1).
-
если символ нашелся, то осуществляется применение этого правила: номер правила выводится в выходной поток, со стека выталкивается один символ (это A) и взамен вталкивается вся правая часть правила, крайне левый символ правой части — последним. Символ входного потока не потребляется.
-
иначе символ не нашелся вовсе. Тогда, если есть правило вида
A → null
— то A выталкивается с вершины стека. Символ входного потока не потребляется.
-
иначе это синтаксическая ошибка, сообщение может быть выведено в виде «ожидалось одно из» и далее списком множество First(A) (для важнейших нетерминалов языка, например, для нетерминала «выражение», можно сформулировать ошибку в терминах имён нетерминалов).
Языки
См. также
Примечания
-
(неопр.)
.
peps.python.org
. Дата обращения: 15 июля 2022.
15 июля 2022 года.
-
Козлов Сергей Валерьевич, Светлаков Алексей Владимирович.
// International Journal of Open Information Technologies. — 2022. —
Т. 10
,
вып. 3
. —
С. 30–38
. —
ISSN
.
18 мая 2022 года.
Литература
-
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
.
-
Козлов С. В., Светлаков А. В.
О LL(1)-грамматиках, алгоритмах на них и методах их анализа в программировании — International Journal of Open Information Technologies. — 2022. — Т. 10. — № 3. — С. 30-38. — URL:
.
Ссылки
-
Larry Ruzzo.
, UW CSE, 2004.
-
,
JFLAP
Tutorial
-