Белорусский государственный университет информатики и
радиоэлектроники, 2007, 127с.
Для студентов специальности I-40 02 01 «Вычислительные машины, системы и сети»
Содержание
Операционные системы
Предмет курса, его цели и задачи.
Методическое обеспечение.
История развития системного ПО.
Классификация системного ПО.
ОС, системы управления файлами, интерфейсы, системы программирования, утилиты. Понятие ресурса в ОС.
Концепция виртуализации ресурса
Операционная система.
Классификация ОС.
ОС реального времени.
Микроядерные и монолитные ОС.
Структура ОС.
Ядро, командный процессор, подсистема ввода-вывода, система управления памятью, файловая система.
Принципы построения ОС.
Понятие виртуальной машины.
Безопасность операционных систем.
Понятие системных вызовов.
Системные вызовы стандарта POSIX.
Интерфейс Win32 API.
Понятие процесса и потока
Концепция процесса.
Диаграмма состояний процесса.
Операции над процессами.
Создание и завершение процесса.
Иерархия процессов.
Структуры управления процессами.
Процессы-зомби.
Системные вызовы для управления процессами.
Процессы в Windows и UNIX.
Процессы и потоки.
Понятия мультизадачности и многопоточности.
Потоки в пространстве пользователя.
Потоки в ядре. Облегченные потоки.
Потоки в Windows и UNIX.
Всплывающие потоки.
Понятие о прерываниях.
Параллельные процессы.
Независимые и взаимодействующие процессы.
Сигналы UNIX.
Сообщения Windows
Диспетчеризация процессов
Стратегии планирования.
Дисциплины диспетчеризации.
Вытесняющие и невытесняющие алгоритмы.
Алгоритмы планирования без переключений.
Циклическое и приоритетное планирование.
Динамические приоритеты.
Планирование в системах реального времени.
Планирование потоков.
Гарантии обслуживания процесса
Механизмы взаимного исключения
Состояние состязания.
Задача об обедающих философах.
Детерминированный набор.
Условия Бернстайна.
Понятие критического ресурса.
Критическая область.
Взаимное исключение.
Механизмы взаимного исключения.
Алгоритм Деккера.
Алгоритм Петерсона
Типовые механизмы синхронизации
Операции Test & Set.
Поддержка механизма TS в современных процессорах.
Семафоры Дейкстры.
Базовые операции над семафорами.
Мьютексы. Задача поставщик-потребитель.
Поддержка механизмов синхронизации в Windows и UNIX.
Мониторы Хоара. Поддержка мониторов в языках программирования.
Задача о парикмахерской.
Задача читатели-писатели
Механизмы межпроцессного взаимодействия
Механизмы для взаимодействия процессов.
Сигналы. Каналы.
Именованные и анонимные каналы.
Сообщения. Очереди со-общений.
Порты.
Буферы сообщений.
Сообщения как средство синхронизации.
Рандеву.
Барьеры.
Поддержка механизмов взаимодействия в ОС UNIX и Windows
Обработка тупиковых ситуаций
Понятие тупика.
Условия Коффмана.
Модель Холта.
Модель пространства состояний.
Надежное, опасное и безопасное состояния.
Обнаружение тупика при наличии одного ресурса каждого вида.
Обнаружение тупика при наличии нескольких ресурсов каждого вида.
Выход из взаимоблокировки.
Обход и предотвращение тупиковой ситуации.
Двухфазовое блокирование.
Проблема голодания
Управление памятью
Управление памятью.
Задачи управления памятью.
Однозадачная система.
Сегментная организация памяти.
Настройка адресов и защита памяти.
Подкачка.
Битовые массивы и связные списки.
Алгоритмы выбора сегмента для размещения процесса.
Страничная организации памяти.
Виртуальная память.
Таблицы страниц.
Многоуровневые таблицы страниц.
Буферы быстрого преобразования TLB.
Инвертированные таблицы страниц.
Обработка страничного прерывания.
Поддержка сегментно-страничной организации памяти в процессорах семейства Pentium. Структура элемента таблицы страниц.
Таблица страничных блоков.
Отдельные пространства команд и данных.
Совместно используемые страницы.
Проблемы, возникающие при вызове страничного прерывания.
Распределение оперативной памяти в Windows NT, UNIX
Алгоритмы замещения страниц
Стратегии выборки по запросу и с упреждением.
Алгоритмы замещения страниц.
Алгоритм NRU, LRU, FIFO, NFU.
Бит использования страницы.
Понятие рабочего набора.
Аномалия Билэди.
Рабочие наборы в Windows
Подсистемы ввода-вывода
Управление вводом-выводом.
Блочные и символьные операции.
Синхронные и асинхронные операции.
Отображение ввода-вывода на адресное пространство памяти.
Прямой доступ к памяти.
Кэширование операций.
Упреждающее чтение.
Отложенная запись.
Программное обеспечение ввода-вывода.
Драйверы UNIX.
Псевдоустройства.
Переключатели устройств.
Файл устройства.
Драйверы Windows.
Процесс загрузки драйверов.
Дерево устройств.
Дисциплины оптимизации запросов чтения-записи
Загрузка ОС
Логическая структура жесткого диска.
Главная загрузочная запись.
Таблица разделов.
Первичные и расширенные разделы.
Таблица логических дисков.
Системный загрузчик Windows.
Варианты синтаксиса указания загрузочного раздела.
Загрузка UNIX.
Разбиение на разделы по схеме GPT.
Динамические диски LDM.
Жесткие и мягкие разделы.
Понятие файловой системы
Функции файловой системы.
Понятие файла.
Структура файла.
Типы файлов.
Регулярные файлы и каталоги.
Специальные файлы.
Файлы с последовательным и произвольным доступом.
Структуры управления файлами.
Атрибуты файла.
Отображение файлов на память.
Непрерывная организация файлов на диске, связные списки, i-узлы.
Каталоги.
Одноуровневая, двухуровневая и иерархическая структуры каталогов.
Имена файлов.
Совместно используемые файлы.
Символьное связывание.
Учет свободных блоков.
Монтирование.
Непротиворечивость файловой системы.
Журналирование и каскадный откат транзакций.
Кэширование.
Типовые операции файловой системы
Реализации файловых систем
Файловая система FAT. Особенности и функциональные возможности файловой системы FAT. Таблица размещения фай-лов.
Структура загрузочной записи FAT16, FAT32.
Хранение длинных имен.
Файловая система HPFS.
Структура раздела HPFS, сбалансированные двоичные деревья.
Файловая система NTFS.
Структура тома.
Особенности системы NTFS.
Файловая система CD (ISO9660).
Основной описатель тома.
Рок-Ридж расширения.
Расширения Joliet.
Базовая файловая система UNIX System V s5fs.
Индексные узлы. Суперблок.
Файловая система Berkeley FFS.
Файловая система Linux Ext2fs.
Файловая система proc.
Файловая система с журнальной структурой LFS
Теория компиляторов
Современные системы программирования
История возникновения трансляторов.
Классификация трансляторов.
Трансляторы, компиляторы, интерпретаторы.
Этапы трансляции.
Технология и средства разработки программ.
Краткая история систем программирования.
Структура современных систем программирования.
Классификация языков программирования.
Непроцедурные языки программирования.
Принципы организации SQL.
Технологии 4GL.
Принципы организации технологий на основе Java, HTML
Формальные языки и грамматики
Понятие алфавита.
Цепочки символов и формальные языки.
Конкатенация, обращение, подстановка, итерация цепочек.
Замыкание алфавита.
Способы задания языков.
Лексика, синтаксис и семантика языка.
Особенности языков программирования.
Понятие грамматики.
Нетерминальный и терминальный словари грамматики, аксиома грамматики, продукции. Вывод цепочек, сентенциальная форма.
Запись правил грамматик.
Форма Бэкуса-Наура.
Синтаксические диаграммы.
Принцип рекурсии.
Общая схема распознавателя.
Конфигурация распознавателя.
Виды распознавателей.
Задача разбора
Классификация грамматик
Классификация грамматик по Хомскому.
Контекстно-зависимые и контекстно-свободные грамматики.
Неукорачивающие грамматики.
Регулярные грамматики и языки.
Праволинейные и леволинейные грамматики.
Автоматные грамматики.
Классификация языков.
Классификация распознавателей.
Машина Тьюринга.
Лексический анализ и регулярные грамматики
Принципы построения лексических анализаторов.
Регулярные множества и регулярные выражения.
Свойства регулярных языков.
Способы задания регулярных языков.
Свойства регулярных языков.
Теорема Клини.
Лемма о разрастании языка.
Преобразование регулярной грамматики к автоматному виду.
Преобразование регулярной грамматики к регулярному выражению
Конечные автоматы
Конечные автоматы.
Детерминированные и недетерминированные КА.
Диаграмма состояний КА.
Связь КА и синтаксических диаграмм.
Построение КА на основе леволинейной и праволинейной грамматик.
Построение леволинейной и праволинейной грамматик на основе КА.
Преобразование КА к детерминированному виду.
Минимизация КА. Устранение недостижимых и эквивалентных состояний КА. Автоматизация построения лексических анализаторов.
Программа LEX
КС-грамматики. Приведение КС-грамматик
Контекстно-свободные языки.
Лемма о разрастании КС-языка.
Дерево синтаксического разбора.
Однозначность и рекурсивность грамматики.
Нормальные формы Хомского и Грейбах.
Преобразование грамматики в нормальную форму Хомского.
Преобразование грамматики в нормальную форму Грейбах.
Приведение КС-грамматик (устранение недостижимых и бесполезных символов, устранение ?-правил, устранение цепных правил).
Устранение левой рекурсии
Алгоритмы построения синтаксических анализаторов
Автоматы с магазинной памятью.
Синтаксические анализаторы КС-языков.
Синтаксический анализ сверху вниз.
Распознаватели с возвратом.
Алгоритм с подбором альтернатив.
Построение МП-автомата с возвратом по заданной КС-грамматике.
Синтаксический анализ снизу вверх.
Алгоритм перенос-свертка.
Построение расширенного МП-автомата.
Построение автомата по НФ Грейбах.
Распознаватели без возвратов.
Алгоритм по методу рекурсивного спуска.
Построение автомата для разбора S-грамматики
LL(k) грамматики
Обозначение грамматик по Кнуту.
Понятие LL(k) грамматики.
Сильно LL(k) грамматики.
Множества направляющих цепочек, цепочек-предшественников и цепочек-последователей.
Формальное определение LL(1) грамматики.
Признаки LL(1) грамматики.
Алгоритм построения множества символов-предшественников.
Алгоритм построения множества символов-последователей.
Алгоритм построения распознавателя для LL(1) грамматики.
LR(k) грамматики
Понятие основы.
Пополненная КС-грамматика. LR(0) и LR(1) грамматики.
Понятие ситуации.
Построение последовательности ситуаций для LR(0) грамматики.
Построение управляющей таблицы распознавателя LR(0) грамматики. Последовательность ситуаций для LR(1) грамматики.
Управляющая таблица распознавателя LR(1) грамматики.
SLR(1) и LALR(1) грамматики.
Распознаватель SLR(1) грамматики.
Иерархия КС-грамматик.
Программа YACC
Грамматики предшествования.
Грамматики простого предшествования.
Отношения предшествования.
Обратимые грамматики.
Построение матрицы предшествования.
Распознаватель для грамматики простого предшествования.
Операторная грамматика.
Грамматика операторного предшествования.
Построение матрицы предшествования для грамматики операторного предшествования. Распознаватель для грамматик операторного предшествования.
Остовная грамматика и остовный вывод
Генерация кода.
Распределение памяти
Семантический анализ.
Проверка контекстных условий.
Таблицы идентификаторов.
Перевод конструкций на промежуточный язык.
Локальные и глобальные данные.
Статическая, автоматическая, динамическая память.
Управление функциями.
Возврат значений.
Исключительные ситуации.
Алгоритмы генерации машинного кода.
Препроцессорная обработка
Синтаксически управляемый перевод
Схемы компиляции.
Многоадресный код с явно и неявно именуемым результатом.
Синтаксически-управляемые схемы.
СУ-перевод.
МП-преобразователи.
Построение промежуточной программы.
Транслирующие грамматики.
Активные цепочки.
МП-преобразователь для Т-грамматики.
Атрибутные Т-грамматики.
Синтезируемые и наследуемые атрибуты.
Свойства АТ-грамматик.
Формирование АТ-грамматик
Верификация и оптимизация кода
Методы оптимизации кода.
Свертка выражений.
Оптимизация линейного участка.
Свертка объектного кода.
Оптимизация передачи параметров.
Оптимизация циклов.
Машинно-зависимые методы оптимизации.
Методы анализа свойств корректности программ.
Автоматизация верификации
Ассемблеры и компоновщики
Схема макроассемблера.
Макроопределения.
Таблицы макрогенератора.
Обработка макрокоманды.
Обработка команд и вложенных макрокоманд.
Задачи и схемы ассемблера.
Таблицы ассемблера.
Формирование команд.
Способы адресации.
Редактор связей и загрузчик.
Объектный модуль.
Загрузочный модуль.
Коррекция адресов программы
Для студентов специальности I-40 02 01 «Вычислительные машины, системы и сети»
Содержание
Операционные системы
Предмет курса, его цели и задачи.
Методическое обеспечение.
История развития системного ПО.
Классификация системного ПО.
ОС, системы управления файлами, интерфейсы, системы программирования, утилиты. Понятие ресурса в ОС.
Концепция виртуализации ресурса
Операционная система.
Классификация ОС.
ОС реального времени.
Микроядерные и монолитные ОС.
Структура ОС.
Ядро, командный процессор, подсистема ввода-вывода, система управления памятью, файловая система.
Принципы построения ОС.
Понятие виртуальной машины.
Безопасность операционных систем.
Понятие системных вызовов.
Системные вызовы стандарта POSIX.
Интерфейс Win32 API.
Понятие процесса и потока
Концепция процесса.
Диаграмма состояний процесса.
Операции над процессами.
Создание и завершение процесса.
Иерархия процессов.
Структуры управления процессами.
Процессы-зомби.
Системные вызовы для управления процессами.
Процессы в Windows и UNIX.
Процессы и потоки.
Понятия мультизадачности и многопоточности.
Потоки в пространстве пользователя.
Потоки в ядре. Облегченные потоки.
Потоки в Windows и UNIX.
Всплывающие потоки.
Понятие о прерываниях.
Параллельные процессы.
Независимые и взаимодействующие процессы.
Сигналы UNIX.
Сообщения Windows
Диспетчеризация процессов
Стратегии планирования.
Дисциплины диспетчеризации.
Вытесняющие и невытесняющие алгоритмы.
Алгоритмы планирования без переключений.
Циклическое и приоритетное планирование.
Динамические приоритеты.
Планирование в системах реального времени.
Планирование потоков.
Гарантии обслуживания процесса
Механизмы взаимного исключения
Состояние состязания.
Задача об обедающих философах.
Детерминированный набор.
Условия Бернстайна.
Понятие критического ресурса.
Критическая область.
Взаимное исключение.
Механизмы взаимного исключения.
Алгоритм Деккера.
Алгоритм Петерсона
Типовые механизмы синхронизации
Операции Test & Set.
Поддержка механизма TS в современных процессорах.
Семафоры Дейкстры.
Базовые операции над семафорами.
Мьютексы. Задача поставщик-потребитель.
Поддержка механизмов синхронизации в Windows и UNIX.
Мониторы Хоара. Поддержка мониторов в языках программирования.
Задача о парикмахерской.
Задача читатели-писатели
Механизмы межпроцессного взаимодействия
Механизмы для взаимодействия процессов.
Сигналы. Каналы.
Именованные и анонимные каналы.
Сообщения. Очереди со-общений.
Порты.
Буферы сообщений.
Сообщения как средство синхронизации.
Рандеву.
Барьеры.
Поддержка механизмов взаимодействия в ОС UNIX и Windows
Обработка тупиковых ситуаций
Понятие тупика.
Условия Коффмана.
Модель Холта.
Модель пространства состояний.
Надежное, опасное и безопасное состояния.
Обнаружение тупика при наличии одного ресурса каждого вида.
Обнаружение тупика при наличии нескольких ресурсов каждого вида.
Выход из взаимоблокировки.
Обход и предотвращение тупиковой ситуации.
Двухфазовое блокирование.
Проблема голодания
Управление памятью
Управление памятью.
Задачи управления памятью.
Однозадачная система.
Сегментная организация памяти.
Настройка адресов и защита памяти.
Подкачка.
Битовые массивы и связные списки.
Алгоритмы выбора сегмента для размещения процесса.
Страничная организации памяти.
Виртуальная память.
Таблицы страниц.
Многоуровневые таблицы страниц.
Буферы быстрого преобразования TLB.
Инвертированные таблицы страниц.
Обработка страничного прерывания.
Поддержка сегментно-страничной организации памяти в процессорах семейства Pentium. Структура элемента таблицы страниц.
Таблица страничных блоков.
Отдельные пространства команд и данных.
Совместно используемые страницы.
Проблемы, возникающие при вызове страничного прерывания.
Распределение оперативной памяти в Windows NT, UNIX
Алгоритмы замещения страниц
Стратегии выборки по запросу и с упреждением.
Алгоритмы замещения страниц.
Алгоритм NRU, LRU, FIFO, NFU.
Бит использования страницы.
Понятие рабочего набора.
Аномалия Билэди.
Рабочие наборы в Windows
Подсистемы ввода-вывода
Управление вводом-выводом.
Блочные и символьные операции.
Синхронные и асинхронные операции.
Отображение ввода-вывода на адресное пространство памяти.
Прямой доступ к памяти.
Кэширование операций.
Упреждающее чтение.
Отложенная запись.
Программное обеспечение ввода-вывода.
Драйверы UNIX.
Псевдоустройства.
Переключатели устройств.
Файл устройства.
Драйверы Windows.
Процесс загрузки драйверов.
Дерево устройств.
Дисциплины оптимизации запросов чтения-записи
Загрузка ОС
Логическая структура жесткого диска.
Главная загрузочная запись.
Таблица разделов.
Первичные и расширенные разделы.
Таблица логических дисков.
Системный загрузчик Windows.
Варианты синтаксиса указания загрузочного раздела.
Загрузка UNIX.
Разбиение на разделы по схеме GPT.
Динамические диски LDM.
Жесткие и мягкие разделы.
Понятие файловой системы
Функции файловой системы.
Понятие файла.
Структура файла.
Типы файлов.
Регулярные файлы и каталоги.
Специальные файлы.
Файлы с последовательным и произвольным доступом.
Структуры управления файлами.
Атрибуты файла.
Отображение файлов на память.
Непрерывная организация файлов на диске, связные списки, i-узлы.
Каталоги.
Одноуровневая, двухуровневая и иерархическая структуры каталогов.
Имена файлов.
Совместно используемые файлы.
Символьное связывание.
Учет свободных блоков.
Монтирование.
Непротиворечивость файловой системы.
Журналирование и каскадный откат транзакций.
Кэширование.
Типовые операции файловой системы
Реализации файловых систем
Файловая система FAT. Особенности и функциональные возможности файловой системы FAT. Таблица размещения фай-лов.
Структура загрузочной записи FAT16, FAT32.
Хранение длинных имен.
Файловая система HPFS.
Структура раздела HPFS, сбалансированные двоичные деревья.
Файловая система NTFS.
Структура тома.
Особенности системы NTFS.
Файловая система CD (ISO9660).
Основной описатель тома.
Рок-Ридж расширения.
Расширения Joliet.
Базовая файловая система UNIX System V s5fs.
Индексные узлы. Суперблок.
Файловая система Berkeley FFS.
Файловая система Linux Ext2fs.
Файловая система proc.
Файловая система с журнальной структурой LFS
Теория компиляторов
Современные системы программирования
История возникновения трансляторов.
Классификация трансляторов.
Трансляторы, компиляторы, интерпретаторы.
Этапы трансляции.
Технология и средства разработки программ.
Краткая история систем программирования.
Структура современных систем программирования.
Классификация языков программирования.
Непроцедурные языки программирования.
Принципы организации SQL.
Технологии 4GL.
Принципы организации технологий на основе Java, HTML
Формальные языки и грамматики
Понятие алфавита.
Цепочки символов и формальные языки.
Конкатенация, обращение, подстановка, итерация цепочек.
Замыкание алфавита.
Способы задания языков.
Лексика, синтаксис и семантика языка.
Особенности языков программирования.
Понятие грамматики.
Нетерминальный и терминальный словари грамматики, аксиома грамматики, продукции. Вывод цепочек, сентенциальная форма.
Запись правил грамматик.
Форма Бэкуса-Наура.
Синтаксические диаграммы.
Принцип рекурсии.
Общая схема распознавателя.
Конфигурация распознавателя.
Виды распознавателей.
Задача разбора
Классификация грамматик
Классификация грамматик по Хомскому.
Контекстно-зависимые и контекстно-свободные грамматики.
Неукорачивающие грамматики.
Регулярные грамматики и языки.
Праволинейные и леволинейные грамматики.
Автоматные грамматики.
Классификация языков.
Классификация распознавателей.
Машина Тьюринга.
Лексический анализ и регулярные грамматики
Принципы построения лексических анализаторов.
Регулярные множества и регулярные выражения.
Свойства регулярных языков.
Способы задания регулярных языков.
Свойства регулярных языков.
Теорема Клини.
Лемма о разрастании языка.
Преобразование регулярной грамматики к автоматному виду.
Преобразование регулярной грамматики к регулярному выражению
Конечные автоматы
Конечные автоматы.
Детерминированные и недетерминированные КА.
Диаграмма состояний КА.
Связь КА и синтаксических диаграмм.
Построение КА на основе леволинейной и праволинейной грамматик.
Построение леволинейной и праволинейной грамматик на основе КА.
Преобразование КА к детерминированному виду.
Минимизация КА. Устранение недостижимых и эквивалентных состояний КА. Автоматизация построения лексических анализаторов.
Программа LEX
КС-грамматики. Приведение КС-грамматик
Контекстно-свободные языки.
Лемма о разрастании КС-языка.
Дерево синтаксического разбора.
Однозначность и рекурсивность грамматики.
Нормальные формы Хомского и Грейбах.
Преобразование грамматики в нормальную форму Хомского.
Преобразование грамматики в нормальную форму Грейбах.
Приведение КС-грамматик (устранение недостижимых и бесполезных символов, устранение ?-правил, устранение цепных правил).
Устранение левой рекурсии
Алгоритмы построения синтаксических анализаторов
Автоматы с магазинной памятью.
Синтаксические анализаторы КС-языков.
Синтаксический анализ сверху вниз.
Распознаватели с возвратом.
Алгоритм с подбором альтернатив.
Построение МП-автомата с возвратом по заданной КС-грамматике.
Синтаксический анализ снизу вверх.
Алгоритм перенос-свертка.
Построение расширенного МП-автомата.
Построение автомата по НФ Грейбах.
Распознаватели без возвратов.
Алгоритм по методу рекурсивного спуска.
Построение автомата для разбора S-грамматики
LL(k) грамматики
Обозначение грамматик по Кнуту.
Понятие LL(k) грамматики.
Сильно LL(k) грамматики.
Множества направляющих цепочек, цепочек-предшественников и цепочек-последователей.
Формальное определение LL(1) грамматики.
Признаки LL(1) грамматики.
Алгоритм построения множества символов-предшественников.
Алгоритм построения множества символов-последователей.
Алгоритм построения распознавателя для LL(1) грамматики.
LR(k) грамматики
Понятие основы.
Пополненная КС-грамматика. LR(0) и LR(1) грамматики.
Понятие ситуации.
Построение последовательности ситуаций для LR(0) грамматики.
Построение управляющей таблицы распознавателя LR(0) грамматики. Последовательность ситуаций для LR(1) грамматики.
Управляющая таблица распознавателя LR(1) грамматики.
SLR(1) и LALR(1) грамматики.
Распознаватель SLR(1) грамматики.
Иерархия КС-грамматик.
Программа YACC
Грамматики предшествования.
Грамматики простого предшествования.
Отношения предшествования.
Обратимые грамматики.
Построение матрицы предшествования.
Распознаватель для грамматики простого предшествования.
Операторная грамматика.
Грамматика операторного предшествования.
Построение матрицы предшествования для грамматики операторного предшествования. Распознаватель для грамматик операторного предшествования.
Остовная грамматика и остовный вывод
Генерация кода.
Распределение памяти
Семантический анализ.
Проверка контекстных условий.
Таблицы идентификаторов.
Перевод конструкций на промежуточный язык.
Локальные и глобальные данные.
Статическая, автоматическая, динамическая память.
Управление функциями.
Возврат значений.
Исключительные ситуации.
Алгоритмы генерации машинного кода.
Препроцессорная обработка
Синтаксически управляемый перевод
Схемы компиляции.
Многоадресный код с явно и неявно именуемым результатом.
Синтаксически-управляемые схемы.
СУ-перевод.
МП-преобразователи.
Построение промежуточной программы.
Транслирующие грамматики.
Активные цепочки.
МП-преобразователь для Т-грамматики.
Атрибутные Т-грамматики.
Синтезируемые и наследуемые атрибуты.
Свойства АТ-грамматик.
Формирование АТ-грамматик
Верификация и оптимизация кода
Методы оптимизации кода.
Свертка выражений.
Оптимизация линейного участка.
Свертка объектного кода.
Оптимизация передачи параметров.
Оптимизация циклов.
Машинно-зависимые методы оптимизации.
Методы анализа свойств корректности программ.
Автоматизация верификации
Ассемблеры и компоновщики
Схема макроассемблера.
Макроопределения.
Таблицы макрогенератора.
Обработка макрокоманды.
Обработка команд и вложенных макрокоманд.
Задачи и схемы ассемблера.
Таблицы ассемблера.
Формирование команд.
Способы адресации.
Редактор связей и загрузчик.
Объектный модуль.
Загрузочный модуль.
Коррекция адресов программы