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

• для правил 2 и 5 – схема полного условного оператора;

• для правила 3 – схема неполного условного оператора;

• для правил 4 и 6 – схема оператора присваивания;

• для правил 7, 8 и 10 – схема для бинарных линейных операций;

• для правила 13 – схема для скобок;

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

Функция MakeTriaD1istNOP содержит две вспомогательные функции:

• функцию MakeOperand для порождения кода, связанного с дочерним узлом дерева (одним из операндов);

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

Для построения кода для нижележащих нетерминальных символов по дереву функция MakeTriaD1istNOP рекурсивно вызывает сама себя. Этот вызов реализован в функции MakeOperand, если нижележащий узел является нетерминальным символом, а также напрямую для узлов, связанных со скобками и с точкой с запятой (как было рассмотрено ранее при построении схем СУ-перевода).

Модуль вычисления значений триад на этапе компиляции

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

Модуль содержит одну-единственную функцию CalcTriad, которая предельно проста и в комментариях не нуждается.

Модуль, реализующий алгоритмы оптимизации

Модуль TrdOpt реализует два алгоритма оптимизации списка триад:

• методом свертки объектного кода;

• методом исключения лишних операций.

Алгоритмы, реализованные в модуле TrdOpt, в общем случае не зависят от входного языка, однако они обрабатывают триады типа «присваивание» (в данной реализации – TRDASSIGN). Кроме того, границы линейных участков, на которых работают эти алгоритмы, зависят от триад условного и безусловного перехода (в данной реализации – TRDIF и TRDJMP). Сами алгоритмы требуют для себя триад специального типа, которые в данном случае реализованы как TRDC и TRDSAME.

В итоге реализация алгоритмов оптимизации зависит от следующих типов триад:

• триад присваивания;

• триад условного и безусловного перехода;

• триад специальных типов.

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

Функция вычисления значений триад при свертке объектного кода, которая имеет явную зависимость от входного языка, вынесена в отдельный модуль (модуль TrdCalc, функция CalcTriad).

Кроме функций, реализующих алгоритмы оптимизации, модуль TrdOpt содержит две структуры данных:

• TConstInfo – для хранения информации о значениях переменных;

• TDepInfo – для хранения информации о числах зависимости переменных.

Обе эти структуры построены на основе структуры TAddVarInfo, описанной в модуле TblElem (этот модуль был создан при выполнении лабораторной работы № 1), и предназначены для хранения информации, связанной с переменной в таблице идентификаторов.

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

Структура TDepInfo хранит информацию о числе зависимости переменной. Она используется в алгоритме оптимизации методом исключения лишних операций.

Каждая из этих структур имеет одно поле, которое и предназначено для хранения информации. Для доступа к этому полю используются виртуальные функции и связанные с ними свойства, которые переопределяют функции и свойства типа данных TAddVarInfo.

Эти структуры данных создаются по мере выполнения соответствующих алгоритмов и уничтожаются после завершения их выполнения.

Теперь можно сравнить два подхода к хранению дополнительной информации:

1. Хранение информации внутри структур данных (реализовано для триад).

2. Хранение внутри структур данных только ссылок (указателей), а самой информации – во внешних структурах.

Первый подход имеет следующие преимущества:

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

• нет необходимости работать с динамической памятью, выделять и освобождать ее по мере надобности.

В то же время первый подход имеет ряд недостатков:

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

• обеспечивается меньшая гибкость в обработке информации.

Второй подход имеет следующие преимущества:

• можно хранить разнородную информацию в зависимости от потребностей на каждой стадии компиляции;

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

• обеспечивается более гибкая обработка информации (например, легко реализуется понятие «отсутствие данных» в алгоритме оптимизации методом свертки объектного кода через пустую ссылку nil).

Но и он имеет ряд недостатков:

• использование ссылок увеличивает время доступа к хранимой информации, что может быть важно при обработке компилятором больших объемов данных;

• использование ссылок требует работы с динамической памятью, выделения и освобождения памяти по мере использования информации, что расходует время и ресурсы ОС.

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

Алгоритмы оптимизации реализованы в модуле TrdOpt в виде двух процедур:

• OptimizeConst – для оптимизации методом свертки объектного кода;

• OptimizeSame – для оптимизации методом исключения лишних операций.

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

• С (TRDC) – при оптимизации методом свертки объектного кода;

• Same (TRDSAME) – при оптимизации методом исключения лишних операций.

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

Процедуры OptimizeConst иOptimizeSame реализуют алгоритмы оптимизации, которые были описаны в разделе «Краткие теоретические сведения», поэтому в дополнительных пояснениях не нуждаются.

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

Кроме перечисленных модулей необходим еще модуль, обеспечивающий интерфейс с пользователем. Этот модуль (FormLab4) реализует графическое окно TLab4Form на основе класса TForm библиотеки VCL и включает в себя две составляющие:

• файл программного кода (файл FormLab4.pas);

• файл описания ресурсов пользовательского интерфейса (файл FormLab4.dfm).

Модуль FormLab4 построен на основе модуля FormLab3, который использовался для реализации интерфейса с пользователем в лабораторной работе № 3. Он содержит все данные, управляющие и интерфейсные элементы, которые были использованы в лабораторных работах № 2 и 3. Такой подход оправдан, поскольку первым этапом лабораторной работы № 4 является лексический анализ, который выполняется модулями, созданными для лабораторной работы № 2, а вторым этапом – синтаксический анализ, который выполняется модулями, созданными для лабораторной работы № 3.

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

Кроме органов управления, использованных в лабораторной работе № 3, интерфейсная форма, описанная в модуле FormLab4, содержит органы управления для генератора списка триад лабораторной работы № 4:

• в многостраничной вкладке (PageControll) появилась новая закладка (Sheet-Triad) под названием «Триады»;

• на закладке SheetTriad расположены интерфейсные элементы для вывода и просмотра списков триад (группа с заголовком и список строк для отображения каждого списка триад):

GroupTriadAll и ListTriadAll – для отображения полного списка триад, построенного до применения алгоритмов оптимизации;

GroupTriadConst и ListTriadConst – для отображения списка триад, построенного после оптимизации методом свертки объектного кода;

GroupTriadSame и ListTriadSame – для отображения списка триад, построенного после оптимизации методом исключения лишних операций.

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

• на первой закладке SheetFi 1 е («Исходный файл») появились два дополнительных органа управления – флажки с двумя состояниями («пусто» или «отмечено»):

CheckDelC – при установке этого флажка триады типа С удаляются из списка триад после выполнения оптимизации методом свертки объектного кода;

CheckDelSame – при установке этого флажка триады типа same удаляются из списка триад после выполнения оптимизации методом исключения лишних операций.

Внешний вид новой закладки интерфейсной формы TLab4Form приведен на рис. 4.3.

Рис. 4.3. Внешний вид четвертой закладки интерфейсной формы для лабораторной работы № 4.

Чтение содержимого входного файла организовано точно так же, как в лабораторной работе № 2.

После чтения файла выполняется лексический анализ, как это было описано в лабораторной работе № 2, а затем, при успешном выполнении лексического анализа, синтаксический анализ, как это было описано в лабораторной работе № 3.

Если синтаксический анализ выполнен успешно, полученная в результате его выполнения переменная symbRes указывает на корень построенного синтаксического дерева. Тогда, после того как синтаксическое дерево отобразится на экране с помощью функции MakeTree, вызывается функция построения списка триад по синтаксическому дереву MakeTriaD1ist (из модуля TrdMake). Список триад запоминается в список listTriad, а результат выполнения функции – во временную переменную lexTmp.

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

Иначе, если переменная lexTmp после построения списка триад содержит пустую ссылку (nil), это значит, что построение списка триад выполнено без ошибок, и список listTriad содержит все построенные триады в порядке их следования. Список триад отображается на экране в списке строк ListTriadAll, после чего выполняется оптимизация методом свертки объектного кода – вызывается процедура OptimizeConst. Если установлен флажок CheckDel_C, то после оптимизации методом свертки объектного кода из списка триад удаляются триады типа C (вызывается функция DelTriadTypes с параметром TRD_CONST), после чего список триад отображается в списке строк ListTriadConst. Затем выполняется оптимизация методом исключения лишних операций – вызывается процедура OptimizeSame. Если установлен флажок CheckDelSame, то после оптимизации методом исключения лишних операций из списка триад удаляются триады типа same (вызывается функция DelTriadTypes с параметром TRD_SAME), после чего список триад отображается в списке строк ListTriadSame.

Полный текст программного кода модуля интерфейса с пользователем и описание ресурсов пользовательского интерфейса можно найти в архиве, который располагается на веб-сайте издательства, в файлах FormLab4.pas и FormLab4.dfm соответственно.

Полный текст всех программных модулей, реализующих рассмотренный пример для лабораторной работы № 4, можно найти в архиве, располагающемся на вебсайте издательства, в подкаталогах LABS и COMMON (в подкаталог COMMON вынесены те программные модули, исходный текст которых не зависит от входного языка и задания по лабораторной работе). Главным файлом проекта является файл LAB4.DPR в подкаталоге LABS. Кроме того, текст модуля Triads приведен в листинге П3.10, а текст модуля TrdOpt – в листинге П3.11 в приложении 3.

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

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

Построенный при выполнении данной лабораторной работы генератор списка триад входит в состав компилятора, в который также входят: лексический анализатор, построенный при выполнении лабораторной работы № 2, и синтаксический анализатор, построенный при выполнении лабораторной работы № 3. Этот компилятор получает на вход исходную программу в соответствии с заданной грамматикой и порождает результирующую программу в виде списка триад.

Компилятор позволяет обнаруживать следующие однократные ошибки:

• любые лексические ошибки (неправильные лексемы);

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

• семантические ошибки типа «присваивание значения константе».

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

В результате выполнения лабораторных работ № 1–4 построен компилятор, выполняющий обработку исходной программы за пять проходов:

1. Лексический анализ исходного текста и построение таблицы лексем.

2. Синтаксический анализ по таблице лексем и построение дерева синтаксического разбора.

3. Построение списка триад по дереву синтаксического разбора.

4. Оптимизация списка триад методом свертки объектного кода.

5. Оптимизация списка триад методом исключения лишних операций.

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

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

Курсовая работа

Цель работы

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

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

Для программной реализации компилятора рекомендуется использовать язык программирования Object Pascal и систему программирования Borland Delphi. Возможно использовать другие языки и системы программирования по согласованию с преподавателем.

Компилятор рекомендуется построить из следующих составных частей:

1. Лексический анализатор.

2. Синтаксический анализатор.

3. Оптимизатор.

4. Генератор результирующего кода.

Для построения компилятора рекомендуется использовать методы, освоенные в ходе выполнения лабораторных работ по курсу «Системное программное обеспечение».

Порядок выполнения работы

Рекомендуемый порядок выполнения работы представлен в табл. 5.1.

Таблица 5.1. Рекомендуемые этапы и время выполнения курсовой работы

Требования к содержанию пояснительной записки

Пояснительная записка к курсовой работе должна содержать следующие разделы:

1. Краткое изложение цели работы.

2. Задание по лабораторной работе (номер варианта и полное описание своего варианта).

3. Грамматика входного языка в одном из трех возможных видов:

• форма Бэкуса—Наура;

• форма с метасимволами;

• графическая форма.

4. Описание выбранного способа организации таблицы идентификаторов с обоснованием сделанного выбора.

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

6. Граф переходов или иное описание конечного автомата лексического анализатора.

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

8. Описание синтаксического анализатора в зависимости от выбранного класса КС-грамматик (включая все необходимые управляющие таблицы и множества).

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

10. Описание используемого метода порождения результирующего кода.

11. Описание используемого метода оптимизации.

12. Информация об организации построенного компилятора, его разбиении на проходы, количество проходов в компиляторе.

13. Выводы по проделанной работе.

14. Пример входной программы и результирующей программы, построенной компилятором.

15. Текст программы компилятора.

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

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

Допускается для построения лексического и (или) синтаксического анализаторов использовать автоматизированные методы построения распознавателей (например на основе программ LEX и YACC) [2, 3, 7, 27, 35]. В этом случае не требуется приводить граф переходов конечного автомата (для лексического анализатора) и описание синтаксического анализатора.

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