Разрабатываем компилятор для учебного языка Cool на языке C# под .NET (Часть 1)

Введение


Здравствуй, уважаемый хабраюзер.Я хотел бы тебе представить материал о практическом создании компилятора, который будет транслировать код, написанный на языке Cool, в код виртуальной машины CIL (Common Intermediate Language) под платформу .NET.Данный материал я решил разбить на две части из-за лени все сразу это описывать

В первой части будет описан процесс написания грамматики с учетом приоритетов операторов в среде ANTLR, а также генерации лексера и парсера под язык C#. Также в ней будут рассмотрены подводные камни, которые встретились у меня на пути. Таким образом я постараюсь хоть кому-нибудь сэкономить время (может быть для себя в будущем).

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

Предупреждение: перед разработкой данного компилятора я практически не изучал никакой тематической литературы. Всё обошлось чтением нескольких интересующих меня статей, просмотром видеоуроков по ANTLR на официально сайте и разговорами с «шарящими» одногруппниками. Так что разработанное ПО является УГ далеко не идеальным.

Чтобы читатель лучше понимал меня, я дам в начале сначала некоторые определения (из Википедии):
  • Токен — последовательности символов в лексическом анализе в информатике, соответствующий лексеме.
  • Лексер — модуль для аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в слова).
  • Парсер — модуль для сопоставления линейной последовательности лексем (слов, токенов) языка с его формальной грамматикой. Результатом является дерево разбора или синтаксическое дерево.
На хабрахабре, да и не только, есть много статей, подробно объясняющих как написать грамматику для математических выражений и языков, так что подробно останавливаться на настройке среды я не буду. Также я не буду углубляться в теоретические вопросы конструирования компиляторов, так как на эту тему тоже есть ряд неплохих статей, например данный цикл.

Итак, для разработки компилятора были использованы следующие программы и библиотеки:
  1. ANTLRWorks — IDE для написания грамматик и генерации кода лексеров и парсеров под различные языки (C, C#, Java, JavaScript, Objective-C, Perl, Python, Ruby и др.). Основана на LL(*) парсинге.
  2. ANTLR C# runtime distribution (Antlr3.Runtime.dll) используется в сгенерированном лексере и парсере.
  3. Visual Studio 2010 В следующей статье будет рассмотрен компонент под WPF, расширенный текстовый редактор для подсветки синтаксиса и автодополнения кода AvalonEdit).
  4. Java Runtime Environment (так как ANTLRWorks написана на Java).
  5. IL Disassembler будет использоваться во второй части для того, чтобы понимать, как компилятор, например языка C#, генерирует CIL код и как он должен выглядеть.

Описание языка Cool


Cool — Classroom Object-Oriented Language является, как мы видим из названия, учебным никому не нужным языком программирования, включающий классы и объекты. Cool является функциональным строготипизированным языком, т.е. проверка типов происходит статически на этапе компиляции. Программа по сути является набором классов. Классы включают в себя набор полей и функций (тут они называются feature).
Все поля являются видимыми внутри базового и производного классов. Все функции являются видимыми отовсюду (public).
Данный язык построен на выражениях (expression). Все функции в качестве аргументов могут принимать выражения и телами всех функций являются выражения, который возвращают какой-либо результат. Даже такие функции, как вывод строки, возвращают результат, а именно экземпляр класса, из которого они вызваны.
Cool содержит также и статические классы String, Int, Bool, от которых нельзя наследоваться и которые не могут принимать значения null (здесь это называется void). Объекты данных классов передаются по значению, а не по ссылке.
Ключевые слова данного языка: class, else, false, fi, if, in, inherits, isvoid, let, loop, pool, then, while,case, esac, new, of, not, true
Хочу обратить внимание, что некоторые операторы заканчивается не фигурной скобкой (как в С-подобных) или словом end; (как в мертвом паскале), а названием названием этого же оператора в обратном порядке (if -> fi, loop -> pool, case -> esac).
Как вы думаете, если каждый оператор возвращает какой-то результат, то что же должен возвращать if? Ведь он может возвратить вариант из двух альтернатив. Правильный ответ: наиболее близкий общий предок (в учебнике написано про это как-то сложно, там еще специальный оператор используется). Привожу для наглядности картинку:

Рисунок 1.

Здесь у классов A и B наиболее близким общим предком является класс D.

Оператор case подобен оператору if, примененному несколько раз.

В конструкции while всегда возвращается void (если конечно цикл не зацикливается).

Такая конструкция { <expr1>;… <exprn>; } возвращает объект выражения exprn, т.е. последнего выражения.

Функции здесь могут вызываться не только у класса и его предка (виртуальные функции), но и вообще у любых предков данного класса. Это можно осуществить, использовав оператор '@'. В качестве примера рассмотрим иерархию классов на рисунке 1. Пусть класс E имеет функцию func(), все остальные потомки переопределяют ее по своему. Тогда, если мы имеет экземпляр объекта A и хотим вызывать функцию func из класса D, нужно использовать следующий синтаксис:
result <- (new A)@D.func()

Ключевое слово SELF_TYPE используется как синоним класса, в котором описывается определенная функция. Идентификатор self же является указатель на текущий класс (т.е. this в других языка).

Локальных переменные вводятся в языке Cool с помощью оператора let и они могут использоваться только в рамках данного блока let.

void — аналог null, признак того, что объект не создан.

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

Написание грамматики языка Cool в ANTLRWorks


Итак, исходная грамматика задана в следующей форме:

program ::= [[class; ]]+
class ::= class TYPE [inherits TYPE] { [[feature; ]]*}
feature ::= ID( [ formal [[, formal]]*] ) : TYPE { expr } | ID : TYPE [ <- expr ]
formal ::= ID : TYPE
expr ::=
ID <- expr
| expr[@TYPE].ID( [ expr [[, expr]]*] )
| ID( [ expr [[, expr]]*] )
| if expr then expr else expr fi
| while expr loop expr pool
| { [[expr; ]] +}
| let ID : TYPE [ <- expr ] [[, ID : TYPE [ <- expr ]]]* in expr
| case expr of [[ID : TYPE => expr; ]]+ esac
| new TYPE
| isvoid expr
| expr + expr
| expr ? expr
| expr ? expr
| expr / expr
| ~expr
| expr < expr
| expr <= expr
| expr = expr
| not expr
| (expr)
| ID
| integer
| string
| true
| false


Обозначения:[[]]* — итерация; [[]]+ — положительная итерация;Итак, что нужно сделать, увидев такую грамматику? Забыть навсегда про нее и про компиляторы. Кому нужен еще один недоязык?? Итак, если данную грамматику сразу переписать в ANTLR и сгенерировать код лексера и парсера, то ничего хорошего не выйдет из-за следующих причин:
  • Существование левой рекурсии. Конечно, ANTLRWorks, основанная на методе рекурсивного спуска, это сразу определит и выдаст ошибку такого рода:[fatal] rule compilation_unit has non-LL(*) decision due to recursive rule invocations reachable from alts… Resolve by left-factoring or using syntactic predicates or using backtrack=true option… И, конечно же, в ANTLR есть опция backtrack=true, которая позволяет преодолеть данное ограничение. Но применив ее, придется смириться с еще одним узлом в сгенерированном КА для выражения с левой рекурсией. Так что все-таки хорошо бы от нее избавиться. К тому же, как видно из этой статьи, данная опция замедляет работу парсера и автор рекомендует по возможности отказываться от нее.
  • Но главное, что в этой форме грамматики не учтен приоритет операторов. Если левая рекурсия влияет только на эффективность парсера, то игнорирование данной проблемы приведет к неправильной генерации кода уже потом (например 2 + 2 * 2 будет равно 8, а не 6)
Читаем руководство дальше. А дальше как раз и написано про приоритеты операций. Они принимают следующий вид (вверху — наивысший, внизу — наинизший приоритеты).
  • .
  • @
  • ~
  • isvoid
  • * /
  • + -
  • <= < =
  • not
  • <-
Итак, нужно построить нашу грамматику с учетом этих операций. Для этого придерживаемся такого правила построения:Для каждого оператора более низкого приоритета создаем новое правило, которое будет в правой части содержать оператор данного приоритета и нетерминал для оператора более высокого приоритета.Знаю, что звучит сумбурно, поэтому привожу данное построение для нашей исходной грамматики:
expr:
  (ID ASSIGN^)* not;
not:
  (NOT^)* relation;
relation:
  addition ((LE^ | LT^ | GE^ | GT^ | EQUAL^) addition)*;
addition:
  multiplication ((PLUS^ | MINUS^) multiplication)*;
multiplication:
  isvoid ((MULT^ | DIV^) isvoid)*;
isvoid:
  (ISVOID^)* neg;
neg:
  (NEG^)* dot;
dot:
  term ((ATSIGN typeName)? DOT ID LPAREN invokeExprs? RPAREN)? ->
  ^(Term term ID? typeName? invokeExprs?);

Терм в данном случае включает в себя все оставшиеся выражения, которые не были рассмотрены, т.е. выражения с одинаковым приоритетом.

Комментарии в языке по сути являются последовательностью символов, которую нужно проигнорировать при лексическом разборе. Для этого в ANTLR используется конструкция
{$channel = Hidden;};
, написанная справа от каждого правила, описывающего комментарии. Например:
COMMENT : '--' .* ('\n'|'\r') {$channel = Hidden;};


Операторы ANTLR


Далее я опишу используемые операторы ANTLR:
  1. ! — нужен для того, чтобы лишние токены языка не мешали при разборе. Например, скобки и другие операторы, которые нужны только для парсера (например те же окончания синтаксических конструкций fi, esac). Данные оператор нужен для того, чтобы строилось именно синтаксическое дерево из потока токенов, а не дерева разбора).
  2. -> — нужен для того, чтобы преобразовывать последовательность токенов, стоящих в левой части, в последовательность токенов, стоящих в правой части, которую было бы удобно обрабатывать при генерации кода.Вместе с этим оператором используется также и оператор ^.
  3. ^ используется для того, чтобы в генерируемом синтаксическом дереве создавался новый узел из токена, помеченного этим оператором, и его потомков. Существует две формы у этого оператора:
    • Постфиксная. Например для такого правила:
      relation: addition ((LE^ | LT^ | GE^ | GT^ | EQUAL^) addition)*;
      в синтаксическое дерево вставится узел с одним из операторов, указанных в скобках, и детьми addition, который слева от оператора и addition, который справа от оператора.
    • Префиксная. Например для такого правила:
      CLASS typeName (INHERITS typeName)? LCURLY featureList RCURLY -> ^(Class typeName featureList typeName?)
      в синтаксическое дерево вставится узел-родитель Class с потомками typeName featureList typeName?

Все остальные используемые операторы ANTLR в комментариях не нуждаются (для человека, изучавшего дискретную математику), а если и нуждаются, то в небольших:
  1. * — Итерация.
  2. + — Положительная итерация.
  3. ? — Левостоящий токен или группа токенов может как присутствовать, так и отсутствовать.
Хочу отметить, что при использовании операторов '->' и '^', возникает необходимость вводить новые токены. Это делается в соответствующем разделе tokens { }.Кстати, я сторонник того, чтобы в файле .g было минимум кода, предназначенного для конкретного языка лексера и парсера (в нашем случае для C#). Тем не менее такой код все же пришлось использовать для токена STRING:

STRING: '"'
{ StringBuilder b = new StringBuilder(); }
( '"' '"' { b.Append('"');}
| c=~('"'|'\r'|'\n') { b.Append((char)c);}
)*
'"'
{ Text = b.ToString(); }
;


Здесь используется StringBuilder для того, чтобы обработка строк была эффективной.В принципе, для оптимизации лексера допустимы и другие вкрапления такого кода, но не для всех правил.Для того, чтобы в C# коде лексера и парсера указать пространства имен (например System.Text для StringBuilder), используются следующие конструкции (здесь также отключаются некоторые «ненужные» предупреждения):

@lexer::header {#pragma warning disable 3021
using System;
using System.Text;
}

@parser::header {#pragma warning disable 3021
using System.Text;}


После того, как мы составили грамматику в ANTLRWorks, нужно сгенерировать C# код лексера и парсера (спасибо, кэп).

ANTLRWorks с заданными настройками генерирует 3 файла:
  • CoolGrammar.tokens
  • CoolGrammarLexer.cs
  • CoolGrammarParser.cs

Использование сгенерированного лексера в C# коде


Получение списка всех токенов в сгенерированном C# коде выглядит не очень тривиально (хоть это и не всегда нужно):
var stream = new ANTLRStringStream(Source); // Source - исходный код.
lexer = new CoolGrammarLexer(stream, new RecognizerSharedState() { errorRecovery = true });
IToken token;
token = lexer.NextToken();
 
while (token.Type != CoolGrammarLexer.EOF)
{
  // Здесь обрабатываем каждый токен.
  // Имя токена: CoolTokens.Dictionary[token.Type] (Например для '(' это LPAREN,
  //  используется дополнительный заранее подготовленный словарь, сопоставляющий имя токена и его значение)
  // Текст токена: token.Text (Например для '(' это просто "(")
  // Номер линии токена в коде: token.Line
  // Позиция токена в коде от начала строки: token.Column
  token = lexer.NextToken(); // Читаем следующий токен, то тех пор, пока не дойдем до конца файла.
}
 
// Далее перегружаем поток токенов и устанавливаем позицию в коде в 0,
// чтобы использовать этот же поток токенов потом (читай в парсере).
lexer.Reset();

CoolTokens.Dictionary должен генерироваться следующим образом:
var Lines = File.ReadAllLines(fileName);
Dictionary = new Dictionary<int, string>(Lines.Length);
foreach (var line in Lines)
{
  var parts = line.Split('=');
  if (!Dictionary.ContainsKey(int.Parse(parts[1])))
    Dictionary.Add(int.Parse(parts[1]), parts[0]);
}
fileName — Путь к файлу CoolCompiler.tokens

Использование сгенерированного парсера в C# коде


var tokenStream = new CommonTokenStream(lexer); // как получить lexer, было описано ранее. 
parser = new CoolGrammarParser(tokenStream);
Tree = parser.program(); // Самый верхний узел, отвечающий за аксиому грамматики (т.е. program в нашем случае).
Для обхода же синтаксического дерева используются следующие свойства и методы интерфейса IList:
  • treeNode.ChildCount — количество детей у узла treeNode
  • treeNode.GetChild(i) — получение ребенка у узла treeNode под номером i
  • treeNode.Type — токен данного узла. Имеет тип int и должен сравниваться с константами, объявленными в классе лексера. Например:treeNode.Type == CoolGrammarLexer.EQUAL (является ли данный токен знаком '=').Хочу обратить внимание, что при обходе дерева нужно использовать именно свойство Type, а не Text, поскольку сранивание чисел быстрее, чем сравнивание строк, к тому же вероятность ошибки уменьшается, поскольку все константы генерируются автоматически.
  • treeNode.Line — номер линии токена в коде
  • treeNode.CharPositionInLine — позиция токена в коде от начала строки
Также я хотел обратить особое внимание на то, что при генерации кода из грамматики в C#, необходимо ставить модификатор public перед аксиомой грамматики (в данном случае перед program), чтобы можно было ее потом вызывать из кода (а иначе она будет private)

Заключение


В этой статье было рассказано, как описать грамматику в среде ANTLRWorks, которая затем используется для генерации кода лексеров и парсеров на языке C#, а также как использовать лексер и парсер. В следующей статье будет рассказано про обработку семантики языка (т.е. проверке типов, обработке семантических ошибок), как обходить каждый узел синтаксического дерева и генерировать CIL код для соответствующей синтаксической конструкции с объяснением CIL инструкций, объяснением работы стека виртуальной машины и использование встроенной в .NET библиотеки System.Reflection.Emit для облегчении генерации кода. Разумеется, я опишу и подводные камни, которые встретились у меня на пути (В частности, создание иерархии классов с помощью System.Reflection.Emit). Также там будет описано, как сделать красивые обои красивый и современный интерфейс! Впрочем, о том, что написано в заключении, уже частично написано во вступлении.

Напоследок я бы хотел задать один вопрос хабрасообществу, ответ на который мне найти не удалось:

Для C# лексера у меня всегда генерируется такой код для исключения NoViableAltException, причем этот throw невозможно никак перехватить:

catch (NoViableAltException nvae) {
  DebugRecognitionException(nvae);
  throw;
}
Как мне написать файл грамматики, чтобы в этой строчке не просто стояло throw, а вызывалось например мое исключение или вообще лексер продолжал работу? А то приходится при каждой генерации C# кода исправлять эту строчку.Примечание: манипуляции с @rulecatch в ANTLR ни к чему не привели.

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

Рекомендуемая к прочтению литература

  • Definite ANTLR Reference, Terence Parr, 2007.
  • Компиляторы. Принципы, технологии и инструментарий, 2008, Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман
Мануал по языку Cool, файл его грамматики с расширением .g, среда ANTLRWorks

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 14

    +1
    14 голосов, 23 человека добавили в избранное и ни одного комментария. Думаю пора создавать отдельный блок, с названием Yet Another Compiler.
      +1
      Или хотя бы перенести этот пост в «Компиляторы».
      –1
      > Оператор case подобен оператору if, примененному несколько раз.В Cool это
        0
        Сорри, рано отправилось. В Cool case не так работает. Это скорее похоже на «as» в C#. case проверяет можно ли привести объект (результат выражения) к типу и если да, то выполняет выражение после стрелки.
          0
          Я не до конца разъяснил: результат в операторе Case получается как если бы мы несколько раз применили поиск «наиболее общего близкого предка» поочередно к выражениям expr1,…, exprn, которые справа.
          А про «as» у вас верно написано.
            0
            Либо я не так понял, либо нет.
            case expr of x1: T1 => expr1; x2: T2 => expr2;… esac
            работает так: вычисляем expr (запоминаем результат), запоминаем его динамический тип, скажем T. Если T1 предок T (или равен T), то биндим результат expr в x1 и вычисляем expr1, иначе повторяем это T2/expr2/x2,… и т.д.
            Это что-то вроде:
            var x = expr;
            if(x is T1) { x1 = x; expr1; }
            else if (x is T2) { x2 = x; expr2; }
              0
              Смотрите: оператор case всегда должен возвращать статический тип, как и остальные операторы. Этот тип определяется на этапе компиляции по выражениям expr1...exprn.

              А у вас тоже почти все верно написано: в Case вводятся как бы локальные переменные x1,…, xn с соответствующими типами, которые затем могут использоваться в выражениях expr1,…, exprn.
                0
                Так, я понял в чем наша проблема :) Мы говорим о разных вещах.
                Я просто по той (в первом моем коменте) подумал что речь о case как if не с точки зрения типизации, а в смысле рантайма. Просто до этого вы нигде не описали как case работает (ведь работает он не так как в других языках case/switch) и я подумал что речь именно про это. Вы же писали про типизацию.
                Тогда да, все верно.
                  0
                  Кстати, ваше замечание про оператор Case было прямо в точку.
                  Именно этот оператор не реализован у меня в генерации кода, поскольку это оказалось слишком ресурсозатратно для меня ;) (Этот проект вообще идет в качестве 4 лабораторных по курсу «Конструирование компиляторов»).

                  Теперь я подумаю, стоит ли для него сделать генерацию или нет.
            0
            case проверяет можно ли привести объект (результат выражения) к типу и если да, то выполняет выражение после стрелки.

            Как в Scala чтоли?
          0
          Советую посмотреть на Nemerle.Peg — не видел лучшего средства для создания парсеров под .net. У самого проект, который могу поддерживать только из-за того, что в свое время выбрал peg в качестве инструмента для создания парсера.

          Из особенностой можно отметить отсутствие деления на лексер и парсер, а так же то, что писать парсер приходиться на Nemerle.
            0
            Думаю вам будет интересно посмотреть на Peggy пакет в Haskell, так как он на Template Haskell.

            Как-то для решения простенькой задачки из ЖЖ Darkus'а воспользовался:
            {-# Language TemplateHaskell, QuasiQuotes, FlexibleContexts #-}

            module PeggyTest (
                test
                ) where

            import Text.Peggy

            import Data.Word

            [peggy|

            file :: [(Word32, Word32)] = ranges !.

            ranges :: [(Word32, Word32)]
                = ips* { $1 }

            ips :: (Word32, Word32)
                = ip ',' ip { ($1, $2) }

            ip :: Word32
                = byte "." byte "." byte "." byte { $1 * 256 * 256 * 256 + $2 * 256 * 256 + $3 * 256 + $4 }

            byte ::: Word32
                = [0] { 0 }
                / [1-9] [0-9]* { read ($1 : $2) }

            |]

            test :: IO ()
            test = print $ parseString file "test" "0.0.0.0,255.255.255.255 192.168.0.3,192.168.1.13"

              0
              Ну и какие есть аргументы, кроме того, что он вам больше всего нравится?

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

              Вы наверное хотели сказать, код, который использует парсер, нужно писать на Nemerle? Потому что парсер писать вообще не надо — для этого и используются генераторы.

              Судя по этому и этому сравнениям, единственным адекватным конкурентом для ANTLR является Gold Parser. Он основан на LALR синтезе.

              Если сравнивать его с ANTLR, то основными преимуществами являются:
              • 1. Скорость работы.
              • 2. Допустимость левой рекурсии.
              • 3. Поддержка большего количества языков.
              • 4. Более красивый интерфейс (нет мелких шрифтов, как в ANTLR под Windows).

              А недостатки следующие:
              • 1. Сложновоспринимаемый человеком код лексера и парсера.
              • 2. Необходимость приведения грамматики к форме Бэкуса-Наура.
              3. Работает только под Windows (ANTLR на Java, а значит кроссплатформенная).

                +1
                Я Nemerle.PEG пользовался не очень много, но могу прокомментировать.

                Код, который использует парсер можно писать на любом .NET совместимом языке. Так, как Nemerle.PEG — это макрос, то он во время компиляции раскрывается в парсер, который можно использовать из другой сборки.

                Из преимуществ могу отметить то, что во время написания грамматики компилятор сразу подчёркивает некорректные места и выдаёт ошибку. Причём эта ошибка не в сгенерированном коде, а именно в грамматике, поэтому понять где ошибся очень легко.

                Сгенерированный парсер реально быстр: «Производительность парсера C# с построением AST колеблется между 3 и 4 МБ/c. Для YAML это число видимо будет выше в несколько раз.» © Hardcase
                Можно поискать на rsdn ветки по производительности, там народ вроде бы мерил.

                Я думаю, shai_xylyd сможет более подробно описать остальные преимущества. Я на PegParsere только один проект написал. Конвертер из CSS в SASS cо свёрткой и прочим. bit.ly/xSVDGE

            Only users with full accounts can post comments. Log in, please.