Системное программное обеспечение. Лабораторный практикум
Шрифт:
На графе и при описании функции переходов не обозначено состояние «ошибка», чтобы не загромождать и без того сложный граф и функцию. В это состояние КА переходит всегда, когда получает на вход символ, по которому нет переходов из текущего состояния.
Функция F, которой помечены дуги КА на графе и переходы в функции переходов, соответствует выполнению записи данных в таблицу лексем. Аргументы функции зависят от текущего состояния КА. В реализации программы, моделирующей функционирование КА, этой функции должны соответствовать несколько функций, вызываемые в зависимости от текущего состояния и входного символа.
Надо
Можно заметить, что функция переходов КА получилась довольно громоздкой, хотя и простой по своей сути (для всех ключевых слов она работает однотипно). В реализации функционирования КА проще было бы не выделять отдельные состояния для ключевых слов, а переходить всегда по обнаружению буквы на входе КА в состояние V. Тогда проверку того, является ли считанная строка ключевым словом или же идентификатором, можно было бы выполнять на момент ее записи в таблицу лексем с помощью стандартных операций сравнения строк. Граф переходов КА в таком варианте был бы намного компактнее – он выглядел бы точно так же, как фрагмент, представленный на рис. 2.1. Его можно назвать «сокращенным» графом переходов КА (или «сокращенным КА»).
Но следует отметить, что, несмотря на большую наглядность и простоту реализации, сокращенный КА будет менее эффективным, поскольку в момент записи лексемы в таблицу он должен будет выполнять ее сравнение со всеми известными ключевыми словами (в данном случае надо определять шесть ключевых слов – следовательно, будет выполняться шесть сравнений строк). То есть такой КА будет повторно просматривать уже прочитанную часть входной цепочки, да еще и несколько раз! И хотя в явном виде в реализации сокращенного КА эта операция не присутствует, она все равно будет выполняться в вызове библиотечной функции сравнения строк.
Итак, хотя сокращенный КА меньше по количеству состояний и проще в реализации, он является менее эффективным, чем полный КА, построенный на анализе всех входных лексем. Тем не менее оба варианта реализации КА обеспечивают построение требуемого лексического анализатора. Какой из них выбрать, решает разработчик компилятора.
Реализация лексического анализатора
Разбиение на модули
Модули, реализующие лексический анализатор, разделены на две группы:
• модули, программный код которых не зависит от входного языка;
• модули, программный код которых зависит от входного языка.
В первую группу входят модули:
• LexElem – описывает структуру данных элемента таблицы лексем;
• FormLab2 – описывает интерфейс с пользователем.
Во вторую группу входят модули:
• LexType – описывает типы входных лексем, связанные с ними наименования и текстовую информацию;
• LexAuto – реализует функционирование КА.
Такое разбиение на модули позволяет использовать те же самые структуры данных для организации лексического распознавателя при изменении входного языка.
Кроме этих модулей для реализации лабораторной работы № 2 используются также программные модули (TblElem и FncTree), позволяющие работать с комбинированной таблицей
Кратко опишем содержание программных модулей, используемых для организации лексического анализатора.
Модуль типов лексем
Модуль LexType в детальных комментариях не нуждается. В нем перечислены все допустимые типы лексем (тип данных TLexType), каждой из которых соответствует наименование и обозначение лексемы. Вывод наименований лексем обеспечивает функция LexTypeName, а вывод обозначений – функция LexTypeInfo. Следует отметить, что кроме перечисленных в задании лексем используется еще одна дополнительная информационная лексема (LEXSTART), обозначающая конец строки.
Модуль LexElem описывает структуры данных элемента таблицы лексем (TLexem) и самой таблицы лексем (TLexList), а также все, что с ними связано.
Модуль структур данных таблицы идентификаторов
Структура данных таблицы лексем содержит информацию о лексеме (поле LexInfo). В этом поле содержится тип лексемы (LexType), а также следующие данные:
• VarInfo – ссылку на элемент таблицы идентификаторов для лексем типа «переменная»;
• ConstVal – целочисленное значение для лексем типа «константа»;
• szInfo – произвольная строка для информационной лексемы.
Для лексем других типов не требуется никакой дополнительной информации.
Следует отметить, что для лексем типа «переменная» хранится именно ссылка на таблицу идентификаторов, а не имя переменной. Именно для этого в данной лабораторной работе используются модули из лабораторной работы № 1. Для самого лексического анализатора не имеет значения, что хранить в таблице лексем – ссылку на таблицу идентификаторов со всей информацией о переменной или же только имя переменной. Но реализация лексического анализатора, при которой хранится именно ссылка на таблицу идентификаторов, чрезвычайно удобна для дальнейшей обработки данных, что будет очевидно в последующих работах (лабораторных работах № 3 и № 4). Поскольку лексический анализатор интересен не сам по себе, а в составе компилятора, такой подход принципиально важен.
Кроме этого в структуре данных элемента таблицы лексем хранится информация о позиции лексемы в тексте входной программы:
• iStr – номер строки, где встретилась лексема;
• iPos – позиция лексемы в строке;
• iAllP – позиция лексемы относительно начала входного файла.
Эта информация будет полезна, в частности, при информировании пользователя об ошибках.
Кроме этих данных структура содержит также:
• четыре конструктора для создания лексем четырех разных типов:
– CreateVar – для создания лексем типа «переменная»;
– CreateConst – для создания лексем типа «константа»;
– CreateInfo – для создания информационных лексем;
– CreateKey – для создания лексем других типов;
• деструктор Destroy для освобождения памяти, занятой лексемой (важен для информационных лексем);
• свойства и функции для доступа к информации о лексеме.
Хранить в структуре строку самой лексемы нет никакой необходимости (для переменных строка хранится в таблице идентификаторов, для других типов лексем она просто не нужна).