Синтаксический анализатор сдвига-сокращения — это класс эффективных, управляемых таблицами методов синтаксического анализа снизу вверх для компьютерных языков и других обозначений, формально определенных грамматикой . Методы синтаксического анализа, наиболее часто используемые для анализа языков программирования , LR-анализа и его разновидностей, — это методы с сокращением сдвига. [1] Анализаторы приоритета , использовавшиеся до изобретения LR-анализа, также представляют собой методы сокращения сдвига. Все анализаторы сдвига-сокращения имеют схожие внешние эффекты в том порядке, в котором они строят дерево разбора или вызывают определенные выходные действия.
Синтаксический анализатор со сдвигом-сокращением сканирует и анализирует входной текст за один проход вперед по тексту без резервного копирования. Синтаксический анализатор строит дерево разбора постепенно, снизу вверх и слева направо, без угадывания или возврата. На каждом этапе этого прохода синтаксический анализатор накапливает список поддеревьев или фраз входного текста, которые уже были проанализированы. Эти поддеревья еще не соединены вместе, поскольку синтаксический анализатор еще не достиг правого конца синтаксического шаблона, который их объединит.
Рассмотрим строку A = B + C * 2.
На шаге 7 в примере было проанализировано только «A = B +». Существует только заштрихованный нижний левый угол дерева синтаксического анализа. Ни один из узлов дерева разбора с номером 8 и выше еще не существует. Узлы 1, 2, 6 и 7 являются корнями изолированных поддеревьев, охватывающих все элементы 1..7. Узел 1 — это переменная A, узел 2 — разделитель =, узел 6 — слагаемое B, а узел 7 — оператор +. Эти четыре корневых узла временно хранятся в стеке синтаксического анализа. Оставшаяся неразобранная часть входного потока — это «C * 2».
Анализатор сдвига-сокращения работает, выполняя некоторую комбинацию шагов сдвига и уменьшения, отсюда и название.
Анализатор продолжает выполнять эти шаги до тех пор, пока все входные данные не будут использованы и все деревья синтаксического анализа не будут сведены к одному дереву, представляющему весь допустимый ввод.
На каждом этапе синтаксического анализа весь входной текст делится на стек синтаксического анализа, текущий упреждающий символ и оставшийся несканированный текст. Следующее действие анализатора определяется крайним правым символом стека и символом просмотра вперед. Действие считывается из таблицы, содержащей все синтаксически допустимые комбинации символов стека и символов просмотра вперед.
См. [2] для более простого примера.
Грамматика — это набор шаблонов или правил синтаксиса для языка ввода. Он не охватывает все правила языка, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Синтаксические анализаторы сдвига-сокращения используют контекстно-свободную грамматику , которая работает только с локальными шаблонами символов.
Примером грамматики как небольшого подмножества языка Java или C, способного к сопоставлению, A = B + C*2может быть:
Терминальные символы грамматики — это многосимвольные символы или «токены», найденные во входном потоке лексическим сканером . Здесь они включают = + * и int для любой целочисленной константы и id для любого имени идентификатора. Грамматику не волнует, каковы значения int или написание идентификатора , а также не важны пробелы или разрывы строк. Грамматика использует эти терминальные символы, но не определяет их. Они всегда находятся в самом нижнем густом конце дерева синтаксического анализа.
Термины, написанные с заглавной буквы, такие как суммы, являются нетерминальными символами . Это названия понятий или шаблонов в языке. Они определены в грамматике и никогда не встречаются во входном потоке. Они всегда находятся над нижней частью дерева разбора. Они происходят только в результате применения парсером некоторого грамматического правила. Некоторые нетерминалы определяются двумя или более правилами; это альтернативные модели. Правила могут ссылаться на самих себя. Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.
Любой компьютерный язык может быть описан несколькими различными грамматиками. Грамматика синтаксического анализатора со сдвигом-сокращением сама по себе должна быть однозначной или дополняться правилами приоритета, разрешающими конфликты. Это означает, что существует только один правильный способ применить грамматику к данному легальному примеру языка, что приводит к уникальному дереву синтаксического анализа и уникальной последовательности действий сдвига/сокращения для этого примера.
Анализатор, управляемый таблицами, хранит все свои знания о грамматике, закодированные в неизменные данные, называемые таблицами анализатора. Программный код парсера представляет собой простой общий цикл, который без изменений применяется ко многим грамматикам и языкам. Таблицы могут быть составлены вручную для методов приоритета. Для методов LR сложные таблицы механически извлекаются из грамматики с помощью какого-либо инструмента -генератора синтаксического анализатора, такого как Bison . [3] Таблицы парсера обычно намного больше, чем грамматика. В других синтаксических анализаторах, не управляемых таблицами, таких как рекурсивный спуск , каждая языковая конструкция анализируется отдельной подпрограммой, специализированной на синтаксисе этой конструкции.
Анализатор сдвига-сокращения эффективен, поскольку не требует резервного копирования. Общее время выполнения линейно зависит от длины входных данных и размера полного дерева разбора. Другие методы парсера, которые возвращаются назад, могут занять экспоненциальное время, если они плохо угадывают. [ нужна цитата ]
Чтобы избежать угадывания, синтаксический анализатор сдвига-сокращения часто смотрит вперед (вправо в тексте с письмом слева направо) на следующий отсканированный символ, прежде чем решить, что делать с ранее отсканированными символами. Лексический сканер работает на один символ раньше остального синтаксического анализатора. Символ просмотра вперед также называется «правым контекстом» для каждого решения синтаксического анализа. (Редко можно использовать два или более символов просмотра вперед, хотя большинство практических грамматик могут быть разработаны для использования одного символа просмотра вперед.)
Синтаксический анализатор сдвига-сокращения ждет, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем определить, что представляет собой объединенная конструкция. Затем анализатор немедленно воздействует на комбинацию, не дожидаясь дальнейшего. В приведенном выше примере дерева синтаксического анализа фраза B сводится к значению, а затем к продуктам и суммам на шагах 3–6, как только + появляется в предварительном просмотре, вместо того, чтобы больше ждать, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать B, основаны только на том, что анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.
Сокращение реорганизует самые последние анализируемые элементы, то есть те, которые находятся непосредственно слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как стек . Этот стек синтаксического анализа растет вправо. Основание или низ стека находится слева и содержит самый левый и самый старый фрагмент синтаксического анализа. Каждый шаг сокращения действует только на самые правые, новейшие фрагменты анализа. (Этот накопительный стек синтаксического анализа сильно отличается от прогнозирующего стека синтаксического анализа, растущего влево, используемого нисходящими анализаторами .)
Когда такое грамматическое правило, как
применяется, вершина стека содержит деревья синтаксического анализа «... Продукты * Значение». Этот найденный экземпляр правой части правила называется дескриптором . Шаг уменьшения заменяет дескриптор «Продукты * Значение» на левый нетерминал, в данном случае на более крупный «Продукты». Если анализатор создает полные деревья синтаксического анализа, то три дерева для внутренних продуктов, * и стоимости объединяются в новый корень дерева для более крупных продуктов. В противном случае семантические детали из внутренних продуктов и стоимости выводятся на какой-либо более поздний этап компилятора или объединяются и сохраняются в новом символе продуктов. [4]
Синтаксический анализатор продолжает применять сокращения к вершине стека синтаксического анализа до тех пор, пока находит там вновь завершенные примеры грамматических правил. Когда больше никаких правил применить невозможно, анализатор перемещает упреждающий символ в стек синтаксического анализа, сканирует новый упреждающий символ и повторяет попытку.
Таблицы синтаксического анализатора показывают, что делать дальше для каждой допустимой комбинации символов верхнего уровня стека синтаксического анализа и символа просмотра вперед. Следующее действие должно быть уникальным; либо сдвинуть, либо уменьшить, но не то и другое. (Это подразумевает некоторые дополнительные ограничения на грамматику, помимо однозначности.) Детали таблицы сильно различаются в зависимости от типа анализаторов со сдвигом и сокращением.
В анализаторах приоритета правый конец дескрипторов находится путем сравнения уровня приоритета или грамматической строгости символов верхнего стека с уровнем предпросмотренного символа. В приведенном выше примере int и id принадлежат внутренним уровням грамматики по сравнению с разделителем операторов ; . Таким образом, int и id считаются более приоритетными, чем ; и должен быть сведен к чему-то другому всякий раз, когда за ним следует ; . Существуют различные разновидности анализаторов приоритета, каждый из которых имеет разные способы поиска левого конца дескриптора и выбора правильного правила для применения:
Парсеры приоритета ограничены в грамматиках, которые они могут обрабатывать. Они игнорируют большую часть стека синтаксического анализа при принятии решений. Они учитывают только имена самых верхних символов, а не полный контекст того, где в грамматике эти символы сейчас появляются. Приоритет требует, чтобы похожие комбинации символов анализировались и использовались одинаковым образом во всей грамматике, однако эти комбинации происходят независимо от контекста.
LR- парсеры представляют собой более гибкую форму синтаксического анализа с сокращением сдвига, обрабатывающую гораздо больше грамматик. [8]
Анализаторы LR функционируют как конечный автомат , выполняя переход состояний для каждого действия сдвига или сокращения. Они используют стек, в котором текущее состояние сдвигается (вниз) с помощью действий сдвига. Этот стек впоследствии выдвигается (вверх) с помощью действий сокращения (и одновременно с этим создается новое состояние). Этот механизм позволяет анализатору LR обрабатывать все детерминированные контекстно-свободные грамматики, расширенный набор грамматик приоритета. Парсер LR полностью реализован парсером Canonical LR . Анализаторы Look-Ahead LR и Simple LR реализуют его упрощенные варианты, которые значительно сокращают требования к памяти. [9] [10] Недавние исследования выявили методы, с помощью которых канонические LR-парсеры могут быть реализованы с существенно меньшими требованиями к таблицам по сравнению с алгоритмом построения таблиц Кнута. [11]
Независимо от того, LR, LALR или SLR, базовый конечный автомат один и тот же; только таблицы разные, и эти таблицы почти всегда создаются механически. Кроме того, эти таблицы обычно реализуются так, что REDUCE приводит к ВЫЗОВУ закрытой подпрограммы, которая является внешней по отношению к конечному автомату и выполняет функцию, подразумеваемую семантикой грамматического правила, которое REDUCE. Таким образом, синтаксический анализатор разделен на часть инвариантного конечного автомата и часть вариантной семантики. Это фундаментальное различие стимулирует разработку высококачественных и исключительно надежных парсеров.
Учитывая определенное состояние стека и символ прогнозирования, существует ровно четыре возможных действия: ОШИБКА, СДВИГ, УМЕНЬШЕНИЕ и СТОП (далее называемые конфигурациями). Наличие точки • в конфигурации представляет текущую позицию просмотра вперед, при этом символ просмотра вперед отображается справа от точки (и который всегда соответствует символу терминала), а текущее состояние стека слева от точки. (и который обычно соответствует нетерминальному символу).
По практическим соображениям, в том числе для повышения производительности, таблицы обычно расширяются за счет довольно большого вспомогательного массива двухбитовых символов, очевидно сжатого в четыре двухбитовых символа, байта, для эффективного доступа на байт-ориентированных машинах, часто кодируемых как :
(STOP является частным случаем SHIFT). Весь массив обычно включает в себя в основном конфигурации ERROR, определенное грамматически определенное количество конфигураций SHIFT и REDUCE и одну конфигурацию STOP.
В системах программирования, которые поддерживают указание значений в четвертичной системе счисления (основание 4, два бита на четвертичную цифру), таких как XPL, они кодируются, например, так:
Таблицы SHIFT и REDUCE реализованы отдельно от массива. Вспомогательный массив «исследуется» только на предмет текущего состояния и символа просмотра вперед. (Вспомогательный) массив является «полным», тогда как таблицы (сдвига и сокращения) действительно могут быть очень «разреженными», и значительная эффективность может быть достигнута за счет оптимального «разложения» этих таблиц SHIFT и REDUCE (ERROR и STOP не нуждаются в таблицах). ).
Конфигурации SHIFT и REDUCE очевидны из базового определения парсера SHIFT-REDUCE.
STOP, таким образом, представляет собой конфигурацию, в которой состояние наверху стека и символ терминала просмотра вперед находятся внутри предметной грамматики, и представляет собой окончание программы:
невозможно СДВИГАТЬСЯ за пределы финального ⊥ , чтобы концептуально достичь
Таким образом, ОШИБКА представляет собой конфигурацию, в которой состояние находится на вершине стека, а символ терминала просмотра не находится в пределах предметной грамматики. Это дает возможность вызвать процедуру восстановления ошибок, возможно, в ее самой упрощенной форме, чтобы отбросить символ терминала просмотра вперед и прочитать следующий символ терминала, но возможны и многие другие запрограммированные действия, включая обрезку стека или отбрасывание символа прогноза вперед. терминального символа и обрезки стека (а в патологическом случае обычно можно получить
где <program> состоит только из «нулевого оператора» ).
В большинстве случаев стек намеренно предварительно загружается, то есть инициализируется, с помощью
при этом предполагается, что начальный символ ⊥ уже распознан. Таким образом, это представляет собой начало программы и, таким образом, позволяет избежать отдельной конфигурации START, которая концептуально
⊥ — специальный псевдотерминальный символ, механически добавляемый в грамматику, так же, как <программа> — специальный псевдонетерминальный символ, механически добавляемый в грамматику (если программист явно не включил в грамматику <программу>, то <программа> будет автоматически добавлен в грамматику от имени программиста).
Очевидно, что такой анализатор имеет ровно одну (неявную) конфигурацию START и одну (явную) конфигурацию STOP, но он может и обычно имеет сотни конфигураций SHIFT и REDUCE и, возможно, тысячи конфигураций ERROR.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка )