Всего за 133 руб. Купить полную версию
Модуль структур данных для синтаксического анализа и реализации алгоритма "сдвиг-свертка"
Модуль 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); новый символ, полученный в результате свертки, помещается на вершину стека.
Кроме трех перечисленных ранее структур данных в модуле SyntSymb описана также функция Bui 1 dSyntList, моделирующая работу алгоритма "сдвиг-свертка" для грамматик операторного предшествования. Входными данными для функции являются список лексем (1 istLex), который должен быть заполнен в результате лексического анализа, и синтаксический стек (symbStack), который в начале выполнения функции должен быть пуст. Результатом функции является:
• нетерминальный символ (ссылающийся на корень синтаксического дерева), если разбор был выполнен успешно;
• терминальный символ, ссылающийся на лексему, где была обнаружена ошибка, если разбор выполнен с ошибками.
Функция BuildSyntList моделирует алгоритм "сдвиг-свертка" для грамматик операторного предшествования так, как он был описан в разделе "Краткие теоретические сведения".
Текст программы распознавателя
Кроме перечисленных выше модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Этот модуль (FormLab3) реализует графическое окно TLab3Form на основе класса TForm библиотеки VCL и включает в себя две составляющие:
• файл программного кода (файл FormLab3.pas);
• файл описания ресурсов пользовательского интерфейса (файл FormLab3.dfm).
Модуль FormLab3 построен на основе модуля FormLab2, который использовался для реализации интерфейса с пользователем в лабораторной работе № 2. Он содержит все данные, управляющие и интерфейсные элементы, которые были использованы в лабораторной работе № 2, поскольку первым этапом лабораторной работы № 3 является лексический анализ, который выполняется модулями, созданными для лабораторной работы № 2.
Кроме данных, используемых для выполнения лексического анализа так, как это было описано в лабораторной работе № 2, модуль содержит поле symbStack, которое представляет собой синтаксический стек, используемый для выполнения синтаксического анализа. Этот стек инициализируется при создании интерфейсной формы и уничтожается при ее закрытии. Он также очищается всякий раз, когда запускаются процедуры лексического и синтаксического анализа.
Кроме органов управления, использованных в лабораторной работе № 2, интерфейсная форма, описанная в модуле FormLab3, содержит органы управления для синтаксического анализатора лабораторной работы № 3:
• в многостраничной вкладке (PageControl1) появилась новая закладка (SheetSynt) под названием "Синтаксис";
• на закладке SheetSynt расположен интерфейсный элемент для просмотра иерархических структур (TreeSynt типа TTreeView).
Внешний вид новой закладки интерфейсной формы TLab3Form приведен на рис. 3.3.
Чтение содержимого входного файла организовано точно так же, как в лабораторной работе № 2.
После чтения файла выполняется лексический анализ, как это было описано в лабораторной работе № 2.
Если лексический анализ выполнен успешно, то в список лексем listLex добавляется информационная лексема, обозначающая конец строки, после чего вызывается функция выполнения синтаксического анализа BuildSyntList, на вход которой подаются список лексем (listLex) и синтаксический стек (symbStack). Результат выполнения функции запоминается во временной переменной symbRes.
Если переменная symbRes содержит ссылку на лексему, это значит, что синтаксический анализ выполнен с ошибками и эта лексема как раз указывает на то место, где была обнаружена ошибка. Тогда список строк входного файла позиционируется на указанное место ошибки, а пользователю выдается сообщение об ошибке.
Иначе, если ошибок не обнаружено, переменная symbRes указывает на корень построенного синтаксического дерева. Тогда в интерфейсный элемент TreeSynt записывается ссылка на корень синтаксического дерева, после чего все дерево отображается на экране с помощью функции MakeTree.
Функция MakeTree обеспечивает рекурсивное отображение синтаксического дерева в интерфейсном элементе типа TTreeView. Элемент типа TTreeView является стандартным интерфейсным элементом в ОС типа Windows для отображения иерархических структур (например он используется для отображения файловой структуры).
Рис. 3.3. Внешний вид третьей закладки интерфейсной формы для лабораторной работы № 3.
Полный текст программного кода модуля интерфейса с пользователем и описание ресурсов пользовательского интерфейса находятся в архиве, находящемся на веб-сайте издательства, в файлах FormLab3.pas и FormLab3.dfm соответственно.
Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 3, можно найти в архиве, находящемся на веб-сайте издательства, в подкаталогах LABS и COMMON (в подкаталог COMMON вынесены те программные модули, исходный текст которых не зависит от входного языка и задания по лабораторной работе). Главным файлом проекта является файл LAB3.DPR в подкаталоге LABS. Кроме того, текст модуля SyntSymb приведен в листинге П3.7 в приложении 3.
Выводы по проделанной работе
В результате лабораторной работы № 3 построен синтаксический анализатор на основе грамматики операторного предшествования. Синтаксический анализ позволяет проверять соответствие структуры исходного текста заданной грамматике входного языка. Синтаксический анализ позволяет обнаруживать любые синтаксические ошибки во входной программе. При наличии одной ошибки пользователю выдается сообщение с указанием местоположения ошибки в исходном тексте. Анализ типа обнаруженной ошибки не производится. При наличии нескольких ошибок в исходном тексте обнаруживается только первая из них, после чего дальнейший анализ не выполняется.
Результатом работы синтаксического анализатора является структура данных, представляющая синтаксическое дерево. В комплексе с лексическим анализатором, созданным при выполнении лабораторной работы № 2, построенный синтаксический анализатор позволяет выполнять подготовку данных, необходимых для выполнения следующей лабораторной работы, связанной с генерацией кода.