В информатике LALR -парсер [a] ( смотрящий вперед, слева направо, самый правый выводной парсер ) является частью процесса компиляции, где читаемый человеком текст преобразуется в структурированное представление для чтения компьютерами. LALR-парсер — это программный инструмент для обработки ( анализа ) текста в очень специфическое внутреннее представление, с которым могут работать другие программы, такие как компиляторы. Этот процесс происходит в соответствии с набором правил производства, заданных формальной грамматикой для компьютерного языка .
Парсер LALR представляет собой упрощенную версию канонического парсера LR .
Парсер LALR был изобретен Фрэнком ДеРемером в его докторской диссертации 1969 года « Практические переводчики для языков LR(k)» [ 1] при рассмотрении практических трудностей того времени при реализации парсеров LR(1). Он показал, что парсер LALR обладает большей мощностью распознавания языка, чем парсер LR(0), при этом требуя того же количества состояний, что и парсер LR(0) для языка, который может быть распознан обоими парсерами. Это делает парсер LALR эффективной с точки зрения памяти альтернативой парсеру LR(1) для языков, которые являются LALR. Было также доказано, что существуют языки LR(1), которые не являются LALR. Несмотря на эту слабость, мощности парсера LALR достаточно для многих основных компьютерных языков, [2] включая Java , [3] хотя справочные грамматики для многих языков не являются LALR из-за неоднозначности . [2]
В оригинальной диссертации не было алгоритма для построения такого анализатора с заданной формальной грамматикой. Первые алгоритмы для генерации анализатора LALR были опубликованы в 1973 году. [4] В 1982 году ДеРемер и Том Пеннелло опубликовали алгоритм, который генерировал высокоэффективные по памяти анализаторы LALR. [5] Анализаторы LALR могут быть автоматически сгенерированы из грамматики генератором анализаторов LALR, таким как Yacc или GNU Bison . Автоматически сгенерированный код может быть дополнен написанным вручную кодом для увеличения мощности результирующего анализатора.
В 1965 году Дональд Кнут изобрел парсер LR ( слева направо, самый правый вывод ). Парсер LR может распознавать любой детерминированный контекстно-свободный язык за линейно ограниченное время. [6] Самый правый вывод имеет очень большие требования к памяти, и реализация парсера LR была непрактичной из-за ограниченной памяти компьютеров того времени. Чтобы устранить этот недостаток, в 1969 году Фрэнк ДеРемер предложил две упрощенные версии парсера LR, а именно Look-Ahead LR (LALR) [1] и Simple LR parser (SLR), которые имели гораздо меньшие требования к памяти за счет меньшей мощности распознавания языка, причем парсер LALR был самой мощной альтернативой. [1] В 1977 году были изобретены оптимизации памяти для парсера LR [7], но парсер LR все равно был менее эффективным с точки зрения памяти, чем упрощенные альтернативы.
В 1979 году Фрэнк ДеРемер и Том Пеннелло объявили о серии оптимизаций для парсера LALR, которые еще больше повысили бы эффективность его памяти. [8] Их работа была опубликована в 1982 году. [5]
Обычно парсер LALR ссылается на парсер LALR(1), [b] так же, как парсер 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 ) [9] , но они не нашли практического применения.
Как и другие типы LR-анализаторов, LALR-анализатор весьма эффективен при поиске единственного правильного анализа снизу вверх за один проход слева направо по входному потоку, поскольку ему не нужно использовать возврат . Будучи анализатором с предпросмотром по определению, он всегда использует предпросмотр, причем LALR(1) является наиболее распространенным случаем.
Анализатор LALR(1) менее мощный, чем анализатор LR(1), и более мощный, чем анализатор SLR(1), хотя все они используют одни и те же правила производства . Упрощение, которое вводит анализатор LALR, заключается в слиянии правил, которые имеют идентичные наборы элементов ядра , поскольку во время процесса построения состояния LR(0) опережающие просмотры неизвестны. Это снижает мощность анализатора, поскольку незнание опережающих символов может сбить с толку анализатор относительно того, какое правило грамматики выбрать следующим, что приводит к конфликтам reduce/reduce . Все конфликты, возникающие при применении анализатора LALR(1) к однозначной грамматике LR(1), являются конфликтами reduce/reduce. Анализатор SLR(1) выполняет дальнейшее слияние, что вносит дополнительные конфликты.
Стандартный пример грамматики LR(1), которую невозможно проанализировать с помощью анализатора LALR(1), демонстрирующий такой конфликт «свернуть/свернуть», выглядит следующим образом: [10] [11]
С → а Е с → а Ф д → б Ф в → б Э д Э → е Ф → е
В построении таблицы LALR два состояния будут объединены в одно состояние, и позже будет обнаружено, что прогнозы неоднозначны. Единственное состояние с прогнозами:
Е → е. {c,d} Ф → е. {c,d}Анализатор LR(1) создаст два разных состояния (с неконфликтующими предпросмотрами), ни одно из которых не является неоднозначным. В анализаторе LALR это одно состояние имеет конфликтующие действия (при предпросмотре c или d, свести к E или F), «конфликт свести/свести»; указанная выше грамматика будет объявлена неоднозначной генератором анализатора LALR , и будут сообщены о конфликтах.
Чтобы восстановить, эта неоднозначность разрешается выбором E, поскольку в грамматике она стоит перед F. Однако полученный парсер не сможет распознать допустимую входную последовательность b e c, поскольку неоднозначная последовательность e cсокращается до (E → e) c, а не до правильной (F → e) c, но b E cне находится в грамматике.
Парсеры LALR( j ) несравнимы с парсерами LL( k ) : для любых j и k, которые оба больше 0, существуют грамматики LALR( j ), которые не являются грамматиками LL( k ) и наоборот. Фактически, невозможно решить, является ли заданная грамматика LL(1) LALR( k ) для любого . [2]
В зависимости от наличия пустых выводов грамматика LL(1) может быть равна грамматике SLR(1) или LALR(1). Если грамматика LL(1) не имеет пустых выводов, то она является SLR(1), а если все символы с пустыми выводами имеют непустые выводы, то она является LALR(1). Если существуют символы, имеющие только пустой вывод, то грамматика может быть или не быть LALR(1). [12]
