Красновидов А.В. Теория языков программирования и методы трансляции

Учеб. пособие. — М.: Учебно-методический центр по образованию на железнодорожном транспорте, 2016. — 176 с.Рассмотрены различные синтаксически ориентированные алгоритмы анализа предложений и основные этапы трансляции, а также структура трансляторов с различных языков. Проанализированы структуры таблиц трансляторов и алгоритмы работы с этими таблицами. Освещены вопросы оптимизации исходных программ.
Кроме того, рассмотрено обобщение грамматик Хомского — так называемых plex-грамматик. Показано, как с помощью plex-грамматик можно
анализировать изображение.
Предназначено для студентов, обучающихся по направлению подготовки 09.03.02 «Информационные системы и технологии» (профиль «Программное обеспечение средств вычислительной техники и автоматизированных систем»).Введение. Обзор языков программирования
Машинный язык и язык ассемблера
Ассемблер
Макроязык и макропроцессор
Макрокоманды
Функции макропроцессора
Языки программирования высокого уровня
Конечные автоматы
Таблицы переходов
Эквивалентность состояний конечных автоматов
Проверка эквивалентности двух состояний
Недостижимые состояния
Приведенные автоматы
Недетерминированные автоматы
Эквивалентность детерминированных и недетерминированных автоматов
Автоматы с магазинной памятью
Структура языка. Формальные системы
Бэкус-наурова форма (БНФ). Определение языка
Грамматики Хомского. Иерархия языков
Связь между формальными грамматиками и автоматами
Нисходящий синтаксический анализ предложений
Ограничения на порождающие правила
Эквивалентность и однозначность грамматик
Синтаксические диаграммы
Грамматики рекурсивного спуска
Таблично-управляемый алгоритм грамматического разбора
Восходящие алгоритмы грамматического анализа
Грамматики простого предшествования
LR(k)-грамматики
Атрибутные грамматики
Применение атрибутных грамматик
Атрибутные транслирующие грамматики
Лексический анализ и таблицы транслятора
Структура таблиц транслятора
Генерация кода
Синтаксические деревья разбора
Многоадресный код с явно именуемым результатом (тетрады)
Многоадресный код с неявно именуемым результатом (триады)
Ассемблерный код и машинные команды
Обратная польская запись операций
Организация таблиц трансляторов и поиск в таблицах
Таблицы расстановки
Таблицы расстановки со списками
Функции расстановки
Таблицы с использованием двоичных деревьев
Реализация блочной структуры
Сравнение методов реализации таблиц
Распределение памяти
Оптимизация
Аппаратно-зависимая оптимизация
Аппаратно-независимая оптимизация
Вычисления во время компиляции
PLEX-грамматики
Особенности использования plex-грамматик для описания изображений
Рекомендуемая литература