Генератор парсера LALR

Генератор упреждающего анализатора LR (LALR) — это программный инструмент, который считывает контекстно-свободную грамматику (CFG) и создает анализатор LALR , способный анализировать файлы, написанные на контекстно-свободном языке, определенном CFG. LALR-парсеры желательны, потому что они очень быстрые и небольшие по сравнению с другими типами парсеров.

Существуют и другие типы генераторов парсеров , такие как простой парсер LR , парсер LR , парсер GLR , синтаксический анализатор LL и генераторы парсеров GLL . Что отличает один от другого, так это тип CFG, который они способны принимать, и тип алгоритма анализа, который используется в сгенерированном анализаторе. Генератор анализатора 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. Другой, «TWS», был создан Фрэнком ДеРемером и Томом Пеннелло. Сегодня доступно множество генераторов парсеров LALR, многие из которых вдохновлены оригинальным Yacc и в значительной степени совместимы с ним, например GNU bison , игра слов на основе оригинального Yacc/ Yak . см . в разделе «Сравнение детерминированных генераторов контекстно-свободных языковых анализаторов» Более подробный список .

Обзор

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

Подобно синтаксическому анализатору SLR и генератору синтаксического анализатора LR Canonical, генератор синтаксического анализатора LALR сначала создает конечный автомат LR(0), а затем вычисляет наборы опережающего просмотра для всех правил в грамматике, проверяя на неоднозначность. Canonical LR создает полные наборы просмотра вперед. LALR использует наборы слияния, то есть объединяет наборы просмотра вперед, в которых ядро ​​LR(0) одинаково. SLR использует наборы FOLLOW в качестве наборов просмотра вперед, которые связывают правую часть ядра LR (0) с терминалом просмотра вперед. Это большее упрощение, чем в случае с LALR, поскольку многие конфликты могут возникнуть из-за того, что ядра LR(0) используют одну и ту же правую часть и терминал просмотра вперед, конфликты, которых нет в LALR. Вот почему SLR обладает меньшей способностью распознавания языка, чем LALR, а Canonical LR сильнее обоих, поскольку не включает в себя никаких упрощений.

См. также

• Сравнение генераторов парсеров – для более полного списка, в который также входят генераторы парсеров LL, SLR, GLR и LR.

Ссылки

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

Дальнейшее чтение

• Кнут, DE (июль 1965 г.). «О переводе языков слева направо». Информация и контроль . 8 (6): 607–639. дои : 10.1016/S0019-9958(65)90426-2 .
• ДеРемер, Франклин Л. (1969). Практические переводчики языков LR(k) (PDF) (доктор философии). Массачусетский технологический институт. Архивировано из оригинала (PDF) 19 августа 2013 г. Проверено 19 августа 2013 г.
• Эффективное вычисление наборов прогноза LALR(1), ДеРемер и Пеннелло, TOPLAS (1982)