Войти
A просмотр вперед слева-к- right (LALR) синтаксический генератор - это программный инструмент, который считывает BNF g rammar и создает парсер LALR, который способен анализировать файлы, написанные на компьютерном языке, определенном грамматикой BNF. Парсеры LALR желательны, потому что они очень быстрые и маленькие по сравнению с другими типами парсеров.
Существуют и другие типы генераторов синтаксического анализатора, такие как Simple LR parser, LR parser, GLR parser, LL парсер и генераторы. Что отличает один от другого, так это тип грамматики 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 году в ATT Labs. Другой, TWS, был создан Фрэнком Де Ремером и Томом Пеннелло. Сегодня доступно множество генераторов парсеров LALR, многие из которых созданы на основе оригинального Yacc и в значительной степени совместимы с ним, например, GNU bison, игра слов на оригинальном Yacc / Yak. См. Сравнение детерминированных генераторов парсеров контекстно-свободных языков для более подробного списка.
Анализатор LALR и его альтернативы, синтаксический анализатор SLR и канонический синтаксический анализатор LR, имеют похожие методы и таблицы синтаксического анализа; их главное отличие заключается в алгоритме анализа математической грамматики, используемом инструментом генерации синтаксического анализатора. Генераторы LALR принимают больше грамматик, чем генераторы SLR, но меньше грамматик, чем полные LR (1). Полный LR включает в себя гораздо большие таблицы синтаксического анализа, и его следует избегать, если это явно не требуется для определенного компьютерного языка. Реальные компьютерные языки часто можно выразить как грамматики LALR (1). В тех случаях, когда это невозможно, обычно достаточно грамматики LALR (2). Если генератор синтаксического анализатора допускает только грамматики LALR (1), синтаксический анализатор обычно вызывает некоторый рукописный код всякий раз, когда он встречает конструкции, требующие расширенного просмотра вперед.
Подобно синтаксическому анализатору SLR и генератору синтаксического анализатора Canonical LR, генератор синтаксического анализатора LALR сначала конструирует конечный автомат LR (0), а затем вычисляет опережающие наборы для всех правил грамматики, проверяя за двусмысленность. Канонический LR создает полные наборы опережающих просмотров. LALR использует наборы слияния, то есть сливает наборы предвидения, в которых ядро LR (0) одинаково. SLR использует наборы FOLLOW как наборы предвидения, которые связывают правую часть ядра LR (0) с терминалом предвидения. Это большее упрощение, чем в случае LALR, поскольку многие конфликты могут возникать из-за того, что ядра LR (0) совместно используют одну и ту же правую часть и опережающий терминал, конфликты, которых нет в LALR. Вот почему у SLR меньше возможностей распознавания языка, чем у LALR, причем Canonical LR сильнее, чем у обоих, поскольку он не включает никаких упрощений.
