В чем разница между парсерами 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)?

EDIT (ybungalobill): я не получил удовлетворительного ответа на вопрос, в чем разница между LALR и LR. Таким образом, таблицы LALR меньше по размеру, но он может распознавать только подмножество грамматик LR. Может кто-нибудь подробнее рассказать о разнице между LALR и LR, пожалуйста? LALR(1) и LR(1) будет достаточно для ответа. Оба они используют 1 токен look-ahead и и стол везут! Чем они отличаются?

7 93
parsing compiler-construction algorithm grammar

7 ответов:

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

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

  • SHIFT: если текущая таблица говорит о сдвиге на токене T, пара (S,T) помещается в стек синтаксического анализа, состояние изменяется в соответствии с тем, что говорит таблица GOTO текущий токен(например, GOTO (T)), другой входной токен T' извлекается, и процесс повторяется
  • уменьшить: каждое состояние имеет 0, 1 или много возможных сокращений, которые могут произойти в состоянии. Если синтаксическим анализатором является LR или LALR, маркер проверяется по наборам lookahead для всех допустимых сокращений для состояния. Если токен соответствует набору lookahead для сокращения для правила грамматики G = R1 R2 .. Rn, происходит сокращение стека и сдвиг: вызывается семантическое действие для G, стек выскакивает n (из RN) раз, пара(S,G) помещается в стек, новое состояние S' устанавливается в GOTO (G), и цикл повторяется с тем же маркером T. Если синтаксический анализатор является синтаксическим анализатором SLR, существует не более одного правила сокращения для состояния, и поэтому действие сокращения может быть выполнено вслепую без поиска, чтобы увидеть, какое сокращение применяется. Это полезно для парсера SLR, чтобы знать, если там и сокращение или нет; это легко сказать, если каждое государство четко фиксирует количество сокращений, связанных с это, и этот счет необходим для версий L(AL)R на практике в любом случае.
  • ошибка: если ни сдвиг, ни уменьшение не возможны, объявляется синтаксическая ошибка.

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

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

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

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

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

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

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

[EDIT November 2011: Мы расширили наш парсер для обработки всех C++11. ДЖЛР сделала это намного проще. Редактировать августа 2014 года: теперь справляется со всем в C++17. Ничего не сломалось или стало хуже, ДЖЛР все еще мяукает кошка.]

48

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

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

дополнительное соглашение

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

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

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

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

17

еще один ответ (YAA).

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

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

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

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

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

LRSTAR 9.1 может генерировать минимальные Парсеры LR(1) и LR(*) в C++. Смотрите этой схемы что показывает разницу между парсерами LR.

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

12

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

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

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

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

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

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

это ваш LALR(1) синтаксический анализатор.

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

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

5

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

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

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

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

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

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

4

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

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

The Книга Дракона пример грамматики LALR(1), которая не является зеркальной это:

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

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

S → L•= R
R → L•

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

здесь парсер может либо сдвинуть= или уменьшить R → L.

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

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

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

, следующее состояние LALR(1) вызывает конфликт shift-reduce в реализации SLR:

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

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

4

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

0