stringtranslate.com

LALR-парсер

В информатике парсер 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] и простой анализатор LR (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) .

Отношение к другим парсерам

LR-парсеры

Анализатор LALR(1) менее мощный, чем анализатор LR(1), и более мощный, чем анализатор SLR(1), хотя все они используют одни и те же правила производства . Упрощение, которое вводит синтаксический анализатор LALR, заключается в объединении правил, имеющих идентичные наборы элементов ядра , поскольку во время процесса построения состояния LR(0) предварительные просмотры неизвестны. Это снижает мощность синтаксического анализатора, поскольку незнание символов опережения может сбить синтаксический анализатор с толку относительно того, какое грамматическое правило выбрать следующим, что приведет к конфликтам сокращения/сокращения . Все конфликты, которые возникают при применении анализатора LALR(1) к однозначной грамматике LR(1), являются конфликтами сокращения/сокращения. Анализатор SLR(1) выполняет дальнейшее слияние, что приводит к дополнительным конфликтам.

Стандартный пример грамматики LR(1), которую невозможно проанализировать с помощью анализатора LALR(1), демонстрирующей такой конфликт сокращения/сокращения: [10] [11]

 S → а E c → а F d → б F c → б Е г Э → е Ж → е

При построении таблицы LALR два состояния будут объединены в одно состояние, и позже окажется, что прогнозы неоднозначны. Единственное состояние с опережением:

 Э → е. {CD} Ф → е. {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. ^ abc ДеРемер 1969.
  2. ^ abc LR Анализ: теория и практика, Найджел П. Чепмен, с. 86–87
  3. ^ «Создать парсер». Проект Eclipse JDT . Проверено 29 июня 2012 г.
  4. ^ Андерсон, Т.; Ева, Дж.; Хорнинг, Дж. (1973). «Эффективные парсеры LR (1)». Акта Информатика (2): 2–39.
  5. ^ аб ДеРемер, Фрэнк; Пеннелло, Томас (октябрь 1982 г.). «Эффективное вычисление наборов упреждающего просмотра LALR (1)» (PDF) . Транзакции ACM в языках и системах программирования . 4 (4): 615–649. дои : 10.1145/69622.357187.
  6. ^ Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 . Архивировано из оригинала (PDF) 15 марта 2012 года . Проверено 29 мая 2011 г.
  7. ^ Пейджер, Д. (1977), «Практический общий метод построения анализаторов LR (k)», Acta Informatica 7 , vol. 7, нет. 3, стр. 249–268, номер документа : 10.1007/BF00290336.
  8. ^ Фрэнк ДеРемер, Томас Пеннелло (1979), «Эффективное вычисление наборов упреждающего просмотра LALR (1), Уведомления Sigplan - 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)

Внешние ссылки