- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •1. Краткий обзор процесса компиляции
- •2. Лексический анализ
- •0123...9 Пробел
- •3. Организация таблиц компилятора
- •3.1. Общий вид таблиц
- •3.2. Прямой доступ к таблице или метод индексов
- •3.3. Неупорядоченная таблица или метод линейного списка
- •3.4. Упорядоченная таблица. Бинарный, двоичный или логарифмический поиск
- •3.5. Сбалансированные деревья
- •3.6. Деревья оптимального поиска
- •3.7.1. Рехеширование
- •3.7.3. Метод цепочек или гроздей
- •4. Общие методы синтаксического анализа
- •4.1. Нисходящий разбор с возвратами
- •4.2. Восходящий разбор с возвратами
- •4.3. Символьный препроцессор на основе бэктрекинга
- •4.3.1. Фаза анализа и перевода грамматики во внутреннее представление
- •4.3.2. Лексичекий анализ в сп
- •4.3.3. Синтаксический анализ в сп
- •4.3.4. Выполнение семантических действий
- •5. Однопроходный синтаксический анализ без возвратов
- •5.1. Ll(k) языки и грамматики
- •5.1.1. Предсказывающие алгоритмы разбора и разбор для ll(1)-грамматик
- •5.1.2. Рекурсивный спуск
- •5.2. Языки и грамматики простого предшествования
- •Xy, если u xy
- •X y, если u xU1) (y l(u1))
- •X y, если (u u1y) (X r(u1)) or
- •5.2.1. Алгоритм Вирта–Вебера для анализа языков простого предшествования
- •5.2.2. Функции предшествования.
- •5.2.3. Проблемы построения грамматик предшествования
- •5.3. Операторная грамматика предшествования
- •6. Введение в семантику
- •6.1. Внутренние формы исходной программы
- •6.1.1. Польская инверсная запись
- •If выр then инстр 1 else инстр 2
- •6.1.2. Интерпретация полиЗа
- •6.1.3. Генерирование команд по полиЗу
- •6.1.4. Тетрады и триады
- •6.2. Семантические подпрограммы перевода инфиксной записи в полиз и аспекты их реализации
- •6.3. Семантические подпрограммы для перевода в тетрады
- •6.4. Метод замельсона–бауэра для перевода в полиз и тетрады
- •6.5. Нейтрализация ошибок
- •6.5.1. Исправления орфографических ошибок
- •6.5.2. Нейтрализация семантических ошибок
- •6.5.3. Нейтрализация синтаксических ошибок
- •7. Машинно-независимая оптимизация программ
- •7.1. Исключение общих подвыражений
- •7.2. Вычисления во время компиляции
- •7.3. Оптимизация булевых выражений
- •7.4. Вынесение инвариантных вычислений за цикл
- •8. Машинно-зависимые фазы компиляции
- •8.1. Распределение памяти
- •8.2. Генерация кода и сборка
- •8.3. Трансляция с языка ассемблера
- •Заключение
- •Список литературы
- •Содержание
- •1. Краткий обзор процесса компиляции 5
- •2. Лексический анализ 10
- •3. Организация таблиц компилятора 16
- •4. Общие методы синтаксического анализа 28
- •5. Однопроходный синтаксический анализ без возвратов 52
- •6. Введение в семантику 78
- •7. Машинно-независимая оптимизация программ 102
- •8. Машинно-зависимые фазы компиляции 109
Содержание
ПРЕДИСЛОВИЕ 3
ВВЕДЕНИЕ 4
1. Краткий обзор процесса компиляции 5
2. Лексический анализ 10
3. Организация таблиц компилятора 16
3.1. ОБЩИЙ ВИД ТАБЛИЦ 16
3.2. ПРЯМОЙ ДОСТУП К ТАБЛИЦЕ ИЛИ МЕТОД ИНДЕКСОВ 17
3.3. НЕУПОРЯДОЧЕННАЯ ТАБЛИЦА ИЛИ МЕТОД ЛИНЕЙНОГО СПИСКА 17
3.4. УПОРЯДОЧЕННАЯ ТАБЛИЦА. БИНАРНЫЙ, ДВОИЧНЫЙ ИЛИ ЛОГАРИФМИЧЕСКИЙ ПОИСК 18
3.5. СБАЛАНСИРОВАННЫЕ ДЕРЕВЬЯ 19
3.6. ДЕРЕВЬЯ ОПТИМАЛЬНОГО ПОИСКА 22
3.7. ХЕШ – АДРЕСАЦИЯ 23
3.7.1. Рехеширование 23
3.7.2. Хеш–функция 25
3.7.3. Метод цепочек или гроздей 26
4. Общие методы синтаксического анализа 28
4.1. НИСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ 31
4.2. ВОСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ 34
4.3. СИМВОЛЬНЫЙ ПРЕПРОЦЕССОР НА ОСНОВЕ БЭКТРЕКИНГА 37
4.3.1. Фаза анализа и перевода грамматики во внутреннее представление 39
4.3.2. Лексичекий анализ в СП 43
4.3.3. Синтаксический анализ в СП 44
4.3.4. Выполнение семантических действий 49
5. Однопроходный синтаксический анализ без возвратов 52
5.1. LL(k) ЯЗЫКИ И ГРАММАТИКИ 52
5.1.1. Предсказывающие алгоритмы разбора и разбор для LL(1)-грамматик 55
5.1.2. Рекурсивный спуск 57
5.2. ЯЗЫКИ И ГРАММАТИКИ ПРОСТОГО ПРЕДШЕСТВОВАНИЯ 60
5.2.1. Алгоритм Вирта–Вебера для анализа языков простого предшествования 63
5.2.2. Функции предшествования. 67
5.2.3. Проблемы построения грамматик предшествования 71
5.3. ОПЕРАТОРНАЯ ГРАММАТИКА ПРЕДШЕСТВОВАНИЯ 73
6. Введение в семантику 78
6.1. ВНУТРЕННИЕ ФОРМЫ ИСХОДНОЙ ПРОГРАММЫ 78
6.1.1. Польская инверсная запись 79
6.1.2. Интерпретация ПОЛИЗа 80
6.1.3. Генерирование команд по ПОЛИЗу 81
6.1.4. Тетрады и триады 84
6.2. СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ПЕРЕВОДА ИНФИКСНОЙ ЗАПИСИ В ПОЛИЗ И АСПЕКТЫ ИХ РЕАЛИЗАЦИИ 86
6.3. СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ДЛЯ ПЕРЕВОДА В ТЕТРАДЫ 88
6.4. МЕТОД ЗАМЕЛЬСОНА–БАУЭРА ДЛЯ ПЕРЕВОДА В ПОЛИЗ И ТЕТРАДЫ 90
6.5. НЕЙТРАЛИЗАЦИЯ ОШИБОК 95
6.5.1. Исправления орфографических ошибок 96
6.5.2. Нейтрализация семантических ошибок 97
6.5.3. Нейтрализация синтаксических ошибок 98
7. Машинно-независимая оптимизация программ 102
7.1. ИСКЛЮЧЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ 103
7.2. ВЫЧИСЛЕНИЯ ВО ВРЕМЯ КОМПИЛЯЦИИ 104
7.3. ОПТИМИЗАЦИЯ БУЛЕВЫХ ВЫРАЖЕНИЙ 105
7.4. ВЫНЕСЕНИЕ ИНВАРИАНТНЫХ ВЫЧИСЛЕНИЙ ЗА ЦИКЛ 107
8. Машинно-зависимые фазы компиляции 109
8.1. РАСПРЕДЕЛЕНИЕ ПАМЯТИ 109
8.2. ГЕНЕРАЦИЯ КОДА И СБОРКА 110
8.3. ТРАНСЛЯЦИЯ С ЯЗЫКА АССЕМБЛЕРА 112
ЗАКЛЮЧЕНИЕ 114
СПИСОК ЛИТЕРАТУРЫ 115
СОДЕРЖАНИЕ 115