- Артикул:00-01119814
- Автор: Ф. Льюис, Д. Розенкранц,, Р. Стирнз
- Тираж: 14000 экз.
- Обложка: Твердая обложка
- Издательство: МИР (все книги издательства)
- Город: Москва
- Страниц: 654
- Формат: 60х90 1/16
- Год: 1979
- Вес: 948 г
Развернуть ▼
В книге известных американских специалистов излагаются математические понятия и методы теории автоматов и формальных грамматик, лежащие в основе проектирования компиляторов, и показывается, как их применять на практике. Применение теории детально продемонстрировано на примере компилятора для учебного языка программирования. Разработанный авторами метол позволил им включить в синтаксический блок значительную часть того, что обычно относится к семантике (генерации кода). Изложение строгое, но не формальное, доступное читателю, не имеющему специальной математической подготовки.
Книга рекомендуется широкому кругу системных программистов и студентов соответствующего профиля (особенно инженерных вузов).
Содержание
От редактора перевода
От редакционного бюро IВМ
Предисловие
Глава 1. Введение
Программы для обработки языков
1.1. Упрощенная модель компилятора
1.2. Блоки и проходы компилятора
1.3. Организация рабочей программы
1.4. Математические модели перевода
1.5. Компилятор для языка МINI-ВАSIС
Глава 2. Конечные автоматы
2.1. Введение
2.2. Конечные распознаватели
2.3. Таблица переходов
2.4. Концевые маркеры и выходы из распознавания
2.5. Пример построения автомата
2.6. Пустая цепочка
2.7. Эквивалентность состояний
2.8. Проверка эквивалентности двух состояний
2.9. Недостижимые состояния
2.10. Приведенные автоматы
2.11. Получение минимального автомата
2.12. Недетерминированные автоматы
2.13. Эквивалентность недетерминированных и детерминированных конечных распознавателей
2.14. Пример: константы языка МINI-ВАSIС
2.15. Замечания по литературе
Упражнения
Глава 3. Реализация конечных автоматов
3.1. Введение
3.2. Представление входных символов
3.3. Представление состояний
3.4. Выбор переходов
3.5. Идентификация слов: метод автомата
3.6. Идентификация слов: метод индексов
3.7. Идентификация слов: метод линейного списка
3.8. Идентификация слов: метод упорядоченного списка
3.9. Идентификация слов: метод расстановки
3.10. Обнаружение префиксов
3.11. Замечания по литературе
Упражнения
Глава 4. Лексический блок для языка МINI-ВАSIС
4.1. Множество лексем
4.2. Проблемы идентификации
4.3. Транслитератор
4.4. Лексический блок
Упражнения
Глава 5. Автоматы с магазинной памятью
5.1. Определение автомата с магазинной памятью
5.2. Некоторые обозначения для множеств цепочек
5.3. Пример распознавания множества МП-автоматом
5.4. Расширенные операции над магазином
5.5. Перевод с помощью МП-автоматов
5.6. Зацикливание
5.7. Замечания по литературе
Упражнения
Глава 6. Контекстно-свободные грамматики
6.1. Введение
6.2. Формальные языки и формальные грамматики
6.3. Формальные грамматики: пример
6.4. Контекстно-свободные грамматики
6.5. Выводы
6.6. Деревья
6.7. Грамматика для констант языка MINI BASIC
6.8. Грамматика для S-выражений Лиспа
6.9. Грамматика для арифметических выражений
6.10. Разные грамматики для одного и того же языка
6.11. Регулярные множества как контекстно-свободные языки
6.12. Праволинейные грамматики
6.13. Еще одна грамматика для констант языка MINI BASIC
6.14. Лишние нетерминалы
6.15. Грамматика MINI BASIC’а для руководства по этому языку
6.16. Замечания по литературе
Упражнения
Глава 7. Синтаксически управляемые процессы обработки языков
7.1. Введение
7.2. Польская запись
7.3. Транслирующие грамматики
7.4. Синтаксически управляемый перевод
7.5. Пример: синтезируемые атрибуты
7.6. Пример: наследуемые атрибуты
7.7. Атрибутные транслирующие грамматики
7.8. Перевод арифметических выражений
7.9. Трансляция некоторых операторов языка MINI BASIC
7.10. Еще одна атрибутная транслирующая грамматика для выражений
7.11. Неоднозначные грамматики и многозначные переводы
7.12. Замечания по литературе
Упражнения
Глава 8. Нисходящие методы обработки языков
8.1. Введение
8.2. Пример
8.3. S-грамматики
8.4. Нисходящая обработка для транслирующих грамматик
8.5. q-грамматики
8.6. LL(1)-грамматики
8.7. Нахождение множеств выбора
8.8. Обработка ошибок при нисходящем разборе
8.9. Метод рекурсивного спуска
8.10. Замечания по литературе
Упражнения
Глава 9. Нисходящие методы обработки для атрибутных грамматик
9.1. Введение
9.2. L-атрибутные грамматики
9.3. Форма простого присваивания
9.4. Пример атрибутного автомата
9.5. Атрибутный автомат с магазинной памятью
9.6. Пример: условный оператор
9.7. Пример: арифметические выражения
9.8. Метод рекурсивного спуска для атрибутных грамматик
9.9. Замечания по литературе
Упражнения
Глава 10. Синтаксический блок для языка MINI BASIC
10.1. LL(1)-грамматика языка
10.2. Множество атомов и транслирующая грамматика
10.3. L-атрибутная грамматика
10.4. Синтаксический блок
10.5. Компактный процессор для выражений языка MINI BASIC
Упражнения
Глава 11. Восходящие методы обработки языков
11.1 Введение
11.2. Понятие основы
11.3. Пример
11.4. Второй приме
11.5. Грамматические основы восходящих методов
11.6. Польский перевод
11.7. S-атрибутные грамматики
Упражнения
Глава 12. Обработка методами типа «перенос - опознание»
12.1. Введение
12.2. Управление автоматом типа «перенос - опознание»
12.3. Бессуффиксные ПО-грамматики
12.4. Грамматики слабого предшествования
12.5. Простые грамматики смешанной стратегии предшествования
12.6. Вычисление отношений ПОД и СВЕРТЫВАЕТСЯ-ПО
12.7. Обработка ошибок при разборе типа «перенос - опознание»
12.8. Синтаксический блок для языка MINI BASIC
12.9. Замечания по литературе
Упражнения
Глава 13. Обработка методами типа «перенос - свертка»
13.1. Введение
13.2. Пример
13.3. Еще один пример
13.4. LR(0)-грамматики
13.5. SLR(1)-грамматики
13.6. Эпсилон-правила
13.7. Обработка ошибок при разборе типа «перенос - свертка»
13.8. Замечания по литературе
Упражнения
Глава 14. Генератор кода для MINI-BASIC-компилятора
14.1. Введение
14.2. Окружение компилятора и объектная машина
14.3. Моделирование исполнения
14.4. Распределение памяти
14.5. Элементы таблиц
14.6. Процедура ГЕН
14.7. Блок управления сумматором
14.8. Процедуры для атомов
14.9. Обработка описаний в языках с блочной структурой
14.10. Замечания по литературе
Упражнения
Глава 15. Обзор методов оптимизации объектного кода
15.1. Введение
15.2. Распределение регистров
15.3. Оптимизация одного атома
15.4. Оптимизация фиксированной цепочки атомов
15.5. Оптимизация одного оператора
15.6. Оптимизация нескольких операторов
15.7. Оптимизация циклов
15.8. Прочие приемы оптимизации
15.9. Замечания по литературе
Приложение А. Руководство по языку MINI-BASIC
А.1. Общин вид программы на MINI-BASIC'е
А.2. Числа
А.З. Переменные
А.4. Арифметические выражения
А.5. Операторы
Приложение Б. Отношения
Б.1. Введение
Б.2. Представление отношений, определенных на конечных множествах
Б.З. Произведение отношений
Б.4. Транзитивное замыкание
Б.5. Рефлексивно-транзитивное замыкание
Упражнения.
Приложение В. Преобразования грамматик
В.1. Введение
В.2. Нисходящая обработка списков
В.З. Левая факторизация
В.4. Замена края
В.5. Одиночная замена
В.6. Левая рекурсия
В.7. Преобразование «цель-край»
В.8. Исключение е-правил
В.9. Получение польского перевода
В.10. Устранение конфликтов переноса - опознания
В.11. Замечания по литературе
Упражнения
Список литературы
Именной указатель
Предметный указатель