LR-анализ

LR-анализ — это метод синтаксического анализа (парсинга) контекстно-свободных грамматик, используемый в теории формальных языков и компиляторах для построения дерева разбора (или последовательности правил грамматики) для заданной цепочки символов (токенов). LR-анализ относится к классу восходящих (bottom-up) методов, при которых дерево разбора строится от листьев (терминальных символов) к корню (стартовому нетерминалу). Название «LR» расшифровывается как «Left-to-right scan, Rightmost derivation in reverse»: сканирование входной строки слева направо с построением обратного правого вывода.

Принцип работы

LR-анализ основан на использовании детерминированного конечного автомата (ДКА) с магазинной памятью (стеком). Анализатор последовательно читает символы входной строки и, в зависимости от текущего состояния автомата и символа на вершине стека, выполняет одно из двух действий:

• Сдвиг (shift) — перенос очередного входного символа в стек.
• Свёртка (reduce) — замена цепочки символов на вершине стека, соответствующей правой части некоторого правила грамматики, на нетерминал, стоящий в левой части этого правила.

Процесс продолжается до тех пор, пока стек не будет содержать только стартовый нетерминал, а входная строка — полностью прочитана. Если это достигается, цепочка считается синтаксически корректной. Если на каком-то шаге невозможно выполнить ни сдвиг, ни свёртку, анализатор сообщает об ошибке.

Таблицы разбора

Для работы LR-анализатора предварительно строятся две таблицы: таблица действий (action table) и таблица переходов (goto table). Они формируются на основе грамматики с помощью специальных алгоритмов (например, построение LR(0)-автомата, вычисление множеств FIRST и FOLLOW). Таблица действий определяет, какое действие (сдвиг, свёртка, принятие или ошибка) необходимо выполнить для каждой пары (текущее состояние, текущий входной символ). Таблица переходов указывает, в какое состояние перейти после выполнения свёртки, в зависимости от нетерминала, который был помещён в стек.

Виды LR-анализаторов

Различают несколько типов LR-анализаторов, отличающихся объёмом таблиц и мощностью распознаваемых грамматик:

LR(0)

Простейший тип, не использующий информацию о следующем входном символе (lookahead). Решения о свёртке принимаются только на основе содержимого стека. LR(0)-анализаторы могут обрабатывать только очень ограниченный класс грамматик, свободных от конфликтов сдвиг/свёртка и свёртка/свёртка. На практике применяются редко.

SLR(1) (Simple LR)

Использует один символ предпросмотра (lookahead) для разрешения конфликтов. Таблицы строятся на основе LR(0)-автомата, но свёртка допускается только в том случае, если следующий входной символ принадлежит множеству FOLLOW для нетерминала, в который производится свёртка. SLR(1) мощнее LR(0), но всё ещё не способен обрабатывать некоторые распространённые конструкции языков программирования (например, оператор if-else с неоднозначностью).

LALR(1) (Look-Ahead LR)

Наиболее популярный на практике тип. Использует LR(0)-автомат, но для каждого состояния вычисляется более точное множество символов предпросмотра (lookahead) для каждой возможной свёртки. LALR(1) сохраняет компактность таблиц SLR(1), но распознаёт более широкий класс грамматик, включая большинство конструкций реальных языков программирования. Генераторы парсеров Yacc, Bison, CUP и многие другие по умолчанию строят LALR(1)-анализаторы.

LR(1) (Canonical LR)

Самый мощный тип, использующий полные LR(1)-состояния, где каждый элемент включает в себя конкретный символ предпросмотра. Таблицы для LR(1) содержат значительно больше состояний (иногда в десятки раз больше, чем для LALR(1)), что делает их менее практичными из-за большого расхода памяти. Однако LR(1) способен распознавать любую детерминированную контекстно-свободную грамматику.

Преимущества и недостатки

Преимущества:

• Детерминированность: LR-анализаторы работают за линейное время O(n) относительно длины входной строки.
• Возможность раннего обнаружения синтаксических ошибок (принцип жизнеспособного префикса).
• Широкий класс распознаваемых грамматик, включая многие грамматики языков программирования.

Недостатки:

• Сложность построения таблиц вручную (обычно используются автоматические генераторы).
• Большой размер таблиц для LR(1) и LALR(1) по сравнению с LL-анализаторами.
• Невозможность обработки некоторых естественно-языковых конструкций (например, контекстно-зависимых).

Применение

LR-анализ широко применяется в компиляторах для языков программирования, таких как C, C++, Java, Python (в некоторых реализациях), а также в инструментах для синтаксического анализа структурированных данных и DSL (предметно-ориентированных языков). Большинство современных генераторов парсеров (Yacc, Bison, ANTLR — для LL(*), но с поддержкой LR-подобных стратегий) реализуют именно LR-анализ или его варианты.

Связь с другими методами

LR-анализ является обобщением более простых восходящих методов (например, операторного предшествования) и альтернативой нисходящим методам (LL-анализ). В отличие от LL-анализа, который строит дерево разбора сверху вниз, LR-анализ более мощный (класс LR-грамматик строго шире класса LL-грамматик), но требует больше вычислительных ресурсов для построения таблиц. Существуют также обобщённые методы (GLR — Generalized LR), способные обрабатывать неоднозначные грамматики за счёт параллельного анализа нескольких вариантов.

Историческая справка

Метод LR-анализа был впервые описан Дональдом Кнутом в 1965 году в статье «On the Translation of Languages from Left to Right». Кнут показал, что для любой детерминированной контекстно-свободной грамматики можно построить LR(k)-анализатор для достаточно большого k. Впоследствии были разработаны практические алгоритмы построения LALR(1)-таблиц (Франклин ДеРемер, 1969), что сделало LR-анализ основой для большинства промышленных компиляторов.

Источники

• Ахо А., Лам М., Сети Р., Ульман Дж. — «Компиляторы: принципы, технологии и инструментарий» (2-е издание), 2008.
• Грис Д. — «Конструирование компиляторов для цифровых вычислительных машин», 1971.
• Кнут Д. — «Искусство программирования», том 2, 1998.
• Материалы курса «Теория формальных языков и компиляторов» (МФТИ, ВМК МГУ).