Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В информатике , 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.у которого были гораздо более низкие требования к памяти за счет меньшей способности распознавания языка, причем синтаксический анализатор 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 в → б 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]

См. Также [ править ]

  • Сравнение генераторов парсеров
  • Бесконтекстная грамматика
  • Смотреть вперед
  • Генератор парсеров
  • Сканер токенов

Заметки [ править ]

  1. ^ "LALR" произносится как инициализм "эль-ай-эль-арр"
  2. ^ "LALR (1)" произносится как инициализм "эль-ай-эль-арр-он"

Ссылки [ править ]

  1. ^ а б в Де Ремер 1969 .
  2. ^ a b c LR Parsing: Theory and Practice, Найджел П. Чепмен, с. 86–87
  3. ^ "Создать парсер" . Проект Eclipse JDT . Проверено 29 июня 2012 года .
  4. ^ Андерсон, Т .; Eve, J .; Хорнинг, Дж. (1973). «Эффективные парсеры LR (1)». Acta Informatica (2): 2–39.
  5. ^ a b Де Ремер, Франк; Пеннелло, Томас (октябрь 1982 г.). «Эффективное вычисление LALR (1) Look-Ahead Sets» (PDF) . Транзакции ACM по языкам и системам программирования . 4 (4): 615–649. DOI : 10.1145 / 69622.357187 .
  6. ↑ Knuth, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года .
  7. ^ Пейджера, D. (1977), "A Practical Общий метод построения LR (к) парсеры", Acta Informatica 7 , 7 (3), стр 249-268,. Дои : 10.1007 / BF00290336
  8. ^ Франк ДеРемер, Томас Пеннелло (1979), «Эффективное вычисление LALR (1) Look-Ahead Sets», Sigplan Notices - SIGPLAN, vol. 14, вып. 8. С. 176–187.
  9. ^ Методы синтаксического анализа: Практическое руководство, Дик Грюн и Кериэл Дж. Х. Джейкобс, "9.7 LALR (1)", стр. 302
  10. ^ « 7.9 LR (1), но не LALR (1), Архивировано 4 августа 2010 г. на Wayback Machine », CSE 756: Проектирование и реализация компилятора Архивировано 23 июля 2010 г. на Wayback Machine , Эйтан Гурари, весна 2008 г.
  11. ^ " Почему эта грамматика LR (1) не LALR (1)? "
  12. ^ ( Битти 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) синтаксический анализ.