Конспект лекций / составители: А. Н. Карпушин, П. С. Макаров. –
Ульяновск: УлГТУ, 2007. – 59 с.
Приводится конспект лекций, в которых раскрыты основы теории
формальных языков и грамматик, а также основные вопросы построения
трансляторов и компиляторов. Предназначено для студентов различных
форм обучения по направлению "Информатика и вычислительная
техника", специальности "Вычислительные машины, комплексы, системы
и сети". Может быть полезным для студентов других специальностей,
профиль которых
связан с вопросами разработки системного программного обеспечения. Содержание
Основы теории формальных языков
Основные понятия и определения
Способы задания схем грамматик
Классификация грамматик и языков по Хомскому
Построение грамматик. грамматики, описывающие основные конструкции языков программирования
Разбор цепочек. распознаватели.
Разбор цепочек
общая схема распознавателя
Виды распознавателей
Классификация распознавателей по типам языков
Постановка задачи разбора
Трансляторы, интерпретаторы, компиляторы. этапы трансляции. общая схема работы транслятора
Трансляторы
Компиляторы
Интерпретаторы
История развития компиляторов
Этапы трансляции. общая схема работы транслятора
Многопроходные и однопроходные компиляторы
Особенности построения интерпретаторов
Лексический анализ. таблицы идентификаторов. лексические анализаторы
Назначение и особенности построения таблиц идентификаторов
Назначение лексического анализатора (сканера)
Принципы построения лексических анализаторов
Автоматные грамматики и конечные автоматы
Алгоритм разбора цепочек
Алгоритм разбора по диаграмме состояний
Недетерминированный разбор
Алгоритм построения детерминированного ка по НКА
Минимизация конечных автоматов
Синтаксический анализ
Грамматики предшествования
Грамматики простого предшествования
Алгоритм «сдвиг-свертка» для грамматик простого предшествования
Грамматики операторного предшествования
Алгоритм «сдвиг-свертка» для грамматик операторного предшествования
Общий алгоритм работы синтаксического анализатора
Семантический анализ
Генерация кода
Алгоритм генерации объектного кода по дереву вывода
Построение ассемблерного кода по дереву вывода
Построение списка триад по дереву вывода
Оптимизация объектного кода методом свертки
Оптимизация объектного кода методом исключения лишних операций
Общий алгоритм генерации и оптимизации объектного кода
Библиографический список
связан с вопросами разработки системного программного обеспечения. Содержание
Основы теории формальных языков
Основные понятия и определения
Способы задания схем грамматик
Классификация грамматик и языков по Хомскому
Построение грамматик. грамматики, описывающие основные конструкции языков программирования
Разбор цепочек. распознаватели.
Разбор цепочек
общая схема распознавателя
Виды распознавателей
Классификация распознавателей по типам языков
Постановка задачи разбора
Трансляторы, интерпретаторы, компиляторы. этапы трансляции. общая схема работы транслятора
Трансляторы
Компиляторы
Интерпретаторы
История развития компиляторов
Этапы трансляции. общая схема работы транслятора
Многопроходные и однопроходные компиляторы
Особенности построения интерпретаторов
Лексический анализ. таблицы идентификаторов. лексические анализаторы
Назначение и особенности построения таблиц идентификаторов
Назначение лексического анализатора (сканера)
Принципы построения лексических анализаторов
Автоматные грамматики и конечные автоматы
Алгоритм разбора цепочек
Алгоритм разбора по диаграмме состояний
Недетерминированный разбор
Алгоритм построения детерминированного ка по НКА
Минимизация конечных автоматов
Синтаксический анализ
Грамматики предшествования
Грамматики простого предшествования
Алгоритм «сдвиг-свертка» для грамматик простого предшествования
Грамматики операторного предшествования
Алгоритм «сдвиг-свертка» для грамматик операторного предшествования
Общий алгоритм работы синтаксического анализатора
Семантический анализ
Генерация кода
Алгоритм генерации объектного кода по дереву вывода
Построение ассемблерного кода по дереву вывода
Построение списка триад по дереву вывода
Оптимизация объектного кода методом свертки
Оптимизация объектного кода методом исключения лишних операций
Общий алгоритм генерации и оптимизации объектного кода
Библиографический список