Парсер Shift-уменьшить - Shift-reduce parser

А парсер сдвиг-уменьшение класс эффективных, управляемых таблицей восходящий анализ методы для компьютерных языков и других обозначений, формально определенных грамматика. Методы синтаксического анализа, наиболее часто используемые для синтаксического анализа языки программирования, LR разбор и его варианты являются методами уменьшения сдвига.^[1] В парсеры приоритета До изобретения LR-синтаксического анализа использовались также методы уменьшения сдвига. Все синтаксические анализаторы с уменьшенным сдвигом имеют аналогичные внешние эффекты в порядке возрастания, в котором они строят дерево синтаксического анализа или вызывают определенные выходные действия.

Обзор

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

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

Рассмотрим строку А = В + С * 2.

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

Синтаксический анализатор сдвиг-уменьшение работает, выполняя некоторую комбинацию шагов сдвига и уменьшения, отсюда и название.

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

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

Шаги построения дерева

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

Шаг	Разбор стека	Смотреть Предстоящий	Непроверенный	Действие парсера
0	пустой	я бы	= В + С * 2	Сдвиг
1	я бы	=	В + С * 2	Сдвиг
2	я бы =	я бы	+ C * 2	Сдвиг
3	я бы = я бы	+	С * 2	Уменьшить на значение ← я бы
4	я бы = Значение	+	С * 2	Уменьшить по продуктам ← Ценность
5	я бы = Продукты	+	С * 2	Сократить на суммы ← Товары
6	я бы = Суммы	+	С * 2	Сдвиг
7	я бы = Суммы +	я бы	*2	Сдвиг
8	я бы = Суммы + я бы	*	2	Уменьшить на значение ← я бы
9	я бы = Суммы + Значение	*	2	Уменьшить по продуктам ← Ценность
10	я бы = Суммы + Продукты	*	2	Сдвиг
11	я бы = Суммы + Продукты *	int	eof	Сдвиг
12	я бы = Суммы + Продукты * int	eof		Уменьшить на значение ← int
13	я бы = Суммы + Продукты * Стоимость	eof		Уменьшить по продуктам ← Продукты * Стоимость
14	я бы = Суммы + Продукты	eof		Сократить на суммы ← Суммы + произведения
15	я бы = Суммы	eof		Уменьшить назначением ← я бы = Суммы
16	Назначать	eof		Выполнено

Видеть ^[2] для более простого примера.

Грамматики

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

Пример грамматики как крошечного подмножества языка Java или C, способного сопоставить А = В + С * 2 возможно:

Назначить ← я бы = Суммы

Суммы ← Суммы + произведения

Суммы ← Продукция

Продукция ← Продукция * Стоимость

Продукция ← Стоимость

Значение ← int

Значение ← я бы

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

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

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

Управляемый таблицами синтаксический анализатор обладает всеми знаниями о грамматике, закодированной в неизменяемые данные, называемые таблицами синтаксического анализатора. Программный код парсера представляет собой простой универсальный цикл, который без изменений применяется ко многим грамматикам и языкам. Таблицы могут быть составлены вручную для методов приоритета. Для методов LR сложные таблицы механически выводятся из грамматики некоторыми генератор парсеров инструмент как Бизон.^[3] Таблицы парсера обычно намного больше грамматики. В других парсерах, не управляемых таблицами, например рекурсивный спуск, каждая языковая конструкция анализируется отдельной подпрограммой, специализированной для синтаксиса этой конструкции.

Действия парсера

Эффективность синтаксического анализатора сдвиг-уменьшение заключается в отсутствии резервного копирования и отслеживания. Его общее время линейно увеличивается в зависимости от длины ввода и размера всего дерева синтаксического анализа. Другие методы синтаксического анализатора, выполняющие возврат, могут занять экспоненциальное время, если они ошибаются.^{[нужна цитата ]}

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

Синтаксический анализатор сдвиг-уменьшение ожидает, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем зафиксировать, что представляет собой объединенная конструкция. Затем синтаксический анализатор немедленно воздействует на комбинацию, а не ждет дальнейшего. В приведенном выше примере дерева синтаксического анализа фраза B сокращается до значения, а затем до продуктов и сумм на шагах 3–6, как только виден lookahead +, вместо того, чтобы ждать чего-либо позже, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать B, основаны только на том, что синтаксический анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.

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

Когда такое грамматическое правило

Продукция ← Продукция * Стоимость

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

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

Типы парсеров Shift-Reduce

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

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

• Парсер приоритета операторов, очень простой численный метод, который работает с выражениями, но не с общим синтаксисом программы.
• Простой парсер приоритета, использует одну большую таблицу MxN для поиска правого и левого концов. Используется в PL360.^[5] Не поддерживает распространенные языки программирования.
• Слабый парсер приоритета, использует таблицу приоритетов только для поиска правых концов дескрипторов. Обрабатывает больше грамматик, чем простой приоритет.^[6]
• Парсер с расширенным приоритетом.

• Парсер смешанной стратегии, используемый в исходной версии XPL. Расширяет «двойные», присущие любому распознавателю приоритета, для включения «троек». Менее мощный, чем SLR. Обычно имеет очень большие таблицы даже для относительно небольших языков, таких как сам XPL, из-за большого количества «троек», которые требуются для распознавания грамматик за пределами, налагаемыми методами приоритета.^[7]

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

LR синтаксические анализаторы - это более гибкая форма синтаксического анализа сдвиг-сокращение, обрабатывающая гораздо больше грамматик.^[8]

Обработка парсера LR

Парсеры LR работают как Государственный аппарат, выполняя переход между состояниями для каждого действия сдвига или уменьшения. Они используют стек, в котором текущее состояние сдвигается (опускается) действиями сдвига. Затем этот стек всплывает (поднимается) с помощью действий сокращения. Этот механизм позволяет парсеру LR обрабатывать все детерминированные контекстно-свободные грамматики, надмножество грамматик приоритета. Парсер LR полностью реализован Канонический парсер LR. В Look-Ahead LR и Простой LR парсеры реализуют его упрощенные варианты, значительно снижающие требования к памяти.^[9][10] Недавние исследования выявили методы, с помощью которых можно реализовать канонические парсеры LR с резко сниженными требованиями к таблицам по сравнению с алгоритмом построения таблиц Кнута.^[11]

Будь то LR, LALR или SLR, основной конечный автомат один и тот же; только таблицы разные, и эти таблицы почти всегда генерируются механически. Кроме того, эти таблицы обычно реализованы так, что REDUCE приводит к CALL закрытой подпрограмме, которая является внешней по отношению к конечному автомату и которая выполняет функцию, которая подразумевается семантикой правила грамматики, которое REDUCEd. Следовательно, синтаксический анализатор разделяется на инвариантную часть конечного автомата и часть вариантной семантики. Это фундаментальное отличие поощряет разработку высококачественных синтаксических анализаторов, которые отличаются исключительной надежностью.

Учитывая конкретное состояние стека и опережающий символ, существует ровно четыре возможных действия: ERROR, SHIFT, REDUCE и STOP (далее называемые конфигурациями). Наличие точки • в конфигурации представляет текущую позицию просмотра вперед, при этом символ просмотра вперед отображается справа от точки (и который всегда соответствует символу терминала), а текущее состояние стека слева от точки (и которое обычно соответствует нетерминальному символу).

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

00b представляет ОШИБКУ

01b представляет собой SHIFT

10b представляет УМЕНЬШЕНИЕ

11b означает СТОП

(STOP - это особый случай SHIFT). Весь массив обычно включает в себя в основном конфигурации ERROR, определенное грамматикой количество конфигураций SHIFT и REDUCE и одну конфигурацию STOP.

В системах программирования, поддерживающих спецификацию значений в четвертичная система счисления (основание 4, два бита на четвертичную цифру), такие как XPL, они кодируются, например:

"(2)…0… "Представляет ОШИБКУ

"(2)…1… "Представляет SHIFT

"(2)…2… "Представляет СОКРАЩЕНИЕ

"(2)…3… "Означает СТОП

Таблицы SHIFT и REDUCE реализованы отдельно от массива. Вспомогательный массив «исследуется» только на предмет текущего состояния и опережающего символа. (Вспомогательный) массив "заполнен", тогда как таблицы (сдвига и уменьшения) могут быть очень действительно "разреженный", и значительная эффективность может быть достигнута за счет оптимальной "декомпозиции" этих таблиц SHIFT и REDUCE (ERROR и STOP не нуждаются в таблицах).

Конфигурации SHIFT и REDUCE очевидны из базового определения синтаксического анализатора SHIFT-REDUCE.

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

⊥ <program> • ⊥

невозможно ПЕРЕМЕСТИТЬ дальше финального ⊥ чтобы достичь концептуально

⊥ <program> ⊥ •

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

⊥ <program> • ⊥

где <программа> состоит только из "пустое заявление" ).

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

⊥ • <program> ⊥

посредством чего первоначальный ⊥ предполагается, что они уже были распознаны. Таким образом, это представляет собой начало программы и, таким образом, позволяет избежать отдельной конфигурации СТАРТ, которая концептуально

• ⊥ <program> ⊥

⊥ - это специальный псевдотерминальный символ, механически добавляемый к грамматике, так же как - это специальный псевдонетерминальный символ, механически добавляемый в грамматику (если программист явно не включил в грамматику, то будет быть автоматически добавленным в грамматику от имени программиста).

Ясно, что такой синтаксический анализатор имеет ровно одну (неявную) конфигурацию START и одну (явную) конфигурацию STOP, но он может и обычно имеет сотни конфигураций SHIFT и REDUCE и, возможно, тысячи конфигураций ERROR.

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

1. Компиляторы: принципы, методы и инструменты (2-е издание), Альфред Ахо, Моника Лам, Рави Сетхи и Джеффри Уллман, Prentice Hall 2006.
2. https://web.archive.org/web/20160305041504/http://dragonbook.stanford.edu/lecture-notes/Stanford-CS143/08-Bottom-Up-Parsing.pdf
3. Flex & Bison: Инструменты обработки текста, Джон Левин, O'Reilly Media 2009.
4. Создание компилятора, Шарль Фишер, Рон Ситрон и Ричард Леблан, Эддисон Уэсли 2009.
5. PL360 - Язык программирования для компьютеров 360, Никлаус Вирт, J. ACM 15: 1 1968.
6. Теория синтаксического анализа, перевода и компиляции, том 1: синтаксический анализ, Альфред Ахо и Джеффри Уллман, Prentice Hall 1972.
7. Генератор компилятора Уильяма М. МакКимана, Дж. Хорнинга и Д. Уортмана, Прентис Холл, 1970; ISBN  978-0131550773.
8. Кнут, Д. Э. (Июль 1965 г.). «О переводе языков слева направо» (PDF). Информация и контроль. 8 (6): 607–639. Дои:10.1016 / S0019-9958 (65) 90426-2. Получено 29 мая 2011.
9. Практические переводчики языков LR (k), Фрэнк Де Ремер, докторская диссертация Массачусетского технологического института, 1969.
10. Простые LR (k) грамматики, Фрэнк Де Ремер, Comm. ACM 14: 7 1971.
11. X. Чен, Измерение и расширение LR (1) синтаксического анализа, Докторская диссертация Гавайского университета, 2009 г.