- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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. Символьный препроцессор на основе бэктрекинга
Мы уже отмечали, что одной из основных проблем, сдерживающих эффективное применение компьютеров в различных областях науки и техники, является традиционная, исторически сложившаяся технология решения прикладных задач на ЭВМ. Дело в том, что конечный пользователь, ставящий задачу и использующий результаты ее решения, обладая профессиональными знаниями, в общем случае не имеет необходимых знаний о способах использования вычислительной техники для решения его задачи. Посредником между ним и ЭВМ выступает системный аналитик и программист и уже после построения схемы решения происходит почти полное “отчуждение” конечного пользователя от дальнейшего процесса решения задачи. Разработанный и отлаженный программный продукт может дать результаты, не удовлетворяющие пользователя. Однако, при традиционной технологии внесение изменений потребует нового привлечения программистов и аналитиков, которые в соответствии с коррективами постановки задачи должны модифицировать программу, что обычно ничуть не проще разработки новой. После разработки, отладки и оформления программной системы как изделия она поступает к пользователям, но дальнейшая работа с ней не ограничивается решением прикладных задач. Если теоретически и можно предположить существование “безошибочной” программной системы (на практике такое случается крайне редко), то предусмотреть все последующие изменения в постановке задач и требований к их решению в большинстве случаев просто невозможно. Естественное развитие предметной области, условий в которых решается задача, неизбежно приводят к необходимости расширения функциональных возможностей реализованной программы. Таким образом, сопровождение программной системы, связанное с исправлением ошибок и модификацией, выполняется на протяжении всего ее жизненного цикла. Процесс сопровождения в традиционной технологии требует, по крайней мере, такого же количества ресурсов, как и разработка программы. В частности, удваивается число специалистов по программному обеспечению, обслуживающих потребности пользователей. В условиях неуклонного расширения сферы применения ЭВМ потребности в таких специалистах не могут быть реально удовлетворены. Сказанное выше и обуславливает необходимость изменения традиционной технологии использования ЭВМ.
Преодолеть рассмотренную выше кризисную ситуацию можно лишь привлечением конечного пользователя к непосредственному процессу решению его задач на ЭВМ, сопровождению программной системы, разработке прикладных программ. Это можно будет сделать только в том случае, когда между пользователем и ЭВМ будет существовать интеллектуальный интерфейс, позволяющий ставить задачи и получать результаты в терминах его предметной области, без знаний технологии программирования, операционных систем и иных программистских тонкостей. Каким же должен быть этот интерфейс?
Прямое использование пакетов прикладных программ (процедур с параметрами) требует от пользователя знаний программиста. С помощью чисто диалоговых средств достаточно сложную систему описать невозможно. Да и сам диалог предполагает наличие контролируемых ответов. Итак, необходим предметно ориентированный язык, чтобы пользователь описывал свою задачу и получал результаты ее решения ее в терминах области его деятельности. Создание спектра таких языков невозможно без средств автоматизации проектирования - систем построения трансляторов (СПТ). Одним из первых СПТ был генератор компиляторов XPL [12]. Автоматизацию построения трансляторов в ОС UNIX поддерживает программа LEX - генератор сканеров (лексических анализаторов) и программа YACC (Yet Another Compiler Compiler), предназначенная для построения синтаксических анализаторов контекстно-свободных языков.
Этим же целям служит и символьный препроцессор (СП) - программная система, разработанная и реализованная в Куйбышевском авиационном институте автором пособия в 1988 году сначала для PDP-11, а в 1990 году перенесенная и на IBM PC. Эта система использовалась для создания языков описания электротехнических схем, бортовых программно-аппаратных комплексов (СИМПАК), коммутируемых сетей с целью их имитации, исследования, оптимизации и отладки алгоритмов[9]. Упрощенный вариант этой системы до сих пор применяется в учебном процессе [8]. Данный параграф и посвящен описанию этой системы, одним из основных достоинств которой является компактность основных алгоритмов в силу их рекурсивной природы, отражающей рекурсивность КС-грамматик.
Общая схема и фазы функционирования символьного процессора показаны на рис. 4.5.
На рисунке обрамления - обозначают файлы с данными, а - программные компоненты. Указывается также фаза работы СП, на которой используется та или иная связь. Здесь:
Ф1 - фаза анализа и перевода грамматики во внутреннее представление.
Ф2 - фаза трансляции исходного текста (лингвистического описания задачи (ЛОЗ)) в объектный код (информационный образ задачи (ИОЗ)).
Ф3 - фаза интерпретации (выполнения) объектного кода.
Принципы работы этих фаз поясняются в последующих разделах.