В чем разница между анализом LALR и LR?

Ответ 1

На высоком уровне разница между LR (0), LALR (1) и LR (1) заключается в следующем:

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

• Парсеры LALR (1) имеют постоянный коэффициент больше, чем парсеры LR (0), а парсеры LR (1) обычно экспоненциально больше, чем парсеры LALR (1).

• Любая грамматика, которая может быть проанализирована с помощью синтаксического анализатора LR (0), может быть проанализирована с помощью анализатора LALR (1), а любая грамматика, которая может быть проанализирована с помощью синтаксического анализатора LALR (1), может быть проанализирована с помощью анализатора LR (1). Есть грамматики, которые являются LALR (1), но не LR (0) и LR (1), но не LALR (1).

Более формально, анализатор LR (k) - это анализатор снизу вверх, который работает, поддерживая стек терминалов и нетерминалов. Синтаксический анализатор управляется конечным автоматом, который на основе текущего состояния синтаксического анализатора и следующих k входных токенов определяет, следует ли перемещать новый токен в стек или уменьшать верхние символы стека, применяя обратную обработку,

Чтобы отслеживать достаточно информации, чтобы определить, сдвигать или уменьшать, парсеры LR (k) имеют каждое состояние, соответствующее "конфигурирующему набору", набору производств, помеченному следующей информацией:

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

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

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

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

Проблема парсеров LR (k) состоит в том, что с увеличением k число состояний может экспоненциально возрастать. Ожидание в синтаксических анализаторах LR (k) обрабатывается путем создания в синтаксическом анализаторе все большего и большего количества состояний, соответствующих различным комбинациям производств и просмотров, так что с увеличением числа возможных просмотров увеличивается число состояний. Следовательно, парсеры LR (1) обычно слишком велики, чтобы быть практичными, а на практике LR (2) или выше практически не слышны.

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

Другое представление грамматик LALR (1) использует метод "LALR by-SLR". Синтаксические анализаторы LALR (1) можно создать, начиная с синтаксического анализатора LR (0) для грамматики, затем создавая новую грамматику для языка, которая аннотирует нетерминалы информацией о том, каким состояниям в синтаксическом анализаторе LR (0) они соответствуют. Информация о наборах FOLLOW для нетерминалов в этой грамматике затем может быть использована для вычисления ориентиров в синтаксическом анализаторе LR (0).

Чистый результат заключается в том, что

• Парсеры LR (0) небольшие, но не очень выразительные.
• Парсеры LALR (1) немного больше из-за предварительной информации, но очень выразительны.
• Парсеры LR (1) огромны, но чрезвычайно выразительны.

Что касается вашего второго вопроса - как вы определяете, является ли грамматика LR (1) или LALR (1) - стандартный подход состоит в том, чтобы попытаться построить автоматы синтаксического анализа для анализатора LR (1) и анализатора LALR (1) и проверки для конфликтов. Чтобы создать синтаксический анализатор LR (1), вы создаете конфигурационные наборы LR (1), а затем проверяете, есть ли у какого-либо из этих конфигурационных наборов конфликт сдвига/уменьшения или уменьшения/уменьшения. Чтобы создать синтаксический анализатор LALR (1), вы можете либо создать синтаксический анализатор LR (1), а затем сжать конфигурирующие множества с тем же ядром, либо использовать метод LALR by-SLR, основанный на синтаксическом анализаторе LR (0) для языка. Более подробную информацию о том, как создать эти наборы настроек, можно найти в большинстве учебников по компиляторам. Вы также можете ознакомиться с примечаниями к лекциям курса компиляторов, который я преподавал летом 2012 года, которые охватывают все перечисленные выше методы синтаксического анализа и некоторые другие.

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

Ответ 2

Алгоритм синтаксического анализа для хорошего парсера LALR (1) отличается двумя способами: (1) он должен иметь действия с уменьшением смещения, что уменьшает число состояний примерно на 30% и делает парсер быстрее, и (2) он должен сделать одно или несколько сокращений при обнаружении синтаксической ошибки, что усложняет восстановление после ошибки.

Алгоритм синтаксического анализа для канонического анализатора LR (1) (1) не имеет действий уменьшения сдвига и (2) не делает никаких сокращений при обнаружении синтаксической ошибки, что упрощает восстановление после ошибки.

Существует еще один случай, называемый минимальным LR (1), в котором используется тот же алгоритм синтаксического анализа и алгоритм восстановления после ошибок, что и LALR (1). Минимальные парсеры LR (1) имеют мощность LR (1), а их размер почти такой же, как LALR (1). Генератор синтаксических анализаторов LRSTAR создает минимальные анализаторы LR (1) для программистов C++.

Ответ 3

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

У канонических LR (1) парсеров будет много состояний, слишком много для средних или больших компьютерных языков.

Генераторы парсеров SLR (1) создают конечный автомат LR (0) и определяют k = 1 lookaheads, изучая грамматику (которая может сообщать о ошибочных конфликтах).

Генераторы парсеров LALR (1) строят конечный автомат LR (0) и определяют k = 1 lookaheads путем изучения конечного автомата LR (0) (что очень сложно).

Генераторы парсера Canonical LR (1) строят конечный автомат LR (1).

Генераторы-генераторы минимального LR (1) строят конечный автомат LR (1) и согласованные друг с другом состояния во время процесса сборки.