В информатике простой LR или SLR-анализатор — это тип LR-анализатора с небольшими таблицами анализа и относительно простым алгоритмом генератора анализаторов. Как и другие типы LR(1)-анализаторов, SLR-анализатор довольно эффективен при поиске единственного правильного анализа снизу вверх за один проход слева направо по входному потоку, без догадок или возвратов. Анализатор механически генерируется из формальной грамматики языка.
SLR и более общие методы LALR parser и Canonical LR parser имеют идентичные методы и похожие таблицы во время анализа; они отличаются только алгоритмами анализа математической грамматики, используемыми инструментом генератора парсера. Генераторы SLR и LALR создают таблицы одинакового размера и идентичных состояний парсера. Генераторы SLR принимают меньше грамматик, чем генераторы LALR, такие как yacc и Bison . Многие компьютерные языки нелегко вписываются в ограничения SLR, как есть. Преобразование естественной грамматики языка в форму грамматики SLR требует больше компромиссов и грамматических хакерских трюков. Поэтому генераторы LALR стали гораздо более широко использоваться, чем генераторы SLR, несмотря на то, что являются несколько более сложными инструментами. Методы SLR остаются полезным этапом обучения на занятиях в колледже по теории компиляторов.
SLR и LALR были разработаны Фрэнком ДеРемером как первые практические примеры использования теории LR-анализатора Дональда Кнута . [ требуется ссылка ] Таблицы, созданные для реальных грамматик с помощью полных методов LR, были непрактично большими, больше, чем большинство компьютерных запоминающих устройств того десятилетия, и имели в 100 раз больше состояний анализатора, чем методы SLR и LALR. [ требуется ссылка ] .
Чтобы понять различия между SLR и LALR, важно понимать их многочисленные сходства и то, как они оба принимают решения о сдвиге-сокращении. (См. статью LR parser now для получения дополнительной информации, вплоть до раздела о наборах опережающих просмотров сокращений .)
Единственное различие между SLR и LALR заключается в том, как их генераторы вычисляют опережающие наборы входных символов, которые должны появиться следующими, когда будет найдено и сокращено некоторое завершенное правило продукций .
Генераторы SLR вычисляют этот lookahead простым методом приближения, основанным непосредственно на грамматике, игнорируя детали отдельных состояний и переходов парсера. Это игнорирует конкретный контекст текущего состояния парсера. Если некоторый нетерминальный символ S используется в нескольких местах в грамматике, SLR обрабатывает эти места одним и тем же способом, а не обрабатывает их по отдельности. Генератор SLR вычисляет Follow(S), набор всех терминальных символов, которые могут непосредственно следовать за некоторым вхождением S . В таблице разбора каждое сокращение до S использует Follow(S) в качестве своего набора LR(1) lookahead. Такие наборы follow также используются генераторами для LL-анализаторов сверху вниз. Грамматика, в которой нет конфликтов сдвиг/сокращение или сокращение/сокращение при использовании наборов follow, называется грамматикой SLR .
Генераторы LALR вычисляют наборы lookahead более точным методом, основанным на исследовании графа состояний парсера и их переходов. Этот метод учитывает конкретный контекст текущего состояния парсера. Он настраивает обработку каждого вхождения грамматики некоторого нетерминального S. См. статью Парсер LALR для получения дополнительных сведений об этом расчете. Наборы lookahead, вычисляемые генераторами LALR, являются подмножеством (и, следовательно, лучше) приближенных наборов, вычисляемых генераторами SLR. Если грамматика имеет конфликты таблиц при использовании наборов follow SLR, но не имеет конфликтов при использовании наборов follow LALR, она называется грамматикой LALR.
Грамматика, которая может быть проанализирована анализатором SLR, но не анализатором LR(0), выглядит следующим образом:
Построение таблицы действий и перехода, как это делается для парсеров LR(0), даст следующие наборы элементов и таблицы:
Таблицы действий и переходов:
Как можно заметить, существует конфликт сдвиг-свертка для состояния 1 и терминала '1'. Это происходит потому, что при создании таблицы действий для анализатора LR(0) действия свертки вставляются на основе строк. Однако, используя набор следования, действия свертки можно добавлять с более тонкой гранулярностью. Набор следования для этой грамматики:
Сокращение необходимо добавлять только в определенный столбец действий, если это действие находится в следующем наборе, связанном с этим сокращением. Этот алгоритм описывает, должно ли действие сокращения быть добавлено в столбец действий:
функция mustBeAdded(reduceAction, действие) { ruleNumber = reduceAction.value; ruleSymbol = rules[номер_правила].leftHandSide; возврат (действие в followSet(ruleSymbol))}например, mustBeAdded(r2, "1")ложно, потому что левая часть правила 2 — «E», а 1 не входит в набор последователей E. Наоборот, mustBeAdded(r2, "$")истинно, потому что «$» входит в набор последователей E.
Используя mustBeAdded для каждого действия reduce в таблице действий, мы получаем таблицу действий без конфликтов: