В информатике LR-парсеры — это тип восходящего парсера , который анализирует детерминированные контекстно-свободные языки за линейное время. [1] Существует несколько вариантов парсеров LR: парсеры SLR , парсеры LALR , канонические парсеры LR(1) , минимальные парсеры LR(1) и обобщенные парсеры LR (парсеры GLR). Анализаторы LR могут быть сгенерированы генератором анализаторов из формальной грамматики , определяющей синтаксис анализируемого языка. Они широко используются для обработки компьютерных языков .
Парсер LR (слева направо, крайний правый вывод в обратном порядке) читает входной текст слева направо без резервного копирования (это верно для большинства парсеров) и производит самый правый вывод в обратном порядке: он выполняет синтаксический анализ снизу вверх – это не нисходящий анализ LL или специальный анализ. За именем «LR» часто следует числовой определитель, например «LR(1)» или иногда «LR( k )». Чтобы избежать возврата или угадывания, анализатору LR разрешено просматривать k входных символов, прежде чем решить, как анализировать более ранние символы. Обычно k равно 1 и не упоминается. Имени «LR» часто предшествуют другие уточнения, например, «SLR» и «LALR». Обозначение LR( k ) для грамматики было предложено Кнутом для обозначения «переводимой слева направо с границей k ». [1]
Парсеры LR детерминированы; они производят единственный правильный анализ без догадок и возвратов за линейное время. Это идеально для компьютерных языков, но парсеры LR не подходят для человеческих языков, которым нужны более гибкие, но неизбежно более медленные методы. Некоторые методы, которые могут анализировать произвольные контекстно-свободные языки (например, Cocke–Younger–Kasami , Earley , GLR ), имеют производительность в худшем случае O( n3 ). Другие методы, которые возвращаются или дают множественный анализ, могут даже занять экспоненциальное время, если они плохо угадывают. [2]
Вышеупомянутые свойства L , R и k фактически являются общими для всех анализаторов сдвига-сокращения , включая анализаторы приоритета . Но по соглашению имя LR обозначает форму синтаксического анализа, изобретенную Дональдом Кнутом , и исключает более ранние, менее мощные методы приоритета (например, анализатор приоритета оператора ). [1] Парсеры LR могут обрабатывать более широкий диапазон языков и грамматик, чем парсеры приоритета или нисходящий синтаксический анализ LL . [3] Это связано с тем, что анализатор LR ждет, пока он не увидит весь экземпляр некоторого грамматического шаблона, прежде чем фиксировать то, что он нашел. Анализатор LL должен решить или угадать, что он видит, гораздо раньше, когда он увидит только самый левый входной символ этого шаблона.
Анализатор LR сканирует и анализирует входной текст за один проход вперед по тексту. Синтаксический анализатор строит дерево разбора постепенно, снизу вверх и слева направо, без угадывания или возврата. На каждом этапе этого прохода синтаксический анализатор накапливает список поддеревьев или фраз входного текста, которые уже были проанализированы. Эти поддеревья еще не соединены вместе, поскольку синтаксический анализатор еще не достиг правого конца синтаксического шаблона, который их объединит.
На шаге 6 в примере синтаксического анализа только «A*2» был проанализирован не полностью. Существует только заштрихованный нижний левый угол дерева синтаксического анализа. Ни один из узлов дерева разбора с номером 7 и выше еще не существует. Узлы 3, 4 и 6 являются корнями изолированных поддеревьев для переменной A, оператора * и числа 2 соответственно. Эти три корневых узла временно хранятся в стеке синтаксического анализа. Оставшаяся неразобранная часть входного потока равна «+1».
Как и другие парсеры сдвига-сокращения, парсер LR работает, выполняя некоторую комбинацию шагов сдвига и шагов сокращения.
Если входные данные не содержат синтаксических ошибок, анализатор продолжает выполнять эти шаги до тех пор, пока все входные данные не будут использованы и все деревья синтаксического анализа не будут сведены к одному дереву, представляющему весь допустимый входной сигнал.
Анализаторы LR отличаются от других анализаторов сдвига-сокращения тем, как они решают, когда сокращать, и как выбирать между правилами со схожими окончаниями. Но окончательные решения и последовательность шагов по сдвигу или сокращению остаются теми же.
Большая часть эффективности парсера LR обусловлена его детерминированностью. Чтобы избежать угадывания, анализатор LR часто смотрит вперед (вправо) на следующий отсканированный символ, прежде чем решить, что делать с ранее отсканированными символами. Лексический сканер обрабатывает один или несколько символов раньше синтаксического анализатора. Символы просмотра вперед представляют собой «правый контекст» для принятия решения о синтаксическом анализе. [4]
Как и другие парсеры сдвига-сокращения, парсер LR лениво ждет, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем определить, что представляет собой объединенная конструкция. Затем анализатор немедленно воздействует на комбинацию, не дожидаясь дальнейшего. В примере с деревом синтаксического анализа фраза A сводится к значению, а затем к продуктам на шагах 1–3, как только появляется просмотр вперед *, вместо того, чтобы ждать позже, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать A, основаны только на том, что анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.
Сокращение реорганизует самые последние анализируемые элементы, расположенные сразу слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как стек . Этот стек синтаксического анализа растет вправо. Основание или низ стека находится слева и содержит самый левый и самый старый фрагмент синтаксического анализа. Каждый шаг сокращения действует только на самые правые, новейшие фрагменты синтаксического анализа. (Этот накопительный стек синтаксического анализа сильно отличается от прогнозирующего, растущего влево стека синтаксического анализа, используемого нисходящими анализаторами .)
Шаг 6 применяет грамматическое правило, состоящее из нескольких частей:
Это соответствует вершине стека, содержащей проанализированные фразы «... Products * Value». Шаг уменьшения заменяет этот экземпляр правой части правила «Продукты * Значение» на символ левой части правила, здесь более крупный «Продукты». Если анализатор создает полные деревья синтаксического анализа, три дерева для внутренних продуктов, * и значения объединяются в новый корень дерева для продуктов. В противном случае семантические детали из внутренних продуктов и значения выводятся на какой-либо более поздний этап компилятора или объединяются и сохраняются в новом символе продуктов. [5]
В анализаторах LR решения о сдвиге и сокращении потенциально основаны на всем стеке всего, что было проанализировано ранее, а не только на одном, самом верхнем символе стека. Если сделать это неумным способом, это может привести к очень медленным анализаторам, которые будут работать все медленнее и медленнее при более длинных входных данных. Анализаторы LR делают это с постоянной скоростью, суммируя всю соответствующую информацию левого контекста в одно число, называемое состоянием анализатора LR(0) . Для каждой грамматики и метода LR-анализа существует фиксированное (конечное) число таких состояний. Помимо хранения уже проанализированных символов, стек синтаксического анализа также запоминает номера состояний, достигнутые всем до этих точек.
На каждом этапе синтаксического анализа весь входной текст делится на стопку ранее разобранных фраз, текущий упреждающий символ и оставшийся неотсканированный текст. Следующее действие анализатора определяется его текущим номером состояния LR(0) (крайний правый в стеке) и символом просмотра вперед. В приведенных ниже шагах все черные детали точно такие же, как и в других синтаксических анализаторах, не поддерживающих LR. Стеки парсеров LR добавляют информацию о состоянии фиолетовым цветом, суммируя черные фразы слева от них в стеке и какие синтаксические возможности ожидать дальше. Пользователи анализатора LR обычно могут игнорировать информацию о состоянии. Эти состояния объяснены в следующем разделе.
На начальном шаге 0 входной поток «A*2 + 1» делится на
Стек синтаксического анализа начинается с хранения только начального состояния 0. Когда состояние 0 видит просматриваемый идентификатор , оно знает, что нужно переместить этот идентификатор в стек, сканировать следующий входной символ * и перейти к состоянию 9.
На шаге 4 общий входной поток «A*2 + 1» в данный момент делится на
Состояния, соответствующие составным фразам, — 0, 4 и 5. Текущее, самое правое состояние в стеке — это состояние 5. Когда состояние 5 видит опережающее int , оно знает, что нужно переместить это int в стек как собственную фразу, и отсканируйте следующий входной символ + и перейдите к состоянию 8.
На этапе 12 весь входной поток был использован, но организован лишь частично. Текущее состояние — 3. Когда состояние 3 видит опережающий просмотр eof , оно знает, что нужно применить завершенное грамматическое правило.
объединив три крайние правые фразы стека для сумм, + и продуктов в одну вещь. Состояние 3 само по себе не знает, каким должно быть следующее состояние. Это можно найти, вернувшись в состояние 0, слева от сокращаемой фразы. Когда состояние 0 видит этот новый завершенный экземпляр суммы, оно переходит в состояние 1 (снова). Именно поэтому консультации со старыми состояниями сохраняются в стеке, а не только с текущим состоянием.
Анализаторы LR построены на основе грамматики, которая формально определяет синтаксис входного языка как набор шаблонов. Грамматика не охватывает все правила языка, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Анализаторы LR используют контекстно-свободную грамматику , которая работает только с локальными шаблонами символов.
Используемый здесь пример грамматики представляет собой крошечное подмножество языка Java или C:
Терминальные символы грамматики — это многосимвольные символы или «токены», найденные во входном потоке лексическим сканером . Здесь они включают + * и int для любой целочисленной константы, id для любого имени идентификатора и eof для конца входного файла. Грамматику не волнует, каковы значения int или написание идентификатора , а также не важны пробелы или разрывы строк. Грамматика использует эти терминальные символы, но не определяет их. Это всегда листовые узлы (на нижнем густом конце) дерева разбора.
Термины, написанные с заглавной буквы, такие как суммы, являются нетерминальными символами . Это названия понятий или шаблонов в языке. Они определены в грамматике и никогда не встречаются во входном потоке. Это всегда внутренние узлы (над нижним краем) дерева разбора. Они происходят только в результате применения парсером некоторого грамматического правила. Некоторые нетерминалы определяются двумя или более правилами; это альтернативные модели. Правила могут ссылаться сами на себя, что называется рекурсивным . Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.
Любой компьютерный язык может быть описан несколькими различными грамматиками. Анализатор LR(1) может обрабатывать многие, но не все распространенные грамматики. Обычно можно вручную изменить грамматику, чтобы она соответствовала ограничениям синтаксического анализа LR(1) и инструмента-генератора.
Грамматика синтаксического анализатора LR должна быть однозначной сама по себе или должна быть дополнена правилами приоритета для разрешения конфликтов. Это означает, что существует только один правильный способ применить грамматику к данному легальному примеру языка, в результате чего получается уникальное дерево синтаксического анализа только с одним значением и уникальная последовательность действий сдвига/сокращения для этого примера. LR-синтаксический анализ бесполезен для человеческих языков с неоднозначной грамматикой, зависящей от взаимодействия слов. Человеческие языки лучше обрабатываются такими парсерами, как Generalized LR parser , Earley parser или алгоритм CYK , которые могут одновременно вычислять все возможные деревья синтаксического анализа за один проход.
Большинство парсеров LR управляются таблицами. Программный код парсера представляет собой простой общий цикл, одинаковый для всех грамматик и языков. Знания грамматики и ее синтаксические значения закодированы в неизменяемых таблицах данных, называемых таблицами синтаксического анализа (или таблицами синтаксического анализа ). Записи в таблице показывают, нужно ли сдвигать или сокращать (и по какому правилу грамматики) для каждой допустимой комбинации состояния синтаксического анализатора и символа просмотра вперед. Таблицы анализа также рассказывают, как вычислить следующее состояние, зная только текущее состояние и следующий символ.
Таблицы синтаксического анализа намного больше, чем грамматика. Таблицы LR сложно точно вычислить вручную для больших грамматик. Таким образом, они механически извлекаются из грамматики с помощью какого-либо инструмента -генератора синтаксического анализатора , такого как Bison . [6]
В зависимости от того, как генерируются состояния и таблица синтаксического анализа, результирующий парсер называется либо синтаксическим анализатором SLR (простой LR) , LALR (просматривающим LR) парсером , либо каноническим парсером LR . Парсеры LALR обрабатывают больше грамматик, чем парсеры SLR. Парсеры Canonical LR обрабатывают еще больше грамматик, но используют гораздо больше состояний и гораздо большие таблицы. Пример грамматики — SLR.
Таблицы синтаксического анализа LR двумерны. Каждое текущее состояние анализатора LR(0) имеет свою собственную строку. Каждый возможный следующий символ имеет свой столбец. Некоторые комбинации состояния и следующего символа невозможны для допустимых входных потоков. Эти пустые ячейки вызывают сообщения о синтаксических ошибках.
В левой половине таблицы «Действие» есть столбцы для символов терминала просмотра вперед . Эти ячейки определяют, будет ли следующим действием синтаксического анализатора сдвиг (для состояния n ) или уменьшение (по правилу грамматики r n ).
Правая половина таблицы Goto содержит столбцы для нетерминальных символов . Эти ячейки показывают, к какому состоянию следует перейти после того, как левая сторона некоторого сокращения создала ожидаемый новый экземпляр этого символа. Это похоже на действие сдвига, но для нетерминалов; символ терминала просмотра вперед не изменяется.
Столбец таблицы «Текущие правила» документирует значение и синтаксические возможности каждого состояния, разработанные генератором синтаксического анализатора. Он не включен в фактические таблицы, используемые во время синтаксического анализа. Маркер • (розовая точка) показывает, где сейчас находится синтаксический анализатор, в пределах некоторых частично распознаваемых грамматических правил. То, что слева от •, уже проанализировано, а то, что справа, ожидается в ближайшее время. Состояние имеет несколько таких текущих правил, если парсер еще не сузил возможности до одного правила.
В состоянии 2 выше синтаксический анализатор только что нашел и вставил + в грамматическом правиле.
Следующая ожидаемая фраза — «Продукты». Продукты начинаются с терминальных символов int или id . Если предварительный просмотр является одним из них, синтаксический анализатор сдвигает их и переходит к состоянию 8 или 9 соответственно. Когда продукты найдены, анализатор переходит в состояние 3, чтобы накопить полный список слагаемых и найти конец правила r0. Продукты также могут начинаться с нетерминальной стоимости. Для любого другого просмотра вперед или нетерминала синтаксический анализатор объявляет синтаксическую ошибку.
В состоянии 3 анализатор только что нашел фразу Products, которая может относиться к двум возможным грамматическим правилам:
Выбор между r1 и r3 нельзя сделать, просто оглядываясь назад на предыдущие фразы. Синтаксический анализатор должен проверить символ прогнозирования, чтобы сказать, что делать. Если предварительный просмотр равен * , он находится в правиле 3, поэтому синтаксический анализатор сдвигается в * и переходит в состояние 5. Если предварительный просмотр равен eof , он находится в конце правила 1 и правила 0, поэтому синтаксический анализатор завершен.
В состоянии 9 выше все непустые ячейки без ошибок относятся к одному и тому же сокращению r6. Некоторые парсеры экономят время и табличное пространство, не проверяя символ просмотра в этих простых случаях. Синтаксические ошибки обнаруживаются несколько позже, после некоторых безобидных сокращений, но еще до следующего действия сдвига или решения синтаксического анализатора.
Отдельные ячейки таблицы не должны содержать несколько альтернативных действий, иначе синтаксический анализатор будет недетерминированным с догадками и обратным отслеживанием. Если грамматика отличается от LR(1), в некоторых ячейках будут возникать конфликты сдвига/сокращения между возможными действиями сдвига и действиями сокращения или конфликты сдвига/сокращения между несколькими правилами грамматики. Анализаторы LR(k) разрешают эти конфликты (где это возможно), проверяя дополнительные символы просмотра, помимо первого.
Анализатор LR начинается с почти пустого стека анализа, содержащего только начальное состояние 0, и с просмотра вперед, содержащего первый отсканированный символ входного потока. Затем анализатор повторяет следующий шаг цикла до тех пор, пока он не будет завершен или не застрянет в синтаксической ошибке:
Самое верхнее состояние в стеке синтаксического анализа — это некоторое состояние s , а текущий просмотр вперед — это некоторый терминальный символ t . Найдите следующее действие синтаксического анализатора в строке s и столбце t таблицы предварительных действий. Это действие — «Сдвиг», «Уменьшение», «Принять» или «Ошибка»:
Стек парсера LR обычно хранит только состояния автомата LR(0), поскольку из них могут быть получены грамматические символы (в автомате все входные переходы в какое-то состояние помечаются одним и тем же символом, который является символом, связанным с этим состоянием). . Более того, эти символы почти никогда не нужны, поскольку при принятии решения о синтаксическом анализе имеет значение только состояние. [7]
Этот раздел статьи может быть пропущен большинством пользователей генераторов парсеров LR.
Состояние 2 в примере таблицы анализа относится к частично проанализированному правилу.
Это показывает, как синтаксический анализатор попал сюда, увидев суммы, а затем + , ища большую сумму. Маркер • вышел за пределы начала правила. Он также показывает, как анализатор ожидает в конечном итоге завершить правило, найдя затем полный файл Products. Но необходимы более подробные сведения о том, как анализировать все части этих продуктов.
Частично проанализированные правила состояния называются его «основными элементами LR(0)». Генератор парсера добавляет дополнительные правила или элементы для всех возможных следующих шагов в создании ожидаемых продуктов:
Маркер • находится в начале каждого из этих добавленных правил; парсер еще не подтвердил и не разобрал ни одну из их частей. Эти дополнительные элементы называются «закрытием» основных пунктов. Для каждого нетерминального символа, следующего сразу за символом • , генератор добавляет правила, определяющие этот символ. Это добавляет больше • маркеров и, возможно, другие символы последователей. Этот процесс закрытия продолжается до тех пор, пока все символы-последователи не будут развернуты. Последующие нетерминалы для состояния 2 начинаются с Products. Затем ценность добавляется за счет закрытия. Подчиненные терминалы — int и id .
Элементы ядра и замыкания вместе показывают все возможные законные способы перехода от текущего состояния к будущим состояниям и полным фразам. Если символ последователя появляется только в одном элементе, это приводит к следующему состоянию, содержащему только один основной элемент с выдвинутым маркером • . Таким образом, int приводит к следующему состоянию 8 с ядром
Если один и тот же символ ведомого присутствует в нескольких элементах, синтаксический анализатор еще не может определить, какое правило здесь применимо. Таким образом, этот символ ведет к следующему состоянию, которое показывает все оставшиеся возможности, опять же с выдвинутым маркером • . Продукты появляются как в r1, так и в r3. Таким образом, продукты приводят к следующему состоянию 3 с ядром
Проще говоря, это означает, что если парсер обнаружил один Product, это может быть выполнено, или у него может быть еще больше вещей, которые нужно умножить вместе. Все основные элементы имеют один и тот же символ перед маркером • ; все переходы в это состояние всегда имеют один и тот же символ.
Некоторые переходы будут осуществляться к ядрам и состояниям, которые уже были перечислены. Другие переходы приводят к новым состояниям. Генератор начинается с целевого правила грамматики. После этого он продолжает исследовать известные состояния и переходы, пока не будут найдены все необходимые состояния.
Эти состояния называются состояниями «LR(0)», потому что они используют предварительный просмотр k =0, т.е. никакого предпросмотра. Единственная проверка входных символов происходит при сдвиге символа. Проверка опережающего просмотра на сокращения выполняется отдельно по таблице синтаксического анализа, а не по самим перечисляемым состояниям.
Таблица анализа описывает все возможные состояния LR(0) и их переходы. Они образуют конечный автомат (автомат). FSM — это простой механизм для анализа простых невложенных языков без использования стека. В этом приложении LR модифицированный «язык ввода» FSM имеет как терминальные, так и нетерминальные символы и охватывает любой частично проанализированный снимок стека полного анализа LR.
Вспомните шаг 5 примера шагов анализа:
Стек синтаксического анализа показывает серию переходов состояний: от начального состояния 0 к состоянию 4, а затем к 5 и текущему состоянию 8. Символы в стеке синтаксического анализа представляют собой символы сдвига или перехода для этих переходов. Другой способ увидеть это заключается в том, что конечный автомат может сканировать поток «Products * int + 1» (без использования еще одного стека) и находить самую левую полную фразу, которую следует сократить следующей. И это действительно его работа!
Как простой автомат может это сделать, если исходный неразобранный язык имеет вложенность и рекурсию и обязательно требует анализатора со стеком? Хитрость в том, что все, что находится слева от вершины стека, уже полностью уменьшено. Это устраняет все циклы и вложения в этих фразах. FSM может игнорировать все старые начала фраз и отслеживать только самые новые фразы, которые могут быть завершены следующими. Неясное название этого явления в теории LR — «жизнеспособный префикс».
Состояния и переходы предоставляют всю необходимую информацию для действий сдвига и перехода к таблице синтаксического анализа. Генератору также необходимо вычислить ожидаемые наборы просмотра вперед для каждого действия сокращения.
В анализаторах 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 создают отдельный программный код для каждого состояния, а не таблицу синтаксического анализа. Эти анализаторы могут работать в несколько раз быстрее, чем общий цикл анализатора в таблично-ориентированных анализаторах. Самые быстрые парсеры используют сгенерированный ассемблерный код.
В варианте синтаксического анализатора с рекурсивным восхождением явная структура стека анализа также заменяется неявным стеком, используемым при вызовах подпрограмм. Сокращение завершает несколько уровней вызовов подпрограмм, что в большинстве языков является неуклюжим. Таким образом, парсеры с рекурсивным восхождением обычно медленнее, менее очевидны и их труднее модифицировать вручную, чем парсеры с рекурсивным спуском .
Другой вариант заменяет таблицу синтаксического анализа правилами сопоставления с образцом в непроцедурных языках, таких как Пролог .
GLR Обобщенные анализаторы LR используют восходящие методы LR для поиска всех возможных анализов входного текста, а не только одного правильного анализа. Это важно для неоднозначной грамматики, например, используемой в человеческих языках. Несколько допустимых деревьев синтаксического анализа вычисляются одновременно, без возврата. GLR иногда полезен для компьютерных языков, которые нелегко описать с помощью бесконфликтной грамматики LALR(1).
LC Парсеры левого угла используют восходящие методы LR для распознавания левого конца альтернативных грамматических правил. Когда альтернативы сужены до одного возможного правила, анализатор переключается на нисходящие методы LL(1) для анализа остальной части этого правила. Анализаторы LC имеют меньшие таблицы анализа, чем анализаторы LALR, и лучшую диагностику ошибок. Широко используемых генераторов для детерминированных LC-парсеров не существует. Парсеры LC с множественным анализом полезны для человеческих языков с очень большими грамматиками.
LR-парсеры были изобретены Дональдом Кнутом в 1965 году как эффективное обобщение парсеров приоритета . Кнут доказал, что LR-парсеры являются наиболее универсальными из возможных парсеров, которые все равно будут эффективны в худших случаях. [ нужна цитата ]
Другими словами, если бы язык был достаточно разумным, чтобы обеспечить эффективный однопроходный анализатор, его можно было бы описать грамматикой LR( k ). И эту грамматику всегда можно механически преобразовать в эквивалентную (но более крупную) грамматику LR(1). Таким образом, метод анализа LR(1) теоретически был достаточно мощным, чтобы обрабатывать любой разумный язык. На практике естественные грамматики многих языков программирования близки к LR(1). [ нужна цитата ]
Канонические LR-парсеры, описанные Кнутом, имели слишком много состояний и очень большие таблицы синтаксического анализа, которые были непрактично велики для ограниченной памяти компьютеров той эпохи. Анализ LR стал практичным, когда Фрэнк ДеРемер изобрел анализаторы SLR и LALR с гораздо меньшим количеством состояний. [10] [11]
Полную информацию о теории LR и о том, как LR-парсеры происходят из грамматик, см. в « Теории синтаксического анализа, трансляции и компиляции», том 1 (Ахо и Ульман). [7] [2]
Парсеры Эрли применяют методы и обозначения парсеров LR для создания всех возможных анализов неоднозначных грамматик, например, для человеческих языков.
Хотя грамматики LR( k ) имеют одинаковую порождающую способность для всех k ≥1, случай грамматик LR(0) немного отличается. Говорят, что язык L обладает свойством префикса, если ни одно слово в L не является собственным префиксом другого слова в L. [12] Язык L имеет LR(0)-грамматику тогда и только тогда, когда L является детерминированным контекстно-свободным языком со свойством префикса. [13] Как следствие, язык L является детерминированным и неконтекстно-свободным тогда и только тогда, когда L $ имеет LR(0) -грамматику , где «$ » не является символом алфавита L. [14]
В этом примере анализа LR используется следующая небольшая грамматика с символом цели E:
для анализа следующего ввода:
Две таблицы синтаксического анализа LR(0) для этой грамматики выглядят следующим образом:
Таблица действий индексируется по состоянию парсера и терминала (включая специальный терминал $, обозначающий конец входного потока) и содержит три типа действий:
Таблица перехода индексируется по состоянию анализатора и нетерминала и просто указывает, каким будет следующее состояние анализатора, если он распознал определенный нетерминал. Эта таблица важна для определения следующего состояния после каждого сокращения. После сокращения следующее состояние находится путем поиска записи таблицы перехода для вершины стека (т. е. текущего состояния) и LHS сокращенного правила (т. е. нетерминального).
Таблица ниже иллюстрирует каждый этап этого процесса. Здесь состояние относится к элементу в верхней части стека (самый правый элемент), а следующее действие определяется с помощью приведенной выше таблицы действий. К входной строке добавляется $, обозначающий конец потока.
Анализатор начинается со стека, содержащего только начальное состояние («0»):
Первый символ входной строки, который видит синтаксический анализатор, — это «1». Чтобы найти следующее действие (сдвиг, уменьшение, принятие или ошибка), таблица действий индексируется по текущему состоянию («текущее состояние» — это все, что находится на вершине стека), которое в данном случае равно 0, и текущий входной символ, равный «1». Таблица действий определяет переход в состояние 2, поэтому состояние 2 помещается в стек (опять же, вся информация о состоянии находится в стеке, поэтому «переход в состояние 2» аналогичен помещению 2 в стек). Полученный стек
где вершина стека равна 2. Для пояснения показан символ (например, '1', B), вызвавший переход в следующее состояние, хотя, строго говоря, он не является частью стека.
В состоянии 2 таблица действий требует сокращения с помощью грамматического правила 5 (независимо от того, какой терминал синтаксический анализатор видит во входном потоке), что означает, что синтаксический анализатор только что распознал правую часть правила 5. В этом случае синтаксический анализатор записывает 5 в выходной поток, извлекает одно состояние из стека (поскольку правая часть правила имеет один символ) и помещает в стек состояние из ячейки в таблице перехода для состояний 0 и B, т.е. , состояние 4. Итоговый стек:
Однако в состоянии 4 таблица действий сообщает, что анализатор теперь должен сокращать по правилу 3. Поэтому он записывает 3 в выходной поток, извлекает одно состояние из стека и находит новое состояние в таблице перехода для состояний 0 и E. это состояние 3. Итоговый стек:
Следующий терминал, который увидит парсер, — это «+», и в соответствии с таблицей действий он должен перейти в состояние 6:
Полученный стек можно интерпретировать как историю конечного автомата , который только что прочитал нетерминал E, за которым следует терминальный «+». Таблица переходов этого автомата определяется действиями сдвига в таблице действий и действиями перехода в таблице перехода.
Следующий терминал теперь равен «1», и это означает, что парсер выполняет сдвиг и переходит в состояние 2:
Как и предыдущая «1», эта цифра уменьшается до B, давая следующий стек:
Стек соответствует списку состояний конечного автомата, который прочитал нетерминал E, за которым следует «+», а затем нетерминал B. В состоянии 8 синтаксический анализатор всегда выполняет сокращение по правилу 2. Верхние 3 состояния на стек соответствует 3 символам в правой части правила 2. На этот раз мы извлекаем 3 элемента из стека (поскольку правая часть правила содержит 3 символа) и ищем состояние перехода для E и 0. , тем самым помещая состояние 3 обратно в стек
Наконец, анализатор считывает «$» (конец входного символа) из входного потока, что означает, что в соответствии с таблицей действий (текущее состояние — 3) анализатор принимает входную строку. Номера правил, которые затем будут записаны в выходной поток, будут [5, 3, 5, 2], что действительно является крайним правым производным строки «1 + 1» в обратном порядке.
Конструкция этих таблиц синтаксического анализа основана на понятии элементов LR(0) (здесь они называются просто элементами ), которые представляют собой грамматические правила со специальной точкой, добавленной где-то в правой части. Например, правило E → E + B имеет следующие четыре соответствующих пункта:
Правила вида A → ε имеют только один пункт A → • . Например, элемент E → E • + B указывает, что синтаксический анализатор распознал строку, соответствующую E во входном потоке, и теперь ожидает прочитать «+», за которым следует другая строка, соответствующая B.
Обычно невозможно охарактеризовать состояние парсера одним элементом, поскольку он может заранее не знать, какое правило он будет использовать для редукции. Например, если также существует правило 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. В общем виде это можно сформулировать следующим образом:
Таким образом, любой набор элементов можно расширить путем рекурсивного добавления всех соответствующих элементов до тех пор, пока не будут учтены все нетерминалы, которым предшествуют точки. Минимальное расширение называется замыканием набора элементов и записывается как clos ( I ), где I — набор элементов. Именно эти закрытые наборы элементов принимаются за состояния парсера, хотя в таблицы будут включены только те, которые реально достижимы из начального состояния.
Прежде чем будут определены переходы между различными состояниями, грамматика дополняется дополнительным правилом.
где S — новый стартовый символ, а E — старый стартовый символ. Синтаксический анализатор будет использовать это правило для сокращения именно тогда, когда он примет всю входную строку.
В этом примере та же грамматика, что и выше, дополнена следующим образом:
Именно для этой дополненной грамматики будут определяться наборы элементов и переходы между ними.
Первый шаг построения таблиц состоит в определении переходов между закрытыми множествами элементов. Эти переходы будут определяться так, как если бы мы рассматривали конечный автомат, который может читать как терминалы, так и нетерминалы. Начальным состоянием этого автомата всегда является закрытие первого пункта добавленного правила: S → • E eof:
Выделенный жирным шрифтом « + » перед элементом указывает элементы, которые были добавлены для замыкания (не путать с математическим оператором «+», который является терминалом). Исходные элементы без знака « + » называются ядром набора элементов.
Начиная с начального состояния (S0), теперь определяются все состояния, в которые можно попасть из этого состояния. Возможные переходы для набора элементов можно найти, посмотрев на символы (терминалы и нетерминалы), расположенные после точек; в случае набора элементов 0 этими символами являются терминалы «0» и «1», а также нетерминалы E и B. Чтобы найти набор элементов, к которому ведет каждый символ, для каждого из символов выполняется следующая процедура:
Для терминала «0» (т.е. где x = «0») это приводит к:
а для терминала «1» (т.е. где x = «1») это приводит к:
а для нетерминала E (т.е. где x = E) это приводит к:
а для нетерминала B (т.е. где x = B) это приводит к:
Замыкание не добавляет новые элементы во всех случаях - например, в новых наборах, указанных выше, после точки нет нетерминалов.
Вышеуказанная процедура продолжается до тех пор, пока не перестанут обнаруживаться новые наборы элементов. Для наборов элементов 1, 2 и 4 переходов не будет, поскольку точка не находится перед каким-либо символом. Однако для набора элементов 3 перед клеммами «*» и «+» стоят точки. Для символа переход идет к:
и для перехода переходит к:
Теперь начинается третья итерация.
Для набора элементов 5 необходимо учитывать терминалы «0» и «1», а также нетерминал B, но результирующие закрытые наборы элементов для терминалов равны уже найденным наборам элементов 1 и 2 соответственно. Для нетерминала B переход идет к:
Для набора элементов 6 необходимо учитывать терминалы «0» и «1», а также нетерминал B, но, как и прежде, результирующие наборы элементов для терминалов равны уже найденным наборам элементов 1 и 2. Для нетерминала B переход идет к:
Эти окончательные наборы элементов 7 и 8 не имеют символов за пределами точек, поэтому новые наборы элементов больше не добавляются, поэтому процедура создания элементов завершена. Конечный автомат с наборами элементов в качестве состояний показан ниже.
Таблица переходов для автомата теперь выглядит следующим образом:
На основе этой таблицы и найденных наборов элементов таблица действий и перехода строится следующим образом:
Читатель может убедиться, что эти шаги приводят к действию и таблице перехода, представленной ранее.
Только шаг 4 описанной выше процедуры производит действия сокращения, поэтому все действия сокращения должны занимать всю строку таблицы, в результате чего сокращение происходит независимо от следующего символа во входном потоке. Вот почему это таблицы синтаксического анализа LR(0): они не выполняют никакого просмотра вперед (то есть, они просматривают нулевые символы), прежде чем решить, какое сокращение выполнить. Грамматика, которой требуется предварительный просмотр для устранения неоднозначности сокращений, потребует строки таблицы синтаксического анализа, содержащей разные действия сокращения в разных столбцах, и описанная выше процедура не способна создавать такие строки.
Усовершенствования процедуры построения таблицы LR (0) (такие как SLR и LALR ) позволяют создавать действия сокращения, которые не занимают целые строки. Следовательно, они способны анализировать больше грамматик, чем парсеры LR(0).
Автомат построен таким образом, что он гарантированно детерминирован. Однако при добавлении действий сокращения в таблицу действий может случиться так, что одна и та же ячейка будет заполнена действием сокращения и действием сдвига ( конфликт сдвига-сокращения ) или двумя разными действиями сокращения ( конфликт сокращения-сокращения ). Однако можно показать, что в этом случае грамматика не является грамматикой LR(0). Классическим примером конфликта сдвига и сокращения из реальной жизни является проблема висячего другого .
Небольшой пример грамматики, отличной от LR(0), с конфликтом сдвига-сокращения:
Один из найденных наборов предметов:
В этом наборе элементов существует конфликт сдвига-сокращения: при построении таблицы действий в соответствии с приведенными выше правилами ячейка для [набор элементов 1, терминал '1'] содержит s1 (переход в состояние 1) и r2 (сокращение с помощью грамматики). правило 2).
Небольшой пример грамматики, отличной от LR(0), с конфликтом сокращения-сокращения:
В этом случае получается следующий набор предметов:
В этом наборе элементов существует конфликт уменьшения-сокращения, поскольку в ячейках таблицы действий для этого набора элементов будет одновременно действие уменьшения для правила 3 и одно для правила 4.
Оба примера выше можно решить, если позволить синтаксическому анализатору использовать следующий набор (см. анализатор LL ) нетерминала A , чтобы решить, будет ли он использовать одно из правил A для сокращения; он будет использовать правило A → w для сокращения только в том случае, если следующий символ во входном потоке находится в следующем наборе A . Результатом этого решения являются так называемые Simple LR parsers .
