Системное программное обеспечение. Лабораторный практикум

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

Правила остовной грамматики G' описаны в виде массива строк GramRules. Каждому правилу в этом массиве соответствует строка, по написанию совпадающая с правой частью правила (пробелы игнорируются). Правила пронумерованы в порядке слева направо и сверху вниз – так, как они были пронумерованы в остовной грамматике G. Для поиска подходящего правила используется метод простого перебора – так как правил мало (всего 13), в данном случае этот метод вполне удовлетворителен.

Кроме двух упомянутых структур данных (GramMatrix и GramRules) в модуле SyntRulе описана также функция MakeSymbolStr, возвращающая наименование нетерминального символа в правилах остовной грамматики. В грамматике G во всех правилах символ обозначен Е, поэтому функция MakeSymbolStr всегда возвращает 'Е' как результат своего выполнения. Но тем не менее эта функция не бессмысленна, так как могут быть другие варианты остовных грамматик.

Модуль структур данных для синтаксического анализа и реализации алгоритма «сдвиг-свертка»

Модуль SyntSymb содержит реализацию алгоритма «сдвиг-свертка» и описания всех структур данных, необходимых для этой реализации. Поскольку сам алгоритм «сдвиг-свертка» не зависит от входного языка, реализующий его модуль также не зависит от входного языка и правил исходной грамматики (они специально вынесены в отдельный модуль).

Основу модуля составляют следующие структуры данных:

• TSymbInfo – описание двух типов символов грамматики: терминальных и нетерминальных;

• TSymbol – описание всех данных, связанных с понятием «символ грамматики»;

• TSymbStack – описание синтаксического стека.

Структура TSymbInfo содержит информацию о типе символа грамматики – поле SymbType, которое может принимать два значения: SYMBLEX (терминальный символ) или SYMBSYNT (нетерминальный символ), и дополнительные данные:

• ссылку на лексему (LexOne) – для терминального символа;

• перечень всех составляющих (LexList) – для нетерминального символа.

Перечень всех составляющих нетерминального символа LexList построен на основе динамического массива (тип TList из библиотеки VCL системы программирования Delphi 5). В него вносятся ссылки на символы, на основании которых создан данный символ, в том порядке, в котором они следуют в правиле грамматики.

Структура TSymbol содержит информацию о символе (поле SymbInfo типа TSymbInfo), а также номер правила грамматики, на основании которого создан символ (поле данных iRuleNum). Для терминальных символов номер правила равен 0, для нетерминальных символов он может быть от 1 до 13.

Кроме этих данных структура содержит методы, необходимые для работы с символами грамматики:

• конструктор CreateLex для создания терминального символа на основе лексемы;

• конструктор CreateSymb для создания нетерминального символа на основе правила грамматики и массива исходных символов;

• деструктор Destroy для освобождения занятой памяти при удалении символа (при удалении нетерминального символа удаляются все ссылки на его составляющие и динамический массив для их хранения);

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

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

Третья структура данных TSymbStack построена на основе динамического массива типа TList из библиотеки VCL системы программирования Delphi 5. Она предназначена для того, чтобы моделировать синтаксический стек МП-автомата. В этой структуре нет никаких данных (используются только данные, унаследованные от класса TList), но с ней связаны методы, необходимые для работы синтаксического стека:

• функция очистки стека (Clear) и деструктор для освобождения памяти при удалении стека (Destroy);

• функция доступа к символам в стеке начиная от его вершины (GetSymbol);

• функция для помещения в стек очередной входящей лексемы (Push), при этом лексема преобразуется в терминальный символ;

• функция, возвращающая самую верхнюю лексему в стеке (TopLexem), при этом нетерминальные символы игнорируются;

• функция, выполняющая свертку (MakeTopSymb); новый символ, полученный в результате свертки, помещается на вершину стека.