Синтаксис языков программирования. Нисходящий синтаксический анализ, процедурная и автоматная реализации

1. Цели работы

Изучение основных идей и понятий нисходящих методов синтаксического анализа, выявление свойств формальных грамматик, необходимых для реализации нисходящего восстановления дерева грамматического разбора, приобретение навыков построения процедурной и различных автоматных реализаций нисходящего анализа, исследование поведения нисходящих синтаксических акцепторов.

2. Индивидуальное задание

Идентификаторы и константы

Объявления примитивных типов (целое, вещественное, символьное, булево):

Объявления объектов и создание/уничтожение экземпляров

Оператор присваивания:

Условный оператор:

Переключатель

Оператор цикла:

3.Порядок выполнения работы

Используя пакет ВебТрансЛаб:

1.  изучить и освоить проверку принадлежности грамматики к классу LL(1), используя в качестве проверяемых грамматики, полученные при выполнении работы №4;

§  построить конечный автомат со стековой памятью и несколькими состояниями (шаблон …SyntAsManySA…), разобраться в структуре управляющей таблицы автомата, уяснить способы формирования и использования всех полей;

§  построить конечный автомат со стековой памятью и одним состоянием, управляемый входным символом и символом, снятым с верхушки стека (шаблон …SyntAsOneSA…), разобраться в структуре управляющей таблицы автомата, уяснить способы формирования и использования клеток таблицы;

§  построить процедурную реализацию рекурсивного спуска (шаблон …SyntAsRD…), уяснить способы формирования функций этого акцептора;

§  построить реализацию нисходящего грамматического разбора с возвратами (шаблон …SyntAsFullTpDn…);

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

3.  Проанализировать и сравнить между собой все полученные тексты программ и результаты выполнения пункта 2. Оценить степень пригодности изученных вариантов реализации нисходящих синтаксических акцепторов для выполнения курсовой работы.

4.  Изучить те элементы языка шаблонов, которые используются для преобразования внутреннего (формируемого преобразователем) представления конечного автомата со стековой памятью в программную реализацию нисходящего синтаксического акцептора.

4.  Ход работы

     Используя пакет ВебТрансЛаб была изучена и освоена проверка принадлежности грамматики к классу LL(1). Построены:

• конечный автомат со стековой памятью и несколькими состояниями (шаблон …SyntAsManySA…),
• конечный автомат со стековой памятью и одним состоянием, управляемый входным символом и символом, снятым с верхушки стека (шаблон …SyntAsOneSA…),
• процедурная реализация рекурсивного спуска (шаблон …SyntAsRD…),
• реализация нисходящего грамматического разбора с возвратами (шаблон …SyntAsFullTpDn…);

Таблица 1. Часть управляющей таблицы автомата с несколькими состояниями

Предполагается, что автомат при запуске оказывается в особом начальном со­стоянии, на каждом такте по входному символу и текущему состоянию опреде­ляет и выполняет операции над входным потоком символов, стековой памятью и собственным состоянием.

Таблица представляет собой список состояний с соответствующими им множествами выбора, так же набор флажков. Эти флаги служат для управления автоматом:

·  A - управляет чтением следующего входного символа

·  S - управляет занесением точки возврата

·  R - обеспечивает переход в состояние, номер которого извлекается из стека

·  E - запрещает останов по ошибке в случае, когда состояние соответствует нетерминалу из левой части и для него еще есть правила