Парсер LR - LR parser

В информатике , LR парсеры представляют собой тип снизу вверх синтаксический анализатор , который анализирует детерминированные контекстно-свободные языки в линейное время. Есть несколько вариантов LR парсеров: SLR парсеры , LALR парсеры , Canonical LR (1) парсеры , Minimal LR (1) парсеры , GLR парсеры . Синтаксические анализаторы LR могут быть сгенерированы генератором синтаксического анализатора из формальной грамматики, определяющей синтаксис анализируемого языка. Они широко используются для обработки компьютерных языков .

LR анализатор ( L EFT-направо, R ightmost вывод в обратном) считывает входной текст слева направо без резервного копирования (это верно для большинства анализаторов), и производит правый вывод в обратном: это делает снизу вверх синтаксический анализ, а не анализ LL сверху вниз или специальный синтаксический анализ. За именем LR часто следует числовой квалификатор, например, LR (1) или иногда LR ( k ) . Чтобы избежать обратного отслеживания или угадывания, синтаксическому анализатору LR разрешено заглядывать вперед на k входных предварительных символов, прежде чем решать, как анализировать более ранние символы. Обычно k равно 1 и не упоминается. Имя LR часто предшествует другим квалификаторам, как в SLR и LALR . LR ( к ) условие грамматики было предложено Кнутом стоять «переводимую слева направо с занными к

Парсеры LR детерминированы; они производят единственный правильный синтаксический анализ без догадок или обратного отслеживания за линейное время. Это идеально подходит для компьютерных языков, но парсеры LR не подходят для человеческих языков, которым нужны более гибкие, но неизбежно более медленные методы. Некоторые методы, которые могут анализировать произвольные контекстно-свободные языки (например, Кок – Янгер – Касами , Эрли , GLR ), имеют производительность в худшем случае за время O ( n 3 ). Другие методы, которые возвращают или приводят к множественному синтаксическому анализу, могут даже занять экспоненциальное время, когда они плохо угадывают.

Вышеупомянутые свойства L , R и k фактически разделяются всеми синтаксическими анализаторами с уменьшением сдвига , включая синтаксические анализаторы приоритета . Но по соглашению имя LR обозначает форму синтаксического анализа, изобретенную Дональдом Кнутом , и исключает более ранние, менее мощные методы приоритета (например, синтаксический анализатор приоритета оператора ). Парсеры LR могут обрабатывать больший диапазон языков и грамматик, чем парсеры приоритета или нисходящий анализ LL . Это связано с тем, что синтаксический анализатор LR ожидает, пока он не увидит весь экземпляр некоторого грамматического шаблона, прежде чем совершить то, что он нашел. Анализатор LL должен решить или угадать, что он видит, гораздо раньше, когда он увидел только крайний левый входной символ этого шаблона.

Обзор

Дерево синтаксического анализа снизу вверх, например A * 2 + 1

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

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

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

Сдвиг и сокращение действий

Как и другие парсеры сдвига-уменьшения, парсер LR работает, выполняя некоторую комбинацию шагов Shift и шагов Reduce.

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

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

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

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

Стек синтаксического анализа снизу вверх

Синтаксический анализатор снизу вверх на шаге 6

Подобно другим синтаксическим анализаторам сдвиг-сокращение, синтаксический анализатор LR лениво ждет, пока он не просканирует и не проанализирует все части некоторой конструкции, прежде чем зафиксировать то, что представляет собой объединенная конструкция. Затем синтаксический анализатор немедленно воздействует на комбинацию, а не ждет дальнейшего. В примере с деревом синтаксического анализа фраза A сокращается до Value, а затем до Products на шагах 1-3, как только просматривается *, вместо того, чтобы ждать позже, чтобы организовать эти части дерева синтаксического анализа. Решения о том, как обрабатывать A, основаны только на том, что синтаксический анализатор и сканер уже видели, без учета вещей, которые появляются намного позже справа.

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

Шаги синтаксического анализа снизу вверх, например A * 2 + 1

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

На шаге 6 применяется правило грамматики, состоящее из нескольких частей:

Продукты → Продукты * Стоимость

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

Шаги анализа LR, например A * 2 + 1

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

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


Шаг

Состояние стека синтаксического анализа [ состояние символа ] *
Смотреть
вперед

Непроверенный

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

Правило грамматики
Следующее
состояние
0

0

я бы * 2 + 1 сдвиг 9
1

0 id 9

* 2 + 1 уменьшать Значение → id 7
2

0 Значение 7

* 2 + 1 уменьшать Продукция → Стоимость 4
3

0 Товаров 4

* 2 + 1 сдвиг 5
4

0 Товаров 4 * 5

int +1 сдвиг 8
5

0 Товары 4 * 5 int 8

+ 1 уменьшать Значение → int 6
6

0 Товаров 4 * 5 Стоимость 6

+ 1 уменьшать Продукты → Продукты * Стоимость 4
7

0 Товаров 4

+ 1 уменьшать Суммы → Товары 1
8

0 Сумма 1

+ 1 сдвиг 2
9

0 Сумма 1 + 2

int eof сдвиг 8
10

0 Суммы 1 + 2 целых 8

eof уменьшать Значение → int 7
11

0 Сумма 1 + 2 Значение 7

eof уменьшать Продукция → Стоимость 3
12

0 Сумма 1 + 2 Товаров 3

eof уменьшать Суммы → Суммы + Продукты 1
13

0 Сумма 1

eof сделано

На начальном шаге 0 входной поток «A * 2 + 1» делится на

  • пустой раздел в стеке синтаксического анализа,
  • прогнозируемый текст "A", сканированный как символ идентификатора , и
  • оставшийся неотсканированный текст «* 2 + 1».

Стек синтаксического анализа начинается с сохранения только начального состояния 0. Когда состояние 0 видит идентификатор просмотра вперед , оно знает, что нужно сдвинуть этот идентификатор в стек, просканировать следующий входной символ * и перейти к состоянию 9.


На шаге 4 общий входной поток «A * 2 + 1» в настоящее время делится на

  • проанализированный раздел «A *» с 2 составными фразами «Товары» и * ,
  • прогнозируемый текст "2" отсканирован как символ int , и
  • оставшийся неотсканированный текст «+1».

Состояниями, соответствующими составным фразам, являются 0, 4 и 5. Текущее, крайнее правое состояние в стеке - это состояние 5. Когда состояние 5 видит опережающий int , оно знает, что нужно переместить это int в стек как свою собственную фразу, и отсканируйте следующий входной символ + и перейдите к состоянию 8.


На шаге 12 весь входной поток израсходован, но организован лишь частично. Текущее состояние - 3. Когда состояние 3 видит опережающий eof , оно знает, что нужно применить завершенное правило грамматики.

Суммы → Суммы + Продукты

путем объединения трех крайних правых фраз стека для Sums, + и Products в одно целое. Само состояние 3 не знает, каким должно быть следующее состояние. Это можно найти, вернувшись в состояние 0, слева от сокращаемой фразы. Когда состояние 0 видит этот новый завершенный экземпляр Sums, он переходит в состояние 1 (снова). Консультации со старыми состояниями являются причиной того, почему они хранятся в стеке, а не только в текущем состоянии.

Грамматика для примера A * 2 + 1

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

Используемый здесь пример грамматики представляет собой крошечное подмножество языка Java или C:

r0: Цель → Сумма
r1: Суммы → Суммы + произведения
r2: Суммы → Товары
r3: Товары → Товары * Стоимость
r4: Продукты → Ценность
r5: Значение → int
r6: Значение → id

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

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

Любой компьютерный язык можно описать несколькими разными грамматиками. Парсер LR (1) может обрабатывать многие, но не все общие грамматики. Обычно можно вручную изменить грамматику, чтобы она соответствовала ограничениям синтаксического анализа LR (1) и инструмента генератора.

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

Таблица синтаксического анализа для примера грамматики

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

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

В зависимости от того, как государства и разбора таблицы генерируются, полученный парсер называется либо SLR (простой LR) анализатор , LALR (упреждающая LR) анализатор , или канонический LR - анализатор . Парсеры LALR обрабатывают больше грамматик, чем парсеры SLR. Канонические парсеры LR обрабатывают еще больше грамматик, но используют гораздо больше состояний и гораздо большие таблицы. Пример грамматики - SLR.

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

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

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

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

Curr Смотреть вперед LHS Goto
Состояние Текущие правила int я бы *   +   eof Суммы Продукты Ценить
0 Цель → Суммы EOF 8 9 1 4 7
1 Цель → Суммы eof
Sums → Sums + Products

2
сделано
 
2 Суммы → Суммы + Продукты 8 9 3 7
3 Суммы → Суммы + Продукты
Продукты → Продукты * Стоимость

5
r1
 
r1
 
4 Суммы → Продукты
Продукты → Продукты * Стоимость

5
r2
 
r2
 
5 Продукты → Продукты * Ценность 8 9 6
6 Продукты → Продукты * Стоимость r3 r3 r3
7 Продукты → Стоимость r4 r4 r4
8 Значение → int r5 r5 r5
9 Значение → id r6 r6 r6

В состоянии 2 выше, синтаксический анализатор только что нашел и сдвинул + грамматического правила

r1: Суммы → Суммы + Произведения

Следующая ожидаемая фраза - это продукты. Товары начинаются с терминальных символов int или id . Если опережающий просмотр является одним из них, синтаксический анализатор сдвигает их и переходит в состояние 8 или 9 соответственно. Когда продукт найден, синтаксический анализатор переходит в состояние 3, чтобы собрать полный список слагаемых и найти конец правила r0. Товары также могут начинаться с нетерминального значения. Для любого другого опережающего или нетерминального сообщения синтаксический анализатор объявляет синтаксическую ошибку.


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

r1: Суммы → Суммы + произведения
r3: Продукты → Продукты * Значение

Выбор между r1 и r3 нельзя решить, просто взглянув назад на предыдущие фразы. Парсер должен проверить символ опережающего просмотра, чтобы сказать, что делать. Если опережающий просмотр * , он находится в правиле 3, поэтому синтаксический анализатор переходит на * и переходит в состояние 5. Если опережающий просмотр - eof , он находится в конце правила 1 и правила 0, поэтому синтаксический анализатор завершен.


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

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

Цикл парсера LR

Анализатор LR начинается с почти пустого стека синтаксического анализа, содержащего только начальное состояние 0, и с опережающего просмотра, содержащего первый отсканированный символ входного потока. Затем синтаксический анализатор повторяет следующий шаг цикла до тех пор, пока не будет выполнен, или не обнаружит синтаксическую ошибку:

Самым верхним состоянием в стеке синтаксического анализа является некоторое состояние s , а текущим опережающим просмотром - некоторый терминальный символ t . Найдите следующее действие синтаксического анализатора в строке s и столбце t таблицы Lookahead Action. Это действие - Shift, Уменьшение, Готово или Ошибка:

  • Shift n :
Переместите согласованный терминал t в стек синтаксического анализа и просканируйте следующий входной символ в опережающий буфер.
Поместить следующее состояние n в стек синтаксического анализа как новое текущее состояние.
  • Уменьшить r m : применить правило грамматики r m : Lhs → S 1 S 2 ... S L
Удалите совпавшие самые верхние L символов (и деревья синтаксического анализа и связанные номера состояний) из стека синтаксического анализа.
Это раскрывает предыдущее состояние p, которое ожидало экземпляра символа Lhs.
Соедините деревья синтаксического анализа L вместе как одно дерево синтаксического анализа с новым корневым символом Lhs.
Найдите следующее состояние n из строки p и столбца Lhs таблицы LHS Goto.
Поместите символ и дерево для Lhs в стек синтаксического анализа.
Поместить следующее состояние n в стек синтаксического анализа как новое текущее состояние.
Предварительный просмотр и входной поток остаются неизменными.
  • Готово: Lookahead t - маркер eof . Конец разбора. Если стек состояний содержит только начальное состояние, сообщите об успешном завершении. В противном случае сообщите о синтаксической ошибке.
  • Ошибка: сообщить о синтаксической ошибке. Синтаксический анализатор завершает работу или пытается какое-то восстановление.

Стек парсера LR обычно хранит только состояния автомата LR (0), так как символы грамматики могут быть производными от них (в автомате все входные переходы в какое-либо состояние помечены одним и тем же символом, который является символом, связанным с этим состоянием) . Более того, эти символы почти никогда не нужны, так как состояние - это все, что имеет значение при принятии решения о парсинге.

Анализ генератора LR

Этот раздел статьи может пропустить большинство пользователей генераторов парсеров LR.

LR заявляет

Состояние 2 в примере таблицы синтаксического анализа относится к частично проанализированному правилу.

r1: Суммы → Суммы + Произведения

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

Частично проанализированные правила для состояния называются его «основными элементами LR (0)». Генератор парсера добавляет дополнительные правила или элементы для всех возможных следующих шагов в создании ожидаемых продуктов:

r3: Продукты → Продукты * Стоимость
r4: Продукты → Ценность
r5: Значение → int
r6: Значение → id

маркер в начале каждого из этих дополнительных правил; парсер еще не подтвердил и не проанализировал какую-либо их часть. Эти дополнительные элементы называются «закрытием» основных элементов. Для каждого нетерминального символа, следующего сразу за , генератор добавляет правила, определяющие этот символ. Это добавляет больше маркер, и , возможно , различные символы повторителей. Этот процесс закрытия продолжается до тех пор, пока все символы-последователи не будут развернуты. Последовательные нетерминалы для состояния 2 начинаются с Products. Затем стоимость добавляется закрытием. Терминалы последователя - это int и id .

Элементы ядра и закрытия вместе показывают все возможные законные способы перехода от текущего состояния к будущим состояниям и полные фразы. Если символ последователя появляется только в одном элементе, он ведет к следующему состоянию, содержащему только один базовый элемент с выдвинутым маркером. Итак, int приводит к следующему состоянию 8 с ядром

r5: Значение → int

Если один и тот же символ последователя появляется в нескольких элементах, синтаксический анализатор еще не может сказать, какое правило здесь применяется. Таким образом, этот символ ведет к следующему состоянию, в котором показаны все оставшиеся возможности, опять же с продвинутым маркером. Продукты появляются как в r1, так и в r3. Таким образом, продукты приводят к следующему состоянию 3 с ядром

r1: Суммы → Суммы + произведения
r3: Продукты → Продукты * Значение

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

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

Эти состояния называются состояниями «LR (0)», потому что они используют опережающий просмотр k = 0, то есть без опережения. Единственная проверка входных символов происходит, когда символ сдвигается внутрь. Проверка опережающих представлений для сокращений выполняется отдельно таблицей синтаксического анализа, а не самими перечисляемыми состояниями.

Конечный автомат

В таблице синтаксического анализа описаны все возможные состояния LR (0) и их переходы. Они образуют конечный автомат (FSM). FSM - это простой механизм для анализа простых невложенных языков без использования стека. В этом приложении LR модифицированный «язык ввода» конечного автомата имеет как терминальные, так и нетерминальные символы и охватывает любой частично проанализированный снимок стека полного анализа LR.

Вспомните шаг 5 примера шагов синтаксического анализа:


Шаг

Состояние синтаксического символа состояния стека ...
Смотреть
вперед

Непроверенный
5

0 Товары 4 * 5 int 8

+ 1

Стек синтаксического анализа показывает серию переходов состояний от начального состояния 0 к состоянию 4, а затем к 5 и текущему состоянию 8. Символы в стеке синтаксического анализа являются символами сдвига или перехода для этих переходов. Другой способ увидеть это - то, что конечный автомат может сканировать поток «Products *  int  + 1» (без использования еще одного стека) и находить крайнюю левую полную фразу, которая должна быть сокращена следующей. И это действительно его работа!

Как может простой автомат сделать это, если исходный неанализируемый язык имеет вложенность и рекурсию и определенно требует анализатора со стеком? Хитрость в том, что все, что находится слева от вершины стека, уже полностью уменьшено. Это устраняет все петли и вложенность этих фраз. FSM может игнорировать все старые начала фраз и отслеживать только самые новые фразы, которые могут быть завершены следующей. В теории LR это неясное название - «жизнеспособный префикс».

Наборы Lookahead

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

В синтаксических анализаторах SLR эти опережающие наборы определяются непосредственно из грамматики, без учета отдельных состояний и переходов. Для каждого нетерминального S генератор SLR вырабатывает Follows (S), набор всех терминальных символов, которые могут сразу следовать за некоторым вхождением S. В таблице синтаксического анализа каждое сокращение до S использует Follow (S) в качестве своего LR (1 ) опережающий набор. Такие последующие наборы также используются генераторами нисходящих синтаксических анализаторов LL. Грамматика, которая не имеет конфликтов сдвига / уменьшения или уменьшения / уменьшения при использовании наборов Follow, называется грамматикой SLR.

Парсеры LALR имеют те же состояния, что и парсеры SLR, но используют более сложный и точный способ определения минимально необходимых опережающих просмотров для каждого отдельного состояния. В зависимости от деталей грамматики он может оказаться таким же, как набор Follow, вычисляемый генераторами парсеров SLR, или может оказаться подмножеством опережающих просмотров SLR. Некоторые грамматики подходят для генераторов парсеров LALR, но не подходят для генераторов парсеров SLR. Это происходит, когда грамматика имеет ложные конфликты сдвига / уменьшения или уменьшения / уменьшения с использованием наборов Follow, но не конфликтует при использовании точных наборов, вычисленных генератором LALR. Грамматика тогда называется LALR (1), но не SLR.

Парсер SLR или LALR избегает дублирования состояний. Но в такой минимизации нет необходимости, и иногда она может создавать ненужные конфликты опережающего просмотра. Канонические парсеры LR используют дублированные (или «разделенные») состояния, чтобы лучше запоминать левый и правый контекст использования нетерминала. Каждое вхождение символа S в грамматике может обрабатываться независимо с его собственным набором опережающих представлений, чтобы помочь разрешить конфликты сокращения. Это обрабатывает еще несколько грамматик. К сожалению, это значительно увеличивает размер таблиц синтаксического анализа, если выполняется для всех частей грамматики. Это разделение состояний также можно выполнить вручную и выборочно с помощью любого анализатора SLR или LALR, создав две или более именованных копий некоторых нетерминалов. Грамматика, которая является бесконфликтной для канонического генератора LR, но имеет конфликты в генераторе LALR, называется LR (1), но не LALR (1) и не SLR.

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

Восстановление синтаксической ошибки

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

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

Многие синтаксические ошибки кодирования - это простые опечатки или пропуски тривиального символа. Некоторые парсеры LR пытаются обнаружить и автоматически исправить эти распространенные случаи. Анализатор перечисляет все возможные вставки, удаления или замены одного символа в точке ошибки. Компилятор выполняет пробный синтаксический анализ каждого изменения, чтобы убедиться, что все работает нормально. (Для этого требуется возврат к снимкам стека синтаксического анализа и входного потока, которые обычно не требуются синтаксическому анализатору.) Выбирается лучший вариант восстановления. Это дает очень полезное сообщение об ошибке и хорошо синхронизирует синтаксический анализ. Однако исправление недостаточно надежно, чтобы навсегда изменить входной файл. Исправление синтаксических ошибок проще всего выполнять последовательно в парсерах (например, LR), которые имеют таблицы синтаксического анализа и явный стек данных.

Варианты парсеров LR

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

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

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

Другой вариант заменяет таблицу синтаксического анализа правилами сопоставления с образцом в непроцедурных языках, таких как Prolog .

Обобщенные синтаксические анализаторы LR GLR используют восходящие методы LR для поиска всех возможных синтаксических анализов входящего текста, а не только одного правильного синтаксического анализа. Это важно для неоднозначных грамматик, например, используемых в человеческих языках. Множественные допустимые деревья синтаксического анализа вычисляются одновременно, без возврата. GLR иногда полезен для компьютерных языков, которые нелегко описать бесконфликтной грамматикой LALR (1).

Анализаторы левого угла LC используют восходящие методы LR для распознавания левого конца альтернативных правил грамматики. Когда альтернативы были сужены до единственного возможного правила, синтаксический анализатор затем переключается на нисходящие методы LL (1) для синтаксического анализа остальной части этого правила. Анализаторы LC имеют меньшие таблицы синтаксического анализа, чем анализаторы LALR, и лучшую диагностику ошибок. Широко используемых генераторов для детерминированных LC-синтаксических анализаторов не существует. Анализаторы LC с множественным синтаксическим анализом полезны с человеческими языками с очень большими грамматиками.

Теория

Парсеры LR были изобретены Дональдом Кнутом в 1965 году как эффективное обобщение парсеров приоритета . Кнут доказал, что синтаксические анализаторы LR были наиболее универсальными из возможных, которые все равно были бы эффективны в худших случаях.

«LR ( k ) грамматики могут быть эффективно проанализированы со временем выполнения, по существу пропорциональным длине строки».
Для каждого k ≥1 «язык может быть сгенерирован грамматикой LR ( k ) тогда и только тогда, когда он является детерминированным [и контекстно-независимым], тогда и только тогда, когда он может быть сгенерирован грамматикой LR (1)».

Другими словами, если язык был достаточно разумным, чтобы позволить эффективный однопроходный синтаксический анализатор, он мог быть описан грамматикой LR ( k ). И эту грамматику всегда можно было механически преобразовать в эквивалентную (но более крупную) грамматику LR (1). Таким образом, метод синтаксического анализа LR (1) теоретически был достаточно мощным, чтобы работать с любым разумным языком. На практике естественная грамматика для многих языков программирования близка к LR (1).

Канонические парсеры LR, описанные Кнутом, имели слишком много состояний и очень большие таблицы синтаксического анализа, которые были непрактично большими для ограниченной памяти компьютеров той эпохи. Разбор LR стал практичным, когда Франк Де Ремер изобрел парсеры SLR и LALR с гораздо меньшим количеством состояний.

Полную информацию о теории LR и о том, как парсеры LR являются производными от грамматик, см . Теория синтаксического анализа, перевода и компиляции, том 1 (Ахо и Ульман).

Эрел парсер применять методы и обозначения LR парсеров к задаче генерации все возможные разборов для неоднозначных грамматик , таких как для человеческих языков.

В то время как грамматики LR ( k ) имеют одинаковую порождающую способность для всех k ≥1, случай грамматик LR (0) немного отличается. Язык L называется иметь свойством префикса , если ни одно слово в L не является собственным префиксом другого слова в L . Язык L имеет грамматику LR (0) тогда и только тогда, когда L - детерминированный контекстно-свободный язык со свойством префикса. Как следствие, язык L является детерминированным контекстно-свободной , если и только если L $ имеет LR (0) грамматики, где «$» не является символом L «ами алфавита .

Дополнительный пример 1 + 1

Разбор снизу вверх 1 + 1

В этом примере анализа LR используется следующая небольшая грамматика с символом цели E:

(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

для анализа следующего ввода:

1 + 1

Таблицы действий и перехода

Две таблицы синтаксического анализа LR (0) для этой грамматики выглядят следующим образом:

штат действие перейти к
  * + 0 1 $ E B
0     s1 s2   3 4
1 r4 r4 r4 r4 r4    
2 r5 r5 r5 r5 r5    
3 s5 s6     соотв    
4 r3 r3 r3 r3 r3    
5     s1 s2     7
6     s1 s2     8
7 r1 r1 r1 r1 r1    
8 r2 r2 r2 r2 r2    

Таблица действий индексируется состоянием анализатора и терминала (включая специальный терминал $, который указывает конец входного потока) и содержит три типа действий:

  • shift , который записывается как 's n ' и указывает, что следующее состояние - n
  • reduce , который записывается как 'r m ' и указывает, что сокращение с правилом грамматики m должно быть выполнено
  • accept , который записывается как acc и указывает, что синтаксический анализатор принимает строку во входном потоке.

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

Шаги разбора

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

Состояние Входной поток Выходной поток Куча Следующее действие
0 1 + 1 $ [0] Сдвиг 2
2 + 1 $ [0,2] Уменьшить 5
4 + 1 $ 5 [0,4] Уменьшить 3
3 + 1 $ 5,3 [0,3] Сдвиг 6
6 1 $ 5,3 [0,3,6] Сдвиг 2
2 $ 5,3 [0,3,6,2] Уменьшить 5
8 $ 5,3,5 [0,3,6,8] Уменьшить 2
3 $ 5,3,5,2 [0,3] Принимать

Прохождение

Парсер начинает со стека, содержащего только начальное состояние ('0'):

[ 0 ]

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

[ 0 '1' 2 ]

где верх стека равен 2. Для пояснения показан символ (например, «1», B), который вызвал переход в следующее состояние, хотя, строго говоря, он не является частью стека.

В состоянии 2 таблица действий сообщает о сокращении с помощью правила грамматики 5 (независимо от того, какой терминал синтаксический анализатор видит во входном потоке), что означает, что синтаксический анализатор только что распознал правую часть правила 5. В этом случае синтаксический анализатор записывает 5 в выходной поток, извлекает одно состояние из стека (поскольку правая часть правила имеет один символ) и помещает в стек состояние из ячейки в таблице перехода для состояний 0 и B, т. е. , состояние 4. Итоговый стек:

[ 0 B 4 ]

Однако в состоянии 4 таблица действий говорит, что синтаксический анализатор теперь должен уменьшить с помощью правила 3. Таким образом, он записывает 3 в выходной поток, извлекает одно состояние из стека и находит новое состояние в таблице перехода для состояний 0 и E, состояние 3. Итоговый стек:

[ 0 E 3 ]

Следующий терминал, который видит синтаксический анализатор, - это '+', и в соответствии с таблицей действий он должен перейти в состояние 6:

[ 0 E 3 '+' 6 ]

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

Следующий терминал теперь равен «1», и это означает, что синтаксический анализатор выполняет сдвиг и переходит в состояние 2:

[ 0 E 3 '+' 6 '1' 2 ]

Так же, как и предыдущая «1», эта сокращается до B, давая следующий стек:

[ 0 E 3 '+' 6 B 8 ]

Стек соответствует списку состояний конечного автомата, который прочитал нетерминал E, за которым следует '+', а затем нетерминал B. В состоянии 8 синтаксический анализатор всегда выполняет сокращение по правилу 2. Три верхних состояния в таблице стек соответствуют 3 символам в правой части правила 2. На этот раз мы извлекаем 3 элемента из стека (поскольку правая часть правила состоит из 3 символов) и ищем состояние перехода для E и 0 , таким образом помещая состояние 3 обратно в стек

[ 0 E 3 ]

Наконец, синтаксический анализатор считывает '$' (конец входного символа) из входного потока, что означает, что в соответствии с таблицей действий (текущее состояние - 3) синтаксический анализатор принимает входную строку. Номера правил, которые затем будут записаны в выходной поток, будут [5, 3, 5, 2], что действительно является крайним правым производным строки «1 + 1» в обратном порядке.

Создание таблиц синтаксического анализа LR (0)

Предметы

Построение этих таблиц синтаксического анализа основано на понятии элементов LR (0) (здесь просто называемых элементами ), которые представляют собой правила грамматики со специальной точкой, добавленной где-то в правой части. Например, правилу E → E + B соответствуют следующие четыре элемента:

E → E + B
E → E + B
E → E + B
E → E + B

Правила вида A → ε имеют только один элемент A . Элемент E → E + B, например, указывает, что синтаксический анализатор распознал строку, соответствующую E во входном потоке, и теперь ожидает прочитать '+', за которым следует другая строка, соответствующая B.

Наборы предметов

Обычно невозможно охарактеризовать состояние анализатора с помощью одного элемента, потому что он может заранее не знать, какое правило будет использовать для сокращения. Например, если существует также правило E → E * B, тогда элементы E → E + B и E → E * B будут применяться после того, как будет прочитана строка, соответствующая E. Поэтому состояние парсера удобно характеризовать набором элементов, в данном случае набором {E → E + B, E → E * B}.

Расширение набора позиций за счет расширения нетерминалов

Элемент с точкой перед нетерминалом, например E → E + B, указывает, что синтаксический анализатор ожидает разобрать нетерминал B следующим. Чтобы гарантировать, что набор элементов содержит все возможные правила, которые синтаксический анализатор может выполнять в процессе синтаксического анализа, он должен включать все элементы, описывающие, как будет анализироваться сам B. Это означает, что если существуют такие правила, как B → 1 и B → 0, то набор элементов должен также включать элементы B → 1 и B → 0. В общем, это можно сформулировать следующим образом:

Если есть элемент формы Av Bw в наборе элементов и в грамматике есть правило формы Bw ', то элемент B w' также должен быть в наборе элементов.

Закрытие наборов предметов

Таким образом, любой набор элементов может быть расширен путем рекурсивного добавления всех соответствующих элементов, пока не будут учтены все нетерминалы, которым предшествуют точки. Минимальное расширение называется закрытием набора элементов и записывается как clos ( I ), где I - набор элементов. Именно эти закрытые наборы элементов принимаются в качестве состояний анализатора, хотя в таблицы будут включены только те, которые фактически достижимы из начального состояния.

Расширенная грамматика

Прежде чем переходы между различными состояниями будут определены, грамматика дополняется дополнительным правилом

(0) S → E eof

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

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

(0) S → E eof
(1) E → E * B
(2) E → E + B
(3) E → B
(4) B → 0
(5) B → 1

Именно для этой расширенной грамматики будут определяться наборы элементов и переходы между ними.

Конструкция стола

Поиск доступных наборов предметов и переходов между ними

Первый шаг построения таблиц состоит в определении переходов между закрытыми наборами элементов. Эти переходы будут определяться так, как если бы мы рассматривали конечный автомат, который может читать как терминалы, так и нетерминалы. Начальным состоянием этого автомата всегда является закрытие первого элемента добавленного правила: S → E:

Набор предметов 0
S → E eof
+ E → E * B
+ E → E + B
+ E → B
+ B → 0
+ B → 1

Жирным шрифтом « + » в передней части элемента указывает на то, что элементы , которые были добавлены к закрытию (не следует путать с математическим «+» оператора , который является терминал). Исходные элементы без " + " называются ядром набора элементов.

Начиная с начального состояния (S0), теперь определены все состояния, которые могут быть достигнуты из этого состояния. Возможные переходы для набора элементов можно найти, посмотрев на символы (терминалы и нетерминалы), следующие за точками; в случае набора элементов 0 этими символами являются терминалы «0» и «1» и нетерминалы E и B. Чтобы найти набор элементов, к которому ведет каждый символ , для каждого из символов выполняют следующую процедуру:

  1. Возьмите подмножество S всех элементов в текущем наборе элементов, где есть точка перед интересующим символом, x .
  2. Для каждого элемента в S переместите точку справа от x .
  3. Закройте получившийся набор предметов.

Для терминала «0» (т.е. где x = «0») это приводит к:

Набор предметов 1
B → 0

и для терминала '1' (т.е. где x = '1') это приводит к:

Набор предметов 2
B → 1

и для нетерминального E (т.е. где x = E) это приводит к:

Набор предметов 3
S → E eof
E → E * B
E → E + B

и для нетерминала B (т.е. где x = B) это приводит к:

Набор предметов 4
E → B

Замыкание не во всех случаях добавляет новые элементы - в новых наборах выше, например, нет нетерминалов после точки.

Вышеуказанная процедура продолжается до тех пор, пока не перестанут быть найдены новые наборы предметов. Для наборов элементов 1, 2 и 4 не будет никаких переходов, поскольку точка не находится перед каким-либо символом. Однако для набора элементов 3 у нас есть точки перед клеммами «*» и «+». Для символа переход идет к:

Набор предметов 5
E → E * B
+ B → 0
+ B → 1

а для перехода идет:

Набор предметов 6
E → E + B
+ B → 0
+ B → 1

Теперь начинается третья итерация.

Для набора элементов 5 необходимо учитывать терминалы «0» и «1» и нетерминал B, но результирующие закрытые наборы элементов равны уже найденным наборам элементов 1 и 2, соответственно. Для нетерминала B переход идет к:

Набор предметов 7
E → E * B

Для набора элементов 6 необходимо учитывать терминал «0» и «1» и нетерминал B, но, как и раньше, результирующие наборы элементов для терминалов равны уже найденным наборам элементов 1 и 2. Для нетерминала B переход идет к:

Набор предметов 8
E → E + B

Эти последние наборы элементов 7 и 8 не имеют символов, кроме точек, поэтому новые наборы элементов не добавляются, поэтому процедура создания элементов завершена. Конечный автомат с наборами элементов в качестве состояний показан ниже.

Таблица переходов для автомата теперь выглядит следующим образом:

Набор предметов * + 0 1 E B
0     1 2 3 4
1            
2            
3 5 6        
4            
5     1 2   7
6     1 2   8
7            
8            

Создание таблиц действий и перехода

Из этой таблицы и найденных наборов элементов таблица действий и перехода строятся следующим образом:

  1. Столбцы для нетерминалов копируются в таблицу перехода.
  2. Столбцы для терминалов копируются в таблицу действий как действия сдвига.
  3. В таблицу действий добавляется дополнительный столбец для '$' (конец ввода), который содержит acc для каждого набора элементов, который содержит элемент формы S → w eof.
  4. Если набор i элементов содержит элемент формы Aw и Aw является правилом m с m > 0, то строка для состояния i в таблице действий полностью заполняется действием сокращения r m .

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

Замечание о LR (0) в сравнении с парсингом SLR и LALR

Только шаг 4 вышеупомянутой процедуры производит действия сокращения, и поэтому все действия сокращения должны занимать всю строку таблицы, в результате чего сокращение происходит независимо от следующего символа во входном потоке. Вот почему это таблицы синтаксического анализа LR (0): они не выполняют никакого предварительного просмотра (то есть они просматривают нулевые символы), прежде чем решить, какое сокращение следует выполнить. Грамматика, которая требует упреждения для устранения неоднозначности сокращений, потребует строки таблицы синтаксического анализа, содержащей различные действия сокращения в разных столбцах, а описанная выше процедура не способна создавать такие строки.

Уточнения процедуры построения таблицы LR (0) (например, SLR и LALR ) позволяют создавать действия сокращения, которые не занимают целые строки. Следовательно, они способны анализировать больше грамматик, чем парсеры LR (0).

Конфликты в построенных таблицах

Автомат устроен таким образом, что он гарантированно детерминирован. Однако, когда действия сокращения добавляются в таблицу действий, может случиться так, что одна и та же ячейка будет заполнена действием уменьшения и действием сдвига ( конфликт сдвига-уменьшения ) или двумя разными действиями уменьшения ( конфликт уменьшения-уменьшения ). Однако можно показать, что когда это происходит, грамматика не является грамматикой LR (0). Классическим реальным примером конфликта сдвига-уменьшения является проблема с висячим else .

Небольшой пример грамматики, отличной от LR (0), с конфликтом сдвиг-уменьшение:

(1) E → 1 E
(2) E → 1

Один из найденных наборов предметов:

Набор предметов 1
E → 1 E
E → 1
+ E → 1 E
+ E → 1

В этом наборе элементов существует конфликт сдвига-уменьшения: при построении таблицы действий в соответствии с приведенными выше правилами ячейка для [набор элементов 1, терминал '1'] содержит s1 (переход в состояние 1) и r2 (сокращение с помощью грамматики правило 2).

Небольшой пример грамматики, отличной от LR (0), с конфликтом уменьшения-уменьшения:

(1) E → A 1
(2) E → B 2
(3) А → 1
(4) B → 1

В этом случае получается следующий набор предметов:

Набор предметов 1
A → 1
B → 1

В этом наборе элементов существует конфликт уменьшения-уменьшения, поскольку в ячейках в таблице действий для этого набора элементов будет действие уменьшения для правила 3 ​​и одно для правила 4.

Оба приведенных выше примера могут быть решены путем разрешения синтаксическому анализатору использовать следующий набор (см. LL-синтаксический анализатор ) нетерминала A, чтобы решить, будет ли он использовать одно из правил A для сокращения; он будет использовать только правило Aш для уменьшения , если следующий символ на входном потоке в последующих множества A . Результатом этого решения являются так называемые простые парсеры LR .

Смотрите также

использованная литература

дальнейшее чтение

внешние ссылки