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

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

Существуют и другие типы парсеров генераторов , таких как Simple LR парсер , LR парсер , РВО синтаксический анализатор , LL синтаксический анализатор и парсер GLL генераторов. Что отличает один от другого, так это тип грамматики BNF, которую они способны принять, и тип алгоритма синтаксического анализа, который используется в сгенерированном синтаксическом анализаторе. Генератор синтаксического анализатора LALR принимает грамматику LALR в качестве входных данных и генерирует синтаксический анализатор, который использует алгоритм синтаксического анализа LALR (который управляется таблицами синтаксического анализатора LALR).

На практике LALR предлагает хорошее решение, потому что грамматики LALR (1) более мощные, чем SLR (1), и могут анализировать большинство практичных грамматик LL (1). Грамматики LR (1) более мощные, чем LALR (1), но канонические синтаксические анализаторы LR (1) могут быть чрезвычайно большими по размеру и считаться непрактичными. Минимальные парсеры LR (1) имеют небольшой размер и сопоставимы с парсерами LALR (1).

История [ править ]

Франк Де Ремер изобрел парсеры LALR в своей докторской диссертации под названием «Практические переводчики LR (k)» в 1969 году в Массачусетском технологическом институте. Это был важный прорыв, потому что переводчики LR (k), как определил Дональд Кнут в его статье 1965 года «О переводе языков слева направо», были слишком большими для внедрения в компьютерные системы в 1960-х и 70-х годах.

Первым генератором парсера LALR и, вероятно, самым популярным в течение многих лет был " yacc " (еще один компилятор компилятора), созданный Стивеном Джонсоном в 1975 году в AT&T Labs. [1] Другой, TWS, был создан Фрэнком Де Ремером и Томом Пеннелло. Сегодня доступно множество генераторов синтаксического анализатора LALR, многие из которых основаны на оригинальном Yacc и в значительной степени совместимы с ним, например GNU bison , игра слов на оригинальном Yacc / Yak . См. Более подробный список в разделе Сравнение детерминированных генераторов контекстно-свободных языковых парсеров .

Обзор [ править ]

Синтаксический анализатор LALR и его альтернативы, синтаксический анализатор SLR и синтаксический анализатор Canonical LR , имеют аналогичные методы и таблицы синтаксического анализа; их главное отличие заключается в алгоритме анализа математической грамматики, используемом инструментом генерации синтаксического анализатора. Генераторы LALR принимают больше грамматик, чем генераторы SLR, но меньше грамматик, чем полные LR (1). Полный LR включает в себя гораздо большие таблицы синтаксического анализа, и его следует избегать, если это явно не требуется для определенного компьютерного языка. Реальные компьютерные языки часто можно выразить как грамматики LALR (1). В тех случаях, когда они не могут, обычно достаточно грамматики LALR (2). Если генератор синтаксического анализатора допускает только грамматики LALR (1), синтаксический анализатор обычно вызывает некоторый рукописный код всякий раз, когда он встречает конструкции, требующие расширенного просмотра вперед.

Подобно синтаксическому анализатору SLR и генератору синтаксического анализатора Canonical LR, генератор синтаксического анализатора LALR сначала создает конечный автомат LR (0), а затем вычисляет опережающие наборы для всех правил грамматики, проверяя неоднозначность. Канонический LR создает полные наборы опережающих просмотров. LALR использует наборы слияния, то есть сливает наборы предвидения, в которых ядро ​​LR (0) одинаково. SLR использует ПОСЛЕДУЮЩИЙнаборы как наборы предвидения, которые связывают правую часть ядра LR (0) с терминалом предвидения. Это большее упрощение, чем в случае LALR, поскольку многие конфликты могут возникать из-за того, что ядра LR (0) совместно используют одну и ту же правую часть и опережающий терминал, конфликты, которых нет в LALR. Вот почему у SLR меньше возможностей распознавания языка, чем у LALR, причем Canonical LR сильнее, чем у обоих, поскольку он не включает никаких упрощений.

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

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

  1. ^ Стивен С. Джонсон (1975). «Yacc: еще один компилятор-компилятор» . AT&T Bell Laboratories.
  • Альфред В. Ахо, Рави Сетхи и Джеффри Д. Ульман. Компиляторы: принципы, методы и инструменты Addison-Wesley, 1986. (также известная как The Dragon Book , описывает традиционные методы построения LALR (1) синтаксических анализаторов).
  • Ричард Борнат Понимание и написание компиляторов , Macmillan, 1979. (Описывает принципы автоматического анализа слева направо и то, как создавать таблицы синтаксического анализатора, что такое следующий набор и т. Д., На английском языке, а не на математическом языке - доступно бесплатно с страница автора по адресу [1] .)

Дальнейшее чтение [ править ]

  • Кнут, DE (июль 1965 г.). «О переводе языков слева направо» (PDF) . Информация и контроль . 8 (6): 607–639. DOI : 10.1016 / S0019-9958 (65) 90426-2 . Архивировано из оригинального (PDF) 15 марта 2012 года . Проверено 29 мая 2011 года . CS1 maint: discouraged parameter (link)
  • Де Ремер, Франклин Л. (1969). Практические переводчики языков LR (k) (PDF) (Ph.D.). Массачусетский технологический институт. Архивировано из оригинального (PDF) 19 августа 2013 года . Проверено 19 августа 2013 .
  • Эффективное вычисление LALR (1) Look-Ahead Sets, DeRemer and Pennello, TOPLAS (1982).