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

Введение

Эта книга является логическим продолжением и дополнением учебника «Системное программное обеспечение»,[1] вышедшего в свет в 2003 году. Главной целевой аудиторией книги «Системное программное обеспечение» были студенты технических вузов, обучающиеся по специальности «Вычислительные машины, комплексы, системы и сети» и родственным с ней направлениям, поэтому материал книги был подобран исходя из требований стандарта этой специальности для курса «Системное программное обеспечение». Программа этого курса предусматривает практические занятия в виде лабораторных работ, а также выполнение курсовой работы по итогам

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

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

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

Для понимания практических примеров необходимо знание языка программирования Object Pascal и хотя бы общее представление о системе программирования Delphi, а также знание языка ассемблера процессоров типа Intel 80x86. В ряде случаев для сравнения и понимания примеров синтаксических конструкций рекомендуется знать язык программирования C. Соответствующие сведения можно почерпнуть в дополнительной литературе, приведенной в конце книги [13, 23–25, 28, 31, 32, 37, 39, 41, 44].

Все практические примеры созданы автором в системе программирования Delphi 5 на языке Object Pascal с использованием примитивных классов из библиотеки VCL. Но автор приложил все усилия, чтобы они не были привязаны ни к версии системы программирования, ни к особенностям исходного языка. Поэтому желающие без проблем могут перенести их под любую версию Delphi, а при необходимости переписать, например на C++, для чего требуются только самые элементарные знания языка.

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

Структура книги проста: она содержит описания четырех лабораторных работ и одной курсовой работы. Каждая лабораторная работа снабжена краткими теоретическими

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

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

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

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

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

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

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

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

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

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

Цель работы

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

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

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

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