LR-анализаторы

Алгоритм синтаксического анализа приоритета операторов

Алгоритм аналогичен рассмотренному ранее в п. 7.4.6.

Разница состоит в том, что отношения приоритетов рассматриваются только между терминальными символами грамматики.

При выполнении свертки с вершины стека выбираются все терминальные символы, связанные отношением , совместно с окружающими их нетерминалами.

Так как нетерминальные символы не играют роли в определении отношений между терминалами, можно заменить все нетерминалы одним символом.

LR- технология наиболее эффективная технология восходящего синтаксического анализа, которая может быть использована для анализа большого класса контекстно-свободных грамматик. Эта технология называется LR(k)-анализ; L означает сканирова­ние входного потока слева направо, R — построение обращенных правых порождений, а k— число входных символов, которые могут быть просмотрены для принятия решения о способе проведения разбора. Если (k) не указывается, подразумевается, что k равно 1. LR-анализ привлекателен по следующим причинам.

· LR-анализаторы могут быть созданы для распознавания, по сути, всех конструкций языков программирования, для которых может быть написана контекстно-свободная грамматика.

· Метод LR-анализа — наиболее общий известный метод ПС-анализа без отката, который, кроме того, не уступает в эффективности другим методам этого типа.

· Класс грамматик, которые могут быть разобраны с использованием LR-метода представляет собой собственное надмножество класса грамматик, которые могут быть разобраны предиктивными синтаксическими анализаторами.

· LR-анализатор может обнаруживать синтаксические ошибки сразу же, как только это становится возможным при сканировании входного потока.

Основной недостаток этого метода состоит в том, что ручное построение LR анализатора для грамматики типичного языка программирования требует большого объема работы. Для решения этой задачи нужен специализированный инструмент — генератор LR-анализаторов. С помощью такого генератора для разработанной контекстно-свободной грамматики можно автоматически построить ее синтаксический анализатор. Если грамматика содержит неоднозначности или другие конструкции, трудные для разбора сканированием слева направо, генератор в состоянии их локализовать и сообщить о них разработчику.

Дата добавления: 2014-12-27