- •Университет наяновой
- •М. А. Шамашов основные структуры данных и алгоритмы компиляции
- •Предисловие
- •Введение
- •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
Университет наяновой
Самарский муниципальный комплекс непрерывного образования
М. А. Шамашов основные структуры данных и алгоритмы компиляции
Учебное пособие
Самара
1999
УДК 681.3
Основные структуры данных и алгоритмы компиляции. Учебное пособие./ М.А. Шамашов. Самара: Научно–внедренческая фирма “Сенсоры, модули, системы”, 1999, 115 с.
В пособии рассмотрены методы, алгоритмы и структуры данных, лежащие в основе трансляторов различной природы, но основное внимание акцентируется на принципах построения современных компиляторов и интерпретаторов для алгоритмических языков высокого уровня.
Пособие ориентировано
на студентов, изучающих компьютерные
науки, и специалистов в области
проектирования системного и прикладного
программного обеспечения в самых разных
областях. Рекомендуется в качестве
учебника для использования в учебном
процессе специальности 01.02 “Прикладная
математика”,
специализация 01.02.01 – математическое
и программное обеспечение систем
(информационные технологии в производстве),
а также специальностей “Автоматизированные
системы обработки информации и управления”
и “Программное
обеспечение вычислительных и
автоматизированных систем”.
Выполнено на кафедре “Информатика”и
в лаборатории “Открытые
системы”
Университета Наяновой.
Ил. 68. Табл. 6. Библ. 18 наимен.
Печатается по решению редакционно–издательского совета научно–внедренческой фирмы “Сенсоры, модули, системы”.
М. А. Шамашов, 1999.
Университет Наяновой, 1999.
Предисловие
Перед вами учебное пособие, которое задумывалось как вторая часть учебника для одно– или двухсеместрового курса по теории формальных языков и основам построения компиляторов. Напомним, что в первом пособии этой серии – “Теория формальных языков. Грамматики и автоматы”[16] освещается та часть математической теории формальных языков и автоматов, на которой базируется синтаксически управляемый перевод. Данное пособие, напротив, более конструктивно. В нем рассмотрены структуры данных, алгоритмы и реализационные аспекты трансляторов, компиляторов, интерпретаторов и ассемблеров. И в этой связи пособие должно представлять несомненный самостоятельный интерес.
На наш взгляд, нельзя быть специалистом в области Computer Science и не знать принципов функционирования различных трансляторов для языков высокого уровня и ассемблеров, стоящих в ряду наиболее сложных и интересных программных систем.
Кроме того, развитие вычислительной техники невозможно без изобретения новых языков общения с ней. Человеку вообще свойственно создавать новые языки. Современные информационные технологии предполагают привлечение конечного пользователя, ученого или инженера, специалиста в конкретной предметной области, а не вычислительной техники и технологии программирования к решению своих задач на ЭВМ. Для качественного решения этой проблемы между пользователем и ЭВМ должен существовать интеллектуальный интерфейс, – пользователь должен ставить задачу и получать результаты в терминах известной ему предметной области. То есть, нужен предметно ориентированный язык. Думаю, что многим из Вас придется столкнуться с разработкой таких языков. Да и при разработке любой простейшей автоматизированной системы, пакета программ необходимо помнить о входном языке этой системы, знать как его анализировать, контролировать, транслировать и воплощать в действие. И для того, чтобы не “изобретать велосипед”, надо, конечно же, знать методы, алгоритмы, способы организации данных и средства автоматизации, лежащие в основе построения подобных систем.
Предлагаемое пособие и дает основы знаний в области проектирования компиляторов и других транслирующих систем. Разделы пособия сложились на основании конспектов лекционного курса, который в течении ряда лет читается автором в Самарском государственном аэрокосмическом университете и Самарском муниципальном университете Наяновой.
В первой главе пособия кратко рассмотрена вся совокупность задач, решаемых компилятором в их взаимосвязи. Последующие главы посвящены детальному рассмотрению наиболее интересных и важных фаз компиляции. Во второй главе рассмотрены алгоритмы и структуры данных лексического анализатора (сканера). В третьей главе обсуждаются возможные способы организации таблиц компиляторов. Четвертая и пятая, наиболее объемные главы посвящены описанию различных методов синтаксического анализа. Рассматриваются недетерминированные алгоритмы (алгоритмы с возвратами) нисходящего и восходящего синтаксического анализа, наименее эффективные, но подходящие для произвольных контекстно–свободных языков. Обсуждаются детерминированные LL(k) анализаторы, а также анализаторы языков простого и операторного предшествования. В шестой главе дано введение в семантику, обеспечивающую перевод программ во внутреннюю форму (ПОЛИЗ, тетрады) с ее последующей интерпретацией или генерацией кода. В седьмой главе обсуждаются методы машинно–независимой оптимизации программ. В восьмой главе дан обзор машинно-зависимых фаз компиляции. Там же приводятся некоторые сведения о трансляции с языка ассемблера.