Синтаксический анализатор сдвига-сокращения
Синтаксический анализатор сдвига-сокращения — это класс эффективных, управляемых таблицами методов синтаксического анализа снизу вверх для компьютерных языков и других обозначений, формально определенных грамматикой . Методы синтаксического анализа, наиболее часто используемые для анализа языков программирования , 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».
Анализатор сдвига-сокращения работает, выполняя некоторую комбинацию шагов сдвига и уменьшения, отсюда и название.
- Шаг Shift продвигается во входном потоке на один символ. Этот сдвинутый символ становится новым деревом разбора с одним узлом.
- Шаг сокращения применяет завершенное грамматическое правило к некоторым из последних деревьев синтаксического анализа, объединяя их в одно дерево с новым корневым символом.
Анализатор продолжает выполнять эти шаги до тех пор, пока все входные данные не будут использованы и все деревья синтаксического анализа не будут сведены к одному дереву, представляющему весь допустимый входной сигнал.
Этапы построения дерева
[ редактировать ]На каждом этапе синтаксического анализа весь входной текст делится на стек синтаксического анализа, текущий упреждающий символ и оставшийся неотсканированный текст. Следующее действие анализатора определяется крайним правым символом стека и символом просмотра вперед. Действие считывается из таблицы, содержащей все синтаксически допустимые комбинации символов стека и просмотра вперед.
| Шаг | Разбор стека | Смотреть Предстоящий | Несканированный | Действие парсера |
|---|---|---|---|---|
| 0 | пустой | идентификатор | = Б + С*2 | Сдвиг |
| 1 | идентификатор | = | Б + С*2 | Сдвиг |
| 2 | идентификатор = | идентификатор | + С*2 | Сдвиг |
| 3 | идентификатор = идентификатор | + | С*2 | Уменьшить по значению ← id |
| 4 | идентификатор = значение | + | С*2 | Уменьшить по продуктам ← Стоимость |
| 5 | идентификатор = Продукты | + | С*2 | Уменьшить по суммам ← Товары |
| 6 | идентификатор = Суммы | + | С*2 | Сдвиг |
| 7 | идентификатор = Суммы + | идентификатор | *2 | Сдвиг |
| 8 | идентификатор = суммы + идентификатор | * | 2 | Уменьшить по значению ← id |
| 9 | идентификатор = суммы + значение | * | 2 | Уменьшить по продуктам ← Стоимость |
| 10 | id = Суммы + Продукты | * | 2 | Сдвиг |
| 11 | id = Суммы + Продукты * | интервал | эоф | Сдвиг |
| 12 | id = Суммы + Продукты * int | эоф | Уменьшить по значению ← int | |
| 13 | id = Суммы + Продукты * Значение | эоф | Уменьшить по продуктам ← Продукты * Стоимость | |
| 14 | id = Суммы + Продукты | эоф | Уменьшить по суммам ← Суммы + произведения | |
| 15 | идентификатор = Суммы | эоф | Уменьшить путем назначения ← id = Суммы | |
| 16 | Назначать | эоф | Сделанный |
Видеть [2] для более простого примера.
Грамматика
[ редактировать ]Грамматика — это набор шаблонов или правил синтаксиса для языка ввода. Он не охватывает все правила языка, такие как размер чисел или последовательное использование имен и их определений в контексте всей программы. Синтаксические анализаторы сдвига-сокращения используют контекстно-свободную грамматику , которая работает только с локальными шаблонами символов.
Пример грамматики как крошечного подмножества языка Java или C, способного сопоставлять A = B + C*2 может быть:
- Присвоить ← id = Суммы
- Суммы ← Суммы + произведения
- Суммы ← Товары
- Продукция ← Продукция * Стоимость
- Продукция ← Стоимость
- Значение ← целое
- Значение ← идентификатор
грамматики Терминальные символы — это многосимвольные символы или «токены», найденные во входном потоке лексическим сканером . Здесь они включают = + * и int для любой целочисленной константы и id для любого имени идентификатора. Грамматику не волнует, каковы значения int или написание идентификатора , а также не важны пробелы или разрывы строк. Грамматика использует эти терминальные символы, но не определяет их. Они всегда находятся в самом нижнем густом конце дерева синтаксического анализа.
Термины, написанные с заглавной буквы, такие как суммы, являются нетерминальными символами . Это названия понятий или шаблонов в языке. Они определены в грамматике и никогда не встречаются во входном потоке. Они всегда находятся над нижней частью дерева разбора. Они происходят только в результате применения парсером некоторого грамматического правила. Некоторые нетерминалы определяются двумя или более правилами; это альтернативные модели. Правила могут ссылаться на самих себя. Эта грамматика использует рекурсивные правила для обработки повторяющихся математических операторов. Грамматики полных языков используют рекурсивные правила для обработки списков, выражений в скобках и вложенных операторов.
Любой компьютерный язык может быть описан несколькими различными грамматиками. Грамматика синтаксического анализатора со сдвигом-сокращением сама по себе должна быть однозначной или дополняться правилами приоритета, разрешающими конфликты. Это означает, что существует только один правильный способ применить грамматику к данному легальному примеру языка, что приводит к уникальному дереву синтаксического анализа и уникальной последовательности действий сдвига/сокращения для этого примера.
Анализатор, управляемый таблицами, хранит все свои знания о грамматике, закодированные в неизменные данные, называемые таблицами анализатора. Программный код парсера представляет собой простой общий цикл, который без изменений применяется ко многим грамматикам и языкам. Таблицы могут быть составлены вручную для методов приоритета. Для методов LR сложные таблицы механически извлекаются из грамматики с помощью какого-либо -генератора синтаксического анализатора, инструмента такого как Bison . [3] Таблицы парсера обычно намного больше, чем грамматика. В других синтаксических анализаторах, которые не управляются таблицами, таких как рекурсивный спуск , каждая языковая конструкция анализируется отдельной подпрограммой, специализированной на синтаксисе этой конструкции.
Действия парсера
[ редактировать ]Анализатор сдвига-сокращения эффективен, поскольку не требует резервного копирования. Общее время выполнения линейно зависит от длины входных данных и размера полного дерева разбора. Другие методы парсера, которые возвращаются назад, могут занять экспоненциальное время, если они плохо угадывают. [ нужна ссылка ]
Чтобы избежать угадывания, синтаксический анализатор сдвига-сокращения часто смотрит вперед (вправо в тексте с письмом слева направо) на следующий отсканированный символ, прежде чем решить, что делать с ранее отсканированными символами. Лексический сканер работает на один символ раньше остального синтаксического анализатора. Символ просмотра вперед также называется «правым контекстом» для каждого решения синтаксического анализа. (Редко можно использовать два или более символов просмотра вперед, хотя большинство практических грамматик могут быть разработаны для использования одного символа просмотра вперед.)
Синтаксический анализатор сдвига-сокращения ждет, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем определить, что представляет собой объединенная конструкция. Затем анализатор немедленно воздействует на комбинацию, не дожидаясь дальнейшего. В приведенном выше примере дерева синтаксического анализа фраза B сводится к значению, а затем к продуктам и суммам на шагах 3–6, как только + появляется в предварительном просмотре, вместо того, чтобы больше ждать, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать B, основаны только на том, что анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.
Сокращение реорганизует самые последние анализируемые элементы, то есть те, которые находятся непосредственно слева от символа просмотра вперед. Таким образом, список уже проанализированных вещей действует как стек . Этот стек синтаксического анализа растет вправо. Основание или низ стека находится слева и содержит самый левый и самый старый фрагмент синтаксического анализа. Каждый шаг сокращения действует только на самые правые, новейшие фрагменты синтаксического анализа. (Этот накопительный стек синтаксического анализа очень отличается от прогнозирующего, растущего влево стека синтаксического анализа, используемого нисходящими анализаторами .)
Когда такое грамматическое правило, как
- Продукция ← Продукция * Стоимость
применяется, вершина стека содержит деревья синтаксического анализа «... Продукты * Значение». Этот найденный экземпляр правой части правила называется дескриптором . Шаг уменьшения заменяет дескриптор «Продукты * Значение» на левый нетерминал, в данном случае на более крупный «Продукты». Если анализатор создает полные деревья синтаксического анализа, то три дерева для внутренних продуктов, * и стоимости объединяются в новый корень дерева для более крупных продуктов. В противном случае семантические детали из внутренних продуктов и значения выводятся на какой-либо более поздний этап компиляции или объединяются и сохраняются в новом символе продуктов. [4]
Синтаксический анализатор продолжает применять сокращения к вершине стека синтаксического анализа до тех пор, пока находит там вновь завершенные примеры грамматических правил. Когда больше правил применить невозможно, анализатор перемещает упреждающий символ в стек синтаксического анализа, сканирует новый упреждающий символ и повторяет попытку.
Типы парсеров сдвига-сокращения
[ редактировать ]Таблицы синтаксического анализатора показывают, что делать дальше для каждой допустимой комбинации символов верхнего уровня стека синтаксического анализа и символа просмотра вперед. Следующее действие должно быть уникальным; либо сдвинуть, либо уменьшить, но не то и другое. (Это подразумевает некоторые дополнительные ограничения на грамматику, помимо однозначности.) Детали таблицы сильно различаются в зависимости от типа анализаторов сдвига-сокращения.
В анализаторах приоритета правый конец дескрипторов находится путем сравнения уровня приоритета или грамматической строгости символов верхнего стека с уровнем предпросмотренного символа. В приведенном выше примере int и id принадлежат внутренним уровням грамматики по сравнению с разделителем операторов ; . Таким образом, int и id считаются более приоритетными, чем ; и должен быть сведен к чему-то другому всякий раз, когда за ним следует ; . Существуют различные разновидности анализаторов приоритета, каждый из которых имеет разные способы поиска левого конца дескриптора и выбора правильного правила для применения:
- Анализатор приоритета операторов — очень простой численный метод, который работает с выражениями, но не с общим синтаксисом программы.
- Простой анализатор приоритетов , использует одну большую таблицу MxN для поиска правого и левого концов. Используется в PL360 . [5] Не поддерживает распространенные языки программирования.
- Слабый анализатор приоритета, использует таблицу приоритета только для поиска правых концов дескрипторов. Обрабатывает больше грамматик, чем простой приоритет. [6]
- Расширенный парсер приоритетов.
- Парсер смешанного приоритета стратегий, используемый исходной версией XPL . Расширяет «двойники», присущие любому распознавателю приоритета, включая «тройки». Менее мощный, чем зеркалка. Обычно имеет очень большие таблицы даже для относительно небольших языков, таких как сам XPL, из-за большого количества «троек», которые необходимы для распознавания грамматик за пределами ограничений, налагаемых методами приоритета. [7]
Парсеры приоритета ограничены в грамматиках, которые они могут обрабатывать. Они игнорируют большую часть стека синтаксического анализа при принятии решений. Они учитывают только имена самых верхних символов, а не полный контекст того, где в грамматике эти символы сейчас появляются. Приоритет требует, чтобы похожие комбинации символов анализировались и использовались одинаковым образом во всей грамматике, однако эти комбинации происходят независимо от контекста.
LR- парсеры представляют собой более гибкую форму синтаксического анализа с сокращением сдвига, обрабатывающую гораздо больше грамматик. [8]
Обработка парсера LR
[ редактировать ]Анализаторы LR функционируют как конечный автомат , выполняя переход состояний для каждого действия сдвига или сокращения. Они используют стек, в котором текущее состояние сдвигается (вниз) с помощью действий сдвига. Этот стек впоследствии выдвигается (вверх) с помощью действий сокращения (и одновременно с этим создается новое состояние). Этот механизм позволяет анализатору LR обрабатывать все детерминированные контекстно-свободные грамматики, расширенный набор грамматик приоритета. Парсер LR полностью реализован парсером Canonical LR . Анализаторы Look -Ahead LR и Simple LR реализуют его упрощенные варианты, которые значительно сокращают требования к памяти. [9] [10] Недавние исследования выявили методы, с помощью которых канонические анализаторы LR могут быть реализованы с существенно меньшими требованиями к таблицам по сравнению с алгоритмом построения таблиц Кнута. [11]
Независимо от того, LR, LALR или SLR, базовый конечный автомат один и тот же; только таблицы разные, и эти таблицы почти всегда создаются механически. Кроме того, эти таблицы обычно реализуются таким образом, что REDUCE приводит к ВЫЗОВУ закрытой подпрограммы, которая является внешней по отношению к конечному автомату и выполняет функцию, подразумеваемую семантикой грамматического правила, которое REDUCEd. Таким образом, синтаксический анализатор разделен на часть инвариантного конечного автомата и часть вариантной семантики. Это фундаментальное различие способствует разработке высококачественных и исключительно надежных парсеров.
Учитывая конкретное состояние стека и символ просмотра вперед, существует ровно четыре возможных действия: ОШИБКА, СДВИГ, УМЕНЬШЕНИЕ и СТОП (далее называемые конфигурациями). Наличие точки • в конфигурации представляет текущую позицию просмотра вперед, при этом символ просмотра вперед отображается справа от точки (и который всегда соответствует символу терминала), а текущее состояние стека — слева от точки. (и который обычно соответствует нетерминальному символу).
По практическим соображениям, в том числе для повышения производительности, таблицы обычно расширяются с помощью довольно большого вспомогательного массива двухбитовых символов, очевидно сжатого в четыре двухбитовых символа, байт, для эффективного доступа на байт-ориентированных машинах, часто кодируемых как :
- 00 b представляет ОШИБКУ
- 01 b представляет собой SHIFT
- 10 b представляет собой УМЕНЬШИТЬ
- 11 b представляет СТОП
(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> состоит только из «нулевого оператора» ).
В большинстве случаев стек намеренно предварительно загружается, то есть инициализируется, с помощью
- ⊥ • <программа> ⊥
при этом предполагается, что начальный символ ⊥ уже распознан. Таким образом, это представляет собой начало программы и, таким образом, позволяет избежать отдельной конфигурации START, которая концептуально
- • ⊥ <программа> ⊥
⊥ — специальный псевдотерминальный символ, механически добавляемый в грамматику, так же как <программа> — специальный псевдонетерминальный символ, механически добавляемый в грамматику (если программист явно не включил в грамматику <программу>, то <программа> будет автоматически добавлен в грамматику от имени программиста).
Очевидно, что такой анализатор имеет ровно одну (неявную) конфигурацию START и одну (явную) конфигурацию STOP, но он может и обычно имеет сотни конфигураций SHIFT и REDUCE и, возможно, тысячи конфигураций ERROR.
Ссылки
[ редактировать ]- ^ Составители: принципы, методы и инструменты (2-е издание), Альфред Ахо, Моника Лам, Рави Сетхи и Джеффри Уллман, Prentice Hall, 2006.
- ^ «Архивная копия» (PDF) . www.dragonbook.stanford.edu . Архивировано из оригинала (PDF) 5 марта 2016 года . Проверено 17 января 2022 г.
{{cite web}}: CS1 maint: архивная копия в заголовке ( ссылка ) - ^ Flex & Bison: инструменты обработки текста, Джон Левайн, O'Reilly Media, 2009.
- ^ Создание компилятора, Фишер, Рон и Ричард, Аддисон Уэсли, 2009.
- ^ PL360 — язык программирования для компьютеров 360, Никлаус Вирт, J. ACM 15:1 1968.
- ^ Теория синтаксического анализа, перевода и компиляции, Том 1: Синтаксический анализ, Альфред Ахо и Джеффри Уллман, Прентис Холл, 1972.
- ^ Генератор компилятора, Уильям М. Маккиман, Дж. Хорнинг и Д. Вортман, Прентис Холл, 1970; ISBN 978-0131550773 .
- ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 . Проверено 29 мая 2011 г.
- ^ Практические переводчики для языков LR (k), Фрэнк ДеРемер, докторская диссертация Массачусетского технологического института, 1969 г.
- ^ Простые грамматики LR(k), Фрэнк ДеРемер, Comm. АКМ 14:7 1971.
- ^ X. Чен, Измерение и расширение анализа LR(1) , Кандидатская диссертация Гавайского университета, 2009 г.