 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
ЗАКЛЮЧЕНИЕ. Завершая пособие, заметим, что его рамки не позволили рассмотреть и малой толики того объема знаний
|
Читайте также: |
Завершая пособие, заметим, что его рамки не позволили рассмотреть и малой толики того объема знаний, который накоплен в данной области. Здесь приведены лишь наиболее важные фрагменты стройной теории компиляции и перевода. Заинтересованный читатель откроет для себя массу полезного, если познакомиться с работами, приведенными в списке литературы. Обсуждаемые там методы и алгоритмы играют большую роль не только в компиляции, - это часть общей культуры программирования и искусственного интеллекта.
Наиболее современный учебник “Compilers: principles, techniques, and tools” [18] подробно излагает большинство тем курса, но у нас, к сожалению, он практически недоступен. В замечательной, хотя и несколько устаревшей монографии Д. Гриса [5] основное внимание уделяется реализационным вопросам конструирования компиляторов. Вместе с двухтомником А. Ахо и Д. Ульмана [1, 2], освещающим теоретические аспекты рассматриваемого предмета, они удачно дополняют друг друга. Небесполезные сведения содержатся и во многих других книгах, в названии которых встречаются слова "компилятор" или "транслятор", “теория формальных грамматик и языков”. Наиболее интересные из них также приведены в списке. Мы сочли возможным включить в список литературы и ряд работ, которые отражают скромный вклад автора в теорию и практику компиляции.
СПИСОК ЛИТЕРАТУРЫ
1. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. – М.: Мир, 1978.
2. Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция. – М.: Мир, 1978.
3. Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
4. Гамин П.В., Куликов В.В., Шамашов М.А. Система автоматизации проектирования синтаксических анализаторов. - В кн.: Автоматизация производства пакетов прикладных программ (Автоматизация проектирования трансляторов). -Тезисы докладов Всесоюзного семинара. -Таллин: ТПИ, 1980, с.176-180.
5. Грис Д. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир, 1975.
6. Донован Д. Системное программирование. – М.: Мир, 1975.
7. Ингерман П. Синтаксически ориентированный транслятор. – М.: Мир, 1969.
8. Кораблин М.А., Симонова Е.В., Шамашов М.А., Мажаров Л.Г. Учебно-исследовательская система конструирования формальных языков “Грамматика”. Методические указания. – Самара, СГАУ, 1997.
9. Кораблин М.А., Шамашов М.А. Языковые оболочки - интеллектуальный интерфейс пользователя пакетов прикладных программ. В кн.: Интеллектуальные системы в машиностроении. Материалы Всесоюзной конференции. Часть 3. Интеллектуальные системы в научных исследованиях. Программно-аппаратные средства для разработки интеллектуальных систем. – Самара: ИМАШ АН СССР, 1991, с. 85-88.
10. Куликов В.В., Шамашов М.А. Автоматизация проектирования синтаксических анализаторов проблемно - ориентированных языков систем автоматизации эксперимента. В кн.: Автоматизация экспериментальных исследований. Межвузовский сборник. – Куйбышев: КуАИ, 1982, с. 94-100.
11. Льюис Ф., Розенкранц Д. Стирнз Р. Теоретические основы построения компиляторов. – М.: Мир, 1979.
12. Маккиман У., Хорнинг Д., Уортман Д. Генератор компиляторов. –М.: Статистика, 1980.
13. Семантика языков программирования. Сборник статей. – М.: Мир, 1980.
14. Р.Хантер. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984.
15. Хопгуд Ф. Методы компиляции. – М.: Мир, 1972.
16. Шамашов М.А. Теория формальных языков. Грамматики и автоматы. – Самара: Университет Наяновой, 1996.
17. Штернберг Л.Ф. Теория формальных грамматик. – Куйбышев: КуАИ, 1979.
18. Aho A., Sethi R., Ullman J. Compilers: principles, techniques, and tools. Addison-Wesley, Reading, MA, 1986.
СОДЕРЖАНИЕ
ПРЕДИСЛОВИЕ....................................................................................................................... 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. ОБЩИЕ МЕТОДЫ СИНТАКСИЧЕСКОГО АНАЛИЗА.................................... 29
4.1. НИСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ....................................................... 31
4.2. ВОСХОДЯЩИЙ РАЗБОР С ВОЗВРАТАМИ....................................................... 34
4.3. СИМВОЛЬНЫЙ ПРЕПРОЦЕССОР НА ОСНОВЕ БЭКТРЕКИНГА............... 38
4.3.1. Фаза анализа и перевода грамматики во внутреннее представление.... 40
4.3.2. Лексичекий анализ в СП...................................................................................... 44
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. Функции предшествования................................................................................ 66
5.2.3. Проблемы построения грамматик предшествования............................. 70
5.3. ОПЕРАТОРНАЯ ГРАММАТИКА ПРЕДШЕСТВОВАНИЯ............................... 72
6. ВВЕДЕНИЕ В СЕМАНТИКУ....................................................................................... 77
6.1. ВНУТРЕННИЕ ФОРМЫ ИСХОДНОЙ ПРОГРАММЫ..................................... 77
6.1.1. Польская инверсная запись................................................................................ 78
6.1.2. Интерпретация ПОЛИЗа................................................................................... 79
6.1.3. Генерирование команд по ПОЛИЗу.................................................................. 80
6.1.4. Тетрады и триады.............................................................................................. 83
6.2. СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ПЕРЕВОДА ИНФИКСНОЙ ЗАПИСИ В ПОЛИЗ И АСПЕКТЫ ИХ РЕАЛИЗАЦИИ........................................................................... 85
6.3. СЕМАНТИЧЕСКИЕ ПОДПРОГРАММЫ ДЛЯ ПЕРЕВОДА В ТЕТРАДЫ.. 87
6.4. МЕТОД ЗАМЕЛЬСОНА–БАУЭРА ДЛЯ ПЕРЕВОДА В ПОЛИЗ И ТЕТРАДЫ 89
6.5. НЕЙТРАЛИЗАЦИЯ ОШИБОК................................................................................ 94
6.5.1. Исправления орфографических ошибок......................................................... 95
6.5.2. Нейтрализация семантических ошибок......................................................... 96
6.5.3. Нейтрализация синтаксических ошибок....................................................... 97
7. МАШИННО-НЕЗАВИСИМАЯ ОПТИМИЗАЦИЯ ПРОГРАММ................... 101
7.1. ИСКЛЮЧЕНИЕ ОБЩИХ ПОДВЫРАЖЕНИЙ.................................................. 101
7.2. ВЫЧИСЛЕНИЯ ВО ВРЕМЯ КОМПИЛЯЦИИ.................................................. 102
7.3. ОПТИМИЗАЦИЯ БУЛЕВЫХ ВЫРАЖЕНИЙ.................................................... 103
7.4. ВЫНЕСЕНИЕ ИНВАРИАНТНЫХ ВЫЧИСЛЕНИЙ ЗА ЦИКЛ.................... 105
8. МАШИННО-ЗАВИСИМЫЕ ФАЗЫ КОМПИЛЯЦИИ...................................... 107
8.1. РАСПРЕДЕЛЕНИЕ ПАМЯТИ................................................................................. 107
8.2. ГЕНЕРАЦИЯ КОДА И СБОРКА.......................................................................... 108
8.3. ТРАНСЛЯЦИЯ С ЯЗЫКА АССЕМБЛЕРА........................................................ 110
ЗАКЛЮЧЕНИЕ.................................................................................................................... 112
СПИСОК ЛИТЕРАТУРЫ................................................................................................ 113
СОДЕРЖАНИЕ.................................................................................................................... 114
Поиск по сайту: