Парсер LR - Википедия - LR parser

В Информатика, Парсеры LR являются разновидностью восходящий парсер это анализирует детерминированные контекстно-свободные языки в линейное время.^[1] Есть несколько вариантов парсеров LR: SLR парсеры, LALR парсеры, Канонический LR (1) парсеры, Минимальный LR (1) парсеры, GLR парсеры. Парсеры LR могут быть сгенерированы генератор парсеров из формальная грамматика определение синтаксиса анализируемого языка. Они широко используются для обработки компьютерные языки.

An LR парсер (Lслева направо, рправый вывод в обратном порядке) читает входной текст слева направо без резервного копирования (это верно для большинства синтаксических анализаторов) и производит крайнее правое происхождение наоборот: он делает восходящий синтаксический анализ - не нисходящий анализ LL или специальный синтаксический анализ. За именем LR часто следует числовой квалификатор, как в LR (1) или иногда LR (k). Избежать возврат или догадываясь, парсер LR может заглянуть вперед k смотреть вперед Вход символы прежде чем решить, как разбирать более ранние символы. Обычно k равно 1 и не упоминается. Имя LR часто предшествует другим квалификаторам, как в SLR и LALR. В LR (k) Условие грамматики было предложено Кнутом для обозначения «переводимая слева направо со связанными k."^[1]

Парсеры LR детерминированы; они производят единственный правильный синтаксический анализ без догадок или отката в линейное время. Это идеально подходит для компьютерных языков, но парсеры LR не подходят для человеческих языков, которым нужны более гибкие, но неизбежно более медленные методы. Некоторые методы, которые могут анализировать произвольные контекстно-свободные языки (например, Кок-Янг-Касами, Эрли, GLR ) имеют производительность O (п³) время. Другие методы, которые возвращают или дают несколько синтаксических анализов, могут даже занять экспоненциальное время, когда они плохо угадывают.^[2]

Вышеуказанные свойства L, р, и k фактически разделяют все парсеры shift-reduce, включая парсеры приоритета. Но по соглашению имя LR означает форму синтаксического анализа, изобретенную Дональд Кнут, и исключает более ранние, менее мощные методы приоритета (например, Парсер приоритета операторов ).^[1]Парсеры LR могут обрабатывать больший диапазон языков и грамматик, чем парсеры приоритета или нисходящие LL разбор.^[3] Это связано с тем, что синтаксический анализатор LR ожидает, пока он не увидит полный экземпляр некоторого грамматического шаблона, прежде чем совершить то, что он нашел. Анализатор LL должен решить или угадать, что он видит, гораздо раньше, когда он видел только крайний левый входной символ этого шаблона.

Обзор

Например, дерево синтаксического анализа снизу вверх А * 2 + 1

Дерево синтаксического анализа снизу вверх, состоящее из пронумерованных шагов

Парсер LR сканирует и анализирует вводимый текст за один проход по тексту. Парсер создает дерево синтаксического анализа постепенно, снизу вверх и слева направо, без угадывания или возврата. На каждом этапе этого прохода синтаксический анализатор накапливает список поддеревьев или фраз входного текста, которые уже были проанализированы. Эти поддеревья еще не объединены, потому что синтаксический анализатор еще не достиг правого конца синтаксического шаблона, который их объединит.

На шаге 6 в примере синтаксического анализа только "A * 2" был проанализирован не полностью. Существует только затененный нижний левый угол дерева синтаксического анализа. Ни один из узлов дерева синтаксического анализа с номерами 7 и выше еще не существует. Узлы 3, 4 и 6 являются корнями изолированных поддеревьев для переменной A, оператора * и числа 2 соответственно. Эти три корневых узла временно хранятся в стеке синтаксического анализа. Оставшаяся неанализируемая часть входного потока равна «+ 1».

Сдвиг и сокращение действий

Как и другие парсеры сдвига-уменьшения, парсер LR работает, выполняя некоторую комбинацию шагов Shift и шагов Reduce.

• А Сдвиг step продвигается во входном потоке на один символ. Этот сдвинутый символ становится новым деревом синтаксического анализа с одним узлом.
• А Уменьшать step применяет завершенное правило грамматики к некоторым из недавних деревьев синтаксического анализа, объединяя их вместе как одно дерево с новым корневым символом.

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

Парсеры LR отличаются от других парсеров сдвига-уменьшения тем, как они решают, когда сокращать, и как выбирать правила с похожими окончаниями. Но окончательные решения и последовательность шагов сдвига или уменьшения одинаковы.

Во многом эффективность парсера LR обусловлена ​​детерминированностью. Чтобы избежать догадок, анализатор LR часто смотрит вперед (вправо) на следующий отсканированный символ, прежде чем решить, что делать с ранее отсканированными символами. Лексический сканер опережает синтаксический анализатор на один или несколько символов. В смотреть вперед символы - это «правый контекст» для решения синтаксического анализа.^[4]

Стек синтаксического анализа снизу вверх

Парсер снизу вверх на шаге 6

Подобно другим синтаксическим анализаторам сдвиг-сокращение, синтаксический анализатор LR лениво ждет, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем зафиксировать то, что представляет собой объединенная конструкция. Затем синтаксический анализатор немедленно воздействует на комбинацию, а не ждет дальнейшего. В примере с деревом синтаксического анализа фраза A сокращается до Value, а затем до Products на шагах 1-3, как только просматривается *, вместо того, чтобы ждать позже, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать A, основаны только на том, что синтаксический анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.

Редукции реорганизуют самые недавно проанализированные объекты, непосредственно слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как куча. Этот синтаксический стек растет вправо. Основание или нижняя часть стека находится слева и содержит самый левый, самый старый фрагмент синтаксического анализа. Каждый шаг редукции действует только на самые правые, самые новые фрагменты синтаксического анализа. (Этот накопительный стек синтаксического анализа очень отличается от прогнозирующего, растущего влево стека синтаксического анализа, используемого нисходящие парсеры.)

Шаги синтаксического анализа снизу вверх, например A * 2 + 1

Шаг 6 применяет правило грамматики, состоящее из нескольких частей:

Продукты → Продукты * Стоимость

Это соответствует вершине стека, содержащей проанализированные фразы «... Продукты * Значение». Шаг уменьшения заменяет этот экземпляр правой части правила, «Products * Value», на левый символ правила, в данном случае на более крупный Products. Если парсер строит полные деревья синтаксического анализа, три дерева для внутренних продуктов, * и Value объединяются новым корнем дерева для продуктов. Иначе, семантический детали из внутренних продуктов и значения выводятся на более поздний этап компилятора или объединяются и сохраняются в новом символе продуктов.^[5]

Шаги анализа LR, например A * 2 + 1

В парсерах LR решения о сдвиге и сокращении потенциально основаны на всем стеке всего, что было проанализировано ранее, а не только на одном, самом верхнем символе стека. Если сделать это неумелым образом, это может привести к очень медленным анализаторам, которые становятся все медленнее и медленнее для более длинных входных данных. Парсеры LR делают это с постоянной скоростью, суммируя всю соответствующую левую контекстную информацию в одно число, называемое LR (0). состояние парсера. Для каждой грамматики и метода анализа LR существует фиксированное (конечное) количество таких состояний. Помимо хранения уже проанализированных символов, стек синтаксического анализа также запоминает номера состояний, достигнутые всем до этих точек.

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

На начальном шаге 0 входной поток «A * 2 + 1» делится на

• пустой раздел в стеке синтаксического анализа,
• прогнозируемый текст "A", сканированный как я бы символ, и
• оставшийся неотсканированный текст «* 2 + 1».

Стек синтаксического анализа начинается с сохранения только начального состояния 0. Когда состояние 0 видит опережающий просмотр я бы, он знает, как сдвинуть это я бы в стек и сканировать следующий входной символ *, и перейти к состоянию 9.

На шаге 4 общий входной поток «A * 2 + 1» в настоящее время делится на

• проанализированный раздел «A *» с 2 составными фразами «Продукты» и *,
• прогнозируемый текст "2", сканированный как int символ, и
• оставшийся неотсканированный текст «+1».

Состояниям, соответствующим составным фразам, являются 0, 4 и 5. Текущее самое правое состояние в стеке - это состояние 5. Когда состояние 5 видит опережающий просмотр int, он знает, как сдвинуть это int в стек как свою собственную фразу и просканируем следующий входной символ +, и перейти к состоянию 8.

На шаге 12 весь входной поток израсходован, но организован лишь частично. Текущее состояние - 3. Когда состояние 3 видит опережающий eof, он знает, как применить законченное правило грамматики

Суммы → Суммы + Продукты

путем объединения трех крайних правых фраз стека для Sums, +, и продукты в одно целое. Само состояние 3 не знает, каким должно быть следующее состояние. Это можно найти, вернувшись в состояние 0, слева от сокращаемой фразы. Когда состояние 0 видит этот новый завершенный экземпляр Sums, он переходит в состояние 1 (снова). Консультации по старым состояниям - вот почему они хранятся в стеке, а не только в текущем состоянии.

Грамматика для примера A * 2 + 1

Парсеры LR построены на основе грамматики, которая формально определяет синтаксис входного языка как набор шаблонов. Грамматика не охватывает все языковые правила, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Парсеры LR используют контекстно-свободная грамматика это касается только локальных шаблонов символов.

Используемый здесь пример грамматики представляет собой крошечное подмножество языка Java или C:

r0: Цель → Сумма eof

r1: Суммы → Суммы + произведения

r2: Суммы → Продукты

r3: Товары → Товары * Стоимость

r4: Продукты → Ценность

r5: Значение → int

r6: Значение → я бы

Грамматика терминальные символы - это многосимвольные символы или «токены», обнаруженные во входном потоке лексический сканер. Сюда входят + * и int для любой целочисленной константы и я бы для любого имени идентификатора и eof для конца входного файла. Грамматике все равно, что int ценности или я бы правописание, и не заботится о пробелах или переносах строк. Грамматика использует эти терминальные символы, но не определяет их. Они всегда являются листовыми узлами (в нижнем густом конце) дерева синтаксического анализа.

Термины с заглавной буквы, такие как суммы, нетерминальные символы. Это названия концепций или шаблонов в языке. Они определены в грамматике и никогда не встречаются во входном потоке. Они всегда являются внутренними узлами (над нижней частью) дерева синтаксического анализа. Они случаются только в результате применения парсером некоторого грамматического правила. Некоторые нетерминалы определяются двумя или более правилами; это альтернативные модели. Правила могут ссылаться на самих себя, что называется рекурсивный. Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики для полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.

Любой компьютерный язык можно описать несколькими различными грамматиками. Парсер LR (1) может обрабатывать многие, но не все общие грамматики. Обычно можно вручную изменить грамматику, чтобы она соответствовала ограничениям синтаксического анализа LR (1) и инструмента генератора.

Грамматика парсера LR должна быть однозначный сам по себе, или должен быть дополнен правилами приоритета, разрешающими ничьи. Это означает, что существует только один правильный способ применения грамматики к данному легальному примеру языка, в результате чего получается уникальное дерево синтаксического анализа с одним значением и уникальная последовательность действий сдвига / уменьшения для этого примера. Анализ LR не является полезным методом для человеческих языков с неоднозначной грамматикой, зависящей от взаимодействия слов. Человеческие языки лучше обрабатываются парсерами вроде Обобщенный парсер LR, то Парсер Эрли, или CYK алгоритм который может одновременно вычислять все возможные деревья синтаксического анализа за один проход.

Таблица синтаксического анализа для примера грамматики

Большинство парсеров LR управляются таблицами. Программный код парсера представляет собой простой универсальный цикл, одинаковый для всех грамматик и языков. Знание грамматики и ее синтаксических последствий кодируется в неизменяемые таблицы данных, называемые таблицы синтаксического анализа (или же таблицы синтаксического анализа). Записи в таблице показывают, следует ли сдвигать или уменьшать (и по какому правилу грамматики) для каждой допустимой комбинации состояния синтаксического анализатора и символа просмотра вперед. Таблицы синтаксического анализа также сообщают, как вычислить следующее состояние, учитывая только текущее состояние и следующий символ.

Таблицы синтаксического анализа намного больше, чем грамматика. Таблицы LR трудно точно вычислить вручную для больших грамматик. Таким образом, они механически получены из грамматики некоторыми генератор парсеров инструмент как Бизон.^[6]

В зависимости от того, как генерируются состояния и таблица синтаксического анализа, результирующий синтаксический анализатор называется либо SLR (простой LR) парсер, LALR (упреждающий LR) парсер, или же канонический парсер LR. Парсеры LALR обрабатывают больше грамматик, чем парсеры SLR. Канонические парсеры LR обрабатывают еще больше грамматик, но используют гораздо больше состояний и таблицы гораздо большего размера. Пример грамматики - SLR.

Таблицы синтаксического анализа LR двумерны. Каждое текущее состояние парсера LR (0) имеет свою собственную строку. Каждый возможный следующий символ имеет свой столбец. Некоторые комбинации состояния и следующего символа невозможны для допустимых входных потоков. Эти пустые ячейки вызывают сообщения об ошибках синтаксиса.

В Действие В левой половине таблицы есть столбцы для символов упреждающего терминала. Эти ячейки определяют, будет ли следующим действием синтаксического анализатора сдвиг (чтобы указать п) или уменьшить (по правилу грамматики р_п).

В Идти к в правой половине таблицы есть столбцы для нетерминальных символов. Эти ячейки показывают, к какому состоянию перейти после того, как левая сторона некоторого сокращения создала ожидаемый новый экземпляр этого символа. Это похоже на действие сдвига, но для нетерминалов; символ упреждающего терминала не изменился.

Столбец таблицы «Текущие правила» документирует значение и возможности синтаксиса для каждого состояния, разработанные генератором синтаксического анализатора. Он не входит в фактические таблицы, используемые во время анализа. В • Маркер (розовая точка) показывает, где сейчас находится синтаксический анализатор в рамках некоторых частично распознанных грамматических правил. Вещи слева от • были проанализированы, и скоро ожидаются вещи справа. Состояние имеет несколько таких текущих правил, если синтаксический анализатор еще не сузил возможности до одного правила.

В состоянии 2 выше синтаксический анализатор только что нашел и переместил + правила грамматики

r1: Суммы → Суммы + • Товары

Следующая ожидаемая фраза - это продукты. Продукция начинается с терминальных символов int или же я бы. Если предварительный просмотр является одним из тех, синтаксический анализатор сдвигает их и переходит в состояние 8 или 9 соответственно. Когда продукт найден, синтаксический анализатор переходит в состояние 3, чтобы собрать полный список слагаемых и найти конец правила r0. Товары также могут начинаться с нетерминального значения. Для любого другого опережающего или нетерминального сообщения синтаксический анализатор сообщает о синтаксической ошибке.

В состоянии 3 синтаксический анализатор только что нашел фразу Products, которая могла быть основана на двух возможных грамматических правилах:

r1: Суммы → Суммы + произведения •

r3: Товары → Товары • * Ценить

Выбор между r1 и r3 нельзя решить, просто взглянув назад на предыдущие фразы. Синтаксический анализатор должен проверить символ опережения, чтобы сказать, что делать. Если опережающий просмотр *, это в правиле 3, поэтому парсер переходит в * и переходит к состоянию 5. Если опережающий просмотр eof, он находится в конце правила 1 и правила 0, поэтому синтаксический анализатор готов.

В состоянии 9, приведенном выше, все непустые ячейки без ошибок относятся к одному и тому же сокращению r6. Некоторые парсеры экономят время и табличное пространство, не проверяя в этих простых случаях опережающий символ. Затем синтаксические ошибки обнаруживаются несколько позже, после некоторых безвредных сокращений, но еще до следующего действия сдвига или решения синтаксического анализатора.

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

Цикл парсера LR

Анализатор LR начинается с почти пустого стека синтаксического анализа, содержащего только начальное состояние 0, и с предварительного просмотра, содержащего первый отсканированный символ входного потока. Затем синтаксический анализатор повторяет следующий шаг цикла до тех пор, пока не будет выполнен, или не обнаружит синтаксическую ошибку:

Самое верхнее состояние в стеке синтаксического анализа - это некоторое состояние s, а текущий просмотр вперед - это некоторый конечный символ т. Найдите в строке следующее действие парсера s и столбец т таблицы Lookahead Action. Это действие - Shift, Уменьшение, Готово или Ошибка:

• Сдвиг п:

Сдвинуть согласованный терминал т в стек синтаксического анализа и сканировать следующий входной символ в опережающий буфер.

Нажать следующее состояние п в стек синтаксического анализа как новое текущее состояние.

• Уменьшить r_м: Применить правило грамматики r_м: Lhs → S₁ S₂ ... S_L

Удалите совпавшие самые верхние L символов (и деревья синтаксического анализа и соответствующие номера состояний) из стека синтаксического анализа.

Это показывает предыдущее состояние п что ожидал экземпляр символа Lhs.

Соедините деревья синтаксического анализа L вместе как одно дерево синтаксического анализа с новым корневым символом Lhs.

Найти следующее состояние п из ряда п и столбец Lhs таблицы LHS Goto.

Поместите символ и дерево для Lhs в стек синтаксического анализа.

Нажать следующее состояние п в стек синтаксического анализа как новое текущее состояние.

Предварительный просмотр и входной поток остаются без изменений.

• Готово: смотреть вперед т это eof маркер. Конец разбора. Если стек состояний содержит только начальное состояние, сообщите об успехе. В противном случае сообщите о синтаксической ошибке.
• Ошибка: сообщить о синтаксической ошибке. Синтаксический анализатор завершает работу или пытается какое-то восстановление.

Стек парсера LR обычно хранит только состояния автомата LR (0), так как символы грамматики могут быть получены из них (в автомате все входные переходы в какое-либо состояние помечены одним и тем же символом, который является символом, связанным с этим состоянием) . Более того, эти символы почти никогда не нужны, так как состояние - это все, что имеет значение при принятии решения о синтаксическом анализе.^[7]

Анализ генератора LR

Этот раздел статьи может пропустить большинство пользователей генераторов парсеров LR.

LR заявляет

Состояние 2 в примере таблицы синтаксического анализа относится к частично проанализированному правилу.

r1: Суммы → Суммы + • Товары

Это показывает, как парсер попал сюда, увидев затем Sums + пока ищу большую сумму. В • маркер продвинулся за пределы начала правила. Он также показывает, как синтаксический анализатор ожидает в конечном итоге завершить правило, найдя в следующий раз полные продукты. Но необходимы дополнительные сведения о том, как анализировать все части этих продуктов.

Частично проанализированные правила для состояния называются его «основными элементами LR (0)». Генератор парсера добавляет дополнительные правила или элементы для всех возможных следующих шагов в создании ожидаемых продуктов:

r3: Продукты → • Продукты * Стоимость

r4: Продукты → • Ценить

r5: Значение → • int

r6: Значение → • я бы

В • маркер находится в начале каждого из этих добавленных правил; парсер еще не подтвердил и не проанализировал какую-либо их часть. Эти дополнительные элементы называются «закрытием» основных элементов. Для каждого нетерминального символа, следующего сразу за •, генератор добавляет правила, определяющие этот символ. Это добавляет больше • маркеры и, возможно, различные символы последователей. Этот процесс закрытия продолжается до тех пор, пока все символы-последователи не будут развернуты. Последовательные нетерминалы для состояния 2 начинаются с Products. Затем стоимость добавляется закрытием. Следящие терминалы int и я бы.

Элементы ядра и закрытия вместе показывают все возможные законные способы перехода от текущего состояния к будущим состояниям и полные фразы. Если символ последователя появляется только в одном элементе, он приводит к следующему состоянию, содержащему только один базовый элемент с • маркер продвинутый. Так int приводит к следующему состоянию 8 с ядром

r5: Значение → int •

Если один и тот же символ последователя появляется в нескольких элементах, синтаксический анализатор еще не может сказать, какое правило здесь применяется. Таким образом, этот символ ведет к следующему состоянию, в котором показаны все оставшиеся возможности, снова с • маркер продвинутый. Продукты появляются как в r1, так и в r3. Таким образом, продукты приводят к следующему состоянию 3 с ядром

r1: Суммы → Суммы + произведения •

r3: Товары → Товары • * Ценить

На словах это означает, что если синтаксический анализатор видел один продукт, это может быть сделано, или у него все еще может быть еще больше вещей для умножения вместе. Все основные предметы имеют один и тот же символ перед • маркер; все переходы в это состояние всегда имеют один и тот же символ.

Некоторые переходы будут к ядрам и состояниям, которые уже были перечислены. Другие переходы приводят к новым состояниям. Генератор начинается с целевого правила грамматики. Оттуда он продолжает исследовать известные состояния и переходы, пока не будут найдены все необходимые состояния.

Эти состояния называются состояниями "LR (0)", потому что они используют опережающий просмотр k= 0, т.е. без опережения. Единственная проверка входных символов происходит, когда символ сдвигается внутрь. Проверка опережающих просмотров для сокращений выполняется отдельно таблицей синтаксического анализа, а не самими перечисленными состояниями.

Конечный автомат

Таблица синтаксического анализа описывает все возможные состояния LR (0) и их переходы. Они образуют конечный автомат (FSM). FSM - это простой механизм для разбора простых невложенных языков без использования стека. В этом приложении LR модифицированный «язык ввода» конечного автомата имеет как терминальные, так и нетерминальные символы и охватывает любой частично проанализированный снимок стека полного анализа LR.

Вспомните шаг 5 примера шагов синтаксического анализа:

Стек синтаксического анализа показывает серию переходов состояний, от начального состояния 0 до состояния 4, а затем до 5 и текущего состояния 8. Символы в стеке синтаксического анализа представляют собой символы сдвига или перехода для этих переходов. Другой способ увидеть это - конечный автомат может сканировать поток «Продукты *int + 1 "(без использования еще одного стека) и найдите самую левую законченную фразу, которую нужно сократить следующей. И это действительно его работа!

Как может простой автомат сделать это, если исходный неанализируемый язык имеет вложенность и рекурсию и определенно требует анализатора со стеком? Хитрость в том, что все, что находится слева от вершины стека, уже полностью уменьшено. Это устраняет все петли и вложенность этих фраз. FSM может игнорировать все старые начала фраз и отслеживать только самые новые фразы, которые могут быть завершены следующей. В теории LR это неясное название - «жизнеспособный префикс».

Наборы Lookahead

Состояния и переходы предоставляют всю необходимую информацию для действий сдвига и перехода таблицы синтаксического анализа. Генератору также необходимо вычислить ожидаемые наборы опережающих вычислений для каждого действия сокращения.

В SLR синтаксические анализаторы, эти опережающие наборы определяются непосредственно из грамматики, без учета отдельных состояний и переходов. Для каждого нетерминального S генератор SLR вырабатывает Follows (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 создают отдельный программный код для каждого состояния, а не таблицу синтаксического анализа. Эти парсеры могут работать в несколько раз быстрее, чем стандартный цикл парсеров в парсерах, управляемых таблицами. Самые быстрые парсеры используют сгенерированный код ассемблера.

в рекурсивный восходящий парсер В случае вариации явная структура стека синтаксического анализа также заменяется неявным стеком, используемым вызовами подпрограмм. Редукции завершают несколько уровней вызовов подпрограмм, что для большинства языков неуклюже. Таким образом, рекурсивные парсеры с восходящим движением обычно медленнее, менее очевидны и их труднее модифицировать вручную, чем парсеры рекурсивного спуска.

Другой вариант заменяет таблицу синтаксического анализа правилами сопоставления с образцом в непроцедурных языках, таких как Пролог.

GLR Обобщенные парсеры LR используйте восходящие методы LR для поиска всех возможных синтаксических разборов входного текста, а не только одного правильного анализа. Это важно для неоднозначных грамматик, например, используемых в человеческих языках. Множественные допустимые деревья синтаксического анализа вычисляются одновременно, без возврата. GLR иногда бывает полезен для компьютерных языков, которые нелегко описать бесконфликтной грамматикой LALR (1).

LC Парсеры левого угла Используйте восходящие методы LR для распознавания левого края альтернативных правил грамматики. Когда альтернативы были сужены до единственного возможного правила, анализатор затем переключается на нисходящие методы LL (1) для синтаксического анализа остальной части этого правила. Анализаторы LC имеют меньшие таблицы синтаксического анализа, чем анализаторы LALR, и лучшую диагностику ошибок. Широко используемых генераторов для детерминированных LC-анализаторов не существует. Анализаторы LC с множественным синтаксическим анализом полезны для человеческих языков с очень большими грамматиками.

Теория

Парсеры LR были изобретены Дональд Кнут в 1965 г. как эффективное обобщение парсеры приоритета. Кнут доказал, что синтаксические анализаторы LR были наиболее универсальными из возможных, которые все равно были бы эффективны в худших случаях.^{[нужна цитата ]}

«LR (k) грамматики могут быть эффективно проанализированы, время выполнения по существу пропорционально длине строки ".^[8]

Для каждого k≥1, "язык может быть порожден LR (k) грамматика тогда и только тогда, когда она детерминирована [и контекстно-свободна], тогда и только тогда, когда она может быть сгенерирована грамматикой LR (1) ".^[9]

Другими словами, если язык был достаточно разумным, чтобы позволить эффективный однопроходный синтаксический анализатор, он мог бы быть описан LR (k) грамматика. И эту грамматику всегда можно было механически преобразовать в эквивалентную (но более крупную) грамматику LR (1). Таким образом, метод синтаксического анализа LR (1) был теоретически достаточно мощным, чтобы работать с любым разумным языком. На практике естественные грамматики для многих языков программирования близки к LR (1).^{[нужна цитата ]}

The canonical LR parsers described by Knuth had too many states and very big parse tables that were impractically large for the limited memory of computers of that era. LR parsing became practical when Frank DeRemer изобрел SLR и LALR parsers with much fewer states.^[10][11]

For full details on LR theory and how LR parsers are derived from grammars, see The Theory of Parsing, Translation, and Compiling, Volume 1 (Aho and Ullman).^[7][2]

Earley parsers apply the techniques and • notation of LR parsers to the task of generating all possible parses for ambiguous grammars such as for human languages.

While LR(k) grammars have equal generative power for all k≥1, the case of LR(0) grammars is slightly different.A language L is said to have the prefix property if no word in L это proper prefix of another word in L.^[12]A language L has an LR(0) grammar if and only if L это deterministic context-free language with the prefix property.^[13]As a consequence, a language L is deterministic context-free if and only if L$ has an LR(0) grammar, where "$" is not a symbol of LС alphabet.^[14]

Additional example 1+1

Bottom-up parse of 1+1

This example of LR parsing uses the following small grammar with goal symbol E:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

to parse the following input:

1 + 1

Action and goto tables

The two LR(0) parsing tables for this grammar look as follows:

В action table is indexed by a state of the parser and a terminal (including a special terminal $ that indicates the end of the input stream) and contains three types of actions:

• shift, which is written as 'sп' and indicates that the next state is п
• reduce, which is written as 'rм' and indicates that a reduction with grammar rule м should be performed
• accept, which is written as 'acc' and indicates that the parser accepts the string in the input stream.

В goto table is indexed by a state of the parser and a nonterminal and simply indicates what the next state of the parser will be if it has recognized a certain nonterminal. This table is important to find out the next state after every reduction. After a reduction, the next state is found by looking up the goto table entry for top of the stack (i.e. current state) and the reduced rule's LHS (i.e. non-terminal).

Parsing steps

The table below illustrates each step in the process. Here the state refers to the element at the top of the stack (the right-most element), and the next action is determined by referring to the action table above. A $ is appended to the input string to denote the end of the stream.

Walkthrough

The parser starts out with the stack containing just the initial state ('0'):

[0]

The first symbol from the input string that the parser sees is '1'. To find the next action (shift, reduce, accept or error), the action table is indexed with the current state (the "current state" is just whatever is on the top of the stack), which in this case is 0, and the current input symbol, which is '1'. The action table specifies a shift to state 2, and so state 2 is pushed onto the stack (again, all the state information is in the stack, so "shifting to state 2" is the same as pushing 2 onto the stack). The resulting stack is

[0 '1' 2]

where the top of the stack is 2. For the sake of explanation the symbol (e.g., '1', B) is shown that caused the transition to the next state, although strictly speaking it is not part of the stack.

In state 2, the action table says to reduce with grammar rule 5 (regardless of what terminal the parser sees on the input stream), which means that the parser has just recognized the right-hand side of rule 5. In this case, the parser writes 5 to the output stream, pops one state from the stack (since the right-hand side of the rule has one symbol), and pushes on the stack the state from the cell in the goto table for state 0 and B, i.e., state 4. The resulting stack is:

[0 B 4]

However, in state 4, the action table says the parser should now reduce with rule 3. So it writes 3 to the output stream, pops one state from the stack, and finds the new state in the goto table for state 0 and E, which is state 3. The resulting stack:

[0 E 3]

The next terminal that the parser sees is a '+' and according to the action table it should then go to state 6:

[0 E 3 '+' 6]

The resulting stack can be interpreted as the history of a finite state automaton that has just read a nonterminal E followed by a terminal '+'. The transition table of this automaton is defined by the shift actions in the action table and the goto actions in the goto table.

The next terminal is now '1' and this means that the parser performs a shift and go to state 2:

[0 E 3 '+' 6 '1' 2]

Just as the previous '1' this one is reduced to B giving the following stack:

[0 E 3 '+' 6 B 8]

The stack corresponds with a list of states of a finite automaton that has read a nonterminal E, followed by a '+' and then a nonterminal B. In state 8 the parser always performs a reduce with rule 2. The top 3 states on the stack correspond with the 3 symbols in the right-hand side of rule 2. This time we pop 3 elements off of the stack (since the right-hand side of the rule has 3 symbols) and look up the goto state for E and 0, thus pushing state 3 back onto the stack

[0 E 3]

Finally, the parser reads a '$' (end of input symbol) from the input stream, which means that according to the action table (the current state is 3) the parser accepts the input string. The rule numbers that will then have been written to the output stream will be [5, 3, 5, 2] which is indeed a rightmost derivation of the string "1 + 1" in reverse.

Constructing LR(0) parsing tables

Items

The construction of these parsing tables is based on the notion of LR(0) items (simply called items here) which are grammar rules with a special dot added somewhere in the right-hand side. For example, the rule E → E + B has the following four corresponding items:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Rules of the form А → ε have only a single item А → •. The item E → E • + B, for example, indicates that the parser has recognized a string corresponding with E on the input stream and now expects to read a '+' followed by another string corresponding with B.

Item sets

It is usually not possible to characterize the state of the parser with a single item because it may not know in advance which rule it is going to use for reduction. For example, if there is also a rule E → E * B then the items E → E • + B and E → E • * B will both apply after a string corresponding with E has been read. Therefore, it is convenient to characterize the state of the parser by a set of items, in this case the set { E → E • + B, E → E • * B }.

Extension of Item Set by expansion of non-terminals

An item with a dot before a nonterminal, such as E → E + • B, indicates that the parser expects to parse the nonterminal B next. To ensure the item set contains all possible rules the parser may be in the midst of parsing, it must include all items describing how B itself will be parsed. This means that if there are rules such as B → 1 and B → 0 then the item set must also include the items B → • 1 and B → • 0. In general this can be formulated as follows:

If there is an item of the form А → v • Bw in an item set and in the grammar there is a rule of the form B → w' then the item B → • w' should also be in the item set.

Closure of item sets

Thus, any set of items can be extended by recursively adding all the appropriate items until all nonterminals preceded by dots are accounted for. The minimal extension is called the closure of an item set and written as clos(я) where я is an item set. It is these closed item sets that are taken as the states of the parser, although only the ones that are actually reachable from the begin state will be included in the tables.

Augmented grammar

Before the transitions between the different states are determined, the grammar is augmented with an extra rule

(0) S → E eof

where S is a new start symbol and E the old start symbol. The parser will use this rule for reduction exactly when it has accepted the whole input string.

For this example, the same grammar as above is augmented thus:

(0) S → E eof

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

It is for this augmented grammar that the item sets and the transitions between them will be determined.

Table construction

Finding the reachable item sets and the transitions between them

The first step of constructing the tables consists of determining the transitions between the closed item sets. These transitions will be determined as if we are considering a finite automaton that can read terminals as well as nonterminals. The begin state of this automaton is always the closure of the first item of the added rule: S → • E:

Item set 0

S → • E eof

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

В boldfaced "+" in front of an item indicates the items that were added for the closure (not to be confused with the mathematical '+' operator which is a terminal). The original items without a "+" are called the kernel of the item set.

Starting at the begin state (S0), all of the states that can be reached from this state are now determined. The possible transitions for an item set can be found by looking at the symbols (terminals and nonterminals) found following the dots; in the case of item set 0 those symbols are the terminals '0' and '1' and the nonterminals E and B. To find the item set that each symbol ${ extstyle xin {0,1,E,B}}$leads to, the following procedure is followed for each of the symbols:

1. Take the subset, S, of all items in the current item set where there is a dot in front of the symbol of interest, Икс.
2. For each item in S, move the dot to the right of Икс.
3. Close the resulting set of items.

For the terminal '0' (i.e. where x = '0') this results in:

Item set 1

B → 0 •

and for the terminal '1' (i.e. where x = '1') this results in:

Item set 2

B → 1 •

and for the nonterminal E (i.e. where x = E) this results in:

Item set 3

S → E • eof

E → E • * B

E → E • + B

and for the nonterminal B (i.e. where x = B) this results in:

Item set 4

E → B •

The closure does not add new items in all cases - in the new sets above, for example, there are no nonterminals following the dot.

Above procedure is continued until no more new item sets are found. For the item sets 1, 2, and 4 there will be no transitions since the dot is not in front of any symbol. For item set 3 though, we have dots in front of terminals '*' and '+'. For symbol ${ extstyle x={ exttt {*}}}$the transition goes to:

Item set 5

E → E * • B

+ B → • 0

+ B → • 1

and for ${ extstyle x={ exttt {+}}}$the transition goes to:

Item set 6

E → E + • B

+ B → • 0

+ B → • 1

Now, the third iteration begins.

For item set 5, the terminals '0' and '1' and the nonterminal B must be considered, but the resulting closed item sets are equal to already found item sets 1 and 2, respectively. For the nonterminal B, the transition goes to:

Item set 7

E → E * B •

For item set 6, the terminal '0' and '1' and the nonterminal B must be considered, but as before, the resulting item sets for the terminals are equal to the already found item sets 1 and 2. For the nonterminal B the transition goes to:

Item set 8

E → E + B •

These final item sets 7 and 8 have no symbols beyond their dots so no more new item sets are added, so the item generating procedure is complete. The finite automaton, with item sets as its states is shown below.

The transition table for the automaton now looks as follows:

Constructing the action and goto tables

From this table and the found item sets, the action and goto table are constructed as follows:

1. The columns for nonterminals are copied to the goto table.
2. The columns for the terminals are copied to the action table as shift actions.
3. An extra column for '$' (end of input) is added to the action table that contains acc for every item set that contains an item of the form S → w • eof.
4. If an item set я contains an item of the form А → ш • и А → ш is rule м с м > 0 then the row for state я in the action table is completely filled with the reduce action rм.

The reader may verify that this results indeed in the action and goto table that were presented earlier on.

A note about LR(0) versus SLR and LALR parsing

Only step 4 of the above procedure produces reduce actions, and so all reduce actions must occupy an entire table row, causing the reduction to occur regardless of the next symbol in the input stream. This is why these are LR(0) parse tables: they don't do any lookahead (that is, they look ahead zero symbols) before deciding which reduction to perform. A grammar that needs lookahead to disambiguate reductions would require a parse table row containing different reduce actions in different columns, and the above procedure is not capable of creating such rows.

Refinements to the LR(0) table construction procedure (such as SLR и LALR ) are capable of constructing reduce actions that do not occupy entire rows. Therefore, they are capable of parsing more grammars than LR(0) parsers.

Conflicts in the constructed tables

The automaton is constructed in such a way that it is guaranteed to be deterministic. However, when reduce actions are added to the action table it can happen that the same cell is filled with a reduce action and a shift action (a shift-reduce conflict) or with two different reduce actions (a reduce-reduce conflict). However, it can be shown that when this happens the grammar is not an LR(0) grammar. A classic real-world example of a shift-reduce conflict is the dangling else problem.

A small example of a non-LR(0) grammar with a shift-reduce conflict is:

(1) E → 1 E

(2) E → 1

One of the item sets found is:

Item set 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

There is a shift-reduce conflict in this item set: when constructing the action table according to the rules above, the cell for [item set 1, terminal '1'] contains s1 (shift to state 1) and r2 (reduce with grammar rule 2).

A small example of a non-LR(0) grammar with a reduce-reduce conflict is:

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

In this case the following item set is obtained:

Item set 1

A → 1 •

B → 1 •

There is a reduce-reduce conflict in this item set because in the cells in the action table for this item set there will be both a reduce action for rule 3 and one for rule 4.

Both examples above can be solved by letting the parser use the follow set (see LL parser ) of a nonterminal А to decide if it is going to use one of Аs rules for a reduction; it will only use the rule А → ш for a reduction if the next symbol on the input stream is in the follow set of А. This solution results in so-called Simple LR parsers.

Смотрите также

• Canonical LR parser
• Simple LR
• Look-Ahead LR
• Generalized LR

Рекомендации

дальнейшее чтение

• Chapman, Nigel P., LR Parsing: Theory and Practice, Издательство Кембриджского университета, 1987. ISBN  0-521-30413-X
• Pager, D., A Practical General Method for Constructing LR(k) Parsers. Acta Informatica 7, 249 - 268 (1977)
• "Compiler Construction: Principles and Practice" by Kenneth C. Louden. ISBN  0-534-939724

внешняя ссылка

• dickgrune.com, Parsing Techniques - A Practical Guide 1st Ed. web page of book includes downloadable pdf.
• Parsing Simulator This simulator is used to generate parsing tables LR and to resolve the exercises of the book
• Internals of an LALR(1) parser generated by GNU Bison - Implementation issues
• Course notes on LR parsing
• Shift-reduce and Reduce-reduce conflicts in an LALR parser
• A LR parser example
• Practical LR(k) Parser Construction
• The Honalee LR(k) Algorithm