В чем разница между парсерами LR, SLR и LALR?

В чем разница между парсерами LR, SLR и LALR? Я знаю, что SLR и LALR являются типами парсеров LR, но какова реальная разница в их таблицах синтаксического анализа?

И как показать, является ли грамматика LR, SLR или LALR? Для грамматики LL мы просто должны показать, что любая ячейка таблицы синтаксического анализа не должна содержать несколько производственных правил. Есть ли аналогичные правила для LALR, SLR и LR?

Например, как показать, что грамматика

S --> Aa | bAc | dc | bda
A --> d

такое LALR (1), но не SLR (1)?

РЕДАКТИРОВАТЬ (ybungalobill) : я не получил удовлетворительного ответа о том, в чем разница между LALR и LR. Таким образом, таблицы LALR меньше по размеру, но они могут распознавать только подмножество грамматик LR. Может кто-нибудь подробнее рассказать о разнице между LALR и LR, пожалуйста? Для ответа достаточно LALR (1) и LR (1). Оба они используют упреждающий просмотр на 1 токен, и оба управляются таблицей! Чем они разные?

Синтаксические анализаторы SLR, LALR и LR могут быть реализованы с использованием одного и того же механизма, управляемого таблицами.

По сути, алгоритм синтаксического анализа собирает следующий входной токен T и обращается к текущему состоянию S (и связанным таблицам просмотра вперед, GOTO и редукционным таблицам), чтобы решить, что делать:

• SHIFT: если текущая таблица говорит о SHIFT для токена T, пара (S, T) помещается в стек синтаксического анализа, состояние изменяется в соответствии с тем, что таблица GOTO говорит для текущего токена (например, GOTO (T) ), выбирается другой входной токен T ', и процесс повторяется
• УМЕНЬШЕНИЕ: каждое состояние имеет 0, 1 или много возможных сокращений, которые могут произойти в состоянии. Если синтаксическим анализатором является LR или LALR, токен проверяется на соответствие наборам опережающих вычислений для всех допустимых сокращений для состояния. Если маркер соответствует опережающему набору для сокращения для правила грамматики G = R1 R2 .. Rn, происходит сокращение и сдвиг стека: вызывается семантическое действие для G, стек выталкивается n (из Rn) раз, пара ( S, G) помещается в стек, новое состояние S 'устанавливается в GOTO (G), и цикл повторяется с тем же маркером T. Если синтаксический анализатор является синтаксическим анализатором SLR, существует не более одного правила сокращения для состояние, поэтому действие сокращения можно выполнять вслепую, не пытаясь понять, какое сокращение применяется. Парсеру SLR полезно знать, есть ли естьсокращение или нет; это легко определить, если каждое состояние явно записывает количество связанных с ним сокращений, и этот счет в любом случае необходим для версий L (AL) R на практике.
• ОШИБКА: если ни SHIFT, ни REDUCE невозможно, объявляется синтаксическая ошибка.

Итак, если все они используют одно и то же оборудование, в чем смысл?

Предполагаемая ценность SLR - это простота реализации; вам не нужно просматривать возможные сокращения, проверяя наборы опережающих просмотров, потому что существует не более одного, и это единственное жизнеспособное действие, если нет SHIFT-выходов из состояния. Какое сокращение применяется, может быть привязано конкретно к состоянию, поэтому машинному анализу SLR не нужно его искать. На практике парсеры L (AL) R обрабатывают гораздо больший набор языков, и для их реализации требуется так мало дополнительной работы, что никто не реализует SLR, кроме как в качестве академического упражнения.

Разница между LALR и LR связана с генератором таблиц.. Генераторы парсеров LR отслеживают все возможные сокращения из определенных состояний и их точный набор опережающих действий; вы получаете состояния, в которых каждое сокращение связано с его точным опережением, установленным из его левого контекста. Это имеет тенденцию создавать довольно большие наборы состояний. Генераторы парсеров LALR готовы комбинировать состояния, если таблицы GOTO и наборы просмотровых заголовков для сокращений совместимы и не конфликтуют; это приводит к значительно меньшему количеству состояний за счет невозможности различать определенные последовательности символов, которые может различать LR. Таким образом, парсеры LR могут анализировать больший набор языков, чем парсеры LALR, но имеют гораздо большие таблицы парсеров. На практике можно найти грамматики LALR, которые достаточно близки к целевым языкам, поэтому размер конечного автомата стоит оптимизировать;

Итак: все трое используют одно и то же оборудование. SLR «проста» в том смысле, что вы можете игнорировать крошечную часть оборудования, но это не стоит усилий. LR анализирует более широкий набор языков, но таблицы состояний, как правило, довольно большие. Это оставляет LALR как практический выбор.

Сказав все это, стоит знать, что парсеры GLR могут анализировать любой контекстно-свободный язык, используя более сложную технику, но точно такие же таблицы. (включая меньшую версию, используемую LALR). Это означает, что GLR строго более мощный, чем LR, LALR и SLR; в значительной степени, если вы можете написать стандартную грамматику BNF, GLR будет анализировать в соответствии с ней. Различие в механизме состоит в том, что GLR желает попробовать несколько синтаксических разборов, когда есть конфликты между таблицей GOTO и / или наборами опережающего просмотра. (То, как GLR делает это эффективно, гениально [не мое], но не вписывается в этот пост SO).

Для меня это чрезвычайно полезный факт. Я строю программные анализаторы и преобразователи кода, а парсеры необходимы, но «неинтересны»; интересная работа - это то, что вы делаете с анализируемым результатом, поэтому основное внимание уделяется работе после анализа. Использование GLR означает, что я могу относительно легко создавать рабочие грамматики, по сравнению с взломом грамматики, чтобы получить пригодную для использования LALR форму. Это имеет большое значение, когда вы пытаетесь работать с неакадемическими языками, такими как C ++ или Fortran, где вам буквально нужны тысячи правил для правильной обработки всего языка, и вы не хотите тратить свою жизнь, пытаясь взломать правила грамматики, чтобы соответствовать ограничениям LALR (или даже LR).

Как своего рода известный пример, C ++ считается чрезвычайно сложным для синтаксического анализа ... парнями, выполняющими анализ LALR. C ++ легко анализировать с помощью оборудования GLR, используя в значительной степени правила, приведенные в конце справочного руководства C ++. (У меня есть именно такой парсер, и он обрабатывает не только обычный C ++, но также и различные диалекты поставщиков. Это возможно только на практике, потому что мы используем парсер GLR, IMHO).

[РЕДАКТИРОВАТЬ Ноябрь 2011: Мы расширили наш синтаксический анализатор для обработки всего C ++ 11. GLR сделал это намного проще. РЕДАКТИРОВАТЬ Август 2014: теперь обрабатывается весь C ++ 17. Ничего не сломалось и не стало хуже, GLR все еще кошачье мяуканье.]

Анализаторы LALR объединяют похожие состояния в грамматике LR для создания таблиц состояний анализатора, которые имеют точно такой же размер, что и эквивалентная грамматика SLR, которые обычно на порядок меньше, чем таблицы синтаксического анализа чистого LR. Однако для грамматик LR, которые слишком сложны для LALR, эти объединенные состояния приводят к конфликтам синтаксического анализатора или создают синтаксический анализатор, который не полностью распознает исходную грамматику LR.

Кстати, я упомянул несколько вещей об этом в моем алгоритме таблицы синтаксического анализа MLR (k) здесь .

Дополнение

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

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

Недостатком является то, что не все грамматики LR могут быть закодированы как таблицы LALR, потому что более сложные грамматики имеют более сложный просмотр вперед, что приводит к двум или более состояниям вместо одного объединенного состояния.

Основное отличие состоит в том, что алгоритм создания таблиц LR передает больше информации между переходами из состояния в состояние, а алгоритм LALR - нет. Таким образом, алгоритм LALR не может сказать, действительно ли данное объединенное состояние должно быть оставлено как два или более отдельных состояния.

Еще один ответ (ЯА).

Алгоритмы синтаксического анализа для SLR (1), LALR (1) и LR (1) идентичны, как сказал Ира Бакстер:
однако таблицы синтаксического анализатора могут отличаться из-за алгоритма генерации синтаксического анализатора.

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

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

Генератор синтаксического анализатора Canonical LR вычисляет конечный автомат LR (1), а упреждающий просмотр уже является частью конечного автомата LR (1). Эти таблицы парсера могут быть очень большими.

Генератор синтаксического анализатора минимального LR вычисляет конечный автомат LR (1), но объединяет совместимые состояния во время процесса, а затем вычисляет упреждающий просмотр из конечного автомата минимального LR (1). Эти таблицы синтаксического анализатора имеют тот же размер или немного больше, чем таблицы синтаксического анализатора LALR, что дает лучшее решение.

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

[Полное раскрытие: LRSTAR - это мой продукт]

Предположим, что синтаксический анализатор без просмотра вперед успешно разбирает строки для вашей грамматики.

Используя ваш пример, он встречает строку dc, что он делает? Уменьшает ли он его до S, потому что dcэта грамматика производит правильную строку? ИЛИ, может быть, мы пытались разобрать, bdcпотому что даже это приемлемая строка?

Как люди, мы знаем, что ответ прост, нам просто нужно помнить, только что проанализировали мы его bили нет. Но компьютеры тупые :)

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

То, как он запоминает этот контекст, заключается в том, что он дисциплинирует себя, что всякий раз, когда он сталкивается с a b, он начинает идти по пути к чтению bdc, как одна из возможностей. Поэтому, когда он видитd он знает, идет ли он уже по пути. Таким образом, синтаксический анализатор CLR (1) может делать то, что синтаксический анализатор SLR (1) не может!

Но теперь, когда нам пришлось определить так много путей, состояния машины стали очень большими!

Поэтому мы объединяем одинаковые пути, но, как и ожидалось, это может привести к путанице. Однако мы готовы пойти на риск за счет уменьшения размера.

Это ваш парсер LALR (1).

Теперь как это сделать алгоритмически.

Когда вы рисуете наборы конфигурации для вышеуказанного языка, вы увидите конфликт сдвига-уменьшения в двух состояниях. Чтобы удалить их, вы можете рассмотреть SLR (1), который принимает решения, глядя на подписку, но вы заметите, что он все равно не сможет этого сделать. Таким образом, вы должны снова нарисовать наборы конфигурации, но на этот раз с ограничением, что всякий раз, когда вы вычисляете закрытие, добавляемые дополнительные производства должны иметь строгое следование (я). Обратитесь к любому учебнику, чтобы узнать, какими они должны быть.

Основное различие между таблицами синтаксического анализатора, созданными с помощью SLR и LR, заключается в том, что действия сокращения основаны на наборе Follows для таблиц SLR. Это может быть чрезмерно ограничительным, что в конечном итоге приведет к конфликту смены-сокращения.

С другой стороны, синтаксический анализатор LR принимает решения о сокращении только на наборе терминалов, которые фактически могут следовать за сокращаемым нетерминалом. Этот набор терминалов часто является правильным подмножеством набора Follows такого нетерминала и, следовательно, имеет меньше шансов на конфликт с действиями сдвига.

По этой причине парсеры LR более мощные. Однако таблицы синтаксического анализа LR могут быть очень большими.

Анализатор LALR начинается с идеи построения таблицы синтаксического анализа LR, но объединяет сгенерированные состояния таким образом, что приводит к значительно меньшему размеру таблицы. Обратной стороной является небольшая вероятность конфликтов для некоторых грамматик, которых в противном случае удалось бы избежать в таблице LR.

Парсеры LALR немного менее мощные, чем парсеры LR, но все же более мощные, чем парсеры SLR. По этой причине YACC и другие подобные генераторы парсеров обычно используют LALR.

PS Для краткости, SLR, LALR и LR выше действительно означают SLR (1), LALR (1) и LR (1), поэтому подразумевается просмотр одного токена.

Синтаксические анализаторы SLR распознают правильное подмножество грамматик, распознаваемых синтаксическими анализаторами LALR (1), которые, в свою очередь, распознают правильное подмножество грамматик, распознаваемых синтаксическими анализаторами LR (1).

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

Вот пример грамматики LALR (1), отличной от SLR, в Dragon Book :

S → L = R | R
L → * R | id
R → L

Вот одно из состояний этой грамматики:

S → L•= R
R → L•

•Указывает положение синтаксического анализа в каждом из возможных производств. Он не знает, в какой постановке он находится, пока не дойдет до конца и не попытается сократить.

Здесь синтаксический анализатор может либо сдвинуть, =либо уменьшить R → L.

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

Однако парсер LALR (1) будет использовать набор всех терминалов, которые могут следовать этому конкретному продукту R, который является единственным $(т. Е. Концом ввода). Таким образом, конфликта нет.

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

В вашем примере следующее состояние LALR (1) вызывает конфликт сдвига-уменьшения в реализации SLR:

S → b d•a / $
A → d• / c

Символ после /- это следующий набор для каждого продукта в анализаторе LALR (1). В SLR функция follow ( A) включает a, которую также можно сдвинуть.

В дополнение к приведенным выше ответам эта диаграмма демонстрирует, как связаны разные парсеры:

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