- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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.5. Сбалансированные деревья
Для добавления элементов к дереву и реорганизации дерева, лучше всего подходит теория и алгоритмы сбалансированных деревьев, прекрасно изложенные в монографии Н. Вирта [3]. Дерево называется сбалансированным тогда и только тогда, когда высоты двух поддеревьев каждой из его вершин отличаются не более чем на единицу.
Рассмотрим алгоритм включения элемента в сбалансированное дерево. Если у нас есть корень r и левое (L) и правое (R) поддеревья, то необходимо различать 3 возможных случая. Предположим, что включение в L новой вершины, приведет к увеличению на 1 его высоты, тогда возможно:
1. hL = hR(где h – высота дерева). Тогда после включения L и R станут разной высоты, но критерий сбалансированности не будет нарушен.
2. hL < hR, L и R станут равной высоты, то есть сбалансированность улучшится.
3. hL > hR, критерии сбалансированности нарушатся и дерево необходимо перестраивать.
Для примера, возьмем дерево, представленное на рис. 3.4. Вершины с ключами 9 и 11 можно включить, не нарушая сбалансированности дерева; дерево с корнем 10 становится односторонним (случай 1), а с корнем 8 – лишь лучше сбалансированным (случай 2). Отдельное включение ключей 1,3,5 или 7 требует последующей балансировки.
При внимательном изучении этой ситуации можно обнаружить, что существует лишь две по существу различные возможности, требующие индивидуального подхода. Оставшиеся могут быть выведены из этих двух на основе симметрии. Первый случай возникает при включении в дерево на рис. 3.4 ключей 1 или 3, ситуация характерная для второго случая, возникает при включении ключей 5 или 7.
Схематично эти случаи представлены на рисунке 3.5, где прямоугольниками обозначены поддеревья, причем “добавленная” при включении высота отмечена перечеркиванием.
Простые преобразования сразу же восстанавливают сбалансированность. Их результат приведен на рисунке 3.6. Обратите внимание, что допускаются лишь перемещения в вертикальном направлении, в то время как относительное горизонтальное расположение вершин и поддеревьев должно остаться неизменным.
Алгоритм включения и балансировки существенно зависит от того, каким образом хранится информация о сбалансированности дерева. Крайнее решение – хранить эту информацию полностью неявно, в структуре самого дерева. Однако в этом случае сбалансированность узла нужно определять всякий раз, когда включение затрагивает этот узел. Это ведет к очень большим затратам.
Другая крайность – хранить в каждой вершине показатели сбалансированности. В этом случае определение узла дерева представляется в виде
Type Ptr=Pointer to Node;
Type Balance=[–1..+1];
Type Node=record
count: Integer;
left,right:Ptr;
hol:Balance;
end;
Показатель сбалансированности вершины можно определять как разность между высотой правого поддерева и левого. Процесс включения вершины фактически состоит из трех последовательно выполняемых пунктов
1. Проходя по пути поиска, пока не убедимся, что ключа в дереве нет.
2. Включение новой вершины и определения результирующего показателя сбалансированности.
3. “Отступления” по пути поиска и проверки в каждой вершине показателя сбалансированности. Если необходима – балансировка.
Хотя при таком методе и требуются некоторые избыточные проверки (если сбалансированность уже зафиксирована, то нет необходимости проверять ее в вышестоящих вершинах), традиционно придерживаются именно этой корректной схемы, так как ее можно реализовать простым расширением процедуры поиска элемента в дереве с включениями. В этой процедуре описываются действия, связанные с поиском в каждой вершине, и в силу рекурсивной природы этой процедуры ее легко приспособить для выполнения дополнительных действий при возвращении вдоль пути поиска. Информация, которую необходимо передавать на каждом шаге, указывает, увеличилось ли или нет высота поддерева, где произошло включение. Поэтому кроме традиционных параметров, x ключ поиска и p – указатель вершины дерева, добавляется булевское значение (параметр – переменная) h, – означающее – “ высота дерева увеличилась”.
Cложность операции балансировки предполагает, что сбалансированные деревья следует использовать, когда поиск информации проводится значительно чаще, чем ее включения. Это утверждение особенно верно, поскольку вершины дерева поиска для экономии памяти обычно хранится в виде плотно упакованных записей. Поэтому решающим фактором, определяющим эффективность операции балансировки, часто бывает доступность показателя балансировки и простота его изменения, ведь для его представления нужно всего 2 разряда.
Исключением из сбалансированного дерева– процесс еще более сложный, чем включение в него. Тем не менее, операции поиска, включения и исключения из сбалансированного дерева выполняются даже в худшем случае за время пропорциональное t(log 2 N), где t – некоторое константа, а N – количество элементов в таблице.