Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

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

В. Т. Калайда, В. В. Романенко

ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

И МЕТОДЫ ТРАНСЛЯЦИИ

Учебное пособие

Томск – 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

мизация кода». Многие элементы этой схемы в процессе развития теории программирования из интуитивных, эмпирических алгоритмов превращались в строго математически обоснованные методы, базирующиеся на теории языков, теории перевода, методах синтаксического анализа и др.

В рассматриваемом пособии используются следующие принципы:

–основное внимание уделяется теоретическим идеям, а не техниче-

ским подробностям реализации;

–широко используется принцип декомпозиции исходной задачи на составляющие, что позволяет каждую часть задачи подвергнуть оп-

тимизации;

–изложение материала базируется на уверенности в хорошей матема-

тической подготовке слушателей.