Парсер LALR - Википедия - LALR parser

В Информатика, Парсер LALR[а] или же Парсер Look-Ahead LR это упрощенная версия канонический парсер LR, разобрать (разделить и проанализировать) текст по набору правила производства указанный формальная грамматика для компьютерный язык. («LR» означает слева направо, крайнее правое происхождение.)

Парсер LALR был изобретен Фрэнк Де Ремер в его докторской диссертации 1969 г., Практические переводчики языков LR (k),[1] в его трактовке практических трудностей в то время при реализации парсеров LR (1). Он показал, что синтаксический анализатор LALR имеет больше возможностей распознавания языка, чем синтаксический анализатор LR (0), при этом требуя того же количества состояний, что и синтаксический анализатор LR (0) для языка, который может распознаваться обоими синтаксическими анализаторами. Это делает парсер LALR альтернативой парсеру LR (1) с эффективным использованием памяти для языков, которые являются LALR. Также было доказано, что существуют языки LR (1), которые не являются LALR. Несмотря на эту слабость, мощности парсера LALR достаточно для многих основных компьютерных языков,[2] включая Ява,[3] хотя справочные грамматики для многих языков не могут быть LALR из-за того, что двусмысленный.[2]

В оригинальной диссертации не было алгоритма построения такого синтаксического анализатора с учетом формальной грамматики. Первые алгоритмы генерации парсера LALR были опубликованы в 1973 году.[4] В 1982 году Де Ремер и Том Пеннелло опубликовали алгоритм, генерирующий LALR-анализаторы с высокой эффективностью памяти.[5] Парсеры LALR могут быть автоматически сгенерированы из грамматики с помощью Генератор парсера LALR Такие как Yacc или же GNU Bison. Автоматически сгенерированный код может быть дополнен рукописным кодом для увеличения мощности результирующего синтаксического анализатора.

История

В 1965 г. Дональд Кнут изобрел Парсер LR (Lсмещение вправо, рсамое правильное происхождение ). Парсер 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 → a F d → b F c → b E d E → e F → e

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

  E → e. {c, d} F → e. {CD}

Парсер LR (1) создаст два разных состояния (с неконфликтными опережающими просмотрами), ни одно из которых не является неоднозначным. В синтаксическом анализаторе LALR это одно состояние имеет конфликтующие действия (с учетом упреждения c или d, уменьшить до E или F), «уменьшить / уменьшить конфликт»; указанная выше грамматика будет объявлена ​​двусмысленной Генератор парсера LALR и о конфликтах будет сообщено.

Чтобы исправить эту неоднозначность, нужно выбрать E, потому что она стоит перед F в грамматике. Однако результирующий синтаксический анализатор не сможет распознать действительную входную последовательность. б д в, поскольку неоднозначная последовательность e c сводится к (E → e) c, а не правильный (F → e) c, но б E в нет в грамматике.

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

внешняя ссылка

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