- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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
Заключение
Завершая пособие, заметим, что его рамки не позволили рассмотреть и малой толики того объема знаний, который накоплен в данной области. Здесь приведены лишь наиболее важные фрагменты стройной теории компиляции и перевода. Заинтересованный читатель откроет для себя массу полезного, если познакомиться с работами, приведенными в списке литературы. Обсуждаемые там методы и алгоритмы играют большую роль не только в компиляции, - это часть общей культуры программирования и искусственного интеллекта.
Наиболее современный учебник “Compilers: principles, techniques, and tools” [18] подробно излагает большинство тем курса, но у нас, к сожалению, он практически недоступен. В замечательной, хотя и несколько устаревшей монографии Д. Гриса [5] основное внимание уделяется реализационным вопросам конструирования компиляторов. Вместе с двухтомником А. Ахо и Д. Ульмана [1, 2], освещающим теоретические аспекты рассматриваемого предмета, они удачно дополняют друг друга. Небесполезные сведения содержатся и во многих других книгах, в названии которых встречаются слова "компилятор" или "транслятор", “теория формальных грамматик и языков”. Наиболее интересные из них также приведены в списке. Мы сочли возможным включить в список литературы и ряд работ, которые отражают скромный вклад автора в теорию и практику компиляции.
Список литературы
-
Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 1. Синтаксический анализ. – М.: Мир, 1978.
-
Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. Том 2. Компиляция. – М.: Мир, 1978.
-
Вирт Н. Алгоритмы и структуры данных. – М.: Мир, 1989.
-
Гамин П.В., Куликов В.В., Шамашов М.А. Система автоматизации проектирования синтаксических анализаторов. В кн.: Автоматизация производства пакетов прикладных программ (Автоматизация проектирования трансляторов). Тезисы докладов Всесоюзного семинара. Таллин: ТПИ, 1980, с.176-180.
-
Грис Д. Конструирование компиляторов для цифровых вычислительных машин. – М.: Мир, 1975.
-
Донован Д. Системное программирование. – М.: Мир, 1975.
-
Ингерман П. Синтаксически ориентированный транслятор. – М.: Мир, 1969.
-
Кораблин М.А., Симонова Е.В., Шамашов М.А., Мажаров Л.Г. Учебно-исследовательская система конструирования формальных языков “Грамматика”. Методические указания. – Самара, СГАУ, 1997.
-
Кораблин М.А., Шамашов М.А. Языковые оболочки - интеллектуальный интерфейс пользователя пакетов прикладных программ. В кн.: Интеллектуальные системы в машиностроении. Материалы Всесоюзной конференции. Часть 3. Интеллектуальные системы в научных исследованиях. Программно-аппаратные средства для разработки интеллектуальных систем. – Самара: ИМАШ АН СССР, 1991, с. 85-88.
-
Куликов В.В., Шамашов М.А. Автоматизация проектирования синтаксических анализаторов проблемно - ориентированных языков систем автоматизации эксперимента. В кн.: Автоматизация экспериментальных исследований. Межвузовский сборник. – Куйбышев: КуАИ, 1982, с. 94-100.
-
Льюис Ф., Розенкранц Д. Стирнз Р. Теоретические основы построения компиляторов. – М.: Мир, 1979.
-
Маккиман У., Хорнинг Д., Уортман Д. Генератор компиляторов. –М.: Статистика, 1980.
-
Семантика языков программирования. Сборник статей. – М.: Мир, 1980.
-
Р.Хантер. Проектирование и конструирование компиляторов. - М.: Финансы и статистика, 1984.
-
Хопгуд Ф. Методы компиляции. – М.: Мир, 1972.
-
Шамашов М.А. Теория формальных языков. Грамматики и автоматы. – Самара: Университет Наяновой, 1996.
-
Штернберг Л.Ф. Теория формальных грамматик. – Куйбышев: КуАИ, 1979.
-
Aho A., Sethi R., Ullman J. Compilers: principles, techniques, and tools. Addison-Wesley, Reading, MA, 1986.