В чем разница между LR(0) и SLR parsing?

оба парсера LR(0) и SLR(1) являются восходящие, направленные, прогнозирующие Парсеры. Это значит, что

• синтаксические анализаторы пытаются применить производство в обратном порядке, чтобы уменьшить входное предложение обратно к символу начала (снизу-вверх)
• Парсеры сканируют входные данные слева направо (направленного)
• Парсеры пытаются предсказать, какие сокращения применять, не обязательно видя все входные данные (словарь)

оба LR (0) и SLR(1) являются сдвиг / уменьшение парсеров, что означает, что они обрабатывают маркеры входного потока, помещая их в стек, и в каждой точке либо сдвиг токен, нажав его в стек или сокращение некоторая последовательность терминалов и нетерминалов на вершине стека возвращается к некоторому нетерминальному символу. Можно показать, что любая грамматика может быть проанализирована снизу вверх с помощью shift / reduce парсер, но этот парсер не может быть детерминированные. То есть, парсер может "угадать", применять ли сдвиг или сокращение, и может в конечном итоге вернуться, чтобы понять, что он сделал неправильный выбор. Независимо от того, насколько мощный детерминированный парсер сдвига/уменьшения вы строите, он никогда не сможет проанализировать все грамматики.

когда детерминированный парсер shift / reduce используется для анализа грамматики, которую он не может обработать, это приводит к сдвиг/уменьшить конфликты или уменьшить/уменьшить конфликты, где парсер может войти в состояние, в котором он не может сказать, какое действие предпринять. В конфликте shift/reduce он не может сказать, должен ли он добавить другой символ в стек или выполнить некоторое сокращение на верхних символах стека. В конфликте reduce/reduce синтаксический анализатор знает, что ему нужно заменить верхние символы стека на некоторые нетерминальные, но он не может сказать, какое сокращение использовать.

прошу прощения, если это длинная экспозиция, но нам нужно это, чтобы иметь возможность решить разницу между разбором LR(0) и SLR(1). Парсер LR(0) - это парсер сдвига/уменьшения, который использует нулевые маркеры lookahead для определения того, какое действие предпринять (следовательно, 0). Это означает, что в любой конфигурации парсера парсер должен иметь однозначное действие для выбора - либо он сдвигает определенный символ, либо применяет определенное сокращение. Если есть когда-либо два или более вариантов, чтобы сделать, парсер терпит неудачу, и мы говорим что грамматика не LR (0).

Напомним, что двумя возможными конфликтами LR являются shift/reduce и reduce / reduce. В обоих этих случаях есть по крайней мере два действия, которые может выполнять автомат LR(0), и он не может сказать, какой из них использовать. Поскольку по крайней мере одно из конфликтующих действий является сокращением, разумной линией атаки было бы попытаться заставить парсер быть более осторожным, когда он выполняет определенное сокращение. Более конкретно, предположим, что парсер может посмотреть на следующий маркер ввода, чтобы определить, следует ли его сдвигать или уменьшать. Если мы позволим парсеру уменьшать только тогда, когда это" имеет смысл "(для некоторого определения" имеет смысл"), тогда мы сможем устранить конфликт, если автомат специально выберет либо сдвиг, либо уменьшение на определенном шаге.

в SLR(1) ("упрощенный LR(1)") синтаксическому анализатору разрешено смотреть на один маркер lookahead при принятии решения о том, должен ли он сдвигаться или уменьшить. В частности, когда парсер хочет попробовать уменьшить что-то из формы A → w (для нетерминального A и строки w), он смотрит на следующий маркер ввода. Если этот токен может законно появиться после нетерминального A в некотором выводе, синтаксический анализатор уменьшает. В противном случае, это не так. Интуиция здесь заключается в том, что в некоторых случаях нет смысла пытаться сократить, потому что, учитывая токены, которые мы видели до сих пор, и предстоящий токен, невозможно, чтобы сокращение когда-либо могло быть правильный.

на практике, однако, SLR (1) по-прежнему является довольно слабым методом разбора. Чаще всего, вы увидите LALR(1) ("впередсмотрящих ЛР(1)") анализаторов используется. Они слишком много работы, пытаясь разрешить конфликты в парсере LR(0), но правила, которые они используют для разрешения конфликтов, гораздо более точны, чем те, которые используются в SLR(1), и, следовательно, гораздо большее количество грамматик lalr(1), чем SLR(1). Чтобы быть немного более конкретным, синтаксические анализаторы SLR(1) пытаются разрешить конфликты, глядя на структуру грамматики, чтобы узнать больше информации о том, когда сдвигать и когда уменьшать. Lalr (1) Парсеры посмотрите на грамматику и парсер LR (0), чтобы получить еще больше конкретная информация о том, когда сдвигать и когда уменьшать. Поскольку LALR(1) может посмотреть на структуру парсера LR (0), он может более точно определить, когда некоторые конфликты являются ложными. Утилиты Linux yacc и bison по умолчанию, производят LALR(1) парсеров.

в парсере LR(1) парсер отслеживает дополнительную информацию по мере ее работы. В дополнение к отслеживанию того, какое производство, по мнению парсера, используется, он отслеживает, какие возможные токены могут появиться после завершения этого производства. Потому что парсер отслеживает это информация на каждом шаге, а не только тогда, когда он должен принять решение, парсер LR(1) является существенно более мощным и точным, чем любой из парсеров LR(0), SLR(1) или LALR(1), о которых мы говорили до сих пор. LR(1) - чрезвычайно мощная техника синтаксического анализа, и ее можно показать с помощью некоторой сложной математики, что любой язык, который может быть детерминирован любой shift / reduce parser имеет некоторую грамматику, которая может быть проанализирована с помощью автомата LR(1). (Отметим, что это не значит, что все грамматик которые могут быть проанализированы детерминированно являются LR(1); это говорит только о том, что язык, который может быть проанализирован детерминированно, имеет некоторую грамматику LR (1). Однако эта мощность имеет свою цену, и сгенерированный парсер LR(1) может потребовать столько информации для работы, что он не может быть использован на практике. Например, парсер LR(1) для реального языка программирования может потребовать от десятков до сотен мегабайт дополнительной информации для правильной работы. Для по этой причине LR(1) обычно не используется на практике, а вместо этого используются более слабые Парсеры, такие как LALR(1) или SLR(1).

совсем недавно новый алгоритм разбора под названием GLR(0) ("Generalized LR(0)") приобрел популярность. Вместо того, чтобы пытаться разрешить конфликты, которые появляются в парсере LR(0), парсер GLR(0) вместо этого работает, пробуя все возможные варианты параллельно. Используя некоторые хитрые трюки, это может быть сделано, чтобы работать очень эффективно для многих грамматик. Кроме того, GLR (0) может анализировать любая контекстно-свободная грамматика вообще, даже грамматики, которые не могут быть проанализированы парсером LR(k) для любого k. другие Парсеры также способны делать это (например, парсер Earley или парсер CYK), хотя GLR(0) имеет тенденцию быть быстрее на практике.

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

надеюсь, что это помогает!