LALR-парсер

В информатике — парсер LALR. ( анализатор вывода с упреждением, слева направо, крайний правый ) — это часть процесса компиляции, при которой читаемый человеком текст преобразуется в структурированное представление для чтения компьютерами. Парсер LALR — это программный инструмент для обработки ( анализа ) текста в очень специфическое внутреннее представление, с которым могут работать другие программы, такие как компиляторы. Этот процесс происходит в соответствии с набором правил производства , определенных формальной грамматикой компьютерного языка .

Парсер LALR — это упрощенная версия канонического парсера 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 ( слева направо, крайний правый вывод ). Анализатор LR может распознавать любой детерминированный контекстно-свободный язык за линейно ограниченное время. Крайний правый вывод требует очень больших требований к памяти, и реализация анализатора LR была непрактичной из-за ограниченной памяти компьютеров в то время. Чтобы устранить этот недостаток, в 1969 году Фрэнк ДеРемер предложил две упрощенные версии анализатора LR, а именно Look-Ahead LR (LALR). и анализатор Simple LR (SLR), который требовал гораздо меньших требований к памяти за счет меньшей мощности распознавания языка, причем анализатор 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) наиболее распространенным случаем является .

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

LR-парсеры

Анализатор 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. Однако результирующий анализатор не сможет распознать допустимую входную последовательность. 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 ) для любого $k>0$.

В зависимости от наличия пустых дифференцирований грамматика LL(1) может быть равна грамматике SLR(1) или LALR(1). Если грамматика LL(1) не имеет пустых выводов, это SLR(1), а если все символы с пустыми выводами имеют непустые выводы, то это LALR(1). Если существуют символы, имеющие только пустое происхождение, грамматика может быть или не быть LALR(1).

См. также

• Сравнение генераторов парсеров
• Контекстно-свободная грамматика
• просмотр вперед
• Генератор парсера
• Сканер токенов

Ссылки

• ДеРемер, Франклин Л. (1969). Практические переводчики языков LR(k) (PDF) (доктор философии). Массачусетский технологический институт. Архивировано из оригинала (PDF) 19 августа 2013 года . Проверено 13 ноября 2012 г.
• Битти, Джей Си (1982). «О взаимосвязи между грамматиками LL(1) и LR(1)» (PDF) . Журнал АКМ . 29 (4 октября): 1007–1022. дои : 10.1145/322344.322350 .

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

• Симулятор синтаксического анализа Этот симулятор используется для создания таблиц синтаксического анализа LALR и выполнения упражнений из книги.
• Реализация генератора парсера LALR(1) на основе JS/CC JavaScript, который можно запускать в веб-браузере или из командной строки.
• Учебное пособие по LALR(1) на Wayback Machine (архивировано 7 мая 2021 г.), учебное пособие в виде флэш-карты по синтаксическому анализу LALR(1).