Анализатор LR
-
Типы LR-анализаторов
- LR-анализаторы анализируют детерминированные контекстно-свободные языки за линейное время.
- Существуют различные варианты LR-анализаторов: SLR, LALR, канонические LR(1), минимальные LR(1) и GLR.
-
Синтаксический анализ LR
- LR-анализаторы считывают входной текст слева направо и производят вывод от крайнего правого элемента в обратном порядке.
- Они избегают обратного отслеживания и угадывания, просматривая k предварительных символов перед принятием решения.
- LR-анализаторы детерминированы и производят единственный правильный синтаксический анализ за линейное время.
-
Преимущества LR-анализаторов
- LR-анализаторы подходят для компьютерных языков, но не для человеческих языков.
- Они могут обрабатывать больший диапазон языков и грамматик, чем другие методы.
-
Процесс анализа
- LR-анализаторы сканируют и разбирают входной текст за один проход.
- Они строят дерево синтаксического анализа снизу вверх, без угадывания или возврата назад.
- На каждом этапе анализатор накапливает поддеревья входного текста, которые еще не соединены.
-
Шаги анализа
- Анализатор LR выполняет шаги сдвига и сокращения, продвигаясь во входном потоке и объединяя деревья.
- Решения о сокращении основаны на стеке синтаксического анализа, который растет вправо.
- На каждом шаге анализатор суммирует информацию левого контекста в состояние анализатора LR(0).
-
Пример анализа
- В примере с деревом синтаксического анализа фраза A преобразуется в Value и Products на этапах 1-3.
- На шаге 6 применяется грамматическое правило, объединяя три дерева в новый корень.
- На шаге 12 весь входной поток был использован, и текущее состояние 3.
-
Синтаксические анализаторы LR
- Используют контекстно-свободную грамматику для определения синтаксиса языка.
- Грамматика не охватывает все языковые правила, такие как размер чисел.
- Конечные символы грамматики — это токены, такие как +, * и int.
- Нетерминальные символы — это названия понятий, такие как Суммы.
- Грамматика использует рекурсивные правила для обработки повторяющихся операторов.
-
Таблицы синтаксического анализа
- Большинство парсеров LR управляются таблицами.
- Таблицы показывают, как сдвигать или уменьшать для каждой комбинации состояния и символа.
- Таблицы трудно вычислить вручную, поэтому используются генераторы, такие как Bison.
- Таблицы двумерные: строки для состояний, столбцы для символов.
-
Цикл синтаксического анализа LR
- Начинается с почти пустого стека и первого символа.
- Повторяет цикл, пока не завершится или не возникнет ошибка.
- Стек хранит только состояния автомата LR(0).
-
Анализ генератора LR
- Генератор добавляет дополнительные правила для завершения основных элементов.
- Маркер показывает, где находится синтаксический анализатор.
- Основные элементы показывают, как синтаксический анализатор попал в текущее состояние.
- Завершение элементов показывает возможные последующие шаги.
- Символы-повторители могут приводить к разным состояниям в зависимости от количества элементов.
-
Переходы и состояния
- Некоторые переходы приводят к новым состояниям, другие — к уже перечисленным.
- Генератор начинается с целевого правила грамматики и исследует состояния и переходы.
- Состояния «LR(0)» используют предварительное значение k=0.
-
Конечный автомат
- Таблица синтаксического анализа описывает состояния и переходы.
- Конечный автомат (FSM) сканирует поток и находит самую полную фразу для сокращения.
- FSM игнорирует старые начальные фразы и отслеживает только новые.
-
Предварительные установки
- Состояния и переходы предоставляют информацию для действий shift и goto.
- Генераторы SLR и LALR вычисляют предварительные наборы для сокращений.
- Грамматики SLR и LALR могут иметь конфликты, но не все.
-
Канонические синтаксические анализаторы LR
- Используют дублированные состояния для лучшего запоминания контекста.
- Каждое появление символа обрабатывается независимо.
- Грамматики LR(1) могут иметь конфликты в LALR.
-
Восстановление синтаксической ошибки
- Анализаторы LR могут генерировать полезные сообщения об ошибках.
- Некоторые анализаторы пытаются автоматически исправлять ошибки.
- Исправление ошибок проще в парсерах с таблицами синтаксического анализа.
-
Варианты LR-анализаторов
- Генераторы могут создавать программный код для каждого состояния.
- Рекурсивные анализаторы подъема используют неявный стек.
- Обобщенные LR-анализаторы GLR ищут все возможные варианты разбора.
- Анализаторы левого угла LC используют методы LR для распознавания левого конца правил.
-
Теория
- Парсеры LR были изобретены Кнутом в 1965 году.
- Канонические LR-анализаторы имели слишком много состояний.
- Деремер изобрел парсеры SLR и LALR с меньшим количеством состояний.
- Анализаторы Earley решают задачу генерации всех возможных вариантов разбора для неоднозначных грамматик.
-
Определение детерминированного и контекстно-свободного языка
- Язык L является детерминированным и контекстно-свободным, если L$ имеет грамматику LR(0), где «$» не является символом алфавита L.
-
Пример синтаксического анализа LR
- Используется грамматика с символом цели E для анализа входных данных.
- Таблицы действий и переходов содержат три типа действий: сдвиг, сокращение и принятие.
- Таблица goto указывает следующее состояние после сокращения.
-
Этапы синтаксического анализа
- Синтаксический анализатор начинает с начального состояния и добавляет символ $ к входной строке.
- Каждое действие определяется таблицей действий и goto.
- После сокращения следующее состояние определяется по таблице goto.
-
Построение таблиц синтаксического анализа LR(0)
- Элементы LR(0) представляют собой грамматические правила с точкой.
- Наборы элементов используются для характеристики состояний анализатора.
- Закрытие наборов элементов включает все возможные правила для нетерминалов.
-
Расширенная грамматика
- Грамматика дополняется правилом S → E eof для сокращения при принятии всей входной строки.
- Определяются переходы между замкнутыми наборами элементов.
-
Конструкция таблиц
- Переходы определяются как конечный автомат, читающий терминалы и нетерминалы.
- Начальное состояние автомата — завершение первого элемента добавленного правила.
- Процедура закрытия наборов элементов продолжается до тех пор, пока не будут найдены новые наборы элементов.
-
Пример построения таблиц
- Для примера грамматики определяются переходы между наборами элементов.
- Конечный автомат с наборами элементов в качестве состояний имеет таблицу переходов.
-
Создание таблиц действий и переходов
- Столбцы для нетерминалов копируются в таблицу goto.
- Столбцы для терминалов копируются в таблицу действий как действия сдвига.
- В таблицу действий добавлен столбец для ‘$’ (конец ввода).
- Действие acc добавляется в столбец «$» для каждого набора элементов, содержащего элемент вида S → w eof.
- Если набор элементов i содержит элемент вида A → w , строка для состояния i в таблице действий полностью заполняется действием rm уменьшения.
-
Особенности LR(0)
- Действия по уменьшению занимают всю строку таблицы.
- Сокращение происходит независимо от следующего символа во входном потоке.
- Грамматики, требующие предварительного просмотра, требуют строк таблицы с различными действиями по сокращению.
-
Конфликты в таблицах
- Автомат детерминирован, но возможны конфликты между сдвигом и уменьшением или между сокращениями.
- Конфликты указывают на то, что грамматика не является LR(0).
- Примеры конфликтов: проблема зависания else и конфликт «уменьшить-уменьшить».
-
Решение конфликтов
- Синтаксический анализатор использует следующий набор нетерминала A для решения, какое правило использовать для сокращения.
- Это приводит к созданию простых LR-анализаторов.
-
Дополнительные ресурсы
- Чепмен, Найджел П., LR Parsing: теория и практика.
- Пейджер Д., Практический общий метод построения LR (k) парсеров.
- «Построение компилятора: принципы и практика» Кеннета К. Лауден.
- Внешние ссылки: dickgrune.com, Методы синтаксического анализа — Практическое руководство.
- Симулятор синтаксического анализа для создания таблиц LR и решения упражнений.
- Внутренние компоненты синтаксического анализатора LALR(1) от GNU Bison.
- Конспекты курса по синтаксическому анализу LR.
- Сдвиг-уменьшение и повторное уменьшение конфликтов в анализаторе LALR.
- Пример синтаксического анализатора LR.
- Практичная конструкция синтаксического анализатора LR(k).
- Алгоритм Honalee LR(k).