Создание компилятора языка для .NET Framework
ОГЛАВЛЕНИЕ
Существуют сотни компиляторов для десятков языков, предназначенные для .NET Framework. .NET CLR сгоняет эти языки в одну песочницу, где они могут играть и мирно взаимодействовать. Крутой разработчик может воспользоваться этим, при создании крупных программных систем, добавляя кусочек C# и каплю Python. Конечно, мастерство этих разработчиков впечатляет, он они и рядом не стоят с истинными мастерами – экспертами по компиляторам, ибо именно эти эксперты обладают глубоким пониманием виртуальных машин, структуры языков и составляющих компонентов этих языков с компиляторами.
В этой статье, я разберу код для компилятора, написанного на C# (метко названного компилятором Good for Nothing («Бесполезным»)), а попутно представлю читателям высокоуровневую архитектуру, теорию и API-интерфейсы .NET Framework, необходимые для создания собственного компилятора .NET. Я начну с определения языка, исследую архитектуру компилятора и затем продемонстрирую подсистему создания кода, которая выдает сборку .NET. Цель здесь заключается в том, чтобы помочь читателям понять основы разработки компиляторов и дать твердое, высокоуровневое понимание того, как языки эффективно ориентируются на CLR. Я не буду здесь разрабатывать эквивалент C# 4.0 или IronRuby, но мой рассказ все же содержит достаточно конкретики, чтобы разжечь в заинтересованных читателях страсть к искусству разработки компиляторов.
Определение языка
Языки программирования начинаются с определенной цели. Эта цель может быть чем угодно, например выразительными возможностями (скажем, Visual Basic®), продуктивностью (скажем, Python, нацеленный на получение максимального эффекта от каждой строки кода), специализацией (скажем, Verilog, являющийся языком описания оборудования, используемым производителями процессоров), или просто удовлетворением личных предпочтений автора. (Например, создатель Boo любит .NET Framework, но не удовлетворен ни одним из доступных языков..
После того, как цель определена, можно разрабатывать язык – думайте о ней как о чертеже для языка. Компьютерные языки должны быть очень точными, чтобы программист мог безошибочно выразить именно то, что нужно и чтобы компилятор мог верно понять его, создав исполняемый код именно для того, что выражено. Чертеж языка должен быть четко определен, чтобы устранить двусмысленности в ходе применения компилятора. Для этого используется метасинтаксис – синтаксис, используемый для описания синтаксиса языков. Существует достаточно много метасинтаксисов, что позволяет подобрать соответствующий личным вкусам. Я буду определять язык Good for Nothing («Бесполезный»), используя метасинтаксис, именуемый EBNF (Extended Backus-Naur Form).
Стоит упомянуть, что EBNF обладает весьма достойными истоками: он связан с Джоном Бэкусом (John Backus), обладателем Премии Тьюринга и ведущим разработчиком FORTRAN. Подробный рассказ о EBNF находится за пределами темы этой статьи, но я могу объяснить базовые концепции.
Определение языка для Good for Nothing показано на рис. 1. В соответствии с моим определением языка, оператор (stmt) может представлять из себя объявления переменных, назначения, циклы, чтение целых чисел из командной строки или печать на экране – и все это можно указывать много раз, разделяя точкой с запятой. Выражения (expr) могут быть строками, интегралами, арифметическими выражениями или идентификаторами. Идентификаторы (ident) могут именоваться с использованием буквы алфавита в качестве первой буквы, за которой следуют символы или цифры. Ну, и так далее. Попросту говоря, я определил синтаксис языка, предоставляющий базовые арифметические возможности, небольшую систему типов и простое взаимодействие с пользователем на основе консоли.
Figure 1 Good for Nothing Language Definition
<stmt> := var <ident> = <expr>
| <ident> = <expr>
| for <ident> = <expr> to <expr> do <stmt> end
| read_int <ident>
| print <expr>
| <stmt> ; <stmt>
<expr> := <string>
| <int>
| <arith_expr>
| <ident>
<arith_expr> := <expr> <arith_op> <expr>
<arith_op> := + | - | * | /
<ident> := <char> <ident_rest>*
<ident_rest> := <char> | <digit>
<int> := <digit>+
<digit> := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<string> := " <string_elem>* "
<string_elem> := <any char other than ">
Можно заметить, что этому определению языка недостает конкретности. Я не указал, насколько большими могут быть числа (например, могут ли они быть больше 32-битного целого числа) и даже могут ли они быть отрицательными. Настоящее определение EBNF точно определило бы такие детали, но, краткости ради, я оставлю мой пример несложным.
Вот пример программы языка Good for Nothing:
var ntimes = 0;
print "How much do you love this company? (1-10) ";
read_int ntimes;
var x = 0;
for x = 0 to ntimes do
print "Developers!";
end;
print "Who said sit down?!!!!!";
Можно сравнить эту простую программу с определением языка, чтобы лучше понять, как работает грамматика. На этом определение языка завершено.
Высокоуровневая архитектура
Задачей компилятора является превращение высокоуровневых задач, созданных программистом, в задачи, которые процессор компьютера может понять и выполнить. Другими словами, он берет программу, написанную на языке Good for Nothing и преобразует ее в нечто, что может быть выполнено .NET CLR. Компилятор достигает это через серию этапов перевода, разбивая язык на имеющие значение части и выкидывая прочее. Компиляторы следуют распространенным принципам разработки программного обеспечения – слабо связанные компоненты, именуемые фазами, подключенные друг другу для выполнения этапов перевода. рис. 2 демонстрирует компоненты, выполняющие фазы компиляции: сканер, анализатор и генератор кода. В каждой фазе, язык последовательно разбивается на компоненты и эта информация о намерениях программы передается следующей фазе.
Рис. 2 Фазы компилятора.
Компиляторщики часто используют абстрактное разделение фаз на фазы предварительной обработки и конечные фазы. Первые включают в себя сканирование и анализ, тогда как вторые обычно состоят из создания кода. Задачей фазы предварительной обработки является обнаружение синтаксической структуры программы и перевод ее из текста в высокоуровневое представление в памяти, именуемое деревом абстрактного синтаксиса (Abstract Syntax Tree – AST), о котором я расскажу подробнее чуть ниже. Задачей конечных фаз является взятие AST и преобразование его в нечто, пригодное для исполнения компьютером.
Три фазы обычно разделяются на фазы предварительной обработки и конечные, поскольку сканеры и анализаторы часто соединены, тогда как генератор кода обычно тесно привязан к целевой платформе. Такая схема позволяет разработчику менять генератор года в зависимости от платформы, если язык должен быть межплатформенным.
Я сделал код для компилятора Good for Nothing доступным в сопровождающем эту статью загружаемом файле. Читатели могут проследить мое продвижение по компонентам каждой фазы и исследовать подробности реализации.
Сканер
Основной задачей сканера является разбивка текста (потока символов в исходном файле) на куски (именуемые лексемами), которые может потребить анализатор. Сканер определяет, какие лексемы отсылаются анализатору и, следовательно, может выкидывать то, что не определено синтаксисом, скажем комментарии. Что касается моего языка Good for Nothing, сканер интересуют символы (A-Z и прочие обычные), числа (0-9), символы, определяющие операции (такие как +, -, * и /), кавычки для инкапсуляции строк и точки с запятой.
Сканнер собирает в группы потоки связанных символов, формируя лексемы для анализатора. Например, поток символов " h e l l o w o r l d ! " будет сгруппирован в одну лексему: "hello world!".
Сканер Good for Nothing чрезвычайно прост, требуя лишь System.IO.TextReader при создании экземпляра. Это запускает процесс сканирования, как показано ниже:
public Scanner(TextReader input)
{
this.result = new Collections.List<object>();
this.Scan(input);
}
рис. 3 иллюстрирует метод Scan («Сканирование»), у которого имеется простой цикл while, проходящий по каждому символу в текстовом потоке и находящий узнаваемые символы, заявленные в определении языка. При каждом обнаружении узнаваемого символа или группы символом, сканер создает лексему и добавляет ее к List<object>. (В дано случае, я ввожу это как объект. Однако я мог бы создать класс Token («Лексема») или что-нибудь подобное для инкапсуляции дополнительной информации о лексеме, такой как строка и номера столбцов.)
Figure 3 The Scanner's Scan Method
private void Scan(TextReader input)
{
while (input.Peek() != -1)
{
char ch = (char)input.Peek();
// Scan individual tokens
if (char.IsWhiteSpace(ch))
{
// eat the current char and skip ahead
input.Read();
}
else if (char.IsLetter(ch) || ch == '_')
{
StringBuilder accum = new StringBuilder();
input.Read(); // skip the '"'
if (input.Peek() == -1)
{
throw new Exception("unterminated string literal");
}
while ((ch = (char)input.Peek()) != '"')
{
accum.Append(ch);
input.Read();
if (input.Peek() == -1)
{
throw new Exception("unterminated string literal");
}
}
// skip the terminating "
input.Read();
this.result.Add(accum);
}
...
}
}
Можно заметить, что когда код сталкивается с символом ", он предполагает, что этот символ инкапсулирует лексему строки, следовательно, я поглощаю строку, оборачиваю ее в экземпляр StringBuilder и добавляю к списку. После того, как сканирование создает список лексем, лексемы отправляются к классу анализатора через свойство, именуемое Tokens.
Синтаксический анализатор
Анализатор является сердцем компилятора и может существовать во множестве видов и форм. У анализатора Good for Nothing есть несколько задач: он обеспечивает соответствие исходной программы определению языка и обрабатывает ошибки в случае сбоя. Он также создает представление программного синтаксиса в памяти, которое потребляется генератором кода и, наконец, анализатор Good for Nothing решает, какие типы среды выполнения использовать.
Первое что мне нужно сделать – это взглянуть на представление программного синтаксиса в памяти, то есть AST. Затем я рассмотрю код, создающий это дерево из лексем сканера. Формат AST быстр, эффективен, прост в кодировании и может быть многократно просмотрен генератором кода. AST для компилятора Good for Nothing показан на рис. 4.
Быстрый взгляд на определение языка Good for Nothing показывает, что AST более-менее соответствует узлам определения языка из синтаксиса EBNF. Лучше всего представить себе определение языка как инкапсуляцию синтаксиса, где абстрактное древо синтаксиса фиксирует структуру этих элементов.
Существует множество доступных алгоритмов анализа и изучение их всех находится за пределами темы этой статьи. В целом, они отличаются в том, как они проходят поток лексем для создания AST. В моем компиляторе Good for Nothing, я использую нисходящий анализатор, именуемый LL (от Left-to-right, Left-most – «Слева направо, Крайний слева») . Это попросту значит, что он читает текст слева направо и конструирует AST, основываясь на следующей доступной лексеме ввода.
Конструктор для моего класса анализатора просто берет список лексем, созданный сканером:
public Parser(IList<object> tokens)
{
this.tokens = tokens;
this.index = 0;
this.result = this.ParseStmt();
if (this.index != this.tokens.Count)
throw new Exception("expected EOF");
}
Основная часть анализа выполняется методом ParseStmt, как показано на рис. 5. Он возвращает узел Stmt, который служит корневым узлом дерева и соответствует узлу верхнего уровня определения синтаксиса языка. Анализатор обходит список лексем, используя индекс в качестве текущей позиции и в то же время определяя лексемы, подчиненные узлу Stmt в синтаксисе языка (декларации переменных и назначения, циклы, read_ints и отображения). Если лексему не удается опознать, выдается исключение.
Figure 5 ParseStmt Method Identifies Tokens
private Stmt ParseStmt()
{
Stmt result;
if (this.index == this.tokens.Count)
{
throw new Exception("expected statement, got EOF");
}if (this.tokens[this.index].Equals("print"))
{
this.index++;
...
}
else if (this.tokens[this.index].Equals("var"))
{
this.index++;
...
}
else if (this.tokens[this.index].Equals("read_int"))
{
this.index++;
...
}
else if (this.tokens[this.index].Equals("for"))
{
this.index++;
...
}
else if (this.tokens[this.index] is string)
{
this.index++;
...
}
else
{
throw new Exception("parse error at token " + this.index +
": " + this.tokens[this.index]);
}
...
}
При опознании лексемы, создается узел AST и выполняется дальнейший анализ, запрошенный узлом. Ниже приведен код, необходимый для создания узла AST отображения:
// <stmt> := print <expr>
if (this.tokens[this.index].Equals("print"))
{
this.index++;
Print print = new Print();
print.Expr = this.ParseExpr();
result = print;
}
Здесь происходят два события. Лексема отображения сбрасывается посредством приращения счетчика индекса, после чего вызывается метод ParseExpr для получения узла Expr, поскольку определение языка требует, чтобы за лексемой отображения следовало выражение.
Рис. 6 приводит код ParseExpr. Он проходит по списку лексем от текущего индекса, определяя лексемы, удовлетворяющие определению выражения для языка. В данном случае, метод просто ищет строки, целые числа и переменные (созданные экземпляром сканера) и возвращает соответствующие узлы AST, представляющие эти выражения.
Figure 6 ParseExpr Performs Parsing of Expression Nodes
// <expr> := <string>
// | <int>
// | <ident>
private Expr ParseExpr()
{
...
if (this.tokens[this.index] is StringBuilder)
{
string value = ((StringBuilder)this.tokens[this.index++]).ToString();
StringLiteral stringLiteral = new StringLiteral();
stringLiteral.Value = value;
return stringLiteral;
}
else if (this.tokens[this.index] is int)
{
int intValue = (int)this.tokens[this.index++];
IntLiteral intLiteral = new IntLiteral();
intLiteral.Value = intValue;
return intLiteral;
}
else if (this.tokens[this.index] is string)
{
string ident = (string)this.tokens[this.index++];
Variable var = new Variable();
var.Ident = ident;
return var;
}
...
}
Для операторов строк, удовлетворяющих определению синтаксиса языка "<stmt> ; <stmt>", используется узел AST последовательности. Этот узел последовательности содержит два указателя на узлы stmt и формирует основу структуры дерева AST. Ниже подробно приведен код, использованные в случае с последовательностью:
if (this.index < this.tokens.Count && this.tokens[this.index] ==
Scanner.Semi)
{
this.index++;
if (this.index < this.tokens.Count &&
!this.tokens[this.index].Equals("end"))
{
Sequence sequence = new Sequence();
sequence.First = result;
sequence.Second = this.ParseStmt();
result = sequence;
}
}
Дерево AST, показанное на <Fig>рис. 7</Fig>, является плодом следующего фрагмента кода Good for Nothing:
Рис. 7 Дерево AST helloworld.gfn и трассировка на высоком уровне.
var x = "hello world!";
print x;
Ориентация на платформу .NET Framework
Прежде чем переходить к разделу, выполняющему создание кода, мне следует сперва остановиться и рассказать о моей цели. So here I will describe the compiler services that the .NET CLR provides, including the stack-based virtual machine, the type system, and the libraries used for .NET assembly creation. Я также кратко коснусь средств, необходимых для обнаружение и диагностики ошибок в выводе компилятора.
CLR – это виртуальная машина, то есть программа, имитирующая компьютерную систему. Как все компьютеры, CLR располагает набором низкоуровневых операций, которые она может выполнять, набором служб памяти и языком сборки для определения выполняемых программ. CLR использует абстрактную структуру данных на основе стеков для моделирования исполнения кода, а также язык сборки, именуемый промежуточным языком (Intermediate Language – IL), для определения операций, которые можно выполнять на стеке.
При исполнении компьютерной программы, определенной в IL, CLR просто имитирует операции, указанные для стека, перемещая и выталкивая данные, для выполнения инструкцией. Предположим, нужно сложить два числа, используя IL. Код для выполнения сложения 10 + 20 выглядит так:
ldc.i4 10
ldc.i4 20
add
Первая строка (ldc.i4 10) помещает целое число 10 на стек. Затем вторая строка (ldc.i4 20) помещает целое число 20 на стек. Третья строка (add) выталкивает два целых числа со стека, складывает их и помещает результат обратно на стек.
Имитация машины стека осуществляется путем перевода IL и семантики стека в машинный язык базового процессора, либо во время выполнения, с помощью компиляции непосредственно перед выполнением (just-in-time – JIT), либо заранее, посредством таких служб, как генератор машинных образов (Ngen).
Существует множество доступных инструкций IL для создания собственных программ – от базовой арифметики, до контроля потока, до различных соглашений о вызовах. Подробности о всех инструкциях IL можно найти в Разделе III спецификаций ассоциации European Computer Manufacturers Association (ECMA) (доступном на msdn2.microsoft.com/aa569283).
Абстрактный стек CLR выполняет операции не только на целых числах. Он обладает богатой системой типов, включая строки, целые числа, логические типы, плавающие типы, дублеры, итд. Чтобы мой язык мог безопасно работать на CLR и взаимодействовать с другими совместимыми с .NET языками, я включил часть системы типов CLR в мою собственную программу. Если конкретно, то язык Good for Nothing определяет два типа – числа и строки, для которых я устанавливаю соответствие с System.Int32 и System.String.
Компилятор Good for Nothing использует компонент библиотеки базовых классов (Base Class Library – BCL), именуемый System.Reflection.Emit для работы с созданием кода IL, а также созданием и упаковкой сборок .NET. Это низкоуровневая библиотека, предоставляющая лишь насущно необходимое в виде простых абстракций создания кода, сверх языка IL. Эта библиотека также используется в других известных API-интерфейсах BCL, включая System.Xml.XmlSerializer.
Высокоуровневые классы, необходимые для создания сборки .NET (показанные на рис. 8) в некотором роде следуют шаблонам программ-компоновщиков с API-интерфейсом компоновщика для каждой логической абстракции метаданных .NET metadata. Класс AssemblyBuilder используется для создания файла PE и устанавливает необходимые элементы метаданных сборки .NET, подобно манифесту. Класс ModuleBuilder используется для создания модулей внутри сборки. TypeBuilder используется для создания типов с связанных с ними метаданных. MethodBuilder и LocalBuilder занимаются, соотвественно, добавлением методов к типам и локальных переменных к методам. Класс ILGenerator используется для создания кода IL для методов, используя класс OpCodes, являющийся большой нумерацией, содержащей все возможные инструкции IL. Все эти классы Reflection.Emit используются в генераторе кода Good for Nothing.
Рис. 8 Библиотеки Reflection.Emit, используемые для создания сборки .NET
Средства устранения ошибок в IL
Даже самые испытанные эксперты по компиляторам делают ошибки на уровне создания кода. Самой частой ошибкой является ошибочный код IL, вызывающий дисбаланс в стеке. CLR обычно выдает исключение при обнаружении ошибочного IL (либо при загрузке сборки , либо при JITed (?) IL, в зависимости от уровня доверия сборки). Эти ошибки несложно диагностировать и исправить при помощи простого средства SDK, именуемого peverify.exe. Оно выполняет проверку IL, убеждаясь в том, что код безошибочен и безопасен для исполнения.
Для примера, ниже приведен код IL, пытающийся добавить число 10 к строке "bad":
ldc.i4 10
ldstr "bad"
add
Выполнение peverify на сборке, содержащий этот ошибочный IL приведет к следующей ошибке:
[IL]: Error: [C:\MSDNMagazine\Sample.exe : Sample::Main][offset 0x0000002][found ref 'System
.String'] Expected numeric type on the stack.
В данном примере, peverify сообщает, что инструкция сложения ожидала два числовых типа, но вместо этого обнаружила целое число и строку.
ILASM (ассемблер IL) и ILDASM (дизассемблер IL) – два средства SDK, которые можно использовать для компиляции текста IL в сборки .NET и декомпиляции сборок в IL, соответственно. ILASM позволяет быстро и просто тестировать потоки инструкций IL, которые будут основой выходящих данных компилятора. Достаточно создать код IL в текстовом редакторе и передать его ILASM. В то же время, средство ILDASM может быстро заглянуть в созданный компилятором IL, чтобы найти конкретный путь кода. Это включает IL, выдаваемый коммерческими компиляторами, такими как компилятор C#. Оно предлагает отличный способ просмотра кода IL для похожих операторов в разных языках; другими словами, код контроль потока IL, созданный для цикла C# , может быть использован другими компиляторами, имеющими подобные конструкции.
Генератор кода
Генератор кода для компилятора Good for Nothing в большой степени полагается на библиотеку Reflection.Emit для создания исполняемых сборок .NET. Я опишу и проанализирую важные части класса, оставив прочее читателям для ознакомления, когда им будет удобно.
Конструктор CodeGen, показанный на рис. 9, устанавливает инфраструктуру Reflection.Emit, которая необходима прежде чем я начну выводить код. Я начинаю с определения имени сборки и передачи его компоновщику сборки. В данном примере, я использую имя исходного файла, как имя сборки. Далее идет определение ModuleBuilder – для определения одного модуля, оно использует то же имя, что и сборка. Далее я определяю TypeBuilder на ModuleBuilder, чтобы содержать единственный тип в сборке. Типов, определенных как привилегированные компоненты определения языка Good for Nothing, не существует, но по крайней мере один тип необходим, чтобы содержать метод, выполняющийся при запуске. MethodBuilder определяет Main для содержания IL, создаваемого кодом Good for Nothing. Мне пришлось вызвать SetEntryPoint на этом MethodBuilder, чтобы он выполнялся во время запуска, при активации пользователем исполняемого файла. Я также создаю глобальный ILGenerator (il) из MethodBuilder, используя метод GetILGenerator.
Figure 9 CodeGen Constructor
Emit.ILGenerator il = null;
Collections.Dictionary<string, Emit.LocalBuilder> symbolTable;public CodeGen(Stmt stmt, string moduleName)
{
if (Path.GetFileName(moduleName) != moduleName)
{
throw new Exception("can only output into current directory!");
}AssemblyName name = new
AssemblyName(Path.GetFileNameWithoutExtension(moduleName));
Emit.AssemblyBuilder asmb =
AppDomain.CurrentDomain.DefineDynamicAssembly(name,
Emit.AssemblyBuilderAccess.Save);
Emit.ModuleBuilder modb = asmb.DefineDynamicModule(moduleName);
Emit.TypeBuilder typeBuilder = modb.DefineType("Foo");
Emit.MethodBuilder methb = typeBuilder.DefineMethod("Main",
Reflect.MethodAttributes.Static,
typeof(void),
System.Type.EmptyTypes);
// CodeGenerator
this.il = methb.GetILGenerator();
this.symbolTable = new Dictionary<string, Emit.LocalBuilder>();
// Go Compile
this.GenStmt(stmt);
il.Emit(Emit.OpCodes.Ret);
typeBuilder.CreateType();
modb.CreateGlobalFunctions();
asmb.SetEntryPoint(methb);
asmb.Save(moduleName);
this.symbolTable = null;
this.il = null;
}
После того, как инфраструктура Reflection.Emit установлена, генератор кода вызывает метод GenStmt, используемый для пошагового анализа AST. This generates the necessary IL code through the global ILGenerator. рис. 10 показывает подмножество метода GenStmt, которое при первом вызове, начинает с узла Sequence («Последовательность») и затем проводит пошаговый анализ AST, переключаясь на текущий тип узла AST.
Figure 10 Subset of GenStmt Method
private void GenStmt(Stmt stmt)
{
if (stmt is Sequence)
{
Sequence seq = (Sequence)stmt;
this.GenStmt(seq.First);
this.GenStmt(seq.Second);
}
else if (stmt is DeclareVar)
{
...
}
else if (stmt is Assign)
{
...
}
else if (stmt is Print)
{
...
}
}
Ниже приведен код, необходимый для DeclareVar (декларации переменной AST:
else if (stmt is DeclareVar)
{
// declare a local
DeclareVar declare = (DeclareVar)stmt;
this.symbolTable[declare.Ident] =
this.il.DeclareLocal(this.TypeOfExpr(declare.Expr));
// set the initial value
Assign assign = new Assign();
assign.Ident = declare.Ident;
assign.Expr = declare.Expr;
this.GenStmt(assign);
}
Первое что здесь нужно сделать, это добавить переменную к таблице символов. Таблица символов – это центральная структура данных компилятора, используемая для привязки символического идентификатора (в данном случае, имени переменной на основе строки) к его типу, расположению и масштабу внутри программы. Таблица символов Good for Nothing несложна и все декларации переменных являются локальными для метода Main. Так что я связываю символ с LocalBuilder, используя простой Dictionary<string, LocalBuilder>.
После добавления символа к таблице символов, я преобразую узел AST DeclareVar в узел Assign («Назначения»), чтобы назначить переменной выражения ее деклараций. Для создания оператора Assignment («Назначение») я пользуюсь следующим кодом:
else if (stmt is Assign)
{
Assign assign = (Assign)stmt;
this.GenExpr(assign.Expr, this.TypeOfExpr(assign.Expr));
this.Store(assign.Ident, this.TypeOfExpr(assign.Expr));
}
Выполнение этого создает код IL для загрузки выражения на стек и затем выдает IL для сохранения выражения в подходящем LocalBuilder.
Код GenExpr, показанный на рис. 11, берет узел Expr AST и выдает IL, необходимый для загрузки выражения на машину стека. StringLiteral и IntLiteral похожи по части наличия прямых инструкций IL загрузить соответствующие строки и целые числа на стек: ldstr и ldc.i4.
Figure 11 GenExpr Method
private void GenExpr(Expr expr, System.Type expectedType)
{
System.Type deliveredType;
if (expr is StringLiteral)
{
deliveredType = typeof(string);
this.il.Emit(Emit.OpCodes.Ldstr, ((StringLiteral)expr).Value);
}
else if (expr is IntLiteral)
{
deliveredType = typeof(int);
this.il.Emit(Emit.OpCodes.Ldc_I4, ((IntLiteral)expr).Value);
}
else if (expr is Variable)
{
string ident = ((Variable)expr).Ident;
deliveredType = this.TypeOfExpr(expr);
if (!this.symbolTable.ContainsKey(ident))
{
throw new Exception("undeclared variable '" + ident + "'");
}this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[ident]);
}
else
{
throw new Exception("don't know how to generate " +
expr.GetType().Name);
}if (deliveredType != expectedType)
{
if (deliveredType == typeof(int) &&
expectedType == typeof(string))
{
this.il.Emit(Emit.OpCodes.Box, typeof(int));
this.il.Emit(Emit.OpCodes.Callvirt,
typeof(object).GetMethod("ToString"));
}
else
{
throw new Exception("can't coerce a " + deliveredType.Name +
" to a " + expectedType.Name);
}
}
}
Переменные выражения просто загружают локальную переменную метода на стек, вызывая ldloc и передавая соответствующий LocalBuilder. Последний раздел кода, показанного на рис. 11 занимается преобразованием типа выражение в ожидаемый тип (что называется принуждением типа). Например, типу может требоваться преобразование в вызове метода отображения, где целое число необходимо преобразовать в строку, чтобы отображение было успешным.
рис. 12 демонстрирует, как переменным назначаются выражения в методе Store. Имя находится в таблице символов и соответствующий LocalBuilder затем передается инструкции stloc IL. Это просто выталкивает текущее выражение со стека и назначает его локальной переменной.
Figure 12 Store Expressions to a Variable
private void Store(string name, Type type)
{
if (this.symbolTable.ContainsKey(name))
{
Emit.LocalBuilder locb = this.symbolTable[name];
if (locb.LocalType == type)
{
this.il.Emit(Emit.OpCodes.Stloc, this.symbolTable[name]);
}
else
{
throw new Exception("'" + name + "' is of type " +
locb.LocalType.Name + " but attempted to store value of type " +
type.Name);
}
}
else
{
throw new Exception("undeclared variable '" + name + "'");
}
}
Код, используемый для создания IL для узла отображения AST, интересен тем, что вызывает метол BCL. Выражение создается на стеке и инструкция вызова IL используется, чтобы вызвать метод System.Console.WriteLine. Reflection («Отражение») используется для получения дескриптора метода WriteLine, необходимой для передачи инструкции вызова:
else if (stmt is Print)
{
this.GenExpr(((Print)stmt).Expr, typeof(string));
this.il.Emit(Emit.OpCodes.Call,
typeof(System.Console).GetMethod("WriteLine",
new Type[] { typeof(string) }));
}
При выполнении вызова метода, аргументы метода выталкиваются из стека по принципу «последний на входе, первый внутри». Другими словами, первый аргумент метода становится верхним элементом стека, второй аргумент – следующим элементом и так далее.
Наиболее сложным кодом является здесь код, создающий IL для моих циклов Good for Nothing (см. рис. 13). Он довольно похож на способы создания подобного кода коммерческими компиляторами. Однако, лучшим способом уяснить код цикла, является взгляд на создаваемый IL, который показан на рис. 14.
Figure 14 For Loop IL Code
// for x = 0
IL_0006: ldc.i4 0x0
IL_000b: stloc.0// jump to the test
IL_000c: br IL_0023// execute the loop body
IL_0011: ...// increment the x variable by 1
IL_001b: ldloc.0
IL_001c: ldc.i4 0x1
IL_0021: add
IL_0022: stloc.0// TEST
// load x, load 100, branch if
// x is less than 100
IL_0023: ldloc.0
IL_0024: ldc.i4 0x64
IL_0029: blt IL_0011
Figure 13 For Loop Code
else if (stmt is ForLoop)
{
// example:
// var x = 0;
// for x = 0 to 100 do
// print "hello";
// end;
// x = 0
ForLoop forLoop = (ForLoop)stmt;
Assign assign = new Assign();
assign.Ident = forLoop.Ident;
assign.Expr = forLoop.From;
this.GenStmt(assign);
// jump to the test
Emit.Label test = this.il.DefineLabel();
this.il.Emit(Emit.OpCodes.Br, test);
// statements in the body of the for loop
Emit.Label body = this.il.DefineLabel();
this.il.MarkLabel(body);
this.GenStmt(forLoop.Body);
// to (increment the value of x)
this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[forLoop.Ident]);
this.il.Emit(Emit.OpCodes.Ldc_I4, 1);
this.il.Emit(Emit.OpCodes.Add);
this.Store(forLoop.Ident, typeof(int));
// **test** does x equal 100? (do the test)
this.il.MarkLabel(test);
this.il.Emit(Emit.OpCodes.Ldloc, this.symbolTable[forLoop.Ident]);
this.GenExpr(forLoop.To, typeof(int));
this.il.Emit(Emit.OpCodes.Blt, body);
}
Код IL начинается с первоначального назначения счетчика цикла и немедленно переходит к тестированию цикла, используя инструкцию IL br (ответвление). Метки, подобные перечисленным слева от кода IL используются, чтобы дать среде выполнения знать, где ответвлять следующую инструкцию. Тестовый код проверяет, меньше ли переменная x, чем 100, используя инструкцию blt (ответвление если меньше чем). Если это так, исполняется тело цикла, переменная x увеличивается и тест запускается снова.
Код цикла на рис. 13 создает код необходимый для выполнения операций назначения и увеличения на переменной счетчика. Он также использует метод MarkLabel на ILGenerator для создания меток, в которые могут ответвляться ветви инструкций.
Подводя итоги... почти
Я показал процесс создания простого компилятора .NET в базе кода и часть лежащей в его основе теории. Эта статья должна дать читателям основу для входа в загадочный мир создания компиляторов. Хотя ценную информацию о нем можно найти в сети, в некоторые книги также стоит заглянуть. Я бы рекомендовал приобрести: «Compiling for the .NET Common Language Runtime» Джона Гауфа (John Gough) (изд-во Prentice Hall, 2001 г.), «Inside Microsoft IL Assembler» Сержа Лидина (Serge Lidin) (изд-во Microsoft Press®, 2002 г.), «Programming Language Pragmatics» Майкла Л. Скотта (Michael L. Scott) (изд-во Morgan Kaufmann, 2000 г.) и «Compilers: Principles, Techniques, and Tools» Альфреда В. Охо (Alfred V. Oho), Моники С Лэм (Monica S. Lam), Рави Сефи (Ravi Sethi) и Джеффри Ульмана (Jeffrey Ullman) (изд-во Addison Wesley, 2006 г.).
Они весьма неплохо охватывают ядро знаний, необходимых для написания собственного языкового компилятора, однако, мой собственный рассказ еще не закончен. Мне бы хотелось рассмотреть более серьезные темы для того, чтобы еще более расширить спектр ваших возможностей.
Динамический вызов методов
Вызовы методов являются краеугольным камнем любого языка программирования – существует целый их спектр. Более современные языки, такие как Python, задерживают привязку метода и его вызов до самого последнего момента – это называется динамическим вызовом. Все популярные динамические языки, такие как Ruby, JavaScript, Lua и даже Visual Basic, следуют этому шаблону. Чтобы компилятор выдал код для выполнения вызова метода, компилятор должен считать имя метода символом, передавая его библиотеке выполнения, которая проведет операции привязки и вызова, в соответствии с семантикой языка.
Предположим, я отключу Option Strict в компиляторе Visual Basic 8.0. Вызовы методов начнут происходить с поздним (динамическим) связыванием, а среда выполнения Visual Basic будет выполнять привязку и вызов во время выполнения.
Вместо компилятора Visual Basic, выдающего инструкцию вызова IL, обращенного к методу Method1, он выдает инструкцию вызова к методу среды выполнения Visual Basic, именуемому CompilerServices.NewLateBinding.LateCall. Делая это, он передает объект (obj) и символическое имя метода (Method1), вместе с всеми аргументами метода. Метод Visual Basic LateCall затем ищет метод Method1на объекте используя Reflection («Отражение») и, если он найден, выполняет вызов метода на основе Reflection:
Option Strict Off
Dim obj
obj.Method1()IL_0001: ldloc.0
IL_0003: ldstr "Method1"
...
IL_0012: call object CompilerServices.NewLateBinding::LateCall(object, ... , string, ...)
Использование LCG для выполнения динамического связывания
Вызов метода на основе Reflection может быть весьма медленным (см. мою статью "Reflection: Dodge Common Performance Pitfalls to Craft Speedy Applications" («Reflection: как избежать обычных провалов в области производительности для создания быстрых приложений» на msdn.microsoft.com/msdnmag/issues/05/07/Reflection). Как связывание метода, так и вызов метода на много порядков медленнее, чем простая инструкция вызова IL. CLR в .NET Framework 2.0 включает функцию, именуемую созданием облегченного кода (Lightweight Code Generation – LCG), которую можно использовать для динамического создания кода на лету с целью связи узла вызова с методом, посредством более быстрой инструкции вызова IL. Это значительно ускоряет вызов методов. Поиск метода на объекте по-прежнему необходим, но после того, как он найден, можно создать мостовой DynamicMethod и кэшировать его для каждого повторяющегося вызова.
Рис. 15 показывает очень простую версию динамического связывателя, выполняющего динамическое создание кода для мостового метода. Сперва он просматривает кэш и проверяет, был ли вызов узла замечен ранее. Если вызов узла выполняется в первый раз, он создает DynamicMethod, возвращающий объект и принимающий массив объектов как аргумент. Аргумент массива объекта содержит объект экземпляра и аргументы, которые будут использованы для финального вызова метода. Код IL создается для распаковки массива объекта на стек, начиная объекта экземпляра и продолжая аргументами. Затем выдается инструкция вызова и результат вызова возвращается вызываемому.
Вызов мостового метода LCG выполняется через делегата, то есть очень быстро. Я просто помещаю аргументы мостового метода в массив объектов и выполняю вызов. Когда это происходит в первый раз, компилятор JIT компилирует динамический метод и исполняет IL, который, в свою очередь, вызывает финальный метод.
По сути этот код является тем, что создал бы статический компилятор с ранней привязкой. Он сперва помещает на стек объект экземпляра, затем аргументы и затем вызывает метод, используя инструкцию вызова. Это хитрый способ задержки данной семантики до последнего момента, что удовлетворяет динамическую семантику вызова, присутствующую в большинстве динамических языков.
Среда выполнения динамического языка
Если вы серьезно намерены внедрить динамический язык в CLR, необходимо проверить среду выполнения динамического языка (DLR), о которой сообщал отдел CLR в конце апреля. Он включает в себя средства и библиотеки, необходимые для создания отлично функционирующих динамических языков, которые работают как с .NET Framework, так и с экосистемой других языков, совместимых с .NET. Эти библиотеки содержат все, что необходимо специалисту для создания динамического языка, в том числе высокопроизводительную реализацию динамического языка (моментальный вызов методов, взаимодействие системы типо в и т.д.), динамическую систему типов, общий AST, поддержку REPL и многое другое.
Подробное рассмотрение DLR находится далеко за пределами темы этой статьи, но я рекомендую изучить ее самостоятельно, чтобы познакомиться со службами, предоставляемыми ею для динамических языков. Дополнительные сведенья о DLR можно найти в блоге Джима Хаганина (Jim Hugunin) по адресу (blogs.msdn.com/hugunin).
Джоэл Побар – бывший руководитель программы в группе разработчиков CLR корпорации Майкрософт. Сейчас он прохлаждается на Золотом Берегу в Австралии, копаясь в компиляторах, языках и прочих занятных вещах.