Операция замыкания

Построение таблиц SLR-анализа

Существуют разные метода, отличающиеся по мощности и сложности реализации. Самый простой в реализации метод — метод "простого LR" (simple LR, SLR) анализа, — самый слабый по количеству грамматик, с которыми он работает. Таблица, по­строенная таким методом, называется SLR-таблицей, а синтаксический анализатор, работающий с SLR-таблицей,— SLR-анализатором (соответствующую грамматику — SLR-грамматикой).

При построении таблиц вводится понятие пункта.

LR(0)-пункт, или элемент грамматики G— продукция Gс точкой в некоторой позиции правой части.

Например, продукция А → XYZ дает четыре пункта:

А→ • XYZ

А→ X • YZ

А→ XY • Z

А→ XYZ •

Продукция А→ λ генерирует только один пункт, A → •.

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

Например, первый пункт, приведен­ный выше, определяет, что во входном потоке мы ожидаем встретить строку, порождае­мую XYZ. Второй пункт указывает, что уже есть строка, порожденная X, и мы ожи­даем получить из входного потока строку, порождаемую YZ.

Основная идея SLR-метода состоит в том, чтобы вначале построить на базе грамма­тики детерминированный конечный автомат для распознавания активных префиксов. Группируем пункты в множества, которые приводят к состояниям SLR-анализатора. Пункты могут рассматриваться как состояния недетерминированного конечного автома­та, распознающего активные префиксы. Система LR(0)-пунктов, которая называется канонической, обеспечивает основу для по­строения SLR-анализаторов.

Для построения канонической LR(0)-системы грамматики необходимо определить расширенную грамматику и две функции — closure и goto.

Если G — грамматика со стартовым символом S, то G', расширенная грамматика грамматики G, представляет собой G с новым стартовым симво­лом S ' и продукцией S' → S. Назначение этой новой стартовой продукции — указать синтаксическому анализатору, когда он должен прекратить разбор и объявить о допущении входной строки. Таким образом, допуск строки происходит тогда, когда синтаксический анализатор выполняет свертку, соответствующую продук­ции S' →S.

Если I — множество пунктов грамматики G, то closure(I) — множество пунктов, построенное из I по следующим правилам.

1. Изначально в closure(I) входят все пункты из I.

2. Если А → α • Вβ входит в closure(I) и В → γ представляет собой продукцию, то добавляем в closure(I) пункт В → •γ (если его там еще нет). Это правило применяется до тех пор, пока не будут внесены все возможные пункты в closure(I).

Наличие А → α • Вβ в closure(I) указывает, что в некоторый момент в процессе синтаксического анализа можно встретить во входном потоке под­строку, выводимую из Bβ. Но если имеется продукция В → γ, то, естественно, можно встретить в этот момент строку, выводимую из γ, поэтому В → • γ включается в closure(I) [3].

Дата добавления: 2014-12-27