В информатике LR-парсеры — это тип восходящего парсера , который анализирует детерминированные контекстно-свободные языки за линейное время. [1] Существует несколько вариантов LR-парсеров: SLR-парсеры , LALR-парсеры , канонические LR(1)-парсеры , минимальные LR(1)-парсеры и обобщенные LR-парсеры (GLR-парсеры). LR-парсеры могут быть сгенерированы генератором парсеров из формальной грамматики, определяющей синтаксис анализируемого языка. Они широко используются для обработки компьютерных языков .
Парсер LR (слева направо, самый правый вывод в обратном порядке) читает входной текст слева направо без резервного копирования (это справедливо для большинства парсеров) и производит самый правый вывод в обратном порядке: он выполняет парсинг снизу вверх , а не парсинг LL сверху вниз или парсинг ad-hoc. За именем «LR» часто следует числовой квалификатор, как в «LR(1)» или иногда «LR( k )». Чтобы избежать возврата или угадывания, парсеру LR разрешено заглядывать вперед на k предварительных входных символов , прежде чем решать, как парсить более ранние символы. Обычно k равно 1 и не упоминается. Имени «LR» часто предшествуют другие квалификаторы, как в «SLR» и «LALR». Обозначение «LR( k )» для грамматики было предложено Кнутом как «переводимое слева направо с привязанным k ». [1]
Анализаторы LR детерминированы; они производят один правильный анализ без догадок или возвратов за линейное время. Это идеально для компьютерных языков, но анализаторы LR не подходят для человеческих языков, которым нужны более гибкие, но неизбежно более медленные методы. Некоторые методы, которые могут анализировать произвольные контекстно-свободные языки (например, Cocke–Younger–Kasami , Earley , GLR ), имеют худшую производительность O( n 3 ) времени. Другие методы, которые откатывают или производят несколько анализов, могут даже занимать экспоненциальное время, когда они плохо угадывают. [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 сводится к Value, а затем к Products на шагах 1-3, как только появляется lookahead *, вместо того, чтобы ждать позже, чтобы организовать эти части дерева разбора. Решения о том, как обрабатывать A, основаны только на том, что парсер и сканер уже видели, без учета того, что появляется гораздо позже справа.
Сокращения реорганизуют самые последние проанализированные вещи, сразу слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как стек . Этот стек анализа растет вправо. Основание или дно стека находится слева и содержит самый левый, самый старый фрагмент анализа. Каждый шаг сокращения действует только на самые правые, самые новые фрагменты анализа. (Этот накопительный стек анализа очень отличается от предиктивного, растущего влево стека анализа, используемого нисходящими анализаторами .)
Шаг 6 применяет грамматическое правило, состоящее из нескольких частей:
Это соответствует вершине стека, содержащей проанализированные фразы "... Products * Value". Шаг сокращения заменяет этот экземпляр правой стороны правила, "Products * Value", на символ левой стороны правила, здесь больший Products. Если анализатор строит полные деревья разбора, три дерева для внутренних Products, *, и Value объединяются новым корнем дерева для Products. В противном случае семантические детали из внутренних Products и Value выводятся на какой-то более поздний проход компилятора или объединяются и сохраняются в новом символе Products. [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 , оно знает, что нужно применить завершенное правило грамматики
путем объединения трех самых правых фраз стека для Sums, + и Products в одну вещь. Состояние 3 само по себе не знает, каким должно быть следующее состояние. Это можно найти, вернувшись в состояние 0, которое находится слева от сокращаемой фразы. Когда состояние 0 видит этот новый завершенный экземпляр Sums, оно переходит в состояние 1 (снова). Это обращение к более старым состояниям — вот почему они хранятся в стеке, а не только текущее состояние.
Парсеры LR построены на основе грамматики, которая формально определяет синтаксис входного языка как набор шаблонов. Грамматика не охватывает все правила языка, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Парсеры LR используют контекстно -свободную грамматику , которая имеет дело только с локальными шаблонами символов.
Приведенный здесь пример грамматики представляет собой небольшое подмножество языка Java или C:
Терминальные символы грамматики — это многосимвольные символы или «токены», найденные во входном потоке лексическим сканером . Здесь они включают + * и int для любой целочисленной константы, id для любого имени идентификатора и eof для конца входного файла. Грамматику не волнует, каковы значения int или написание id , а также не волнуют пробелы или переносы строк. Грамматика использует эти терминальные символы, но не определяет их. Они всегда являются листовыми узлами (в нижнем кустистом конце) дерева разбора.
Термины с заглавной буквы, такие как Sums, являются нетерминальными символами . Это названия концепций или шаблонов в языке. Они определены в грамматике и никогда не встречаются сами по себе во входном потоке. Они всегда являются внутренними узлами (выше дна) дерева разбора. Они возникают только в результате применения парсером некоторого правила грамматики. Некоторые нетерминальные символы определяются двумя или более правилами; это альтернативные шаблоны. Правила могут ссылаться на себя, что называется рекурсивными . Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики для полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.
Любой заданный компьютерный язык может быть описан несколькими различными грамматиками. Анализатор LR(1) может обрабатывать многие, но не все распространенные грамматики. Обычно можно вручную изменить грамматику так, чтобы она соответствовала ограничениям анализа LR(1) и инструмента-генератора.
Грамматика для LR-анализатора должна быть однозначной сама по себе или должна быть дополнена правилами приоритета разрешения конфликтов. Это означает, что существует только один правильный способ применения грамматики к данному законному примеру языка, что приводит к уникальному дереву анализа с одним значением и уникальной последовательности действий сдвига/сокращения для этого примера. LR-анализ не является полезным методом для человеческих языков с неоднозначными грамматиками, которые зависят от взаимодействия слов. Человеческие языки лучше обрабатываются такими анализаторами, как обобщенный LR-анализатор , анализатор Эрли или алгоритм CYK , которые могут одновременно вычислять все возможные деревья анализа за один проход.
Большинство парсеров LR управляются таблицами. Программный код парсера представляет собой простой общий цикл, который одинаков для всех грамматик и языков. Знание грамматики и ее синтаксические импликации закодированы в неизменных таблицах данных, называемых таблицами синтаксического анализа (или таблицами синтаксического анализа ). Записи в таблице показывают, следует ли выполнить сдвиг или сокращение (и по какому правилу грамматики) для каждой допустимой комбинации состояния парсера и опережающего символа. Таблицы синтаксического анализа также сообщают, как вычислить следующее состояние, учитывая только текущее состояние и следующий символ.
Таблицы синтаксического анализа намного больше грамматики. Таблицы LR трудно точно вычислить вручную для больших грамматик. Поэтому они механически выводятся из грамматики каким-то генератором синтаксических анализаторов, например Bison . [6]
В зависимости от того, как генерируются состояния и таблица синтаксического анализа, результирующий синтаксический анализатор называется либо синтаксическим анализатором SLR (simple LR) , либо синтаксическим анализатором LALR (look-ahead LR) , либо каноническим синтаксическим анализатором LR . Синтаксические анализаторы LALR обрабатывают больше грамматик, чем синтаксические анализаторы SLR. Канонические синтаксические анализаторы LR обрабатывают даже больше грамматик, но используют гораздо больше состояний и гораздо большие таблицы. Пример грамматики — SLR.
Таблицы анализа LR двумерны. Каждое текущее состояние анализатора LR(0) имеет свою собственную строку. Каждый возможный следующий символ имеет свой собственный столбец. Некоторые комбинации состояния и следующего символа невозможны для допустимых входных потоков. Эти пустые ячейки вызывают сообщения об ошибках синтаксиса.
Действие левой половины таблицы имеет столбцы для конечных символов просмотра вперед. Эти ячейки определяют, будет ли следующее действие парсера сдвигом (в состояние n ) или сокращением (по правилу грамматики r n ).
Правая половина таблицы Goto содержит столбцы для нетерминальных символов. Эти ячейки показывают, в какое состояние следует перейти после того, как левая сторона некоторого сокращения создала ожидаемый новый экземпляр этого символа. Это похоже на действие сдвига, но для нетерминалов; предварительный терминальный символ не изменяется.
Столбец таблицы «Текущие правила» документирует значение и синтаксические возможности для каждого состояния, разработанные генератором парсера. Он не включен в фактические таблицы, используемые во время парсинга. Маркер • (розовая точка) показывает, где сейчас находится парсер, в пределах некоторых частично распознанных правил грамматики. То, что слева от •, было проанализировано, а то, что справа, ожидается в ближайшее время. Состояние имеет несколько таких текущих правил, если парсер еще не сузил возможности до одного правила.
В состоянии 2 выше синтаксический анализатор только что нашел и вставил знак + правила грамматики
Следующая ожидаемая фраза — Products. Products начинается с терминальных символов int или id . Если предварительный просмотр — один из них, синтаксический анализатор сдвигает их и переходит в состояние 8 или 9 соответственно. Когда Products найден, синтаксический анализатор переходит в состояние 3, чтобы собрать полный список слагаемых и найти конец правила r0. Products также может начинаться с нетерминального Value. Для любого другого предварительных или нетерминальных символов синтаксический анализатор сообщает об ошибке синтаксиса.
В состоянии 3 анализатор только что нашел фразу Products, которая может быть одним из двух возможных правил грамматики:
Выбор между r1 и r3 не может быть решен просто путем просмотра предыдущих фраз. Анализатор должен проверить символ просмотра вперед, чтобы узнать, что делать. Если просмотр вперед — * , он находится в правиле 3, поэтому анализатор переходит в * и переходит в состояние 5. Если просмотр вперед — eof , он находится в конце правила 1 и правила 0, поэтому анализатор завершает работу.
В состоянии 9 выше все непустые, не ошибочные ячейки предназначены для одного и того же сокращения r6. Некоторые парсеры экономят время и место в таблице, не проверяя символ опережающего просмотра в этих простых случаях. Синтаксические ошибки затем обнаруживаются несколько позже, после некоторых безвредных сокращений, но все еще до следующего действия сдвига или решения парсера.
Отдельные ячейки таблицы не должны содержать несколько альтернативных действий, в противном случае синтаксический анализатор будет недетерминированным с догадками и возвратами. Если грамматика не LR(1), некоторые ячейки будут иметь конфликты сдвиг/свертка между возможным действием сдвига и действием свертки или конфликты свертка/свертка между несколькими правилами грамматики. Анализаторы LR(k) разрешают эти конфликты (где это возможно) путем проверки дополнительных опережающих символов после первого.
Анализатор LR начинает с почти пустого стека анализа, содержащего только начальное состояние 0, и с опережающим просмотром, содержащим первый сканированный символ входного потока. Затем анализатор повторяет следующий шаг цикла, пока не завершится или не застрянет на синтаксической ошибке:
Верхнее состояние в стеке анализа — это некоторое состояние s , а текущий просмотр вперед — это некоторый терминальный символ t . Найдите следующее действие анализатора из строки s и столбца t таблицы действий просмотра вперед. Это действие — Shift, Reduce, Accept или Error:
Стек парсера LR обычно хранит только состояния автомата LR(0), поскольку символы грамматики могут быть получены из них (в автомате все входные переходы в некоторое состояние отмечены одним и тем же символом, который является символом, связанным с этим состоянием). Более того, эти символы почти никогда не нужны, поскольку состояние — это все, что имеет значение при принятии решения о синтаксическом анализе. [7]
Большинству пользователей генераторов парсеров LR этот раздел статьи можно пропустить.
Состояние 2 в примере таблицы разбора относится к частично проанализированному правилу.
Это показывает, как парсер попал сюда, увидев Sums, а затем + , пока искал большее Sums. Маркер • продвинулся дальше начала правила. Это также показывает, как парсер ожидает в конечном итоге завершить правило, найдя затем полное Products. Но необходимы дополнительные сведения о том, как разобрать все части этого Products.
Частично проанализированные правила для состояния называются его "элементами ядра LR(0)". Генератор синтаксического анализатора добавляет дополнительные правила или элементы для всех возможных следующих шагов в построении ожидаемых продуктов:
Маркер • находится в начале каждого из этих добавленных правил; анализатор еще не подтвердил и не проанализировал ни одну из их частей. Эти дополнительные элементы называются «замыканием» основных элементов. Для каждого нетерминального символа, следующего сразу за • , генератор добавляет правила, определяющие этот символ. Это добавляет больше маркеров • и, возможно, другие символы последователей. Этот процесс замыкания продолжается до тех пор, пока все символы последователей не будут расширены. Нетерминалы последователей для состояния 2 начинаются с Products. Затем значение добавляется замыканием. Терминалы последователей — int и id .
Элементы ядра и замыкания вместе показывают все возможные законные способы перехода от текущего состояния к будущим состояниям и полным фразам. Если символ последователя появляется только в одном элементе, он ведет к следующему состоянию, содержащему только один основной элемент с маркером • advanced. Таким образом, int ведет к следующему состоянию 8 с основным
Если один и тот же символ последователя появляется в нескольких элементах, анализатор пока не может сказать, какое правило применяется здесь. Поэтому этот символ ведет к следующему состоянию, которое показывает все оставшиеся возможности, снова с маркером • advanced. Products появляется как в r1, так и в r3. Поэтому Products ведет к следующему состоянию 3 с ядром
На словах это означает, что если парсер увидел один продукт, он может быть выполнен, или у него может быть еще больше вещей для умножения. Все основные элементы имеют один и тот же символ перед маркером • ; все переходы в это состояние всегда имеют один и тот же символ.
Некоторые переходы будут к ядрам и состояниям, которые уже были перечислены. Другие переходы ведут к новым состояниям. Генератор начинает с целевого правила грамматики. Оттуда он продолжает исследовать известные состояния и переходы, пока не будут найдены все необходимые состояния.
Эти состояния называются состояниями "LR(0)", поскольку они используют предварительный просмотр k = 0, т. е. без предварительных просмотров. Единственная проверка входных символов происходит, когда символ сдвигается. Проверка предварительных просмотров для сокращений выполняется отдельно таблицей синтаксического анализа, а не самими перечисленными состояниями.
Таблица разбора описывает все возможные состояния LR(0) и их переходы. Они образуют конечный автомат (FSM). FSM — это простой механизм для разбора простых невложенных языков без использования стека. В этом приложении LR модифицированный «входной язык» FSM имеет как терминальные, так и нетерминальные символы и охватывает любой частично проанализированный снимок стека полного разбора LR.
Вспомним шаг 5 из примера шагов анализа:
Стек разбора показывает ряд переходов состояний, от начального состояния 0, до состояния 4 и затем до 5 и текущего состояния 8. Символы в стеке разбора являются символами сдвига или перехода для этих переходов. Другой способ увидеть это заключается в том, что конечный автомат может сканировать поток "Products * int + 1" (без использования еще одного стека) и находить самую левую полную фразу, которая должна быть сокращена следующей. И это действительно его работа!
Как может простой FSM сделать это, когда исходный неразобранный язык имеет вложенность и рекурсию и определенно требует анализатора со стеком? Хитрость в том, что все слева от вершины стека уже полностью сокращено. Это устраняет все циклы и вложенность из этих фраз. FSM может игнорировать все старые начала фраз и отслеживать только самые новые фразы, которые могут быть завершены следующими. Неясное название для этого в теории LR — «жизнеспособный префикс».
Состояния и переходы предоставляют всю необходимую информацию для действий сдвига и действий goto таблицы разбора. Генератору также необходимо вычислить ожидаемые наборы lookahead для каждого действия reduce.
В парсерах SLR эти наборы предпросмотра определяются непосредственно из грамматики, без учета отдельных состояний и переходов. Для каждого нетерминального S генератор SLR вычисляет Follows(S), набор всех терминальных символов, которые могут следовать непосредственно за некоторым вхождением S. В таблице разбора каждое сведение к S использует Follow(S) в качестве своего набора предпросмотра LR(1). Такие наборы следования также используются генераторами для парсеров LL сверху вниз. Грамматика, в которой нет конфликтов сдвиг/свертка или свертка/свертка при использовании наборов следования, называется грамматикой 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 Left corner используют методы 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) для этой грамматики выглядят следующим образом:
Таблица действий индексируется по состоянию парсера и терминала (включая специальный терминал $, который указывает на конец входного потока) и содержит три типа действий:
Таблица goto индексируется по состоянию парсера и нетерминалу и просто указывает, каким будет следующее состояние парсера, если он распознал определенный нетерминал. Эта таблица важна для поиска следующего состояния после каждой редукции. После редукции следующее состояние находится путем поиска записи таблицы goto для вершины стека (т. е. текущего состояния) и LHS сокращенного правила (т. е. нетерминала).
Таблица ниже иллюстрирует каждый шаг процесса. Здесь состояние относится к элементу наверху стека (самый правый элемент), а следующее действие определяется путем ссылки на таблицу действий выше. $ добавляется к входной строке для обозначения конца потока.
Анализатор начинает работу со стека, содержащего только начальное состояние («0»):
Первый символ из входной строки, который видит анализатор, — это «1». Чтобы найти следующее действие (сдвиг, уменьшение, принятие или ошибка), таблица действий индексируется текущим состоянием («текущее состояние» — это просто то, что находится наверху стека), которое в данном случае равно 0, и текущим входным символом, который равен «1». Таблица действий определяет сдвиг в состояние 2, и поэтому состояние 2 помещается в стек (опять же, вся информация о состоянии находится в стеке, поэтому «сдвиг в состояние 2» — это то же самое, что и помещение 2 в стек). Результирующий стек — это
где вершина стека — 2. Для пояснения показан символ (например, «1», B), вызвавший переход в следующее состояние, хотя, строго говоря, он не является частью стека.
В состоянии 2 таблица действий говорит о необходимости сокращения с помощью правила грамматики 5 (независимо от того, какой терминал видит анализатор во входном потоке), что означает, что анализатор только что распознал правую часть правила 5. В этом случае анализатор записывает 5 в выходной поток, извлекает одно состояние из стека (поскольку правая часть правила содержит один символ) и помещает в стек состояние из ячейки в таблице перехода для состояний 0 и B, т. е. состояние 4. Результирующий стек выглядит следующим образом:
Однако в состоянии 4 таблица действий говорит, что анализатор теперь должен выполнить сокращение с помощью правила 3. Поэтому он записывает 3 в выходной поток, извлекает одно состояние из стека и находит новое состояние в таблице goto для состояния 0 и E, которое является состоянием 3. Результирующий стек:
Следующий терминал, который видит анализатор, — это «+», и согласно таблице действий он должен перейти в состояние 6:
Полученный стек можно интерпретировать как историю конечного автомата , который только что прочитал нетерминал E, за которым следует терминал '+'. Таблица переходов этого автомата определяется действиями сдвига в таблице действий и действиями перехода в таблице перехода.
Следующий терминал теперь равен «1», и это означает, что анализатор выполняет сдвиг и переходит в состояние 2:
Как и предыдущая «1», эта сокращается до B, давая следующий стек:
Стек соответствует списку состояний конечного автомата, который прочитал нетерминал E, за которым следует «+», а затем нетерминал B. В состоянии 8 синтаксический анализатор всегда выполняет сокращение с помощью правила 2. Верхние 3 состояния в стеке соответствуют 3 символам в правой части правила 2. На этот раз мы извлекаем 3 элемента из стека (так как в правой части правила 3 символа) и ищем состояние goto для 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 вышеприведенной процедуры производит действия reduce, и поэтому все действия reduce должны занимать всю строку таблицы, в результате чего сокращение происходит независимо от следующего символа во входном потоке. Вот почему это таблицы разбора LR(0): они не выполняют никаких предварительных просмотров (то есть смотрят вперед на ноль символов) перед тем, как решить, какое сокращение выполнять. Грамматике, которой требуется предварительный просмотр для устранения неоднозначности сокращений, потребуется строка таблицы разбора, содержащая различные действия reduce в разных столбцах, и вышеприведенная процедура не способна создавать такие строки.
Усовершенствования процедуры построения таблиц LR (0) (такие как SLR и LALR ) способны строить действия сокращения, которые не занимают целые строки. Поэтому они способны анализировать больше грамматик, чем парсеры LR(0).
Автомат построен таким образом, что он гарантированно является детерминированным. Однако, когда действия reduce добавляются в таблицу действий, может случиться, что одна и та же ячейка будет заполнена действием reduce и действием shift ( конфликт shift-reduce ) или двумя разными действиями reduce ( конфликт reduce-reduce ). Однако можно показать, что когда это происходит, грамматика не является грамматикой LR(0). Классическим примером конфликта shift-reduce из реального мира является проблема зависания else .
Небольшой пример не-LR(0) грамматики с конфликтом сдвига-свертки:
Один из найденных наборов предметов:
В этом наборе элементов возникает конфликт сдвига-свертки: при построении таблицы действий в соответствии с приведенными выше правилами ячейка для [набор элементов 1, терминал '1'] содержит s1 (сдвиг в состояние 1) и r2 (свертка с правилом грамматики 2).
Небольшой пример не-LR(0) грамматики с конфликтом «сведение-сведение»:
В этом случае получается следующий набор элементов:
В этом наборе элементов возникает конфликт «уменьшение-уменьшение», поскольку в ячейках таблицы действий для этого набора элементов будут как действия «уменьшение» для правила 3, так и действия «уменьшение» для правила 4.
Оба приведенных выше примера можно решить, позволив парсеру использовать следующий набор (см. LL-парсер ) нетерминала A , чтобы решить, будет ли он использовать одно из правил A для редукции; он будет использовать правило A → w для редукции только в том случае, если следующий символ во входном потоке находится в следующем наборе A. Это решение приводит к так называемым простым LR-парсерам .
