- •Введение
- •1 Предварительные математические сведения
- •1.1 Множества
- •1.2 Операции и отношения
- •1.2.1 Операции над множествами
- •1.2.2 Отношения на множествах
- •1.3.1 Цепочки
- •1.3.2 Операции над цепочками
- •1.4.2 Операции над языком
- •1.5 Алгоритмы
- •1.5.1 Частичные алгоритмы
- •1.5.2 Всюду определенные алгоритмы
- •1.5.3 Рекурсивные алгоритмы
- •1.5.4 Задание алгоритмов
- •1.5.5 Проблемы
- •1.6 Некоторые понятия теории графов
- •1.6.1 Ориентированные графы
- •1.6.2 Ориентированные ациклические графы
- •1.6.3 Деревья
- •1.6.4 Упорядоченные графы
- •2 Введение в компиляцию
- •2.1 Задание языков программирования
- •2.2 Синтаксис и семантика
- •2.3 Процесс компиляции
- •2.4 Лексический анализ
- •2.5 Работа с таблицами
- •2.6 Синтаксический анализ
- •2.7 Генератор кода
- •2.8 Оптимизация кода
- •2.9 Исправление ошибок
- •2.10 Резюме
- •3 Теория языков
- •3.1 Способы определения языков
- •3.2 Грамматики
- •3.3 Грамматики с ограничениями на правила
- •3.4 Распознаватели
- •3.5.1 Определения
- •3.8 Конечные автоматы и регулярные множества
- •3.9.1 Постановка задачи
- •3.10 Контекстно-свободные языки
- •3.10.2 Преобразование КС-грамматик
- •3.10.2.1. Алгоритм проверки пустоты языка
- •3.10.2.2. Алгоритм устранения недостижимых символов
- •3.10.2.3. Алгоритм устранения бесполезных символов
- •3.10.2.5. Алгоритм устранения цепных правил
- •3.10.3 Грамматика без циклов
- •3.10.4 Нормальная форма Хомского
- •3.10.5 Нормальная форма Грейбах
- •3.11 Автоматы с магазинной памятью
- •3.11.1 Основные определения
- •4.1 LL(k)-грамматики
- •4.2.2 Алгоритм поиска направляющих символов
- •4.2.2.1 Множество предшествующих символов
- •4.2.2.2 Множество последующих символов
- •4.2.2.3 Множество направляющих символов
- •4.3 LL(1)-таблица разбора
- •4.3.1 Построение таблицы
- •5 Синтаксический анализ снизу вверх
- •5.1 LR(k)-грамматики
- •5.2 LR(1)-грамматики
- •5.3 LR(1)-таблица разбора
- •5.3.1 Состояния анализатора
- •5.3.2 Построение таблицы
- •5.3.3 LR-конфликты
- •5.3.4 Разбор цепочки по таблице
- •5.4 Сравнение LL- и LR-методов разбора
- •6 Включение действий в синтаксис
- •6.2 Работа с таблицей символов
- •7 Проектирование компиляторов
- •7.1 Число проходов
- •7.2 Таблицы символов
- •7.2.2 Бинарное дерево
- •7.4.1 Стек времени прогона
- •7.4.2 Методы вызова параметров
- •7.4.3 Обстановка выполнения процедур
- •8 Генерация кода
- •8.1 Генерация промежуточного кода
- •8.2 Структура данных для генерации кода
- •8.3.1 Присвоение
- •8.3.2 Условные зависимости
- •8.3.3 Описание идентификаторов
- •8.3.4 Циклы
- •8.3.5 Вход и выход из блока
- •8.3.6 Прикладные реализации
- •8.4 Проблемы, связанные с типами
- •8.5 Время компиляции и время прогона
- •9 Исправление и диагностика ошибок
- •9.1 Типы ошибок
- •9.2 Лексические ошибки
- •9.3 Ошибки в употреблении скобок
- •9.4 Синтаксические ошибки
- •9.4.1 Методы исправления синтаксических ошибок
- •9.4.2 Предупреждения
- •9.4.3 Сообщения о синтаксических ошибках
- •9.5 Контекстно-зависимые ошибки
- •9.6 Ошибки, связанные с употреблением типов
- •9.7 Ошибки, допускаемые во время прогона
- •9.8 Ошибки, связанные с нарушением ограничений
- •Заключение
- •Список литературы
- •Глоссарий
Министерство науки и высшего образования Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего образования ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
В. Т. Калайда, В. В. Романенко
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
И МЕТОДЫ ТРАНСЛЯЦИИ
Учебное пособие
Томск – 2019
Рецензенты:
Самохвалов И. В., докт. физ.-мат. наук, профессор, зав. кафедрой оптико-
электронных систем и дистанционного зондирования Национального исследовательского Томского государственного университета;
Горитов А. Н., докт. техн. наук, профессор кафедры автоматизированных систем управления ТУСУР.
Калайда В.Т.
Теория языков программирования и методы трансляции: учебное посо-
бие / В. Т. Калайда, В. В. Романенко. – Томск: ТУСУР, 2019. – 264 с.
Настоящее пособие посвящено проблеме теоретического описания ко-
нечных автоматов, формальных языков и методов трансляции программ. В
пособии рассматриваются такие вопросы, как синтаксический и семантиче-
ский анализ цепочек символов, генерация объектного кода программ (вклю-
чая оптимизацию кода и исправление ошибок), а также проектирование ком-
пиляторов.
© Калайда В. Т., Романенко В. В., 2019
|
ОГЛАВЛЕНИЕ |
|
ВВЕДЕНИЕ................................................................................................................. |
6 |
|
1 ПРЕДВАРИТЕЛЬНЫЕ МАТЕМАТИЧЕСКИЕ СВЕДЕНИЯ ......................................... |
8 |
|
1.1 |
Множества..................................................................................................... |
8 |
1.2 |
Операции и отношения............................................................................... |
9 |
1.3 |
Множества цепочек ................................................................................... |
18 |
1.4 |
Языки ........................................................................................................... |
20 |
1.5 |
Алгоритмы .................................................................................................. |
22 |
1.6 |
Некоторые понятия теории графов ....................................................... |
26 |
2 ВВЕДЕНИЕ В КОМПИЛЯЦИЮ............................................................................... |
34 |
|
2.1 |
Задание языков программирования ...................................................... |
34 |
2.2 |
Синтаксис и семантика ............................................................................ |
36 |
2.3 |
Процесс компиляции ................................................................................ |
39 |
2.4 |
Лексический анализ .................................................................................. |
40 |
2.5 |
Работа с таблицами ................................................................................... |
43 |
2.6 |
Синтаксический анализ ........................................................................... |
44 |
2.7 |
Генератор кода ........................................................................................... |
46 |
2.8 |
Оптимизация кода ..................................................................................... |
52 |
2.9 |
Исправление ошибок ................................................................................ |
54 |
2.10 Резюме ........................................................................................................ |
55 |
|
3 ТЕОРИЯ ЯЗЫКОВ.................................................................................................. |
57 |
|
3.1 |
Способы определения языков ................................................................. |
57 |
3.2 |
Грамматики ................................................................................................ |
58 |
3.3 |
Грамматики с ограничениями на правила .......................................... |
63 |
3.4 |
Распознаватели........................................................................................... |
64 |
3.5 |
Регулярные множества, их распознавание и порождение................. |
68 |
3.6 |
Недетерминированные конечные автоматы ....................................... |
74 |
3.7 |
Графическое представление конечных автоматов............................. |
78 |
|
3.8 |
Конечные автоматы и регулярные множества ................................... |
82 |
|
3.9 |
Минимизация конечных автоматов ...................................................... |
83 |
|
3.10 Контекстно-свободные языки ............................................................... |
87 |
|
|
3.11 Автоматы с магазинной памятью ...................................................... |
106 |
|
4 |
КС-ГРАММАТИКИ И СИНТАКСИЧЕСКИЙ АНАЛИЗ СВЕРХУ ВНИЗ ................... |
112 |
|
|
4.1 |
LL(k)-грамматики ................................................................................... |
114 |
|
4.2 |
LL(1)-грамматики.................................................................................... |
116 |
|
4.3 |
LL(1)-таблица разбора ............................................................................ |
135 |
5 |
СИНТАКСИЧЕСКИЙ АНАЛИЗ СНИЗУ ВВЕРХ ..................................................... |
148 |
|
|
5.1 |
LR(k)-грамматики ................................................................................... |
148 |
|
5.2 |
LR(1)-грамматики ................................................................................... |
156 |
|
5.3 |
LR(1)-таблица разбора ............................................................................ |
157 |
|
5.4 |
Сравнение LL- и LR-методов разбора ................................................. |
174 |
6 |
ВКЛЮЧЕНИЕ ДЕЙСТВИЙ В СИНТАКСИС .......................................................... |
176 |
|
|
6.1 |
Получение четверок ................................................................................ |
176 |
|
6.2 |
Работа с таблицей символов.................................................................. |
180 |
7 |
ПРОЕКТИРОВАНИЕ КОМПИЛЯТОРОВ............................................................... |
185 |
|
|
7.1 |
Число проходов ........................................................................................ |
185 |
|
7.2 |
Таблицы символов .................................................................................. |
186 |
|
7.3 |
Таблица видов .......................................................................................... |
192 |
|
7.4 |
Распределение памяти ............................................................................ |
194 |
8 |
ГЕНЕРАЦИЯ КОДА.............................................................................................. |
220 |
|
|
8.1 |
Генерация промежуточного кода ......................................................... |
220 |
|
8.2 |
Структура данных для генерации кода .............................................. |
225 |
|
8.3 |
Генерация кода для типичных конструкций..................................... |
229 |
|
8.4 |
Проблемы, связанные с типами ........................................................... |
236 |
|
8.5 |
Время компиляции и время прогона................................................... |
239 |
9 |
ИСПРАВЛЕНИЕ И ДИАГНОСТИКА ОШИБОК ..................................................... |
242 |
|
|
9.1 |
Типы ошибок ............................................................................................ |
242 |
9.2 |
Лексические ошибки............................................................................... |
243 |
9.3 |
Ошибки в употреблении скобок ........................................................... |
245 |
9.4 |
Синтаксические ошибки ........................................................................ |
247 |
9.5 |
Контекстно-зависимые ошибки............................................................ |
252 |
9.6 |
Ошибки, связанные с употреблением типов...................................... |
254 |
9.7 |
Ошибки, допускаемые во время прогона ........................................... |
255 |
9.8 |
Ошибки, связанные с нарушением ограничений ............................. |
257 |
ЗАКЛЮЧЕНИЕ ....................................................................................................... |
259 |
|
СПИСОК ЛИТЕРАТУРЫ......................................................................................... |
260 |
|
ГЛОССАРИЙ .......................................................................................................... |
261 |
6
ВВЕДЕНИЕ
Существует достаточно большое количество вариантов организации трансляции программы, написанной на одном из языков программирования
(рис. 1).
Блок |
|
Исходная программа |
|
||
|
|
|
|
||
сканирования |
|
|
|
|
|
|
|
|
Постфиксная запись |
Постфиксная запись |
|
Лексемы |
Синтакси- |
||||
Лексемы |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ческий |
|
|
|
|
|
анализ |
|
|
|
|
(проход 2) |
|
|
|
|
|
|
|
|
|
Генератор
кода (проход 3)
Объектный код
Исходная
программа Блок сканиро-
вания
Лексемы
а)
Синтаксический анализ (проход 2)
Постфиксная запись
Генератор
кода (проход 3)
Объектный код
б)
Грамматический разбор (правильность следования операторов)
Синтаксический
анализ (проход 1)
Постфиксная запись
Постфиксная запись
Генератор
кода (проход 2)
Объектный код
|
Лексемы |
Разбивает входной поток символов на |
||
Исходная |
|
|
||
|
|
лексические единицы (лексемы) – опера- |
||
программа |
Блок |
|||
торы (IF, DO, BEGIN и др.), имена перемен- |
||||
|
||||
|
сканирования |
|||
|
ных и т.д. (лексический анализатор) |
|||
|
|
|
в)
Рисунок 1 – Схемы вариантов организации вычислительного процесса
Однако всем этим схемам присуща общая технологическая цепочка –
«лексический анализ → синтаксический анализ → генерация кода → опти-
7
мизация кода». Многие элементы этой схемы в процессе развития теории программирования из интуитивных, эмпирических алгоритмов превращались в строго математически обоснованные методы, базирующиеся на теории языков, теории перевода, методах синтаксического анализа и др.
В рассматриваемом пособии используются следующие принципы:
–основное внимание уделяется теоретическим идеям, а не техниче-
ским подробностям реализации;
–широко используется принцип декомпозиции исходной задачи на составляющие, что позволяет каждую часть задачи подвергнуть оп-
тимизации;
–изложение материала базируется на уверенности в хорошей матема-
тической подготовке слушателей.