Войти
В информатике, LALR parser или Look-Ahead LR parser - это упрощенная версия канонического LR-анализатора, для синтаксического анализа (разделения и анализа) текста в соответствии с набором продукции правила, указанные в формальной грамматике для компьютерного языка. («LR» означает слева направо, крайнее правое происхождение.)
Парсер LALR был изобретен в его докторской диссертации 1969 года «Практические переводчики для языков LR (k)» в его рассмотрение практических трудностей в то время реализации парсеров LR (1). Он показал, что синтаксический анализатор LALR обладает большей способностью распознавания языка, чем синтаксический анализатор LR (0), при этом требуя того же количества состояний, что и синтаксический анализатор LR (0) для языка, который может распознаваться обоими синтаксическими анализаторами. Это делает парсер LALR альтернативой парсеру LR (1) с эффективным использованием памяти для языков, которые являются LALR. Также было доказано, что существуют языки LR (1), которые не являются LALR. Несмотря на эту слабость, мощности синтаксического анализатора LALR достаточно для многих основных компьютерных языков, включая Java, хотя справочные грамматики для многих языков не соответствуют LALR из-за неоднозначности.
Оригинал В диссертации не приводится алгоритм построения такого синтаксического анализатора с учетом формальной грамматики. Первые алгоритмы генерации парсеров LALR были опубликованы в 1973 году. В 1982 году Де Ремер и Том Пеннелло опубликовали алгоритм, который генерировал парсеры LALR с высокой эффективностью памяти. Парсеры LALR могут быть автоматически сгенерированы из грамматики с помощью генератора синтаксического анализатора LALR, такого как Yacc или GNU Bison. Автоматически сгенерированный код может быть дополнен рукописным кодом для увеличения мощности результирующего синтаксического анализатора.
В 1965 году Дональд Кнут изобрел LR-синтаксический анализатор (Left to Right, Rсамое прямое происхождение ). Анализатор LR может распознать любой детерминированный контекстно-свободный язык за линейно-ограниченное время. Крайнее правое производное имеет очень большие требования к памяти, и реализация парсера LR была непрактичной из-за ограниченной памяти компьютеров в то время. Чтобы устранить этот недостаток, в 1969 году Фрэнк Де Ремер предложил две упрощенные версии парсера LR, а именно Look-Ahead LR (LALR) и Simple LR parser <12.>у которого были гораздо более низкие требования к памяти за счет меньшей способности распознавания языка, причем синтаксический анализатор LALR был наиболее мощной альтернативой. В 1977 году была изобретена оптимизация памяти для парсера LR, но все же парсер LR был менее эффективен с точки зрения памяти, чем упрощенные альтернативы.
В 1979 году Фрэнк ДеРемер и объявил о серии оптимизаций для парсера LALR, которые еще больше улучшили его эффективность использования памяти. Их работа была опубликована в 1982 году.
Как правило, синтаксический анализатор LALR относится к синтаксическому анализатору LALR (1), так же как синтаксический анализатор LR обычно относится к синтаксическому анализатору LR (1). "(1)" обозначает просмотр вперед с одним маркером для устранения различий между шаблонами правил во время синтаксического анализа. Точно так же есть парсер LALR (2) с поиском по двум токенам и парсеры LALR (k) с поиском по k-токенам, но они редко используются на практике. Парсер LALR основан на парсере LR (0), поэтому его также можно обозначить LALR (1) = LA (1) LR (0) (1 токен просмотра вперед, LR (0)) или, в более общем смысле, LALR (k) = LA (k) LR (0) (k токенов просмотра вперед, LR (0)). Фактически существует двухпараметрическое семейство парсеров LA (k) LR (j) для всех комбинаций j и k, которые могут быть получены из парсера LR (j + k), но они не находят практического применения.
Как и в случае с другими типами парсеров LR, парсер LALR достаточно эффективен при поиске единственного правильного восходящего синтаксического анализа за одно сканирование входящего потока слева направо, потому что нет необходимости использовать отслеживание с возвратом. Будучи по определению анализатором просмотра вперед, он всегда использует предварительный просмотр, причем LALR (1) является наиболее распространенным случаем.
Парсер LALR (1) менее мощный, чем парсер LR (1), и более мощный, чем SLR (1) синтаксический анализатор, хотя все они используют одни и те же производственные правила. Упрощение, которое вводит синтаксический анализатор LALR, состоит в слиянии правил, которые имеют идентичные наборы элементов ядра, потому что во время процесса построения состояния LR (0) опережающие просмотры неизвестны. Это снижает мощность синтаксического анализатора, поскольку незнание опережающих символов может запутать синтаксический анализатор относительно того, какое правило грамматики выбрать следующим, что приводит к уменьшению / уменьшению конфликтов . Все конфликты, возникающие при применении синтаксического анализатора LALR (1) к однозначной грамматике LR (1), являются конфликтами уменьшения / уменьшения. Парсер SLR (1) выполняет дальнейшее слияние, что приводит к дополнительным конфликтам.
Стандартный пример грамматики LR (1), которая не может быть проанализирована с помощью синтаксического анализатора LALR (1), демонстрирует такой конфликт уменьшения / уменьшения:
S → a E c → a F d → b F c → b E d E → e F → e
При построении таблицы LALR два состояния будут объединены в одно состояние, и позже будет обнаружено, что опережающие просмотры будут неоднозначными. Единственное состояние с опережением:
E → e. {c, d} F → e. {c, d}Анализатор LR (1) создаст два разных состояния (с неконфликтными опережающими просмотрами), ни одно из которых не является неоднозначным. В синтаксическом анализаторе LALR это одно состояние имеет конфликтующие действия (с учетом опережения c или d, уменьшить до E или F), «уменьшить / уменьшить конфликт»; Вышеупомянутая грамматика будет объявлена неоднозначной генератором парсера LALR, и о конфликтах будет сообщено.
Чтобы исправить эту неоднозначность, нужно выбрать E, потому что она стоит перед F в грамматике. Однако результирующий синтаксический анализатор не сможет распознать допустимую входную последовательность Beck, поскольку неоднозначная последовательность ecсокращается до (E → e) c, вместо правильного (F → e) c, но b E cотсутствует в грамматике.
Парсеры LALR (j) несовместимы с парсерами LL (k) : для любых j и k оба больше 0, есть LALR (j) грамматики, которые не являются LL (k) грамматиками и наоборот. Фактически, непонятно, является ли данная грамматика LL (1) LALR (k) для любого 
В зависимости от наличия пустых производных LL ( 1) грамматика может быть равна грамматике SLR (1) или LALR (1). Если грамматика LL (1) не имеет пустых производных, это SLR (1), и если все символы с пустыми производными имеют непустые производные, она является LALR (1). Если существуют символы, имеющие только пустое происхождение, грамматика может быть или не быть LALR (1).
