Простой парсер LR

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

SLR и более общие методы. Анализатор LALR и анализатор Canonical LR имеют идентичные методы и схожие таблицы во время анализа; они отличаются только алгоритмами математического анализа грамматики, используемыми инструментом-генератором синтаксического анализатора. Генераторы SLR и LALR создают таблицы одинакового размера и одинаковых состояний анализатора. Генераторы SLR принимают меньше грамматик, чем генераторы LALR, такие как yacc и Bison . Многие компьютерные языки не всегда соответствуют ограничениям SLR. Преобразование естественной грамматики языка в форму грамматики SLR требует большего количества компромиссов и грамматических хакерских действий. Таким образом, генераторы LALR стали гораздо более широко использоваться, чем генераторы SLR, несмотря на то, что они являются несколько более сложными инструментами. Методы SLR остаются полезным этапом обучения на курсах в колледже по теории компиляторов.

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

Упреждающие наборы

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

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

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

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

Пример

Грамматика, которая может быть проанализирована анализатором SLR, но не анализатором LR(0), выглядит следующим образом:

(0) С → Е

(1) Э → 1 Э

(2) Э → 1

Построение таблицы действий и перехода, как это делается для парсеров LR(0), даст следующие наборы элементов и таблицы:

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

С → • Е

+ Э → • 1 Э

+ Е → • 1

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

Е → 1 • Е

Э → 1 •

+ Э → • 1 Э

+ Е → • 1

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

С → Е •

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

Э → 1 Э •

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

	действие		перейти к
состояние	1	$	И
0	с1		2
1	с1/р2	р2	3
2		соотв.
3	р1	р1

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

символ	С	И	1
следующий	$	$	1,$

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

function mustBeAdded(reduceAction, action) {
    ruleNumber = reduceAction.value;
    ruleSymbol = rules[ruleNumber].leftHandSide;
    return (action in followSet(ruleSymbol))
}

например, mustBeAdded(r2, "1") является ложным, поскольку левая часть правила 2 равна «E», а число 1 не входит в следующий набор E. Напротив, mustBeAdded(r2, "$") верно, потому что "$" находится в следующем наборе E.

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

	действие		перейти к
состояние	1	$	И
0	с1		2
1	с1	р2	3
2		соотв.
3		р1

См. также

• LR-парсер
• LL-парсер
• LALR-парсер
• Грамматика SLR