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

Оглавление

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

Введение

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

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

Цель работы

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

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

Принципы организации таблиц идентификаторов

Простейшие методы построения таблиц идентификаторов

Построение таблиц идентификаторов по методу бинарного дерева

Хэш-функции и хэш-адресация

Хэш-адресация с рехэшированием

Хэш-адресация с использованием метода цепочек

Комбинированные способы построения таблиц идентификаторов

Требования к выполнению работы

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

Требования к оформлению отчета

Основные контрольные вопросы

Варианты заданий

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

Задание для примера

Выбор и описание хэш-функции

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

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

Текст программы

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

Лабораторная работа № 2. Проектирование лексического анализатора

Цель работы

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

Назначение лексического анализатора

Проблема определения границ лексем

Таблица лексем и содержащаяся в ней информация

Построение лексических анализаторов (сканеров)

Требования к выполнению работы

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

Требования к оформлению отчета

Основные контрольные вопросы

Варианты заданий

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

Задание для примера

Грамматика входного языка

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

Реализация лексического анализатора

Текст программы распознавателя

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

Лабораторная работа № 3. Построение простейшего дерева вывода

Цель работы

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

Назначение синтаксического анализатора

Проблема распознавания цепочек КС-языков

Виды распознавателей для КС-языков

Построение синтаксического анализатора

Грамматики предшествования

Алгоритм «сдвиг-свертка» для грамматик операторного предшествования

Требования к выполнению работы

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

Требования к оформлению отчета

Основные контрольные вопросы

Варианты заданий

Варианты исходных грамматик

Исходные грамматики и типы допустимых лексем

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

Задание для примера

Построение матрицы операторного предшествования

Реализация синтаксического распознавателя

Текст программы распознавателя

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

Лабораторная работа № 4. Генерация и оптимизация объектного кода

Цель работы

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

Общие принципы генерации кода

Синтаксически управляемый перевод

Способы внутреннего представления программ

Многоадресный код с неявно именуемым результатом (триады)

Схемы СУ-перевода

Общие принципы оптимизации кода

Принципы оптимизации линейных участков

Свертка объектного кода

Исключение лишних операций

Общий алгоритм генерации и оптимизации объектного кода

Требования к выполнению работы

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

Требования к оформлению отчета

Основные контрольные вопросы

Варианты заданий

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

Задание для примера

Построение схем СУ-перевода

Пример генерации списка триад

Реализация генератора списка триад

Текст программы генератора списка триад

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

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

Цель работы

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

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

Задание на курсовую работу

Варианты заданий

Порядок оценки результатов работы

Рекомендации по выполнению работы

Пример выполнения курсовой работы

Задание для примера выполнения работы

Грамматика входного языка

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

Описание лексического анализатора

Описание синтаксического анализатора

Внутреннее представление программы и генерация кода

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

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

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

Приложение 1. Функция переходов конечного автомата для лабораторной работы № 2

Приложение 2. Функция переходов конечного автомата для курсовой работы

Приложение 3. Тексты программных модулей для курсовой работы

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

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

Модуль описания всех типов лексем

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

Модуль заполнения таблицы лексем по исходному тексту программы

Модуль описания матрицы предшествования и правил исходной грамматики

Модуль описания структур данных синтаксического анализатора и реализации алгоритма «сдвиг-свертка»

Модуль описания допустимых типов триад

Модуль вычисления значений триад при свертке объектного кода

Модуль описания структур данных триад

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

Модуль создания списка триад на основе дерева разбора

Модуль построения ассемблерного кода по списку триад

Модуль интерфейса с пользователем

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

Пример 1. Вычисление факториала

Пример 2. Иллюстрация работы функций оптимизации

Литература

Основная литература

Дополнительная литература

Отрывок из книги

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

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

.....

• схемы организации таблиц идентификаторов (в соответствии с вариантом задания);

• описание алгоритмов поиска в таблицах идентификаторов (в соответствии с вариантом задания);

.....