Формальные языки и компиляторы

                Учебники ^ГTУ





Серия основана в 2001 году

    РЕДАКЦИОННАЯ КОЛЛЕГИЯ СЕРИИ «УЧЕБНИКИ НГТУ»


      д-р техн, наук, проф. (председатель) НВ. Пустовой д-р техн. наук, проф. (зам. председателя) ГИ Расторгуев

      д-р техн. наук, проф. А.А. Батаев
      д-р техн. наук, проф. А.Г Вострецов
      д-р техн. наук, проф. В.И. Гужов
      д-р техн. наук, проф. В.А. Гридчин
      д-р техн. наук, проф. В.И. Денисов
      д-р физ.-мат. наук, проф. В.Г Дубровский
      д-р экон. наук, проф. К.Т. Джурабаев
      д-р филос. наук, проф. В.И Игнатьев
      д-р филос. наук, проф. В.В. Крюков
      д-р техн. наук, проф. В.Н. Максименко
      д-р техн. наук, проф. Х.М. Рахимянов
      д-р техн. наук, проф. Ю.Г Соловейчик
      д-р техн. наук, проф. А.А. Спектор
      д-р экон. наук, проф. ВИ. Титова
      д-р юрид. наук, доц. ВЛ. Толстых
      д-р техн. наук, проф. А.Г. Фишов
      д-р техн. наук, проф. А. Ф. Шевченко
      д-р техн. наук, проф. Н.И Щуров

А. А. МАЛЯВКО




            ФОРМАЛЬНЫЕ ЯЗЫКИ И КОМПИЛЯТОРЫ


Допущено Учебно-методическим объединением вузов по университетскому политехническому образованию в качестве учебного пособия для студентов высших учебных заведений, обучающихся по направлению подготовки 230100 «Информатика и вычислительная техника»









НОВОСИБИРСК
2014

УДК 004.43(075.8) М 219




Рецензенты:
А.В. Гунько, канд. техн. наук, доцент
Е.Л. Романов, канд. техн. наук, доцент




     Малявко А.А.
М 219 Формальные языки и компиляторы : учебник / А.А. Малявко. - Новосибирск: Изд-во НГТУ, 2014. - 431 с. - (Серия «Учебники НГТУ»).
          ISBN 978-5-7782-2318-9
          Изложены теоретические основы аппарата определения лексики (регулярные выражения) и синтаксиса (формальные грамматики) языков программирования, элементы теории конечных автоматов без памяти и методы ее практического применения для автоматизированного преобразования системы регулярных выражений в конечный автомат - лексический анализатор.
          Изучаются нисходящие и восходящие методы синтаксического анализа, основанные на преобразовании формальных грамматик в конечные автоматы с магазинной памятью. Рассматриваются различные способы решения задачи нейтрализации синтаксических ошибок.
          Изучаются наиболее типичные задачи, решаемые на этапе семантического анализа: организация памяти программы, доступ к локальным и нелокальным данным, контроль типов.
          Обсуждаются основные задачи генератора кода, такие как управление памятью, выбор инструкций, распределение регистров и порядок вычислений; рассматриваются методы оптимизации кода.
          Приводится описание учебного программного обеспечения и методические указания по выполнению лабораторных работ и курсового проектирования.
          Учебник рекомендуется студентам старших курсов и аспирантам, а также преподавателям смежных дисциплин, а также студентам и аспирантам ряда других технических специальностей, связанных с разработкой и использованием программного обеспечения.

УДК 004.43(075.8)

ISBN 978-5-7782-2318-9                         © Малявко А.А., 2013, 2014
© Новосибирский государственный
                                                 технический университет, 2013, 2014

    ОГЛАВЛЕНИЕ


ПРЕДИСЛОВИЕ..........................................7

ВВЕДЕНИЕ..............................................9

   Трансляторы: компиляторы и интерпретаторы.............................9
   Этапы процесса трансляции............................................12
   Проектирование трансляторов..........................................16

Глава 1. ВВЕДЕНИЕ В ТЕОРИЮ ФОРМАЛЬНЫХ ЯЗЫКОВ....19

  1.1. Элементарные понятия......................................19
  1.2. Регулярные выражения......................................23
  1.3. Формальные грамматики.....................................26
  1.4. Конечные автоматы.........................................60
Вопросы и упражнения к главе 1...................................76
Г л а в а 2. ЛЕКСИЧЕСКИЙ АНАЛИЗ..................................79

   2.1. Постановка задачи................................................79
   2.2. Способы реализации лексического акцептора........................83
   2.3. Процедурная реализация лексического акцептора....................84
   2.4. Автоматная модель лексического акцептора........................100
Вопросы и упражнения к главе 2..........................................131

Г л а в а 3. СИНТАКСИЧЕСКИЙ АНАЛИЗ..................133

   3.1. Введение в синтаксический анализ............................133
   3.2. Нисходящие методы синтаксического акцепта...................137
   3.3. Восходящие методы синтаксического акцепта...................176
   3.4. Синтаксический анализ.......................................219
Вопросы и упражнения к главе 3......................................251
Глава 4. СЕМАНТИЧЕСКИЙ АНАЛИЗ.......................................253
   4.1. Введение в семантический анализ.............................253
   4.2. Программы и данные..........................................260
   4.3. Адреса и значения...........................................266

4.4. Базовые типы данных..............................
   4.5. Производные типы данных..........................
   4.6. Контроль типов данных объектов программы.........
   4.7. Эквивалентность типов данных.....................
   4.8. Ассоциации наименований объектов.................
   4.9. Среды ссылок периода исполнения..................
   4.10. Локальные данные процедур.......................
   4.11. Вызывающие последовательности...................
   4.12. Доступ к нелокальным объектам...................
   4.13. Передача аргументов.............................
   4.14. Функции контроля структуры транслируемой программы
   4.15. Семантический анализ: краткое заключение........
Вопросы и упражнения к главе 4...........................

268
272
274
277
283
295
306
310
313
329
336
337
338

Глава 5. ГЕНЕРАЦИЯ И ОПТИМИЗАЦИЯ КОДА............341

   5.1. Базовые блоки и графы потоков...........................343
   5.2. Объектный код...........................................349
   5.3. Оптимизация программы...................................356
   5.4. Два примера результатов генерации и оптимизации кода....365
Вопросы и упражнения к главе 5..................................376
Глава 6. ЛАБОРАТОРНЫЙ ПРАКТИКУМ И КУРСОВОЕ ПРОЕКТИРОВАНИЕ...................................................377

   6.1. Учебное программное обеспечение. Состав и структура учебного ПО.377
   6.2. Лабораторный практикум..................................408
   6.3. Курсовое проектирование.................................416
БИБЛИОГРАФИЧЕСКИЙ СПИСОК........................................430

ПРЕДИСЛОВИЕ

    В учебнике представлены основы теории формальных языков и базирующиеся на этой теории алгоритмы и методы трансляции, т. е. процесса перевода программ с одного языка на другой. Рассматриваются все этапы процесса трансляции:
    - лексический анализ;
    - синтаксический анализ;
    - семантический анализ;
    - оптимизация;
    - генерация объектного кода и интерпретация.
    Лексический и синтаксический анализ изучается в тесной взаимосвязи с методами автоматизации проектирования компиляторов. Часть, посвященная лексическому анализу (начало главы 1 и глава 2), содержит процедурную и автоматную модели лексического анализа. В нем изложены теоретические основы формального аппарата определения лексики языков программирования, элементы теории конечных автоматов без памяти и методы ее практического применения для автоматизированного преобразования системы регулярных определений в лексический анализатор.
    В части, посвященной синтаксическому анализу (конец главы 1 и глава 3), изложены нисходящие и восходящие методы синтаксического акцепта, т. е. восстановления дерева грамматического разбора, теоретические основы и методы проверки пригодности формальных грамматик для реализации каждого из этих методов, способы преобразования грамматик в конечные автоматы со стековой памятью (так называемые акцепторы или распознаватели). Далее рассмотрены способы расширения акцепторов до синтаксических анализаторов, решающих задачи нейтрализации ошибок и преобразования входного текста в промежуточную форму представления - постфиксную запись.
    В третьей части (главы 4 и 5) рассматриваются задачи, решаемые семантическими анализаторами и генераторами объектного кода трансляторов. Основное внимание уделяется принципам, закладываемым в организацию памяти транслируемой программы, и методам доступа к локальным и нелокальным

данным процедур. На этой основе изучаются применяемые в современных языках подходы к контролю типов данных и функции семантического анализа. Обсуждаются основные задачи генератора кода, такие как формирование последовательности тетрад, управление памятью, выбор инструкций, распределение регистров и порядок вычислений; анализируются методы оптимизации кода.
    Последняя часть (глава 6) содержит материалы, используемые в лабораторном практикуме и курсовом проектировании по дисциплине. В ней описывается учебный клиент-серверный пакет автоматизации проектирования трансляторов Вебтранслаб, правила формирования исходных данных пакета: определения лексики на метаязыке регулярных выражений, определения синтаксиса на метаязыке формальных грамматик и определения семантики путем вставки действий в лексику и синтаксис. Описывается порядок работы с пакетом. Далее приводятся задания на цикл из 8 лабораторных работ и методические указания по выполнению курсовой работы, включающие в себя типовое задание и рекомендации по разработке элементов транслятора.

ВВЕДЕНИЕ


Трансляторы: компиляторы и интерпретаторы

    Все новые программы для компьютеров создаются с использованием определенного набора уже существующих программ: текстовых редакторов, макропроцессоров (или препроцессоров), трансляторов, компоновщиков, профайл еров, отладчиков. На рис. В1 показана достаточно типичная последовательность технологических операций по созданию и исполнению новой программы. Все эти операции выполняются с помощью уже существующих системных программ. Исполняемые программы представлены в виде блоков с двойными рамками, обрабатываемые ими данные - с одинарными.


Рис. Bl. Технология компиляции: создание и исполнение программы

    Согласно рисунку каждая технологическая операция выполняется один раз. В действительности же при создании любой реальной программы боль

шинство этих шагов вероятнее всего будет выполнено многократно. Не показаны здесь упомянутые выше профайлер и отладчик, хотя создание сколько-нибудь сложной программы без их использования трудно себе представить.
    Для удобства использования все программы, участвующие в процессе создания новых программ, обычно включаются в состав так называемых интегрированных оболочек (IDE - integrated development environment), облегчающих программисту управление технологическим процессом создания программы (оболочка на рисунке тоже не показана). Естественно, и сама эта оболочка и все включенные в ее состав программы работают под управлением операционной системы компьютера.
    Текст новой программы, написанной на языке программирования высокого уровня (например, Java или С#, или C++ ...) для решения некоторой задачи, вводится с клавиатуры с использованием текстового редактора. Результат работы текстового редактора - исходный текст (ИТ) - запоминается в виде файла на диске. Этот файл затем может обрабатываться макропроцессором, реализующим макроподстановки и включение заголовочных файлов. Результатом этой обработки является так называемый исходный модуль (ИМ).
    Далее транслятор осуществляет преобразование исходного модуля в так называемый объектный модуль (ОМ). Объектный модуль представляет собой файл программы, эквивалентной исходной, но содержащей смесь машинных команд с инструкциями компоновщику по «стыковке» с другими объектными модулями.
    Несколько объектных модулей, полученных в результате трансляции разных исходных модулей (возможно, выполнявшейся на различных компьютерах в разных частях света и в разное время), преобразуются компоновщиком (другие названия - сборщик, линкер, редактор связей, .) в файл образа задачи (ОЗ) и сохраняется им на диске. Теперь этот файл может быть использован независимо от тех программ, которые принимали участие в его создании, причем вполне вероятно - на других компьютерах.
    Загрузчик операционной системы при каждом запуске преобразует его в исполняемую программу, работающую под управлением и во взаимодействии с операционной системой. Исполняемая программа обрабатывает исходные данные (ИД) и формирует результаты решения задачи (Р).
    Технология, показанная на рис. В1 и называемая компиляцией (от слова компилировать - собирать), не является единственно возможной. Транслятор, реализующий в этой технологической цепочке перевод с одного языка на другой, называется соответственно компилятором. Другой возможный способ получения результатов решения задачи путем прямого выполнения операций