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

Методическое пособие

В учебном пособии излагаются основы математической теории формальных языков и трансляций, знание которой необходимо всем, кто работает в области теоретической или прикладной информатики. Излагаются основные факты теории с доказательствами. Теоретический материал дополнен примерами и задачами с решениями. Учебное пособие предназначено для студентов, обучающихся по программам высшего профессионального образования по специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем».

Кафедра автоматизированных систем управления

Библиографическая запись:

Калайда, В. Т. Теория языков программирования методов трансляции: Методическое пособие [Электронный ресурс] / В. Т. Калайда. — Томск: ТУСУР, 2012. — 219 с. — Режим доступа: https://edu.tusur.ru/publications/2063
Автор:   Калайда В. Т.
Год издания: 2012
Количество страниц: 219
Скачиваний: 2

Оглавление (содержание)

Введение

1. Предварительные математические сведения

1.1. Множества

1.2. Операции над множествами

1.3. Множества цепочек

1.4. Языки

1.5. Алгоритмы

1.6. Некоторые понятия теории графов

Контрольные вопросы

2. Введение в компиляцию

2.1. Задание языков программирования

2.2. Синтаксис и семантика

2.3. Процесс компиляции

2.4. Лексический анализ

2.5. Работа с таблицами

2.6. Синтаксический анализ

2.7. Генератор кода

2.8. Оптимизация кода

2.9. Резюме

Контрольные вопросы

3. Теория языков

3.1. Способы определения языков

3.2. Грамматики

3.3. Грамматики с ограничениями на правила

3.4. Распознаватели

3.5. Регулярные множества, их распознавание и порождение

3.6. Регулярные множества и конечные автоматы

3.7. Графическое представление конечных автоматов

3.8. Минимизация конечных автоматов

3.9. Контекстно-свободные языки

3.9.1. Преобразование КС–грамматик

3.9.2. Нормальная форма Хомского

3.9.3. Нормальная формула Грейбах

3.10. Автоматы с магазинной памятью

3.10.1. Основные определения

3.10.2. Эквивалентность МП-автоматов и КС-грамматик

Контрольные вопросы

4. КС-грамматики и синтаксический анализ сверху вниз

4.1. LL(1)-грамматики

4.2. LL(1)-таблица разбора

Контрольные вопросы

5. Синтаксический анализ снизу вверх

5.1. Разбор снизу вверх

5.2. LR(1) - таблица разбора

5.3. Построение LR – таблицы разбора

5.4. Сравнение LL – и LR – методов разбора

Контрольные вопросы

6. Оптимизация кода

6.1. Оптимизация линейного участка

6.1.1. Модель линейного участка

6.1.2. Преобразование блока

6.1.3. Графическое представление блоков

6.1.4. Критерий эквивалентности блоков

6.1.5. Оптимизация блоков

6.1.6. Алгебраические преобразования

6.2. Арифметические выражения

6.2.1. Модель машины

6.2.2. Разметка дерева

6.2.3. Программы с командами STORE

6.2.4. Влияние некоторых алгебраических законов

6.3. Программы с циклами

6.3.1. Модель программы

6.3.2. Анализ потока управления

6.3.3. Примеры преобразования программ

6.3.4. Оптимизация циклов

6.4. Анализ потоков данных

6.4.1. Интервалы

6.4.2. Анализ потоков данных с помощью интервалов

6.4.3. Несводимые графы управления

7. Включение действий в синтаксис

7.1. Получение четверок

7.2. Работа с таблицей символов

Контрольные вопросы

8. Проектирование компиляторов

8.1. Число проходов

8.2. Таблицы символов

8.3. Таблица видов

Контрольные вопросы

9. Распределение памяти

9.1. Стек времени прогона

9.2. Методы вызова параметров

9.3. Обстановка выполнения процедур

9.4. «Куча»

9.5. Счетчик ссылок

9.6. Сборка мусора

Контрольные вопросы

10. Генерация кода

10.1. Генерация промежуточного кода

10.2. Структура данных для генерации кода

10.3. Генерация кода для типичных конструкций

10.3.1. Присвоение

10.3.2. Условные зависимости

10.3.3. Описание идентификаторов

10.3.4. Циклы

10.3.5. Вход и выход из блока

10.3.6. Прикладные реализации

10.4. Проблемы, связанные с типами

10.5. Время компиляции и время прогона

Контрольные вопросы

Список литературы