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

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

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

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

Приводимый в книге практический материал не претендует на полноту охвата всего курса «Системное программное обеспечение». Автор считает необходимым дополнить его работами по программированию параллельных взаимодействующих процессов [3, 5], а также методами разработки программного обеспечения в распределенных системах (по технологиям построения систем «клиент-сервер» и многоуровневой архитектуре [7]). Автор надеется, что ему удастся в ближайшее время подготовить соответствующий материал.

От издательства

Ваши замечания, предложения и вопросы отправляйте по адресу электронной почты [email protected] (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

Подробную информацию о наших книгах вы найдете на веб-сайте издательства: http://www.piter.com.

Лабораторная работа № 1 Организация таблиц идентификаторов

Цель работы

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

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

Краткие теоретические сведения

Назначение таблиц идентификаторов

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

Набор характеристик, соответствующий каждому элементу исходной программы, зависит от типа этого элемента, от его смысла (семантики) и, соответственно, от той роли, которую он исполняет в исходной и результирующей программах. В каждом конкретном случае этот набор характеристик может быть свой в зависимости от синтаксиса и семантики входного языка, от архитектуры целевой вычислительной системы и от структуры компилятора. Но есть типовые характеристики, которые чаще всего присущи тем или иным элементам исходной программы. Например для переменной – это ее тип и адрес ячейки памяти, для константы – ее значение, для функции – количество и типы формальных аргументов, тип возвращаемого результата, адрес вызова кода функции. Более подробную информацию о характеристиках элементов исходной программы, их анализе и использовании можно найти в [1, 3, 7].