Читать книгу Системное программное обеспечение. Лабораторный практикум - Алексей Молчанов - Страница 29

Разбиение на модули

Модули, реализующие лексический анализатор, разделены на две группы:

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

• модули, программный код которых зависит от входного языка.

В первую группу входят модули:

• LexElem – описывает структуру данных элемента таблицы лексем;

• FormLab2 – описывает интерфейс с пользователем.

Во вторую группу входят модули:

• LexType – описывает типы входных лексем, связанные с ними наименования и текстовую информацию;

• LexAuto – реализует функционирование КА.

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

Кроме этих модулей для реализации лабораторной работы № 2 используются также программные модули (TblElem и FncTree), позволяющие работать с комбинированной таблицей идентификаторов, которые были созданы при выполнении лабораторной работы № 1. Эти два модуля, очевидно, также не зависят от входного языка.

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

Модуль типов лексем

Модуль LexType в детальных комментариях не нуждается. В нем перечислены все допустимые типы лексем (тип данных TLexType), каждой из которых соответствует наименование и обозначение лексемы. Вывод наименований лексем обеспечивает функция LexTypeName, а вывод обозначений – функция LexTypeInfo. Следует отметить, что кроме перечисленных в задании лексем используется еще одна дополнительная информационная лексема (LEXSTART), обозначающая конец строки.

Модуль LexElem описывает структуры данных элемента таблицы лексем (TLexem) и самой таблицы лексем (TLexList), а также все, что с ними связано.

Модуль структур данных таблицы идентификаторов

Структура данных таблицы лексем содержит информацию о лексеме (поле LexInfo). В этом поле содержится тип лексемы (LexType), а также следующие данные:

• VarInfo – ссылку на элемент таблицы идентификаторов для лексем типа «переменная»;

• ConstVal – целочисленное значение для лексем типа «константа»;

• szInfo – произвольная строка для информационной лексемы.

Для лексем других типов не требуется никакой дополнительной информации.

Следует отметить, что для лексем типа «переменная» хранится именно ссылка на таблицу идентификаторов, а не имя переменной. Именно для этого в данной лабораторной работе используются модули из лабораторной работы № 1. Для самого лексического анализатора не имеет значения, что хранить в таблице лексем – ссылку на таблицу идентификаторов со всей информацией о переменной или же только имя переменной. Но реализация лексического анализатора, при которой хранится именно ссылка на таблицу идентификаторов, чрезвычайно удобна для дальнейшей обработки данных, что будет очевидно в последующих работах (лабораторных работах № 3 и № 4). Поскольку лексический анализатор интересен не сам по себе, а в составе компилятора, такой подход принципиально важен.

Кроме этого в структуре данных элемента таблицы лексем хранится информация о позиции лексемы в тексте входной программы:

• iStr – номер строки, где встретилась лексема;

• iPos – позиция лексемы в строке;

• iAllP – позиция лексемы относительно начала входного файла.

Эта информация будет полезна, в частности, при информировании пользователя об ошибках.

Кроме этих данных структура содержит также:

• четыре конструктора для создания лексем четырех разных типов:

– CreateVar – для создания лексем типа «переменная»;

– CreateConst – для создания лексем типа «константа»;

– CreateInfo – для создания информационных лексем;

– CreateKey – для создания лексем других типов;

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

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

Хранить в структуре строку самой лексемы нет никакой необходимости (для переменных строка хранится в таблице идентификаторов, для других типов лексем она просто не нужна).

Сама таблица лексем (тип данных TLexList) построена на основе динамического массива TList из библиотеки VCL (модуль Classes) системы программирования Delphi 5.

Динамический массив типа TList обеспечивает все функции и данные, необходимые для хранения в памяти произвольного количества лексем (максимальное количество лексем ограничено только объемом доступной оперативной памяти). Для таблицы лексем TLexList дополнительно реализованы функции очистки таблицы, которые освобождают память, занятую лексемами, при их удалении из таблицы (функция Clear и деструктор Destroy), а также функция GetLexem и свойство Lexem, обеспечивающие удобный доступ к любой лексеме в таблице по ее индексу (порядковому номеру).

Модуль моделирования работы КА

Модуль LexAuto, моделирующий работу КА, на основе которого построен лексический распознаватель, – самый значительный по объему программного кода. Однако по содержанию программного кода он предельно прост. Этот модуль обеспечивает функционирование полного КА, фрагменты графа переходов которого были изображены на рис. 2.1 и 2.2, а функция переходов была построена выше.

Главной составляющей этого программного модуля является функция МакеLexList, которая непосредственно моделирует работу КА. На вход функции подается входная программа в виде списка строк (формальный параметр listFile) и таблица лексем, куда должны помещаться найденные лексемы (формальный параметр listLex). Результатом работы функции является 0, если лексический анализ выполнен без ошибок, а если ошибка обнаружена – номер строки в исходном файле, в которой она присутствует. Для более подробной информации об обнаруженной ошибке функция создает информационную лексему и помещает ее в конец таблицы лексем. Сама информационная лексема кроме текстовой информации об ошибке содержит еще дополнительную информацию о ее местонахождении в исходной программе (смещение от начала файла и длина ошибочной лексемы).

В типе данных TAutoPos перечислены все возможные состояния КА. Перечень состояний полностью соответствует функции переходов КА.

Реализация функции MakeLexList, несмотря на большой объем программного кода, предельно проста. Она построена на основе двух вложенных циклов (первый – по строкам входного списка, второй – по символам в текущей строке), внутри которых находятся два уровня вложенных оператора выбора типа case – типичный подход к моделированию функционирования КА. Внешний оператор case выполняется по всем возможным состояниям автомата, а case второго уровня – по допустимым входным символам в каждом состоянии.

Можно обратить внимание на шесть вспомогательных функций:

• AddVarToList – добавление лексемы типа «переменная» в таблицу лексем;

• AddVarKeyToList – добавление лексем типа «переменная» и типа «разделитель» в таблицу лексем;

• AddConstToList – добавление лексемы типа «константа» в таблицу лексем;

• AddConstKeyToList – добавление лексем типа «константа» и типа «разделитель» в таблицу лексем;

• AddKeyToList – добавление лексемы типа «ключевое слово» или «разделитель» в таблицу лексем;

• Add2KeysToList – добавление лексем типа «ключевое слово» и «разделитель» в таблицу лексем подряд.

Эти функции, по сути, являются реализацией функции, которая на графе переходов КА была обозначена F.

Еще две вспомогательные функции служат для упрощения кода. Они выполняют часто повторяющиеся действия в состояниях автомата, которые связаны со средними символами ключевых слов (в функции переходов эти состояния обозначены T2, T3, E2, E3, X2 и A2) и завершающими символами ключевых слов (в функции переходов эти состояния обозначены I2, T4, E4, O2, X3 и A3).

Построенный лексический анализатор обнаруживает три типа ошибок:

• неверный символ в лексеме (например, сочетания «2a» или «:6» будут признаны неверными символами в лексемах);

• незакрытый комментарий (присутствует открывающая фигурная скобка, но отсутствует соответствующая ей закрывающая);

• незавершенная лексема (в данном входном языке это может быть только символ «:» в конце входной программы, который будет воспринят как начало незавершенной лексемы «:=»).

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

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