- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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
4.3.2. Лексичекий анализ в сп
В рассматриваемой версии символьного препроцессора первый проход на основании исходного текста формирует полную строку лексем. Здесь это оправдано, так как отпадает необходимость в многократном сканировании текста при возвратах, что ускоряет процесс синтаксического анализа. Ведь внутренняя форма грамматики уже представляет, по сути дела, набор лексических единиц и синтаксический анализ потребует только сопоставления их типов.
Итак, при лексическом проходе исходный текст разбивается на базовые элементы языка - лексемы (разделители, ключевые слова, идентификаторы, константы и т.п.) и строится промежуточное представление текста в виде последовательности лексем. При этом игнорируются комментарии и “лишние” символы (пробелы, знаки табуляции, перевод строки). По ходу лексического анализа могут быть выявлены и диагностированы ошибки типа “нераспознаваемая лексема” (например, сочетание символов 1В25А7) или “незакрытые скобки комментария”. В случае отсутствия лексических ошибок на первом проходе формируется выходной файл “Строка лексем”, который состоит из записей различной длины, каждая из которых определяет лексему (содержит её атрибуты). Обязательными атрибутами являются тип лексемы, позиция её первого символа в файле исходного текста и количество символов, которое занимает лексема в исходном тексте. Кроме обязательных атрибутов запись лексемы может содержать дополнительную информацию, которая приведена в таблице 4.1.
Таблица 4.1.
-
Лексема
Код
Начало
Длина
Целое
Действительное
Индекс
Размер лексемы
Идентификатор
1
+
+
-
-
-
6 байт
Целое число
2
+
+
+
+
-
18 байт
Действительное число
3
+
+
+
+
-
18 байт
Конец файла
5
+
+
-
-
-
6 байт
Терминал (ключевое слово)
6
+
+
-
-
+
8 байт
Разделитель
7
+
+
-
-
+
8 байт
Здесь представлены следующие поля:
Код, Начало, Длина - соответствуют трём обязательным атрибутам,
Целое - представление лексемы в виде целого числа,
Действительное - представление лексемы в виде числа с плавающей точкой,
Индекс - индекс в таблице терминалов или разделителей.
Значком + отмечено присутствие соответствующего поля в записи лексемы данного типа, а - помечает отсутствие поля.