- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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
Введение
Транслятор – это программа перевода текста (программы) с одного языка (исходного) на другой (объектный).
Если исходный язык является языком программирования высокого уровня, например, таким как ФОРТРАН, АЛГОЛ, АДА, ПАСКАЛЬ, СИ или МОДУЛА – 2 и, если объектный язык автокод (язык ассемблера) или машинный язык, то транслятор называют компилятором. Машинный язык иногда называют кодом машины, и поэтому объектная программа зачастую называется объектным кодом. Трансляция исходной программы в объектную выполняется во время компиляции, а фактическое выполнение объектной программы во время выполнения готовой программы.
Ассемблер – это программа, которая переводит исходную программу, написанную на автокоде или языке ассемблера, на язык вычислительной машины. Язык ассемблера – это по сути дела машинный язык, ориентированный на человеческое восприятие. Он очень близок к машинному языку с точным символическим представлением команд машины с фиксированным форматом, что позволяет легко их анализировать. В языке ассемблера отсутствуют вложенные инструкции, блоки и т.п. То есть ассемблер значительно проще компилятора. Тем не менее, в процессе изложения материала мы в начале будем говорить о компиляторах, и давать примеры трансляции с языка высокого уровня на язык ассемблера для упрощения пояснения. Трансляцию же с языка ассемблера рассмотрим в последнюю очередь.
Интерпретатор для некоторого исходного языка принимает исходную программу, написанную на этом языке, как входную информацию и выполняет ее. Различие между интерпретатором и компилятором состоит в том, что интерпретатор не порождает объектную программу, которая затем должна выполняться, а непосредственно выполняет исходную программу сам. Для того чтобы выяснить, как осуществить выполнение инструкции исходной программы, чистый интерпретатор анализирует ее всякий раз, когда она должна быть выполнена. Конечно же, это не эффективно. С точки зрения программной реализации интерпретатор обычно разделен на две фазы. На первой фазе интерпретатор анализирует всю исходную программу, почти так же, как это делает компилятор, и транслирует ее в некоторое внутреннее представление. На второй фазе это внутреннее представление исходной программы интерпретируется или выполняется. Перевод во внутреннее представление необходим для сведения к минимуму времени на анализ (расшифровку) каждой инструкции при ее выполнении. Таким образом, начальные фазы компилятора и интерпретатора совпадают.
В процессе изложения материала мы будем рассматривать синтаксически управляемые методы компиляции. Почти половина курса будет посвящена автоматическому распознаванию синтаксиса языков, что в свою очередь основывается на теории формальных языков, которую мы рассматривали в первой части курса и учебном пособии “Теория формальных языков. Грамматики и автоматы”. Вам необходимо вспомнить азы этого курса и, в первую очередь, автоматные и контекстно–свободные языки и грамматики, конечные автоматы и автоматы с магазинной памятью. Знание теории формальных языков позволяет глубже понять процессы компиляции, поможет систематически и эффективно проводить проектирование и реализацию компилятора.