Простой парсер LR - Simple LR parser

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

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

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

Наборы Lookahead

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

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

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

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

Пример

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

(0) S → E

(1) E → 1 E

(2) E → 1

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

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

S → • E

+ E → • 1 E

+ E → • 1

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

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

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

S → E •

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

E → 1 E •

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

	действие		идти к
государственный	1	$	E
0	s1		2
1	s1 / r2	r2	3
2		соотв
3	r1	r1

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

символ	S	E	1
следующий	$	$	1,$

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

функция mustBeAdded (reduceAction, действие) {ruleNumber = reduceAction.value; ruleSymbol = правила [номер правила] .leftHandSide; return (действие в followSet (ruleSymbol))}

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

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

	действие		идти к
государственный	1	$	E
0	s1		2
1	s1	r2	3
2		соотв
3		r1

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

• Парсер LR
• LL парсер
• Парсер LALR
• SLR грамматика