Описание этапа синтаксического анализа

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

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

Построение КС-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

1. Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;

2. В качестве терминальных символов использовать токены;

3. Металингвистический символ «::=» заменить символом «à»;

4. Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;

5. Исключить металингвистические символы [ ] и { }, включив в правила грамматики e-правила и рекурсивные правила.

Определение класса КС-грамматики входного языка

Построенная КС-грамматика входного языка должна входить в определенный в задании на курсовую работу класс грамматик. Определение класса КС-грамматики рекомендуется выполнять с помощью лабораторного практикума [2]. Если грамматика не принадлежит заданному классу, то необходимо ее преобразовать. Для преобразования можно использовать алгоритмы и рекомендации, приведенные в [3] – [6].

Разбиение грамматики на подграмматики

Если преобразование КС-грамматики не приведет к нужному результату, то рекомендуется найти правила грамматики, в которых нарушаются требования, предъявляемые к грамматикам заданного класса, после чего выполнить одно или несколько действий из приведенного списка:

1. Изменить (пополнить) список токенов так, чтобы терминальные символы грамматики, приводящие к конфликту, были разбиты на непересекающиеся подмножества.

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

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

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

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

1. Совокупности выделенных из грамматики взаимосвязанных правил должна представлять собой КС-грамматику.

2. Основной символ подграмматики становится (специальным) терминальным символом исходной грамматики.

3. Если множества нетерминальных символов подграмматики и модифицированной исходной грамматики не пересекаются, то синтаксический анализ для каждой из них может быть реализован при помощи отдельного процессора с магазинной памятью (ДМП-процессора).

Описание промежуточного языка

Тип промежуточного языка, используемого для представления программы после синтаксического анализа, определен в задании на курсовую работу. Описание различных типов промежуточных языков приводится в [1].

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

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

Таблица 2.4

Неформальное описание перевода

При описании перевода конструкций входного языка в промежуточный язык следует руководствоваться методикой, изложенной в [1]. Рекомендуемая форма описания перевода приведена на рис. 2.3. Для возможности построения ссылок на описание в его заголовке указывается номер первого правила грамматики, описывающего конструкцию. Формы конструкции и тетрады, входящие в ее перевод, нумеруются. Например (j).1.5 – ссылка на тетраду определения метки перевода полной формы условного оператора IF.