Разработка компиляторов

Разработка компиляторов

2-е издание, исправленное

Вояковская Н.Н.
Москаль А.Е.
Булычев Д.Ю.
Терехов А.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Разработка компиляторов/ Н.Н. Вояковская, А.Е. Москаль, Д.Ю. Булычев, А.А. Терехов - М.:
Национальный Открытый Университет “ИНТУИТ”, 2016

В данном курсе рассматриваются теоретические основы и практические методы создания
компиляторов языков программирования. Изложение ведется на основе языка программирования C#
и платформы .NET.

(c) ООО “ИНТУИТ.РУ”, 2006-2016
(c) Вояковская Н.Н., Москаль А.Е., Булычев Д.Ю., Терехов А.А., 2006-2016

3

Введение и обзор платформы .NET

В введении рассматриваются цели и задачи данного курса, его структура и рамки, а
также говорится об необходимых предварительных знаниях, которые потребуются для
полноценного понимания курса. В первой лекции обсуждаются следующие вопросы:
общая идея архитектуры .NET; достоинства и недостатки .NET; схема трансляции
программ в .NET; основные черты промежуточного представления, используемого в
.NET (MSIL); безопасность в .NET; объектная модель .NET; понятие сборки, манифест
сборки; модель безопасности в .NET; единая система типов данных.

Введение

Данный курс посвящен принципам разработки компиляторов. Основные задача
данного курса - познакомить студентов с базовыми идеями и методами,
используемыми при создании современных компиляторов, а также дать практические
навыки написания простых компиляторов. В качестве целевой платформы для
компиляторов в данном курсе используется Microsoft .NET. Подразумевается, что к
моменту окончания данного курса большинство студентов смогут самостоятельно
создать работающий компилятор с простого C#-подобного языка программирования.

Теория создания компиляторов активно развивалась в течение последних 50-60 лет и к
сегодняшнему дню в данной области накоплено огромное количество знаний. Поэтому
практически невозможно подробно осветить все вопросы создания компиляторов в
рамках университетского курса. В этом курсе авторы пытаются лишь преподать
основные принципы создания компиляторов и познакомить студентов с некоторыми
типичными распространенными приемами. Для дальнейшего совершенствования
полученных навыков студенту необходима практика и самостоятельное изучение
последних достижений в этой области.

Курс состоит из двух частей - теоретической и практической. Теоретическая часть
организована в виде презентаций и данного учебника, а практическая часть состоит из
демонстраций и самостоятельных упражнений.

Для полноценного понимания курса студенту потребуются базовые знания языка C# и
платформы .NET в целом. Но так как эти знания еще нельзя считать повсеместно
распространенными, курс содержит краткое введение в .NET, которое поможет
студентам получить представление об этих технологиях, а также оценить свои знания
платформы .NET.

В этой лекции обсуждаются следующие вопросы:

Общая идея архитектуры .NET
Достоинства и недостатки .NET
Схема трансляции программ в .NET
Основные черты промежуточного представления, используемого в .NET (MSIL)
Безопасность в .NET
Объектная модель .NET

4

Понятие сборки. Манифест сборки.
Модель безопасности в .NET
Единая система типов данных

Обзор платформы .NET

Платформа Microsoft .NET появилась относительно недавно, в 2000 году. Более того,
на момент написания данного курса платформа все еще находилась в стадии бетатестирования (при создании примеров авторы использовали вторую бета-версию Visual
Studio.NET). Тем не менее, технологические преимущества платформы .NET в
совокупности с активной маркетинговой поддержкой приводят к тому, что
популярность .NET неуклонно растет. Выпуск платформы .NET наверняка коснется
всех разработчиков программ для Windows. Поэтому чтение курсов, основанных на
.NET, представляется чрезвычайно полезным для студентов: к моменту выпуска
студентов из университета у них уже будут знания технологий, с которыми они, скорее
всего, будут непосредственно работать.

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

Общая схема архитектуры .NET

5

На рисунке представлена общая схема трансляции в .NET (рисунок заимствован из
статьи Дж.Рихтера, опубликованной в сентябрьском выпуске 2000 года журнала MSDN
Magazine).

Исходные тексты программ компилируются в специальное промежуточное
представление ( Microsoft Intermediate Language, часто употребляется сокращение IL
или MSIL). Промежуточное представление содержит всю необходимую информацию о
программе, но не привязано к какому-либо определенному языку программирования
или к машинному коду какой-либо целевой платформы. Для запуска программы
необходимо специальное окружение, исполняющее программы, и библиотеки
динамической поддержки (execution engine & runtime). Важной особенностью
трансляции в .NET является то, что промежуточное представление не
интерпретируется; вместо этого используется механизм компиляции времени
исполнения, который генерирует машинный код. Подразумевается, что большинство
программ, исполняемых на платформе .NET, будет использовать многочисленные
стандартные классы, предоставляющие базовую функциональность (от работы с
данными до встроенных механизмов безопасности).

На последующих слайдах мы кратко остановимся на основных преимуществах
платформы .NET по сравнению с существующими подходами.

Достоинства платформы .NET

Платформа .NET основана на единой объектно-ориентированной модели; все сервисы,
предоставляемые программисту платформой, оформлены в виде единой иерархии
классов. Это решает многие проблемы программирования на платформе Win32, когда
большинство функций были сосредоточены в COM-объектах, а некоторые функции
необходимо было вызывать через DLL.

6

Благодаря тому, что промежуточное представление .NET не привязано к какой-либо
платформе, приложения, созданные в архитектуре .NET, являются
многоплатформенными.

Платформа .NET предоставляет автоматическое управление ресурсами. Это решает
многие распространенные проблемы, такие как утечки памяти, повторное
освобождение ресурса и т.п. На самом деле, в .NET вообще нет никакого способа явно
освободить ресурс!

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

Достоинства платформы .NET

Безопасные типы и общее повышение безопасности приложений
Единая модель обработки ошибок
Межъязыковое взаимодействие (language interoperability)
Единая среда разработки, позволяющая проводить межъязыковую отладку
Расширенные возможности повторного использования кода

Код, сгенерированный для .NET, может быть проверен на безопасность. Это
гарантирует, что приложение не может навредить пользователю или нарушить
функционирование операционной системы (так называемая “модель песочницы”).
Таким образом, приложения для .NET могут быть сертифицированы на безопасность.

Обработка ошибок в .NET всегда производится через механизм исключительных
ситуаций. Это решает неоднозначность ситуации, когда некоторые ошибки
обозначаются с помощью кодов ошибки платформы Win32, некоторые возвращают

HRESULTS и т.п.

Вероятно, самым большим обещанием .NET остается межъязыковое взаимодействие
(language interoperability). Впервые в истории программирования появляется единая
модель, позволяющая на равных пользоваться различными языками для создания
приложений. Так как MSIL не зависит от исходного языка программирования или от
целевой платформы, в рамках .NET становится возможным развивать новые
программы на базе старых программ - причем и первый, и второй языки
программирования не так уж важны!

Естественно, что для такого подхода к разработке программ необходимо обеспечить,
например, межъязыковую отладку (многие сталкивались с трудностями отладки при
вызове С++ библиотеки из Visual Basic). Visual Studio.NET поддерживает этот процесс

7

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

Перечисленные выше особенности платформы .NET позволяют добиться простоты
повторного использования кода. Раньше платформа Win32 позволяла повторное
использование только на уровне COM-компонент; теперь можно повторно
использовать классы и наследовать от них свои приложения.

Недостатки платформы .NET

Естественно, что все преимущества .NET, которые мы перечислили выше, не могут
быть абсолютно бесплатными. Как и у любой другой архитектуры, у .NET есть свои
недостатки.

Самым ощутимым недостатком является существенное замедление выполнения
программ. Это неудивительно, так как между исходным языком и машинным кодом
вводится дополнительный уровень, MSIL. Однако промежуточное представление .NET
с самого начала проектировалось с прицелом на компиляцию времени исполнения (в
отличие, например, от Java bytecode, который разрабатывался с прицелом на
интерпретацию).

Это дает некоторые дополнительные возможности по борьбе с замедлением.
Например, можно равномерно распределить замедление при запуске, так как обычно
компилируется не вся библиотека, а только тот метод, который вызывается, и
повторной компиляции одного и того же метода не производится.

Другая проблема .NET заключается в том, что при ее создании основной упор был
сделан на С++/Java-подобные языки (например, конструкторы с именем, равным имени
метода, запрет множественного наследования и т.п.). Это ограничивает возможности
интеграции некоторых языков с более богатыми возможностями, особенно с
принципиально отличающимися языками, такими как функциональные языки (ML,
Haskell, Scheme) или устаревшие языки (Кобол, PL/I). Во многих случаях
разработчикам компиляторов все-таки удается реализовать “проблемные” особенности
исходных языков в рамках .NET, пусть даже и не слишком тривиальным образом достаточно сказать, что уже существуют реализации типичных представителей этих
классов языков для платформы .NET. Другое направление связано c развитием самой
платформы .NET: например, недавно было заявлено о поддержке платформой .NET
механизма параметрического полиморфизма (generics).

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

Основные черты MSIL

MSIL можно рассматривать как ассемблер некоторой виртуальной машины. Это

8

нетипичный ассемблер, так как он обладает многими конструкциями, характерными
для языков более высокого уровня: например, в нем есть инструкции для описания
пространств имен, классов, вызовов методов, свойств, событий и исключительных
ситуаций. Кроме того, MSIL является стековой машиной со статической проверкой
типов; это позволяет отслеживать некоторые типичные ошибки.

MSIL представляет собой дополнительный уровень абстракции, позволяющий легко
справляться с переносом кода с одной платформы на другую, в том числе, и с
изменением разрядности платформы: в отличие от Java bytecode MSIL не завязан на 32
бита или какую-либо другую фиксированную разрядность. В данный момент
существуют версии MSIL для мобильных 16-разрядных устройств (.NET Compact
Framework), стандартная 32-разрядная версия и специальная версия для работы с
получающими все более широкое распространение 64-разрядными устройствами.

Отметим, что MSIL сохраняет достаточно много информации об именах,
использованных в исходной программе: имена классов, методов и исключительных
ситуаций сохраняются и могут быть извлечены при обратном ассемблировании.
Однако извлечение из MSIL исходных текстов путем дизассемблирования вряд ли
имеет смысл, так как имена локальных переменных, констант и параметров
сохраняются только в отладочной версии.

Пример кода на MSIL

.class auto ansi Point extends ['mscorlib']System.Object 
{ 
  .field private int32 m_x 
  .field private int32 m_y 
  .method public specialname rtspecialname 
                 instance void .ctor() il managed 
  { 
  // Code size 21 (0x15) 
  .maxstack 2 
  IL_0000: ldarg.0 
  IL_0001: call instance void ['mscorlib']System.Object::.ctor() 
  IL_0006: ldarg.0 
  IL_0007: ldc.i4.0 
  IL_0008: stfld int32 Point::m_y 
  IL_000d: ldarg.0 
  IL_000e: ldc.i4.0 
  IL_000f: stfld int32 Point::m_x 
  IL_0014: ret 
  } // end of method 'Point::.ctor'

На слайде приведен фрагмент MSIL-кода, сгенерированный по следующему классу на
С#:

class Point

9

{
  private int m_x, m_y;
  public Point() { m_x = m_y = 0; }
}

В сгенерированном коде можно найти описание класса Point и тот факт, что он
унаследован от System.Object, описание закрытых переменных типа Int32 m_x и m_y
(отметим, что их имена сохраняются при обратном ассемблировании) и, наконец,
конструктор класса Point.

На начальном этапе знакомства с .NET изучение сгенерированного MSIL-кода
представляется весьма полезным, так что рекомендуем слушателям самостоятельно
ознакомиться с утилитой ILDasm.

Базовая модель .NET

В основе .NET лежит единая объектно-ориентированная модель классов, в которой все
классы унаследованы от базового класса Object. Классы разбиты на пространства имен
для избежания накладок при совпадении имен. Основные сервисы .NET сосредоточены
в пространстве имен System (например, там находится упоминавшийся выше класс

Object ).

Пространства имен имеют много уровней вложенности (например, System.WinForms
или System.Web.UI.WebControls ). На следующем слайде мы приведем часть иерархии
классов .NET.

Программисты могут создавать собственные пространства имен для своих классов или
пользоваться уже существующими классами, расширяя их функциональность путем
наследования и переопределения методов.

Модель платформы .NET может существенно упростить разработку приложений по
сравнению с программированием для Windows-платформ, где практически вся
функциональность предоставлялась разработчику как неструктурированный набор
функций в Windows API.

Иерархия классов (отрывок)

На слайде приведен отрывок из иерархии классов .NET. Несмотря на то, что идея
сведения всех объектов в единую иерархию не нова (одним из первых языков с единой
иерархией объектов был SmallTalk, затем подобный прием был использован в Java),
отличительной особенностью платформы .NET является то, что в .NET единая модель
объектов распространяется сразу на все языки программирования.

Системные классы становятся единственным методом взаимодействия программы с
внешним миром для управляемого кода. Одним из следствий этого является
необходимость переписывания всего ввода/вывода для существующих приложений,

10