Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Сдвиг-свертка анализатор представляет собой класс эффективных, табличной снизу вверх разборе методов для компьютерных языков и других обозначений формально определяется грамматикой . Методы синтаксического анализа, наиболее часто используемые для синтаксического анализа языков программирования , синтаксического анализа 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».

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

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

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

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

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

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

См. Более простой пример в [2] .

Грамматики [ править ]

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

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

Назначить ← id = Суммы
Суммы ← Суммы + произведения
Суммы ← Продукция
Продукция ← Продукция * Стоимость
Продукция ← Стоимость
Значение ← int
Значение ← id

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

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

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

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

Действия парсера [ править ]

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

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

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

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

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

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

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

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

Типы парсеров Shift-Reduce [ править ]

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

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

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

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

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

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

Обработка парсера LR [ править ]

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

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

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

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

00 b представляет ОШИБКУ
01 b представляет SHIFT
10 b означает УМЕНЬШЕНИЕ
11 б представляет СТОП

(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 представляет собой конфигурацию, в которой состояние наверху стека и прогнозирующий терминальный символ находятся в рамках предметной грамматики и представляет собой окончание программы:

⊥ <программа> • ⊥

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

⊥ <программа> ⊥ •

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

⊥ <программа> • ⊥

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

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

⊥ • <программа> ⊥

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

• ⊥ <программа> ⊥

⊥ - это специальный псевдотерминальный символ, механически добавляемый в грамматику, так же как <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. ^ Компилятор Генератор, Уильям М. McKeeman, J Хорнинг и D Wortman, Prentice Hall 1970; ISBN  978-0131550773 .
  8. ↑ Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Проверено 29 мая 2011 года . CS1 maint: обескураженный параметр ( ссылка )
  9. ^ Практические переводчики для языков LR (k), Фрэнк Де Ремер, докторская диссертация Массачусетского технологического института, 1969.
  10. ^ Простые LR (k) грамматики, Фрэнк Де Ремер, Comm. ACM 14: 7 1971.
  11. ^ X. Чен, Измерение и расширение анализа LR (1) , докторская диссертация Гавайского университета, 2009.