- •Содержание
- •Введение
- •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.8. Оптимизация кода
- •2.9. Исправление ошибок
- •2.10. Резюме
- •Контрольные вопросы
- •3. Теория языков
- •3.1. Способы определения языков
- •3.2. Грамматики
- •3.4. Распознаватели
- •3.5. Регулярные множества, их распознавание и порождение
- •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. Время компиляции и время прогона
- •Контрольные вопросы
- •11. Исправление и диагностика ошибок
- •11.1. Типы ошибок
- •11.2. Лексические ошибки
- •11.3. Ошибки в употреблении скобок
- •11.4. Синтаксические ошибки
- •11.5. Методы исправления синтаксических ошибок
- •11.6. Предупреждения
- •11.7. Сообщения о синтаксических ошибках
- •11.8. Контекстно-зависимые ошибки
- •11.9. Ошибки, связанные с употреблением типов
- •11.10. Ошибки, допускаемые во время прогона
- •Контрольные вопросы
- •Список литературы
МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
Кафедра автоматизированных систем управления (АСУ)
УТВЕРЖДАЮ Зав. кафедрой АСУ
Профессор д-р техн. наук
_______________А.М. Кориков «____»_________2007 г.
ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ МЕТОДОВ ТРАНСЛЯЦИИ
Методическое Пособие для студентов специальности 230105 «Программное обеспечение вычислительной техники
и автоматизированных систем»
Разработчик
_____________В.Т.Калайда
2007
2
Методическое Пособие рассмотрено и рекомендовано к изданию -ме тодическим семинаром кафедры автоматизированных систем управле-
ния ТУСУР « » |
2004 г. |
Зав. кафедрой АСУ |
|
проф. д-р техн. наук |
__________А.М. Кориков |
|
3 |
|
|
Содержание |
|
Введение............................................................................................... |
6 |
|
1. Предварительные математические сведения ....................... |
7 |
|
1.1. |
Множества.......................................................................... |
7 |
1.2. |
Операции над множествами.......................................... |
8 |
1.3. |
Множества цепочек........................................................ |
14 |
1.4. |
Языки................................................................................. |
15 |
1.5. |
Алгоритмы ....................................................................... |
16 |
1.6. |
Некоторые понятия теории графов .......................... |
20 |
Контрольные вопросы................................................................ |
24 |
|
2. |
Введение в компиляцию .................................................. |
24 |
2.1. |
Задание языков программирования ........................ |
24 |
2.2. |
Синтаксис и семантика................................................. |
26 |
2.3. |
Процесс компиляции..................................................... |
28 |
2.4. |
Лексический анализ....................................................... |
28 |
2.5. |
Работа с таблицами....................................................... |
30 |
2.6. |
Синтаксический анализ ................................................ |
31 |
2.7. |
Генератор кода................................................................ |
32 |
2.8. |
Оптимизация кода.......................................................... |
37 |
2.9. |
Исправление ошибок .................................................... |
39 |
2.10. |
Резюме .............................................................................. |
40 |
Контрольные вопросы................................................................ |
40 |
|
3. |
Теория языков..................................................................... |
41 |
3.1. |
Способы определения языков................................... |
41 |
3.2. |
Грамматики ...................................................................... |
41 |
3.3. |
Грамматики с ограничениями на правила .............. |
45 |
3.4. |
Распознаватели .............................................................. |
45 |
3.5.Регулярные множества, их распознавание и
порождение .................................................................................... |
48 |
|
3.6. |
Регулярные множества и конечные автоматы...... |
52 |
3.7.Графическое представление конечных автоматов
55
3.8. |
Конечные автоматы и регулярные множества...... |
58 |
|
3.9. |
Минимизация конечных автоматов .......................... |
58 |
|
3.10. |
Контекстно-свободные языки .................................... |
62 |
|
3.10.1. |
Деревья выводов..................................................... |
62 |
|
3.10.2. |
Преобразование КС–грамматик............................ |
66 |
|
3.10.3. |
Грамматика без циклов .......................................... |
71 |
|
3.10.4. |
Нормальная форма Хомского ............................... |
71 |
|
3.10.5. |
Нормальная формула Грейбах ............................. |
72 |
|
3.11. |
Автоматы с магазинной памятью.............................. |
75 |
|
4
3.11.1. |
Основные определения.......................................... |
75 |
3.11.2.Эквивалентность МП-автоматов и КС-грамматик
77
Контрольные вопросы................................................................ |
78 |
4.КС-грамматики и синтаксический анализ сверху вниз
79
|
4.1. |
LL(1)-грамматики ............................................................ |
80 |
|
4.2. |
LL(1)-таблица разбора .................................................. |
86 |
|
Контрольные вопросы................................................................ |
90 |
|
5. |
Синтаксический анализ снизу вверх............................. |
91 |
|
|
5.1. |
Разбор снизу вверх ....................................................... |
91 |
|
5.2. |
LR(1) - таблица разбора................................................ |
93 |
|
5.3. |
Построение LR – таблицы разбора ........................... |
96 |
|
5.4. |
Сравнение LL – и LR – методов разбора ................. |
99 |
|
Контрольные вопросы.............................................................. |
100 |
|
6. |
Оптимизация кода ............................................................ |
100 |
|
|
6.1. |
Оптимизация линейного участка ............................. |
101 |
|
6.1.1. |
Модель линейного участка....................................... |
101 |
|
6.1.2. |
Преобразование блока ............................................. |
103 |
|
6.1.3. |
Графическое представление блоков...................... |
107 |
|
6.1.4. |
Критерий эквивалентности блоков ......................... |
110 |
|
6.1.5. |
Оптимизация блоков ................................................. |
111 |
|
6.1.6. |
Алгебраические преобразования............................ |
115 |
|
6.2. |
Арифметические выражения.................................... |
120 |
|
6.2.1. |
Модель машины......................................................... |
120 |
|
6.2.2. |
Разметка дерева ........................................................ |
122 |
|
6.2.3. |
Программы с командами STORE ............................ |
126 |
|
6.2.4. Влияние некоторых алгебраических законов........ |
126 |
|
|
6.3. |
Программы с циклами ................................................ |
138 |
|
6.3.1. |
Модель программы.................................................... |
138 |
|
6.3.2. |
Анализ потока управления....................................... |
142 |
|
6.3.3. |
Примеры преобразования программ...................... |
146 |
|
6.3.4. |
Оптимизация циклов ................................................. |
149 |
|
6.4. |
Анализ потоков данных ............................................. |
160 |
|
6.4.1. |
Интервалы................................................................... |
161 |
6.4.2.Анализ потоков данных с помощью интервалов.. 167
6.4.3. Несводимые графы управления ............................. |
175 |
|
7. |
Включение действий в синтаксис................................ |
179 |
7.1. |
Получение четверок .................................................... |
179 |
7.2. |
Работа с таблицей символов.................................... |
182 |
Контрольные вопросы.............................................................. |
184 |
|
|
|
5 |
|
8. |
Проектирование компиляторов.................................... |
184 |
|
8.1. |
Число проходов............................................................ |
184 |
|
8.2. |
Таблицы символов...................................................... |
185 |
|
8.3. |
Таблица видов .............................................................. |
189 |
|
Контрольные вопросы.............................................................. |
191 |
||
9. |
Распределение памяти.................................................... |
191 |
|
9.1. |
Стек времени прогона................................................. |
191 |
|
9.2. |
Методы вызова параметров..................................... |
198 |
|
9.3. |
Обстановка выполнения процедур......................... |
199 |
|
9.4. |
«Куча» .............................................................................. |
200 |
|
9.5. |
Счетчик ссылок ............................................................ |
201 |
|
9.6. |
Сборка мусора .............................................................. |
203 |
|
Контрольные вопросы.............................................................. |
208 |
||
10. |
Генерация кода.................................................................. |
208 |
|
10.1. |
Генерация промежуточного кода............................. |
208 |
|
10.2. |
Структура данных для генерации кода.................. |
211 |
|
10.3. |
Генерация кода для типичных конструкций......... |
215 |
|
10.3.1. |
Присвоение ............................................................ |
215 |
|
10.3.2. |
Условные зависимости......................................... |
216 |
|
10.3.3. |
Описание идентификаторов................................ |
217 |
|
10.3.4. |
Циклы ...................................................................... |
217 |
|
10.3.5. |
Вход и выход из блока.......................................... |
219 |
|
10.3.6. |
Прикладные реализации...................................... |
220 |
|
10.4. |
Проблемы, связанные с типами.............................. |
220 |
|
10.5. |
Время компиляции и время прогона ...................... |
222 |
|
Контрольные вопросы.............................................................. |
223 |
||
11. |
Исправление и диагностика ошибок ........................... |
224 |
|
11.1. |
Типы ошибок ................................................................. |
224 |
|
11.2. |
Лексические ошибки.................................................... |
225 |
|
11.3. |
Ошибки в употреблении скобок............................... |
226 |
|
11.4. |
Синтаксические ошибки ............................................. |
227 |
|
11.5. |
Методы исправления синтаксических ошибок.... |
228 |
|
11.6. |
Предупреждения........................................................... |
229 |
|
11.7. |
Сообщения о синтаксических ошибках.................. |
230 |
|
11.8. |
Контекстно-зависимые ошибки................................ |
231 |
|
11.9. |
Ошибки, связанные с употреблением типов........ |
232 |
|
11.10. |
Ошибки, допускаемые во время прогона......... |
233 |
|
11.11.Ошибки, связанные с нарушением ограничений..
...................................................................................... |
234 |
Контрольные вопросы.............................................................. |
234 |
Список литературы........................................................................ |
234 |