Войти
A синтаксический анализатор сдвиг-уменьшение - это класс эффективного, управляемого таблицей восходящего синтаксического анализа методы для компьютерных языков и других обозначений, формально определенных грамматикой. Методы синтаксического анализа, наиболее часто используемые для синтаксического анализа языков программирования, LR-синтаксического анализа и его разновидностей, представляют собой методы сокращения сдвига. Парсеры приоритета , использовавшиеся до изобретения анализа LR, также являются методами уменьшения сдвига. Все синтаксические анализаторы с уменьшением сдвига имеют аналогичные внешние эффекты в порядке возрастания, в котором они строят дерево синтаксического анализа или вызывают определенные выходные действия.
Анализатор shift-reduce сканирует и анализирует введенный текст за один проход по тексту вперед без резервного копирования. (Это прямое направление обычно слева направо внутри строки и сверху вниз для многострочных входных данных.) Анализатор создает дерево синтаксического анализа постепенно, снизу вверх и слева направо., без угадывания или возврата. На каждом этапе этого прохода синтаксический анализатор накапливает список поддеревьев или фраз входного текста, которые уже были проанализированы. Эти поддеревья еще не объединены, потому что синтаксический анализатор еще не достиг правого конца синтаксического шаблона, который их объединит.
Сдвиг-уменьшение дерева синтаксического анализа, построенное снизу вверх в пронумерованных шагах. Рассмотрим строку A = B + C * 2.
На шаге 7 в примере только «A = B +» имеет был проанализирован. Существует только затененный нижний левый угол дерева синтаксического анализа. Ни один из узлов дерева синтаксического анализа с номерами 8 и выше еще не существует. Узлы 1, 2, 6 и 7 являются корнями изолированных поддеревьев, охватывающих все элементы 1..7. Узел 1 - это переменная A, узел 2 - это разделитель =, узел 6 - это слагаемое B, а узел 7 - это оператор +. Эти четыре корневых узла временно хранятся в стеке синтаксического анализа. Оставшаяся неанализируемая часть входного потока - «C * 2».
Анализатор сдвига-уменьшения работает, выполняя некоторую комбинацию шагов сдвига и уменьшения, отсюда и название.
Анализатор продолжает эти шаги до тех пор, пока все входные данные не будут использованы и все деревья синтаксического анализа не будут сведены к одному дереву, представляющему все допустимые входные данные.
На каждом этапе синтаксического анализа весь входной текст делится на стек синтаксического анализа, текущий предварительный символ и оставшийся неотсканированный текст. Следующее действие синтаксического анализатора определяется крайним правым символом (ами) стека и опережающим символом. Действие считывается из таблицы, содержащей все синтаксически допустимые комбинации символов стека и опережающего просмотра.
| Шаг | Разбор стека | Взгляд. Впереди | Несканированный | Действие анализатора |
|---|---|---|---|---|
| 0 | пусто | id | = B + C * 2 | Shift |
| 1 | id | = | B + C * 2 | Shift |
| 2 | id = | id | + C * 2 | Shift |
| 3 | id = id | + | C * 2 | Уменьшить на значение ← id |
| 4 | id = Значение | + | C * 2 | Уменьшить на продукты ← Значение |
| 5 | id = Продукты | + | C * 2 | Уменьшить на суммы ← Продукты |
| 6 | id = Суммы | + | C * 2 | Shift |
| 7 | id = Sums + | id | *2 | Shift |
| 8 | id = Sums + id | * | 2 | Уменьшить на значение ← id |
| 9 | id = Sums + Value | * | 2 | Уменьшить на продукты ← Value |
| 10 | id = Sums + Products | * | 2 | Shift |
| 11 | id = Sums + Products * | int | eof | Shift |
| 12 | id = Sums + Products * int | eof | Уменьшить на значение ← int | |
| 13 | id = Sums + Products * Value | eof | Уменьшить по продуктам ← Продукты * Значение | |
| 14 | id = Суммы + Продукты | eof | Уменьшить на суммы ← Суммы + Продукты | |
| 15 | id = Суммы | eof | Уменьшить назначением ← id = Sums | |
| 16 | Assign | eof | Готово |
См. Более простой пример.
Грамматика - это набор шаблонов или правил синтаксиса для языка ввода. Он не охватывает все языковые правила, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Синтаксические анализаторы с уменьшенным смещением используют контекстно-свободную грамматику, которая имеет дело только с локальными шаблонами символов.
Пример грамматики как крошечного подмножества языка Java или C, способного сопоставить A = B + C * 2, может быть:
Терминальные символы грамматики - это многосимвольные символы или «токены», обнаруженные во входном потоке с помощью лексического сканера. Здесь они включают =+*и int для любой целочисленной константы и id для любого имени идентификатора. Грамматика не заботится о значениях int или написании id, а также о пробелах или переносах строк. Грамматика использует эти терминальные символы, но не определяет их. Они всегда находятся в нижнем густом конце дерева синтаксического анализа.
Термины, написанные с заглавной буквы, например суммы, являются нетерминальными символами. Это названия концепций или шаблонов в языке. Они определены в грамматике и никогда не встречаются во входном потоке. Они всегда находятся над нижней частью дерева синтаксического анализа. Они происходят только в результате применения парсером некоторого грамматического правила. Некоторые нетерминалы определяются двумя или более правилами; это альтернативные модели. Правила могут относиться к себе. Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики для полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.
Любой компьютерный язык можно описать несколькими разными грамматиками. Грамматика для синтаксического анализатора с уменьшением сдвига должна быть однозначной сама по себе или быть дополнена правилами приоритета, разрывающими связи. Это означает, что существует только один правильный способ применения грамматики к данному легальному примеру языка, что приводит к уникальному дереву синтаксического анализа и уникальной последовательности действий сдвига / уменьшения для этого примера.
Управляемый таблицами синтаксический анализатор имеет все свои знания о грамматике, закодированной в неизменяемые данные, называемые таблицами синтаксического анализатора. Программный код парсера представляет собой простой универсальный цикл, который без изменений применяется ко многим грамматикам и языкам. Таблицы могут быть составлены вручную для методов приоритета. Для методов LR сложные таблицы механически выводятся из грамматики с помощью некоторого инструмента генератора синтаксического анализатора, такого как Bison. Таблицы парсера обычно намного больше грамматики. В других синтаксических анализаторах, которые не управляются таблицами, таких как рекурсивный спуск, каждая языковая конструкция анализируется другой подпрограммой, специализированной для синтаксиса этой конструкции.
Эффективность синтаксического анализатора «сдвиг-уменьшение» заключается в отсутствии резервного копирования или отслеживания. Его общее время линейно увеличивается в зависимости от длины ввода и размера всего дерева синтаксического анализа. Другие методы синтаксического анализатора, которые выполняют обратный поиск, могут занять экспоненциальное время, когда они плохо угадывают.
Чтобы избежать угадывания, синтаксический анализатор сдвига-уменьшения часто смотрит вперед (вправо) на следующий отсканированный символ, прежде чем решить, что делать с ранее отсканированными символами. Лексический сканер работает на один символ впереди остальной части синтаксического анализатора. Символ опережающего просмотра - это «правый контекст» для каждого решения синтаксического анализа. (Редко можно использовать два или более символа опережающего просмотра, хотя в большинстве практических грамматик можно использовать один символ опережающего просмотра.)
Синтаксический анализатор с уменьшением сдвига ожидает, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем совершая то, что представляет собой комбинированная конструкция. Затем синтаксический анализатор немедленно воздействует на комбинацию, а не ждет дальнейшего. В приведенном выше примере дерева синтаксического анализа фраза B сокращается до значения, а затем до продуктов и сумм на шагах 3-6, как только будет виден lookahead +, вместо того, чтобы ждать чего-либо позже, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать B, основаны только на том, что синтаксический анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.
Сокращения реорганизовывают самые недавно проанализированные объекты, непосредственно слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как stack. Стек синтаксического анализа увеличивается вправо. Основание или нижняя часть стека находится слева и содержит самый левый, самый старый фрагмент синтаксического анализа. Каждый шаг редукции действует только на самые правые, самые новые фрагменты синтаксического анализа. (Этот накопительный стек синтаксического анализа очень отличается от прогнозирующего, увеличивающегося влево стека синтаксического анализа, используемого нисходящими синтаксическими анализаторами.)
Когда такое правило грамматики, как
, вершина стека содержит деревья синтаксического анализа "... Products * Value". Этот найденный экземпляр правой части правила называется дескриптором . Шаг уменьшения заменяет маркер «Products * Value» на левый нетерминал, в данном случае - на более крупный Products. Если синтаксический анализатор строит полные деревья синтаксического анализа, три дерева для внутренних продуктов, * и Value объединяются в новый корень дерева для продуктов. В противном случае детали семантики из внутренних продуктов и значения выводятся на более поздний этап компилятора или объединяются и сохраняются в новом символе продуктов.
Анализатор продолжает применять сокращения к началу стек синтаксического анализа до тех пор, пока он продолжает находить там недавно завершенные примеры правил грамматики. Когда больше нельзя применить правила, синтаксический анализатор перемещает опережающий символ в стек синтаксического анализа, сканирует новый опережающий символ и пытается снова.
Таблицы синтаксического анализатора показывают, что делать дальше, для каждой допустимой комбинации символов самого верхнего стека синтаксического анализа и символа предварительного просмотра. Это следующее действие должно быть уникальным; либо сдвинуть, либо уменьшить, но не то и другое одновременно. (Это подразумевает некоторые дополнительные ограничения на грамматику, помимо однозначности.) Детали таблицы сильно различаются между различными типами синтаксических анализаторов сдвига и уменьшения.
В синтаксических анализаторах с приоритетом правый конец дескрипторов обнаруживается путем сравнения уровня приоритета или грамматической плотности символов верхнего стека с таковым для символа предварительного просмотра. В приведенном выше примере int и id относятся к уровням внутренней грамматики по сравнению с разделителем операторов ; . Таким образом, int и id считаются более приоритетными, чем ;, и их следует сокращать до чего-то другого, когда за ними следует ; . Существуют различные разновидности парсеров приоритета, каждый из которых имеет разные способы нахождения левого конца дескриптора и выбора правильного правила для применения:
Анализаторы приоритета ограничены в грамматиках, которые они могут обрабатывать. При принятии решений они игнорируют большую часть стека синтаксического анализа. Они рассматривают только названия самых верхних символов, а не полный контекст того, где в грамматике эти символы сейчас появляются. Приоритет требует, чтобы похожие на вид комбинации символов анализировались и использовались одинаковыми способами во всей грамматике, однако эти комбинации случаются независимо от контекста.
LRсинтаксические анализаторы - это более гибкая форма синтаксического анализа сдвиг-сокращение, обрабатывающая намного больше грамматик.
синтаксические анализаторы LR работают как конечный автомат, выполняя переход состояния для каждого сдвига или уменьшения действия. Они используют стек, в котором текущее состояние сдвигается (опускается) действиями сдвига. Затем этот стек всплывает (поднимается) с помощью действий сокращения. Этот механизм позволяет парсеру LR обрабатывать все детерминированные контекстно-свободные грамматики, надмножество грамматик приоритета. Парсер LR полностью реализован с помощью Canonical LR parser. Парсеры Look-Ahead LR и Simple LR реализуют его упрощенные варианты, значительно снижающие требования к памяти. Недавние исследования выявили методы, с помощью которых можно реализовать канонические анализаторы LR с резко сниженными требованиями к таблицам по сравнению с алгоритмом построения таблиц Кнута.
Будь то LR, LALR или SLR, основной конечный автомат остается одним и тем же; только таблицы разные, и эти таблицы почти всегда генерируются механически. Кроме того, эти таблицы обычно реализованы так, что REDUCE приводит к CALL закрытой подпрограмме, которая является внешней по отношению к конечному автомату и которая выполняет функцию, которая подразумевается семантикой правила грамматики, которое REDUCEd. Следовательно, синтаксический анализатор разделяется на инвариантную часть конечного автомата и часть вариантной семантики. Это фундаментальное отличие поощряет разработку высококачественных синтаксических анализаторов, которые отличаются исключительной надежностью.
Для заданного состояния стека и опережающего символа существует четыре возможных действия: ERROR, SHIFT, REDUCE и STOP (далее именуемые конфигурациями). Наличие точки • в конфигурации представляет текущую позицию просмотра вперед, при этом символ просмотра вперед отображается справа от точки (и всегда соответствует терминальному символу), а текущее состояние стека - слева от точки. (и который обычно соответствует нетерминальному символу).
По практическим причинам, включая более высокую производительность, таблицы обычно расширяются довольно большим вспомогательным массивом двухбитовых символов, очевидно сжатых до четырех двухбитовых символов, байта, для эффективного доступа к байтам ориентированные машины, часто кодируются как:
(STOP является частным случаем SHIFT). Весь массив обычно включает в себя в основном конфигурации ERROR, определенное грамматикой количество конфигураций SHIFT и REDUCE и одну конфигурацию STOP.
В системах программирования, которые поддерживают спецификацию значений в четвертичной системе счисления (основание 4, два бита на четвертичную цифру), таких как XPL, они кодируются, например:
Таблицы SHIFT и REDUCE реализованы отдельно от массива. Вспомогательный массив «исследуется» только на предмет текущего состояния и опережающего символа. (Вспомогательный) массив является «полным», тогда как таблицы (сдвига и сокращения) могут быть действительно очень «разреженными», и значительная эффективность может быть достигнута за счет оптимальной «декомпозиции» этих таблиц SHIFT и REDUCE (ERROR и STOP не требуют таблиц.).
Конфигурации SHIFT и REDUCE очевидны из базового определения синтаксического анализатора SHIFT-REDUCE.
STOP, таким образом, представляет конфигурацию, в которой состояние наверху стека и конечный символ упреждающего просмотра находятся в рамках предметной грамматики, и представляет собой окончание программы:
невозможно ПЕРЕМЕСТИТЬ дальше заключительный ⊥ для достижения концептуально
ОШИБКИ, таким образом, представляет конфигурацию, в которой состояние на вершине стека, а конечный символ упреждающего просмотра не находится в рамках предметной грамматики. Это дает возможность вызвать процедуру исправления ошибок, возможно, в ее наиболее упрощенной форме, чтобы отбросить упреждающий терминальный символ и прочитать следующий терминальный символ, но возможны многие другие запрограммированные действия, в том числе обрезка стека или отказ от опережающего просмотра. символ терминала и сокращение стека (и в патологическом случае обычно можно получить
, где
В большинстве случаев стек преднамеренно предварительно загружается, то есть инициализируется с помощью
, при этом предполагается, что начальный ⊥ уже распознан. Таким образом, это представляет собой начало программы и, таким образом, позволяет избежать отдельной конфигурации START, которая концептуально
⊥является специальным псевдотерминальным символом, механически добавленным к грамматике, так же как
Ясно, что такой синтаксический анализатор имеет ровно одну (неявную) конфигурацию START и одну (явную) конфигурацию STOP, но он может и обычно имеет сотни конфигураций SHIFT и REDUCE и, возможно, тысячи конфигураций ERROR.
