Введение
Тип парсера в информатике
В информатике LR-парсеры — это тип парсера снизу вверх, который анализирует детерминированные контекстно-свободные языки за линейное время. Существует несколько вариантов LR-парсеров: SLR-парсеры, LALR-парсеры, канонические LR(1)-парсеры, минимальные LR(1)-парсеры и обобщенные LR-парсеры (GLR-парсеры). LR-парсеры могут быть сгенерированы генератором парсеров из формальной грамматики, определяющей синтаксис языка, который необходимо разобрать. Они широко используются для обработки компьютерных языков. LR-парсер (слева направо, самый правый вывод в обратном порядке) читает входной текст слева направо без отката (это справедливо для большинства парсеров) и строит самый правый вывод в обратном порядке: он выполняет разбор снизу вверх, а не разбор LL сверху вниз или ad hoc-разбор. За названием "LR" часто следует числовой квалификатор, например "LR(1)" или иногда "LR(k)". Чтобы избежать отката или угадывания, LR-парсеру разрешается предварительно просматривать k символов входного потока, прежде чем принимать решение о разборе предыдущих символов. Обычно k равно 1 и не указывается. Названию "LR" часто предшествуют другие квалификаторы, как в "SLR" и "LALR". Обозначение "LR(k)" для грамматики было предложено Кнутом для обозначения "транслируемого слева направо с ограничением k".
Вышеупомянутые свойства L, R и k фактически присущи всем парсерам со сдвигом и восстановлением, включая парсеры приоритетов. Однако по соглашению название LR относится к форме разбора, изобретенной Дональдом Кнутом, и исключает более ранние, менее мощные методы приоритетов (например, парсер приоритетов операторов). Это связано с тем, что LR-парсер ждет, пока не увидит полный экземпляр некоторого грамматического шаблона, прежде чем подтвердить то, что он обнаружил. LL-парсер должен решить или угадать, что он видит, гораздо раньше, когда он увидел только самый левый входной символ этого шаблона.
Например, дерево анализа снизу вверх
LR-анализатор сканирует и разбирает входной текст за один прямой проход. Парсер постепенно строит дерево разбора снизу вверх и слева направо, без предположений или возвратов. На каждом этапе этого прохода анализатор накапливает список поддеревьев или синтаксических конструкций входного текста, которые уже были разобраны. Эти поддеревья еще не объединены, поскольку анализатор еще не достиг правого конца синтаксического шаблона, который их объединит. Например, на шаге 6 разобрано только "A*2", но не полностью. Существует только заштрихованный нижний левый угол дерева разбора. Ни одного из узлов дерева разбора с номером 7 и выше пока не существует. Узлы 3, 4 и 6 являются корнями изолированных поддеревьев для переменной A, оператора * и числа 2 соответственно. Эти три корневых узла временно хранятся в стеке разбора. Неразобранная часть входного потока – "+ 1".
Переместить и уменьшить действия
Как и другие парсеры со сдвигом и восстановлением, LR-парсер работает, выполняя некоторую комбинацию шагов сдвига (Shift) и восстановления (Reduce). Шаг сдвига продвигается во входном потоке на один символ. Этот сдвинутый символ становится новым узлом дерева разбора. Шаг восстановления применяет завершенное грамматическое правило к некоторым из недавно созданных деревьев разбора, объединяя их в одно дерево с новым корневым символом. Если входные данные не содержат синтаксических ошибок, парсер продолжает эти шаги, пока не будут обработаны все входные данные и все деревья разбора не будут сведены к одному дереву, представляющему собой корректный вход. LR-парсеры отличаются от других парсеров со сдвигом и восстановлением тем, как они определяют, когда выполнять восстановление, и как выбирать между правилами с похожими правыми частями. Однако окончательные решения и последовательность шагов сдвига или восстановления остаются одинаковыми. Значительная эффективность LR-парсера обусловлена его детерминированностью. Чтобы избежать неопределенности, LR-парсер часто выполняет просмотр (вправо) следующего сканированного символа, прежде чем принимать решение о ранее сканированных символах. Лексический анализатор работает на один или несколько символов впереди парсера. Символы просмотра служат "правым контекстом" для принятия решения о разборе.
Стены анализа снизу вверх
Как и другие парсеры с приведением и сдвигом, LR-парсер лениво ожидает, пока не отсканирует и не проанализирует все части некоторой конструкции, прежде чем окончательно определить, что представляет собой объединенная конструкция. Затем парсер немедленно обрабатывает эту комбинацию, не дожидаясь дальнейших действий. В примере дерева разбора фраза A приводится к Value, а затем к Products на шагах 1-3, как только появляется символ предварительного просмотра *, а не дожидаясь, чтобы организовать эти части дерева разбора позже. Решения о том, как обрабатывать A, основаны только на том, что парсер и сканер уже видели, без учета элементов, которые появятся позже справа. Приведения реорганизуют наиболее недавно проанализированные элементы, непосредственно слева от символа предварительного просмотра. Таким образом, список уже проанализированных элементов функционирует как стек. Этот стек растет вправо. Основание или дно стека находится слева и содержит самый левый, самый старый фрагмент разбора. Каждый шаг приведения действует только на самые правые, новые фрагменты разбора. (Этот накопительный стек разбора сильно отличается от предсказывающего, растущего влево стека разбора, используемого парсерами сверху вниз.)
Анализ генератора LR
Этот раздел статьи могут пропустить большинство пользователей генераторов LR-парсерoв.
Настройки для прицелов
Состояния и переходы предоставляют всю необходимую информацию для действий сдвига и переходов в таблице разбора. Генератор также должен вычислить ожидаемые множества предпросмотра для каждого действия восстановления. В SLR-анализаторах эти множества предпросмотра определяются непосредственно из грамматики, без учета отдельных состояний и переходов. Для каждого нетерминала S генератор SLR вычисляет Follow(S) – множество всех терминальных символов, которые могут непосредственно следовать за каким-либо вхождением S. В таблице разбора каждое восстановление до S использует Follow(S) в качестве своего LR(1) множества предпросмотра. Такие множества следования также используются генераторами для LL-анализаторов, работающих сверху вниз. Грамматика, не имеющая конфликтов сдвига/восстановления или восстановления/восстановления при использовании множеств Follow, называется SLR-грамматикой. LALR-анализаторы имеют те же состояния, что и SLR-анализаторы, но используют более сложный и точный способ вычисления минимально необходимых множеств предпросмотра для восстановления для каждого отдельного состояния. В зависимости от деталей грамматики, это может оказаться таким же, как множество Follow, вычисленное генераторами SLR-анализаторов, или может оказаться подмножеством множеств предпросмотра SLR. Некоторые грамматики подходят для генераторов LALR, но не для генераторов SLR. Это происходит, когда грамматика имеет ложные конфликты сдвига/восстановления или восстановления/восстановления при использовании множеств Follow, но не имеет конфликтов при использовании точных множеств, вычисленных генератором LALR. Такая грамматика называется LALR(1), но не SLR. SLR или LALR-анализатор избегает дублирования состояний. Однако эта минимизация не является необходимой и иногда может создавать ненужные конфликты предпросмотра. Канонические LR-анализаторы используют дублированные (или "разделенные") состояния, чтобы лучше запоминать левый и правый контекст использования нетерминала. Каждое вхождение символа S в грамматике может рассматриваться независимо, с собственным множеством предпросмотра, чтобы помочь разрешить конфликты восстановления. Это позволяет обрабатывать большее количество грамматик. К сожалению, это значительно увеличивает размер таблиц разбора, если это делается для всех частей грамматики. Разделение состояний также может быть выполнено вручную и выборочно с помощью любого SLR или LALR-анализатора путем создания двух или более именованных копий некоторых нетерминалов. Грамматика, не имеющая конфликтов для канонического генератора LR, но имеющая конфликты в генераторе LALR, называется LR(1), но не LALR(1) и не SLR. SLR, LALR и канонические LR-анализаторы принимают точно такие же решения о сдвиге и восстановлении, когда входной поток является корректным языком. Когда входные данные содержат синтаксическую ошибку, LALR-анализатор может выполнить некоторые дополнительные (безвредные) восстановления, прежде чем обнаружить ошибку, по сравнению с каноническим LR-анализатором. И SLR-анализатор может сделать еще больше. Это происходит потому, что SLR и LALR используют щедрое приближение в виде супермножества к истинным, минимальным символам предпросмотра для данного состояния.
Восстановление синтаксической ошибки
LR-парсеры могут генерировать довольно полезные сообщения об ошибках для первой синтаксической ошибки в программе, просто перечисляя все терминальные символы, которые могли бы появиться далее вместо неожиданного ошибочного символа предварительного просмотра. Но это не помогает парсеру определить, как разобрать оставшуюся часть входной программы для поиска дальнейших, независимых ошибок. Если парсер плохо восстанавливается после первой ошибки, он, скорее всего, неправильно разберет все остальное и выдаст каскад бесполезных ложных сообщений об ошибках. В генераторах парсеров yacc и bison парсер имеет специальный механизм для отказа от текущего оператора, отбрасывания некоторых разобранных фраз и токенов предварительного просмотра, окружающих ошибку, и повторной синхронизации разбора на надежном разделителе операторов, таком как точки с запятой или фигурные скобки. Это часто хорошо работает, позволяя парсеру и компилятору просматривать остальную часть программы. Многие синтаксические ошибки кодирования – это простые опечатки или пропуски тривиального символа. Некоторые LR-парсеры пытаются обнаружить и автоматически исправить эти распространенные случаи. Парсер перечисляет все возможные варианты вставки, удаления или замены одного символа в точке ошибки. Компилятор выполняет пробный разбор с каждой модификацией, чтобы проверить, успешно ли это прошло. (Это требует возврата к снимкам стека разбора и входного потока, что обычно не требуется парсеру.) Выбирается наилучший вариант исправления. Это дает очень полезное сообщение об ошибке и обеспечивает хорошую повторную синхронизацию разбора. Однако исправление недостаточно надежно для постоянного изменения входного файла. Исправление синтаксических ошибок проще всего выполнять последовательно в парсерах (например, LR), которые имеют таблицы разбора и явный стек данных.
Варианты анализаторов LR
Генератор LR-анализатора определяет, что должно происходить для каждой комбинации состояния анализа и опережающего символа. Эти решения обычно преобразуются в таблицы данных, доступные только для чтения, которые управляют общим циклом анализа, независимым от грамматики и состояния. Однако существуют и другие способы реализации этих решений в виде активного анализатора. Некоторые генераторы LR-анализаторов создают отдельный, специализированный программный код для каждого состояния, вместо таблицы анализа. Такие анализаторы могут работать в несколько раз быстрее, чем общий цикл анализа в табличных анализаторах. Самые быстрые анализаторы используют сгенерированный ассемблерный код. В варианте рекурсивного восходящего анализатора явная структура стека анализа также заменяется неявным стеком, используемым при вызовах подпрограмм. Сокращения завершают несколько уровней вызовов подпрограмм, что неудобно в большинстве языков. Таким образом, рекурсивные восходящие анализаторы, как правило, медленнее, менее понятны и сложнее для ручного редактирования, чем рекурсивные нисходящие анализаторы. Другой вариант заменяет таблицу анализа правилами сопоставления с образцом в непроцедурных языках, таких как Prolog. GLR-анализаторы (обобщенные LR-анализаторы) используют методы LR-анализа снизу вверх для поиска всех возможных вариантов анализа входного текста, а не только одного правильного. Это необходимо для неоднозначных грамматик, таких как те, что используются для естественных языков. Множество допустимых деревьев разбора вычисляются одновременно, без возврата. GLR иногда полезен для языков программирования, которые сложно описать с помощью грамматики LALR(1) без конфликтов. LC-анализаторы (анализаторы левого угла) используют методы LR-анализа снизу вверх для распознавания левой части альтернативных грамматических правил. Когда альтернативы сужаются до одного возможного правила, анализатор переключается на методы LL(1)-анализа сверху вниз для анализа остальной части этого правила. LC-анализаторы имеют таблицы анализа меньшего размера, чем LALR-анализаторы, и обеспечивают более точную диагностику ошибок. Широко используемых генераторов для детерминированных LC-анализаторов не существует. LC-анализаторы с множественным разбором полезны для естественных языков с очень большими грамматиками.
Теория
LR-анализаторы были изобретены Дональдом Кнутом в 1965 году как эффективное обобщение анализаторов прецедентов. Кнут доказал, что LR-анализаторы являются наиболее общими анализаторами, которые при этом остаются эффективными в наихудших случаях. "Грамматики LR(k) могут быть эффективно разобраны со временем выполнения, по существу пропорциональным длине входной строки". Для любого k≥1, "язык может быть сгенерирован LR(k)-грамматикой тогда и только тогда, когда он детерминирован [и контекстно-свободен], что равносильно тому, что он может быть сгенерирован LR(1)-грамматикой". Иными словами, если язык был достаточно хорошо структурирован, чтобы позволить эффективный однопроходный анализатор, его можно было описать с помощью LR(k)-грамматики. И эту грамматику всегда можно механически преобразовать в эквивалентную (но более крупную) LR(1)-грамматику. Таким образом, метод LR(1)-анализа, в теории, был достаточно мощным для обработки любого разумного языка. На практике, естественные грамматики многих языков программирования близки к LR(1). Канонические LR-анализаторы, описанные Кнутом, имели слишком много состояний и очень большие таблицы разбора, которые были непрактично большими для ограниченной памяти компьютеров того времени. LR-анализ стал практичным, когда Фрэнк ДеРемер изобрел SLR и LALR-анализаторы с гораздо меньшим количеством состояний. Подробную информацию о теории LR и о том, как LR-анализаторы выводятся из грамматик, можно найти в книге "Теория разбора, трансляции и компиляции", том 1 (Aho и Ullman). Язык L имеет LR(0)-грамматику тогда и только тогда, когда L является детерминированным контекстно-свободным языком с префиксным свойством. Следовательно, язык L является детерминированным контекстно-свободным тогда и только тогда, когда L$ имеет LR(0)-грамматику, где "$" не является символом алфавита L.
Набор статей
Обычно невозможно охарактеризовать состояние парсера одним элементом, поскольку он может не знать заранее, какое правило будет использовано для восстановления. Например, если существует также правило E → E * B, то элементы E → E + B и E → E * B будут применимы оба после прочтения строки, соответствующей E. Поэтому для характеристики состояния парсера удобно использовать набор элементов, в данном случае множество { E → E + B, E → E * B }.
Расширение набора пунктов расширением нетерминалов
Точка перед нетерминалом, например, E → E + B, указывает, что парсер ожидает разобрать нетерминал B следующим. Чтобы гарантировать, что множество элементов содержит все возможные правила, которые парсер может разбирать в данный момент, оно должно включать все элементы, описывающие, как именно будет разбираться B. Это означает, что если существуют правила вида B → 1 и B → 0, то множество элементов также должно включать элементы B → 1 и B → 0. В общем случае это можно сформулировать следующим образом:
Если в множестве элементов есть элемент вида A → v Bw, а в грамматике есть правило вида B → w', то элемент B → w' также должен присутствовать в множестве элементов.
Закрытие наборов статей
Таким образом, любой набор элементов может быть расширен рекурсивным добавлением всех подходящих элементов до тех пор, пока не будут обработаны все нетерминалы, перед которыми стоит точка. Минимальное расширение называется замыканием множества элементов и обозначается как замыкание(I), где I – множество элементов. Именно эти замыкания используются в качестве состояний парсера, однако в таблицы будут включены только те из них, которые действительно достижимы из начального состояния.
Записка о LR(0) против SLR и LALR анализа
Только шаг 4 описанной выше процедуры генерирует действия восстановления, поэтому все действия восстановления должны занимать целую строку таблицы, что приводит к восстановлению независимо от следующего символа во входном потоке. Именно поэтому это таблицы разбора LR(0): они не выполняют никакого предпросмотра (то есть, смотрят на ноль символов вперед), прежде чем решить, какое восстановление выполнить. Грамматика, которой требуется предпросмотр для устранения неоднозначности при восстановлении, потребовала бы строки таблицы разбора, содержащей различные действия восстановления в разных столбцах, и описанная выше процедура не способна создавать такие строки. Усовершенствования процедуры построения таблицы LR(0) (например, SLR и LALR) способны создавать действия восстановления, которые не занимают целые строки. Следовательно, они способны разбирать больше грамматик, чем анализаторы LR(0).