- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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.6. Деревья оптимального поиска
В той же работе Вирта [3] рассматриваются и деревья оптимального поиска. Рассматривая выше поиск по таблице, мы исходили из предположения, что частота обращения ко всем элементам таблицы одинакова, т.е. все ключи с равной вероятностью фигурируют как аргументы поиска. Однако встречаются ситуации, когда есть информация о вероятности обращения к отдельным элементам таблицы. Обычно для таких ситуаций характерно “постоянство” элементов, то есть в дерево поиска элементы не включаются и не исключаются из него. Типичный пример – как раз сканер транслятора, определяющий, не относится ли идентификатор к классу терминалов (ключевых или зарезервированных слов). Статистические измерения на сотнях транслируемых программ могут в этом случае дать точную картину об относительных частотах появления отдельных элементов (обращений к ним). Для этих деревьев вместо понятия средней длины пути по дереву вводится понятие взвешенной длины пути – суммы всех путей от корня каждой из вершин, умноженных на вероятность обращения к этим вершинам.
В качестве примера рассмотрим множество из трех ключей 1, 2, 3 с вероятностями обращения к ним P1=1/7; P2=2/7; P3=4/7. Эти три ключа можно расставить в дерево поиска пятью различными способами, представленными на рис. 3.7. Там же приведены и взвешенные длины пути для каждого дерева.
Таким образом, оптимальным оказывается не идеально сбалансированное дерево (3.7 в), а вырожденное (3.7 а).
Сканер транслятора, предполагает, что задачу следует ставить при несколько больших общих условиях: слова встречающиеся в тексте не всегда ключевые, на самом деле эта ситуация скорее исключение, чем правило. Обнаружение, что данный ключ не является ключом дерева поиска, можно считать обращением к некоторой гипотетической вершине, включенной между следующей большей и следующей меньшой вершиной. Теория этого вопроса довольно сложна и не является задачей нашего курса. Отметим только, что оптимальное дерево поиска ключевых слов большинства языков программирования весьма далеко от сбалансированного.
3.7. ХЕШ – АДРЕСАЦИЯ
Здесь и далее используются термины “хеш–адресация”, “хеширование”, ”хеш–функция” и т.п., происходящих от английского слова hash, что в дословном переводе означает мешанина, путаница. Представляется разумным обходится одним корнем для всей совокупности терминов, связанных с данным кругом понятий, причем корнем, не загруженным другими значениями и дающий максимальную свободу для образования производных слов. Все попытки воспользоваться известными терминами типа “перемешанные таблицы“, “рандомизация“, “функция расстановки“ приводят к длинным и тяжеловесным словосочетаниям.
Метод хеш–адресации впервые был использован при разработке ассемблера для ЭВМ IBM 701 в 1954 году. Суть метода состоит в том, что включение и поиск по таблице основывается на использовании не самого идентифицируемого слова (ключа), а некоторой информации, зависящей от него. Это метод преобразования слова в индекс элемента в таблице. Индекс получается “хешированием“ слова – выполнением над ним (и, возможно, над его длиной) некоторых арифметических или логических операций. Простой хеш–функцией является внутреннее представление кода первой литеры слова. Так, если двоичное представление символа А – 01000001 – 65, то результат хеширования АВЕ будет 65 (или 1, или 0, если использовать не код ASCII, а порядковый номер буквы).
Пока для двух различных слов результаты хеширования различны, время поиска совпадает с временем, затраченным на хеширование, так как мы имеем дело с прямым доступом к таблице и получаем огромную экономию по сравнению с поиском по неупорядоченной и даже упорядоченной таблице. Однако, возникают затруднения, если результаты хеширования двух различных слов совпадают. Это называется коллизией. Очевидно, что в данной позиции таблицы может быть помещено только одно слово, так что мы должны найти другое место для второго. Хорошая хеш–функция распределяет вычисляемые адреса равномерно на все, имеющиеся в распоряжении адреса, так что коллизии не возникают слишком часто. Хеш– функция, описанная выше, очевидна плоха, так как все идентификаторы, начинающиеся с одной и той же буквы, ссылаются на один и тот же адрес. Далее мы рассмотрим различные хеш–функции. Но сначала обсудим один из способов решения задачи коллизии – рехеширование.