Оба парсера LR (0) и SLR (1) имеют значение восходящий, направленный, прогнозирующий парсер . Это означает, что
- Парсеры пытаются применить производство в обратном порядке, чтобы уменьшить вводимое предложение до начального символа ( снизу вверх )
- Парсеры сканируют ввод слева направо ( Направленный )
- Синтаксические анализаторы пытаются предсказать, какие сокращения применить, не обязательно просматривая все входные данные ( прогнозирующий )
И LR (0), и SLR (1) - это парсеры сдвига / уменьшения , что означает, что они обрабатывают токены входного потока, помещая их в стек, и в каждой точке либо сдвиг токена путем помещения его в стек или уменьшения некоторой последовательности терминалов и нетерминалов на вершине стека до некоторого нетерминального символа. Можно показать, что любая грамматика может быть проанализирована снизу вверх с использованием синтаксического анализатора сдвига / уменьшения, но этот синтаксический анализатор может не быть детерминированным . То есть синтаксическому анализатору, возможно, придется «угадать», применять ли сдвиг или уменьшение, и может в конечном итоге вернуться назад, чтобы понять, что он сделал неправильный выбор. Независимо от того, насколько мощный детерминированный парсер сдвига / уменьшения вы создадите, он никогда не сможет проанализировать все грамматики.
Когда для анализа грамматики, которую он не может обработать, используется детерминированный парсер сдвига / уменьшения, это приводит к конфликтам сдвига / уменьшения или конфликтам уменьшения / уменьшения , где парсер может введите состояние, в котором он не может сказать, какое действие предпринять. В конфликте сдвига / уменьшения он не может сказать, должен ли он добавить еще один символ в стек или выполнить некоторое сокращение для верхних символов стека. В конфликте уменьшения / уменьшения синтаксический анализатор знает, что ему нужно заменить верхние символы стека на некоторые нетерминальные, но он не может сказать, какое сокращение использовать.
Я прошу прощения, если это длинное изложение, но нам нужно это, чтобы иметь возможность учесть разницу между синтаксическим анализом LR (0) и SLR (1). Синтаксический анализатор LR (0) - это анализатор сдвига / уменьшения, который использует нулевые маркеры упреждения, чтобы определить, какое действие предпринять (отсюда 0). Это означает, что в любой конфигурации парсера у парсера должно быть однозначное действие, чтобы выбрать - либо он сдвигает определенный символ, либо применяет определенную редукцию. Если когда-либо есть два или более выбора, синтаксический анализатор завершается неудачно, и мы говорим, что грамматика не является LR (0).
Напомним, что двумя возможными конфликтами LR являются сдвиг / уменьшение и уменьшение / уменьшение. В обоих этих случаях есть, по крайней мере, два действия, которые может выполнять автомат LR (0), и он не может сказать, какое из них использовать. Поскольку по крайней мере одно из конфликтующих действий является сокращением, разумной линией атаки было бы попытаться заставить синтаксический анализатор быть более осторожным при выполнении определенного сокращения. Более конкретно, давайте предположим, что анализатору разрешено просматривать следующий токен ввода, чтобы определить, должен ли он сдвигаться или уменьшаться. Если мы позволяем синтаксическому анализатору сокращаться только тогда, когда это «имеет смысл» (для некоторого определения «имеет смысл»), то мы можем устранить конфликт, если автомат специально выберет либо сдвиг, либо уменьшение в конкретный шаг.
В SLR (1) («Упрощенный LR (1)») синтаксическому анализатору разрешается просматривать один токен предпросмотра при принятии решения о его смещении или уменьшении. В частности, когда парсер хочет попытаться уменьшить что-то в форме A & rarr; w (для нетерминала A и строки w), он смотрит на следующий токен ввода. Если этот токен мог бы легально появиться после нетерминала A в некотором производном, синтаксический анализатор уменьшается. В противном случае это не так. Интуиция здесь заключается в том, что в некоторых случаях нет смысла пытаться выполнить сокращение, потому что с учетом токенов, которые мы видели до этого, и готовящегося токена, нет никакого способа, которым сокращение могло бы быть правильным.
Единственная разница между LR (0) и SLR (1) заключается в этой дополнительной способности помочь решить, какие действия предпринять в случае возникновения конфликтов. Из-за этого любая грамматика, которая может быть проанализирована парсером LR (0), может быть проанализирована парсером SLR (1). Однако анализаторы SLR (1) могут анализировать большее количество грамматик, чем LR (0).
Однако на практике SLR (1) все еще является довольно слабым методом анализа. Чаще всего вы увидите парсеры LALR (1) («Lookahead LR (1)»). Они тоже работают, пытаясь разрешить конфликты в синтаксическом анализаторе LR (0), но правила, которые они используют для разрешения конфликтов, гораздо более точные, чем те, которые используются в SLR (1), и, следовательно, гораздо большее количество грамматик - LALR (1). чем зеркалки (1). Чтобы быть более конкретным, анализаторы SLR (1) пытаются разрешать конфликты, просматривая структуру грамматики, чтобы узнать больше информации о том, когда сдвигать, а когда уменьшать. Парсеры LALR (1) проверяют грамматику и парсер LR (0), чтобы получить еще более конкретную информацию о том, когда сдвигать, а когда уменьшать. Поскольку LALR (1) может посмотреть на структуру синтаксического анализатора LR (0), он может более точно определить, когда определенные конфликты являются ложными. Утилиты Linux yacc и bison по умолчанию создают парсеры LALR (1).
Исторически парсеры LALR (1) обычно создавались с помощью другого метода, основанного на гораздо более мощном парсере LR (1), поэтому вы часто будете видеть, как LALR (1) описывается таким образом. Чтобы понять это, нам нужно поговорить о парсерах LR (1). В парсере LR (0) он работает, отслеживая, где он может находиться в середине производства. Как только он обнаружил, что он достиг конца производства, он знает, чтобы попытаться сократить. Однако синтаксический анализатор может не определить, находится ли он в конце одного производства и в середине другого, что приводит к конфликту сдвиг / уменьшение, или в каком из двух различных производств он достиг конца (сокращение / уменьшить конфликт). В LR (0) это немедленно приводит к конфликту, и синтаксический анализатор терпит неудачу. В SLR (1) или LALR (1) синтаксический анализатор затем принимает решение о смещении или уменьшении на основе следующего токена просмотра.
В парсере LR (1) парсер отслеживает дополнительную информацию во время работы. В дополнение к отслеживанию того, какое производство, по мнению парсера, используется, оно отслеживает возможные маркеры, которые могут появиться после завершения этого производства. Поскольку синтаксический анализатор отслеживает эту информацию на каждом этапе, а не только когда ему необходимо принять решение, синтаксический анализатор LR (1) существенно более мощный и точный, чем любой из LR (0), SLR (1) или LALR (1) парсеры, о которых мы говорили до сих пор. LR (1) является чрезвычайно мощной техникой синтаксического анализа, и с помощью некоторой хитрой математики можно показать, что любой язык, который может быть детерминированно проанализирован с помощью любого синтаксического анализатора смещения / уменьшения, имеет некоторую грамматику, которая может быть проанализирована с помощью LR (1) автомат. (Обратите внимание, что это не означает, что все грамматики , которые могут быть проанализированы детерминистически, являются LR (1); это только говорит о том, что язык, который может быть проанализирован детерминистически, имеет некоторую грамматику LR (1)). Однако эта мощность имеет свою цену, и сгенерированный парсер LR (1) может потребовать столько информации для работы, что он не может быть использован на практике. Например, анализатор LR (1) для реального языка программирования может потребовать от десятков до сотен мегабайт дополнительной информации для правильной работы. По этой причине LR (1) обычно не используется на практике, и вместо него используются более слабые парсеры, такие как LALR (1) или SLR (1).
Совсем недавно новый алгоритм синтаксического анализа под названием GLR (0) («Обобщенный LR (0)») приобрел популярность. Вместо того, чтобы пытаться разрешить конфликты, возникающие в синтаксическом анализаторе LR (0), анализатор GLR (0) вместо этого работает, пробуя все возможные варианты параллельно. Используя некоторые хитрые трюки, это можно сделать очень эффективно для многих грамматик. Более того, GLR (0) может анализировать любой неконтекстной грамматики на всех , даже грамматики, которые не могут быть проанализированы анализатором LR (k) для любого k. Другие парсеры также могут это делать (например, парсер Earley или парсер CYK), хотя GLR (0) имеет тенденцию быть быстрее на практике.
Если вы заинтересованы в получении дополнительной информации, этим летом я преподавал вводный курс по компиляторам и потратил чуть меньше двух недель на разговоры о методах синтаксического анализа. Если вы хотите получить более подробное представление о LR (0), SLR (1) и множестве других мощных методов синтаксического анализа, вам могут понравиться мои слайды с лекциями и домашние задания о разборе. Все материалы курса доступны здесь, на моем личном сайте .
Надеюсь, это поможет!