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

Ответ 1

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

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

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

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

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

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

В SLR (1) ( "Упрощенный LR (1)" ) синтаксическому анализатору разрешено смотреть на один токен взгляда при принятии решения о необходимости сдвига или уменьшения. В частности, когда парсер хочет попытаться уменьшить что-то вроде формы A → 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) чем SLR (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) синтаксический анализатор затем принимает решение о сдвиге или уменьшении на основе следующего знака lookahead.

В парсере 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. Другие парсеры также могут это делать (например, анализатор Эрли или анализатор CYK), хотя GLR (0) имеет тенденцию быть более быстрым на практике.

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

Надеюсь, это поможет!

Ответ 2

Это то, что я узнал. Обычно анализатор LR (0) может иметь двусмысленность, то есть одно поле таблицы (вы создаете для создания парсера) может иметь несколько значений (или), чтобы лучше сказать: парсер ведет к двум конечным состояниям с одним и тем же входом. Поэтому для устранения этой двусмысленности создан парсер SLR. Чтобы построить его, найдите все производственные операции, которые приводят к состояниям гото, найдите для производственного символа слева и укажите только те состояния goto, которые присутствуют в следующем. Это inturn означает, что вы не включаете в себя производство, которое невозможно с использованием оригинального грамматика (поскольку это состояние не соответствует следующему набору)