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