В информатике , LALR анализатор [а] или Look-Ahead LR анализатор представляет собой упрощенную версию канонического LR парсера , чтобы разобрать текст в соответствии с набором правил производства , установленных в формальных грамматиках для компьютерного языка . («LR» означает слева направо, крайнее правое происхождение .)
LALR анализатор был изобретен Frank DeRemer в его докторской диссертации 1969, практические переводчики для LR (л) языков , [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 - анализатор ( L EFT направо, R ightmost дифференцирование ). Анализатор LR может распознавать любой детерминированный контекстно-свободный язык за линейно ограниченное время. [6] Крайний правый вывод имеет очень большие требования к памяти, и реализация парсера LR была непрактичной из-за ограниченной памяти компьютеров в то время. Чтобы устранить этот недостаток, в 1969 году Фрэнк Де Ремер предложил две упрощенные версии анализатора LR, а именно Look-Ahead LR (LALR) [1] и простой анализатор LR, который имел гораздо более низкие требования к памяти за счет меньшего распознавания языка. power, причем парсер 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) является наиболее распространенным случаем.
Отношение к другим парсерам
Парсеры LR
Синтаксический анализатор LALR (1) менее мощный, чем синтаксический анализатор LR (1), и более мощный, чем синтаксический анализатор SLR (1), хотя все они используют одни и те же производственные правила . Упрощение, которое вводит синтаксический анализатор LALR, состоит в объединении правил, которые имеют идентичные наборы элементов ядра , потому что во время процесса построения состояния LR (0) опережающие просмотры неизвестны. Это снижает мощность синтаксического анализатора, поскольку незнание опережающих символов может запутать синтаксический анализатор относительно того, какое правило грамматики выбрать следующим, что приведет к конфликтам уменьшения / уменьшения . Все конфликты, возникающие при применении синтаксического анализатора LALR (1) к однозначной грамматике LR (1), являются конфликтами уменьшения / уменьшения. Парсер SLR (1) выполняет дальнейшее слияние, что приводит к дополнительным конфликтам.
Стандартный пример грамматики LR (1), которая не может быть проанализирована с помощью парсера LALR (1), демонстрирует такой конфликт сокращения / уменьшения: [10] [11]
S → a E c → а F d → б F c → б E г E → e F → e
При построении таблицы LALR два состояния будут объединены в одно состояние, и позже опережающие просмотры окажутся неоднозначными. Одно состояние с опережением:
E → e. {CD} F → е. {CD}
Парсер LR (1) создаст два разных состояния (с неконфликтными опережающими просмотрами), ни одно из которых не является неоднозначным. В синтаксическом анализаторе LALR это одно состояние имеет конфликтующие действия (с учетом опережающего просмотра c или d, уменьшить до E или F), «уменьшить / уменьшить конфликт»; указанная выше грамматика будет объявлена генератором парсера LALR неоднозначной, и о конфликтах будет сообщено.
Чтобы исправить эту неоднозначность, выберите E, потому что она стоит перед F в грамматике. Однако результирующий синтаксический анализатор не сможет распознать действительную входную последовательность b e c
, поскольку неоднозначная последовательность e c
сокращается до (E → e) c
, а не до правильной (F → e) c
, но b E c
ее нет в грамматике.
Парсеры LL
Парсеры 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]
Смотрите также
Заметки
- ^ "LALR" произносится как инициализм "эль-ай-эль-арр"
- ^ "LALR (1)" произносится как инициализм "эль-ай-эль-арр-он"
Рекомендации
- ^ а б в Де Ремер 1969 .
- ^ a b c LR Parsing: Theory and Practice, Найджел П. Чепмен, с. 86–87
- ^ "Создать парсер" . Проект Eclipse JDT . Проверено 29 июня 2012 года .
- ^ Андерсон, Т .; Eve, J .; Хорнинг, Дж. (1973). «Эффективные парсеры LR (1)». Acta Informatica (2): 2–39.
- ^ а б Де Ремер, Франк; Пеннелло, Томас (октябрь 1982 г.). «Эффективное вычисление LALR (1) Look-Ahead Sets» (PDF) . Транзакции ACM по языкам и системам программирования . 4 (4): 615–649. DOI : 10.1145 / 69622.357187 .
- ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
- ^ Пейджер, D. (1977), "A Practical Общий метод построения LR (к) парсеры", Acta Informatica 7 , 7 (3), стр 249-268,. Дои : 10.1007 / BF00290336
- ^ Франк ДеРемер, Томас Пеннелло (1979), «Эффективное вычисление LALR (1) Look-Ahead Sets», Sigplan Notices - SIGPLAN, vol. 14, вып. 8. С. 176–187.
- ^ Методы синтаксического анализа: Практическое руководство, Дик Грюн и Кериэл Дж. Х. Джейкобс, "9.7 LALR (1)", стр. 302
- ^ « 7.9 LR (1), но не LALR (1), Архивировано 4 августа 2010 г. на Wayback Machine », CSE 756: Проектирование и реализация компилятора Архивировано 23 июля 2010 г. на Wayback Machine , Эйтан Гурари, весна 2008 г.
- ^ " Почему эта грамматика LR (1) не LALR (1)? "
- ^ ( Битти 1982 )
- Де Ремер, Франклин Л. (1969). Практические переводчики языков LR (k) (PDF) (PhD). Массачусетский технологический институт. Архивировано из оригинального (PDF) 19 августа 2013 года . Проверено 13 ноября 2012 года .
- Битти, JC (1982). «О взаимосвязи между грамматиками LL (1) и LR (1)» (PDF) . Журнал ACM . 29 (4 (октябрь)): 1007–1022. DOI : 10.1145 / 322344.322350 .
Внешние ссылки
- Симулятор синтаксического анализа Этот тренажер используется для создания таблиц синтаксического анализа LALR и решения упражнений книги.
- JS / CC Реализация генератора синтаксического анализатора LALR (1) на основе JavaScript, который можно запускать в веб-браузере или из командной строки.
- LALR (1) учебник , флэш - карта , как учебник по LALR (1) синтаксический анализ.