Приведение грамматики к виду LL(1)

Цель – поиск направляющих символов сконструированной КС-грамматики языка и преобразование ее к виду LL(1).

Содержание

• ОСНОВНЫЕ СВЕДЕНИЯ
• S-грамматика
• Q-грамматики
• LL(1)-грамматика
• Преобразование грамматики
• ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
• ИСПОЛЬЗОВАНИЕ «УЧЕБНОГО КОМПИЛЯТОРА» В Л/Р №2
• Содержание отчета
• Контрольные вопросы
• Литература

Фрагменты из методички

Основные сведения

Рассмотрим более подробно группу КС-грамматик, так как они являются наиболее универсальными и поэтому более пригодны в качестве основы для описания языков программирования, а, следовательно, и для фазы синтаксического анализа ( разбора ) компиляции.

КС-грамматики, в свою очередь, делятся на три класса:

1. s-грамматики;
2. Q-грамматики;
3. LL(1)-грамматики.
   

Появление данной классификации КС-грамматик связано со следующей проблемой. Попытаемся на основе грамматики

  <S> -><T>
  -> <S> + <T>
  <T> -> id
  -> <T> x id

осуществить вывод (разбор) предложения а x b + c x d + e (рис.1).

Разбирать это предложение, в принципе, можно в любом порядке. Это может быть как левый вывод, т.е. последовательная подстановка самых левых НТ-символов правила. Это может быть правый вывод, т.е. последовательная подстановка самых правых НТ-символов правила на каждом шаге вывода. Также вывод может осуществляться и в смешанном порядке. Стратегия вывода ощутимо влияет на эффективность процесса. Каким бы ни был порядок вывода, отдельные шаги состоят из попыток подыскать правило подстановки, подходящее для рассматриваемого участка строки.

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

Таким образом, чем сложнее грамматика, тем более долгим и запутанным становится алгоритм разбора предложения.

Следовательно, конструируемая грамматика должна обладать некоторыми специальными свойствами, позволяющими осуществлять детерминированный ( безвозвратный ) вывод любого предложения.
Именно такими свойствами обладают S, Q, LL(1)-грамматики.

И т.д. (остальное, с картинками, в приложенном файле).