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

Рекомендовано Учебно-методическим объединением вузов по университетскому и политехническому образованию.

Предисловие......9Введение......111. ОБЩИЕ СВЕДЕНИЯ О СИСТЕМАХ ПРОГРАММИРОВАНИЯ......171.1. Типовая система программирования......171.1.1. Схема функционирования......171.1.2. Структура вырабатываемой программы......211.1.3. Варианты основных компонентов СП......241.2. Классификация языков программирования......26Контрольные вопросы......282. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ ФОРМАЛЬНЫХ ЯЗЫКОВ......302.1. Исходные сведения из математики......302.1.1. Множества и их свойства......302.1.2. Отношения и отображения......322.1.3. Графы и деревья......342.2. Формальные грамматики и языки......352.2.1. Определение языков посредством множеств......352.2.2. Понятие о формальной грамматике......372.2.3. Определение формальной грамматики......392.3. Генерация, распознавание и преобразование языков......422.3.1. Классификация грамматик......422.3.2. Механизмы распознавания и преобразования......44Контрольные вопросы......473. РЕГУЛЯРНЫЕ ГРАММАТИКИ И ЯЗЫКИ......493.1. Описание регулярных языков......493.1.1. Регулярные выражения......493.1.2. Свойства регулярных выражений......523.2. Конечный автомат......543.2.1. Определение конечного автомата......543.2.2. Способы представления функции переходов......553.2.3. Примеры конечных автоматов......573.3. Преобразование конечных автоматов......603.3.1. Задачи преобразования......603.3.2. Устранение недостижимых состояний......623.3.3. Объединение эквивалентных состояний......633.3.4. Построение детерминированного К А......653.4. Взаимосвязь способов определения регулярных языков......673.4.1. Характеристика преобразований......673.4.2. Построение КА по регулярному выражению......683.4.3. Построение регулярной грамматики по КА......733.4.4. Построение КА по регулярной грамматике......74Контрольные вопросы......764. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ......774.1. Определение КС-языков......774.1.1. Задача и дерево разбора......774.1.2. Проверка существования языка......814.1.3. Устранение недостижимых символов......834.2. Эквивалентные преобразования КС-грамматик......844.2.1. Устранение #949;-правил......844.2.2. Устранение цепных правил......854.2.3. Левая факторизация правил......864.2.4. Устранение прямой левой рекурсии......874.3. Нормальная форма КС-грамматики......894.3.1. Нормальная форма Хомского......894.3.2. Нормальная форма Грейбах......914.3.3. Устранение левой рекурсии......924.4. Автомат с магазинной памятью......954.4.1. Определение МП-автомата......954.4.2. Разновидности МП-автоматов......974.4.3. Взаимосвязь МП-автоматов и КС-грамматик......984.5. Нисходящие распознаватели языков......1014.5.1. Стратегия нисходящего анализа......1014.5.2. LL(k)-грамматики......1034.6. Восходящие распознаватели языков......1074.6.1. Стратегия восходящего анализа......1074.6.2. LR(k)-грамматики......1094.6.3. Иерархия КС-грамматик......1124.7. Простое предшествование......1144.7.1. Грамматика простого предшествования......1144.7.2. Вычисление матрицы предшествования......1154.7.3. Распознаватель предшествования......118Контрольные вопросы......1215. АЛГОРИТМЫ ТРАНСЛЯЦИИ......1235.1. Задача трансляции......1235.1.1. Постановка задачи трансляции......1235.1.2. Транслирующие преобразования......1245.2. Лексический анализ......1275.2.1. Задачи лексического анализа......1275.2.2. Применение конечных автоматов......1305.2.3. Алгоритмы лексического анализа......1335.2.4. Преобразование константы в машинную форму......1355.3. Синтаксический анализ......1375.3.1. Задачи синтаксического анализа......1375.3.2. Алгоритм нисходящего синтаксического анализа......1385.3.3. Алгоритм восходящего синтаксического анализа......1425.4. Семантический анализ......1485.4.1. Задачи семантического анализа......1485.4.2. Формы промежуточной программы......1505.4.3. Алгоритмы перевода на промежуточный язык......1525.4.4. Особенности перевода сложных конструкций......1565.5. Оптимизация программы......1605.5.1. Методы оптимизации......1605.5.2. Свертка выражений......1615.5.3. Чистка линейного участка......1635.5.4. Чистка циклов......1655.6. Распределение памяти......1685.6.1. Управление данными программы......1685.6.2. Задачи распределения памяти......1745.7. Генерация кода......1795.7.1. Управление подпрограммами......1795.7.2. Алгоритмы генерации машинного кода......1855.8. Препроцессорная обработка......1895.8.1. Назначение препроцессора......1895.8.2. Характеристика алгоритмов......191Контрольные вопросы......1956. ФОРМАЛЬНЫЕ МЕТОДЫ ОПИСАНИЯ ПЕРЕВОДА......1976.1. Синтаксически управляемый перевод......1976.1.1. Схемы компиляции......1976.1.2. СУ-схемы......1996.1.3. МП-преобразователи......2006.1.4. Практическое применение СУ-схем......2026.2. Построение промежуточной программы......2046.2.1. Синтаксическое дерево......2046.2.2. Построение триад по синтаксическому дереву......2066.2.3. Формирование ассемблерных команд......2086.3. Транслирующие грамматики......2106.3.1. Понятие Т-грамматики......2106.3.2. Пример Т-грамматики с подпрограммами......2126.3.3. МП-преобразователь для Т-грамматики......2146.4. Атрибутные транслирующие грамматики......2176.4.1. Синтезируемые и наследуемые атрибуты......2176.4.2. Определение и свойства АТ-грамматики......2216.4.3. Формирование АТ-грамматики......224Контрольные вопросы......2287. АССЕМБЛЕРЫ И КОМПОНОВЩИКИ......2297.1. Макрогенератор......2297.1.1. Схемы макроассемблера и макрогенератора......2297.1.2. Таблицы макрогенератора......2327.1.3. Обработка макроопределения......2337.1.4. Обработка макрокоманды......2347.1.5. Обработка команд генерации и вложенных макрокоманд......2357.2. Ассемблер......2377.2.1. Задачи и схема ассемблера......2377.2.2. Таблицы ассемблера......2397.2.3. Первый просмотр исходной программы......2407.2.4. Второй просмотр исходной программы......2427.2.5. Формирование команд на языке машины......2437.3. Редактор связей и загрузчик......2487.3.1. Структура объектного модуля......2487.3.2. Структура загрузочного модуля......2507.3.3. Схема и таблицы редактора связей......2527.3.4. Распределение памяти для сегментов......2537.3.5. Коррекция адресов программы......2557.3.6. Особенности обработки одноименных сегментов......2577.3.7. Загрузка программы......2587.3.8. Особенности современных компоновщиков......261Контрольные вопросы......2648. ВЕРИФИКАЦИЯ ПРОГРАММ......2668.1. Логическая спецификация программ......2668.1.1. Понятие верификации......2668.1.2. Некоторые сведения из математической логики......2688.1.3. Принципы логической спецификации свойств программ......2728.2. Методы анализа свойств корректности программ......2768.2.1. Доказательство частичной корректности......2768.2.2. Методика верификации программы......2798.2.3. Анализ завершения программы......2828.2.4. Анализ незавершения программы......2878.3. Автоматизация верификации программ......2888.3.1. Формализация семантики программ......2888.3.2. Выбор инварианта цикла......2928.3.3. Типовая схема верификатора......293Контрольные вопросы......295Заключение......296Приложения1. Тематика задач для программирования......3012. Библиотеки системы программирования......303Литература......309Список основных сокращений......311Предметный указатель......313