LL(1) | это... Что такое LL(1)? (original) (raw)
В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.Эта отметка установлена 12 мая 2011. |
---|
Нисходящий алгоритм синтаксического разбора.
Прост в написании вручную без использования автоматических генераторов. Используется для разбора ряда языков программирования, таких, как Pascal (по некоторым сведениям, язык разработан с умыслом сделать его разбираемым по LL(1)).
Очень быстр в исполнении, и имеет характерное сообщение об ошибке вида "ожидался такой-то символ".
Понятие "направляющие символы правила"
Для каждого нетерминала 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).