Компилятор языка программирования MiniJava

в 19:16, , рубрики: .net, antlr, компилятор, Компиляторы, метки: , , ,

Как в сравнительно короткие сроки написать компилятор какого-либо языка программирования. Для этого следует воспользоваться средствами разработки, автоматизирующие процесс. Я хотел бы рассказать о том, как я писал компилятор языка программирования MiniJava под платформу .NET Framework.

Весь процесс написания компилятора в целом отображён на следующем изображении. На вход подаётся файл с исходным кодом на языке программирования MiniJava. Выходом является PE-файл для выполнения средой CLR.

Компилятор языка программирования MiniJava

Далее я хотел бы сконцентрироваться на практической части описания.

Язык программирования MiniJava

MiniJava является подмножеством языка программирования Java. Не допускается использование перегрузок, печать на консоль осуществляется только целых чисел с помощью вызова метода System.out.println(...); выражение e.length применяется только к массивам int[].
Описание грамматики в форме Бекуса-Наура (взято с сайта проекта языка http://www.cambridge.org/us/features/052182060X/):

Goal ::= MainClass ( ClassDeclaration )* <EOF>
MainClass ::= "class" Identifier "{" "public" "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" Statement "}" "}"
ClassDeclaration ::= "class" Identifier ( "extends" Identifier )? "{" ( VarDeclaration )* ( MethodDeclaration )* "}"
VarDeclaration ::= Type Identifier ";"
MethodDeclaration ::= "public" Type Identifier "(" ( Type Identifier ( "," Type Identifier )* )? ")" "{" ( VarDeclaration )* ( Statement )* "return" Expression ";" "}"
Type ::= "int" "[" "]"
	| "boolean"
	| "int"
	| Identifier
Statement ::= "{" ( Statement )* "}"
	| "if" "(" Expression ")" Statement "else" Statement
	| "while" "(" Expression ")" Statement
	| "System.out.println" "(" Expression ")" ";"
	| Identifier "=" Expression ";"
	| Identifier "[" Expression "]" "=" Expression ";"
Expression ::= Expression ( "&&" | "<" | "+" | "-" | "*" ) Expression
	| Expression "[" Expression "]"
	| Expression "." "length"
	| Expression "." Identifier "(" ( Expression ( "," Expression )* )? ")"
	| <INTEGER_LITERAL>
	| "true"
	| "false"
	| Identifier
	| "this"
	| "new" "int" "[" Expression "]"
	| "new" Identifier "(" ")"
	| "!" Expression
	| "(" Expression ")"
Identifier ::= <IDENTIFIER>

Здесь грамматика представлена правилами вывода нетерминалов в цепочки языка.
Терминал – это конечный символ грамматики. Нетерминал – это символ грамматики, для которого найдётся правило вывода, переводящее его в цепочку из комбинаций терминалов и/или нетерминалов, т.е. α→β, где α∈V,β∈(N∪V)*. N – алфавит терминалов, V – алфавит нетерминалов.
Все терминалы в описании грамматики обозначены последовательностью символов в двойных кавычках, нетерминалы – последовательностью символов, а также в угловых кавычках. Аксиома грамматики – нетерминал Goal.
Рассмотрим процесс написания компилятора (до момента генерации IL-кода) на примере программы factorial.java, вычисляющей факториал, взятой с сайта проекта MiniJava:

class Factorial{
		public static void main(String[] a){
		System.out.println(new Fac().ComputeFac(10));
    }
}

class Fac {

    public int ComputeFac(int num){
		int num_aux ;
		if (num < 1)
			num_aux = 1 ;
		else 
			num_aux = num * (this.ComputeFac(num-1)) ;
		return num_aux ;
    }

}

Лексический и синтаксический анализ

Эти две фазы написания компилятора я объединил вместе, поскольку выполнены с использованием генератора компиляторов. Сейчас существует достаточное количество генераторов компиляторов, таких как ANTLR, GPPG, Coco/R, GOLD Parsing System и множество других.
Я использовал ANTLR, поскольку он удобен для написания грамматики, имеет графическую оболочку с текстовым редактором и позволяет проводить визуализацию абстрактного синтаксического дерева (среда ANTLRWorks 1.4.3, но сейчас на сайте уже появилась версия 2.0 http://tunnelvisionlabs.com/products/demo/antlrworks).
Генератор компиляторов позволяет получить набор токенов и абстрактное синтаксическое дерево (Abstract Syntax Tree, AST), соответствующее грамматике.
Из описания грамматики в форме Бекуса-Наура я составил файл грамматики, предназначенный для обработки ANTLR. Приведя грамматику к LL-виду, удалив левую рекурсию и вписав в соответствующие части создание символов грамматики на C#, я подготовил файл для дальнейшего процесса кодогенерации (файл грамматики MiniJava.g находится в директории проекта, ссылка на который дана ниже).
Так, например, создание главного класса описывается следующим образом:

mainClassDecl returns [NonTerm value]
	:
		CLASS^ id=ID LCURLY!
			PUBLIC! STATIC! VOID! MAIN! LPAREN!
				STRING! LBRACK! RBRACK! ID
			RPAREN!
			LCURLY! statement=stmtList RCURLY!
		RCURLY!
		{ 
			$value = NonTerm.CreateMainClassDecl(new Token(TokenType.ID, id.Text, id), statement.valueList);
			if (flagDebug) Console.WriteLine("mainClassDecl");
		}
	;

Здесь mainClassDecl – правило, соответствующее описанию главного класса, отвечающее за следующее описание:

MainClass ::= "class" Identifier "{" "public" "static" "void" "main" "(" "String" "[" "]" Identifier ")" "{" Statement "}" "}"

Знак "^" делает токен CLASS корнем правила, знак "!" после других токенов указывает ANTLR, чтобы он игнорировал их проверку (т.е. исключаются при построении AST). Те правила, результаты которых необходимо сохранить (название главного класса ID и список stmtList), необходимо присвоить переменным (id и statement, соответственно). Следует отметить, что токены записываются в верхнем регистре, а правила – в нижнем регистре. $value – значение, которое возвратиться корневому правилу. Тип возвращаемого значения определяется в квадратных скобках после ключевого слова returns (в данном случае это NonTerm).
Генерация выходного файла производится с помощью команды компилятора ANTLR для .NET (использовалась antlr-dotnet-tool-3.3.1.7705):


Antlr3.exe -o "путь_до_выходной_директории" "путь_до_директории_с_файлом_грамматикиMiniJava.g"

Собственные изменения, которые были внесены в грамматику (для удобства):

  • добавлен тип double;
  • печать на консоль printf(…) аналогична вызову System.out.println(…);
  • после каждой печати вызывается метод Console.Readkey() (с целью упрощения отладки).

Результаты лексического и синтаксического анализа выводятся в виде xml-файла.
Для отображения результата лексичского анализа используется следующий метод класса Lexer.

public void SaveToFile(string fileName)
{
    List<IToken> tokens = TokenStream.GetTokens();

    XElement xElement = new XElement("Lexer", 
        from token in tokens
        select new XElement("Token",
            new XAttribute("Text", token.Text.TokenToString()),
                new XAttribute("TokenIndex", token.TokenIndex),
                new XAttribute("Type", token.Type),
                new XAttribute("Line", token.Line),
                new XAttribute("CharPositionInLine", token.CharPositionInLine),
                new XAttribute("StartIndex", token.StartIndex),
                new XAttribute("StopIndex", token.StopIndex)
           )
        );

    xElement.Save(fileName);
}

Результат лексического анализа – 152 токена (здесь приведены первые 30):

Поток токенов

<?xml version="1.0" encoding="utf-8"?>
<Lexer>
  <Token Text="class" TokenIndex="0" Type="8" Line="1" CharPositionInLine="0" StartIndex="0" StopIndex="4" />
  <Token Text=" " TokenIndex="1" Type="74" Line="1" CharPositionInLine="5" StartIndex="5" StopIndex="5" />
  <Token Text="Factorial" TokenIndex="2" Type="26" Line="1" CharPositionInLine="6" StartIndex="6" StopIndex="14" />
  <Token Text="{" TokenIndex="3" Type="32" Line="1" CharPositionInLine="15" StartIndex="15" StopIndex="15" />
  <Token Text="n" TokenIndex="4" Type="74" Line="1" CharPositionInLine="16" StartIndex="16" StopIndex="16" />
  <Token Text=" " TokenIndex="5" Type="74" Line="2" CharPositionInLine="0" StartIndex="17" StopIndex="17" />
  <Token Text=" " TokenIndex="6" Type="74" Line="2" CharPositionInLine="1" StartIndex="18" StopIndex="18" />
  <Token Text=" " TokenIndex="7" Type="74" Line="2" CharPositionInLine="2" StartIndex="19" StopIndex="19" />
  <Token Text=" " TokenIndex="8" Type="74" Line="2" CharPositionInLine="3" StartIndex="20" StopIndex="20" />
  <Token Text="public" TokenIndex="9" Type="56" Line="2" CharPositionInLine="4" StartIndex="21" StopIndex="26" />
  <Token Text=" " TokenIndex="10" Type="74" Line="2" CharPositionInLine="10" StartIndex="27" StopIndex="27" />
  <Token Text="static" TokenIndex="11" Type="64" Line="2" CharPositionInLine="11" StartIndex="28" StopIndex="33" />
  <Token Text=" " TokenIndex="12" Type="74" Line="2" CharPositionInLine="17" StartIndex="34" StopIndex="34" />
  <Token Text="void" TokenIndex="13" Type="72" Line="2" CharPositionInLine="18" StartIndex="35" StopIndex="38" />
  <Token Text=" " TokenIndex="14" Type="74" Line="2" CharPositionInLine="22" StartIndex="39" StopIndex="39" />
  <Token Text="main" TokenIndex="15" Type="41" Line="2" CharPositionInLine="23" StartIndex="40" StopIndex="43" />
  <Token Text="(" TokenIndex="16" Type="40" Line="2" CharPositionInLine="27" StartIndex="44" StopIndex="44" />
  <Token Text="String" TokenIndex="17" Type="66" Line="2" CharPositionInLine="28" StartIndex="45" StopIndex="50" />
  <Token Text="[" TokenIndex="18" Type="31" Line="2" CharPositionInLine="34" StartIndex="51" StopIndex="51" />
  <Token Text="]" TokenIndex="19" Type="57" Line="2" CharPositionInLine="35" StartIndex="52" StopIndex="52" />
  <Token Text=" " TokenIndex="20" Type="74" Line="2" CharPositionInLine="36" StartIndex="53" StopIndex="53" />
  <Token Text="a" TokenIndex="21" Type="26" Line="2" CharPositionInLine="37" StartIndex="54" StopIndex="54" />
  <Token Text=")" TokenIndex="22" Type="60" Line="2" CharPositionInLine="38" StartIndex="55" StopIndex="55" />
  <Token Text="{" TokenIndex="23" Type="32" Line="2" CharPositionInLine="39" StartIndex="56" StopIndex="56" />
  <Token Text="n" TokenIndex="24" Type="74" Line="2" CharPositionInLine="40" StartIndex="57" StopIndex="57" />
  <Token Text="t" TokenIndex="25" Type="74" Line="3" CharPositionInLine="0" StartIndex="58" StopIndex="58" />
  <Token Text="System.out.println" TokenIndex="26" Type="54" Line="3" CharPositionInLine="1" StartIndex="59" StopIndex="76" />
  <Token Text="(" TokenIndex="27" Type="40" Line="3" CharPositionInLine="19" StartIndex="77" StopIndex="77" />
  <Token Text="new" TokenIndex="28" Type="50" Line="3" CharPositionInLine="20" StartIndex="78" StopIndex="80" />
  <Token Text=" " TokenIndex="29" Type="74" Line="3" CharPositionInLine="23" StartIndex="81" StopIndex="81" />
...
</Lexer>

Для AST я составил объектную модель, представляющую собой каждый элемент грамматики. Классы соответствуют нетерминалам и терминалам. Диаграмма классов показана на следующем рисунке.

Компилятор языка программирования MiniJava

Базовый класс BaseSymbol представляет собой символ грамматики из объединенного алфавита, от него наследуются Token – токен (терминал) и NonTerm – нетерминал. Нетерминалами являются: ProgramStatement – аксиома грамматики, MainClassDecl – главный класс, ClassDecl – класс, MethodDecl – метод, ExtendsClause – наследование класса, TypeDecl – тип, VarDecl – переменная, ExpressionDecl – выражение, StatementDecl – базовый класс операторов. Классы операторов: IfStatement – оператор условия, WhileStatement – оператор цикла while, StatementList – список операторов, AssignVarStatement – объявление и присваивание новой переменной, AssignIdStatement – присваивание переменной по идентификатору, объявленной ранее.
Данные классы используются в файле грамматики ANTLR для генерации AST.
Представление AST, формируемое в результате синтаксического анализа, сохраняется в xml-файле с помощью рекурсивного метода ToXmlTree() базового класса BaseSymbol. Метод переопределяется только для токенов. Для базового класса BaseSymbol метод выглядит следующим образом:

public virtual XElement ToXmlTree()
{
    XElement elements = new XElement(ToString());
    Symbols.ForEach(symbol =>
    {
        if (symbol != null)
        {
            XElement el = symbol.ToXmlTree();
            elements.Add(el);
        }
    });

    return elements;

}

Результат формирования дерева представлен здесь:

AST

<?xml version="1.0" encoding="utf-8"?>
<Program>
  <MainClass>
    <ID Value="Factorial" />
    <PrintStatement>
      <MethodCallExpression>
        <NewStatement>
          <ID Value="Fac" />
        </NewStatement>
        <ID Value="ComputeFac" />
        <ArgumentListExpression>
          <INTEGER Value="10" />
        </ArgumentListExpression>
      </MethodCallExpression>
    </PrintStatement>
  </MainClass>
  <Class>
    <ID Value="Fac" />
    <Method>
      <INT />
      <ID Value="ComputeFac" />
      <FormalArgumentList>
        <Variable>
          <INT />
          <ID Value="num" />
        </Variable>
      </FormalArgumentList>
      <StatementList>
        <VarStatement>
          <Variable>
            <INT />
            <ID Value="num_aux" />
          </Variable>
        </VarStatement>
        <IfElseStatement>
          <LessExpression>
            <ID Value="num" />
            <INTEGER Value="1" />
          </LessExpression>
          <IdStatement>
            <ID Value="num_aux" />
            <INTEGER Value="1" />
          </IdStatement>
          <IdStatement>
            <ID Value="num_aux" />
            <MultiplyExpression>
              <ID Value="num" />
              <MethodThisCallExpression>
                <ID Value="ComputeFac" />
                <ArgumentListExpression>
                  <MinusExpression>
                    <ID Value="num" />
                    <INTEGER Value="1" />
                  </MinusExpression>
                </ArgumentListExpression>
              </MethodThisCallExpression>
            </MultiplyExpression>
          </IdStatement>
        </IfElseStatement>
      </StatementList>
      <ID Value="num_aux" />
    </Method>
  </Class>
</Program>

Для отлова исключений я написал классы исключений, используемые при лексическом разборе ParserException, а также при генерации кода CodeGenerationException, наследуемые от базового класса исключений компилятора CompilerException.
Таким образом, в результате синтаксического анализа составляется абстрактное синтаксическое дерево, по которому на следующей фазе генерируется IL-код.

Генерация IL-кода

Для генерации я опять не стал изобретать велосипед, а воспользовался существующим проектом RunSharp, размещенным на Codeproject http://www.codeproject.com/Articles/20921/RunSharp-Reflection-Emit-Has-Never-Been-Easier. RunSharp – проект, инкапсулирующий вызовы методов классов из пространства имён System.Reflection.Emit, упрощая процесс генерации IL-кода.
Для кодогенерации используются следующие структуры данных: таблица классов программы (для кодогенерации классов и для разрешения зависимостей, например, когда метод одного класса ссылается на другой, и наоборот), список методов каждого класса (для кодогенерации методов), список локальных переменных (для отслеживания ссылок на локальные переменные внутри блоков if, while и тела метода), стеки локальных переменных (для выполнения унарных и бинарных операций), список формальных параметров текущего метода.
Также используется управляющая таблица кодогенерации, содержащая имя символа грамматики и метода, который выполняет генерацию кода при его появлении.
Генерация IL-кода выполняется в главном рекурсивном методе Generate(BaseSymbol root) класса SharpCodeGen.

private void Generate(BaseSymbol root)
{
    if (root == null)
    {
        return;
    }

    if (root.GrammarMember == GrammarMemberType.NonTerm)
    {
        NonTerm nonTerm = root as NonTerm;
        _compilerLogger.PrintGenerateNonTerm(nonTerm);

        if (_emitTableDictionary.ContainsKey(nonTerm.TypeNonTerm))
        {
            _emitTableDictionary[nonTerm.TypeNonTerm](nonTerm);
        }
        else
        {
            root.Symbols.ForEach(Generate);
        }
    }
}

В методе определяется, является ли root нетерминалом, и если тип нетерминала содержится в управляющей таблице, то выполняется метод генерации управляющей таблицы, иначе рекурсивно выполняется генерация для каждого символа грамматики, содержащемся в root.
Управляющая таблица содержит следующие методы, выполняющие генерацию инструкций следующих символов грамматики:

  • EmitMainClass – главный класс программы;
  • EmitClass – класс программы (кроме главного);
  • EmitClassVar – переменная класса (закрытое поле класса);
  • EmitMethod – метод класса;
  • EmitVarStatement – присвоение новой переменной выражения справа;
  • EmitNewStatement – выделение памяти под переменную;
  • EmitNewArrayStatement – выделение памяти под массив;
  • EmitIdStatement – присвоение переменной выражения справа;
  • EmitArrayIdStatement – присвоение массиву выражения справа;
  • EmitArrayIndiciesStatement – доступ по индексу массива;
  • EmitMethodCallExpression – вызов метода;
  • EmitBinaryExpression – бинарная операция;
  • EmitUnaryExpression – унарная операция;
  • EmitPrintStatement – оператор печати;
  • EmitIfStatement – условие;
  • EmitWhileStatement – цикл while;
  • EmitLengthFunctionExpression – длина массива.

В части из этих методов вызывается рекурсивный метод Generate().
Так, метод, генерирующий инструкции метода, следующий:

private void EmitMethod(NonTerm nonTerm)
{
    Token typeMethodDeclSimple;
    Token methodName;
    List<BaseSymbol> formalParametersList;
    BaseSymbol methodStatementList;
    BaseSymbol returnStatement;
    NonTermFactory.GetMethodDecl(nonTerm, out typeMethodDeclSimple, out methodName, 
        out formalParametersList, out methodStatementList, out returnStatement);

    _currentFormalArgumentList.Clear();
    foreach (BaseSymbol symbol in formalParametersList)
    {
        Token type;
        Token id;
        NonTermFactory.GetFormalArgumentDeclaration(symbol, out type, out id);
        _currentFormalArgumentList.Add(id.Value);
    }

    _compilerLogger.PrintRefreshFormalArgumentList(_currentFormalArgumentList);

    _currentMethod = _methodsTables[_currentClass.Name][methodName.Value];
    _g = _currentMethod;

    GeneratePreInitLocalVariables(methodStatementList);
    Generate(methodStatementList);
    Type resultType = GetVariableType(typeMethodDeclSimple);
    string nameResult = AddTempLocalVariable(resultType);
    EmitExpression(returnStatement, resultType, nameResult);

    try
    {
        _g.Return(_currentOperandTempResult);
    }
    catch (InvalidCastException ex)
    {
        throw new CodeGenerationException(MessagesHelper.TypeMismatchEx, returnStatement.ToStringInfo(), ex);
    }
    ClearCurrentBlockLocalVariables();
}

Вначале получаем все необходимые данные по методу (возвращаемый тип typeMethodDeclSimple, имя метода methodName, список формальных параметров formalParametersList, список операторов метода methodStatementList и возвращаемое выражение returnStatement). Далее происходит заполнение текущего списка формальных переменных, после чего переменной _currentMethod присваивается объект (типа MethodGen из библиотеки RunSharp), отвечающий за генерацию метода. Затем в методе GeneratePreInitLocalVariables() заполняется список локальных переменных и рекурсивно генерируется содержимое самого метода, генерируется оператор, отвечающий за возвращение результата метода, стоящий после ключевого слова return, и в конце очищается список локальных переменных блока.
А метод, отвечающий за генерацию операции присваивания переменной, выглядит следующим образом:

private void EmitIdStatement(NonTerm nonTerm)
{
    Token idToken;
    BaseSymbol expression;
    NonTermFactory.GetAssignIdStatement(nonTerm, out idToken, out expression);

    Operand operand;
    if (_currentFormalArgumentList.Contains(idToken.Value))
    {
        operand = _g.Arg(idToken.Value);
    }
    else if (_localVariablesTable.ContainsKey(idToken.Value))
    {
        operand = _localVariablesTable[idToken.Value];
    }
    else
    {
        operand = _g.This().Field(idToken.Value);
    }
    _currentOperandTempResult = EmitExpression(expression, operand.Type, idToken.Value);

    try
    {
        _g.Assign(operand, _currentOperandTempResult);
    }
    catch (InvalidCastException ex)
    {
        throw new CodeGenerationException(MessagesHelper.AssignTypeMismatchEx, expression.ToStringInfo(), ex);
    }
}

Здесь вначале получаем токен, которому присваиваем выражение справа (idToken) и само выражение (expression). Далее определяем, откуда взялась переменная: из списка формальных параметров (_currentFormalArgumentList), из таблицы локальных переменных (_localVariablesTable) или это – переменная класса. После чего вычисляем выражение справа, вызвав метод EmitExpression(), и генерируем присваивание.

Аналогичным образом с учетом специфики других конструкций генерируется их код.

Здесь показан журнал результата выполнения кодогенерации для нашей программы вычисления факториала.

Журнал кодогенерации

Генерирование классов и сигнатур методов
Класс Fac
 Метод ComputeFac System.Int32

Генерация инструкций для Program
Генерация инструкций для MainClass
В данном блоке не встречаются локальные переменные
Генерация инструкций для PrintStatement
Генерация инструкций для MethodCallExpression
Генерация инструкций для NewStatement
Генерация инструкций для Class
Генерация инструкций для Method
Обновлен список текущих параметров метода
num
Добавлены переменные для блока
num_aux
Генерация инструкций для StatementList
Генерация инструкций для VarStatement
Генерация инструкций для IfElseStatement
Генерация инструкций для LessExpression
В данном блоке не встречаются локальные переменные
Генерация инструкций для IdStatement
В данном блоке не встречаются локальные переменные
Генерация инструкций для IdStatement
Генерация инструкций для MultiplyExpression
Генерация инструкций для MethodThisCallExpression
Генерация инструкций для MinusExpression
Удалены переменные 
num_aux

Для компилятора написано консольное приложение, принимающие следующие аргументы командной строки:

-i <входной файл> [-o <выходная директория>]

Если не указана выходная директория, то выходные файлы будут созданы в той директории, где было запущено приложение. Примеры и само приложение расположены в директории Samples.

Заключение

Вцелом был разобран способ написания компилятора языка программирования MiniJava под .NET Framework на языке C#, используя существующие средства разработки. Здесь я сконцентрировался на более высокоуровневых моментах, необходимых для написания компилятора.
Написанный компилятор успешно справляется с примерами из домашней страницы проекта MiniJava такими, как: вычисление факториала, бинарный поиск, пузырьковая сортировка, обход дерева, быстрая сортировка, линейный поиск, построение связного списка, построение бинарного дерева.
Исходный код проекта доступен на GitHub.

Источники

Общее (теория и практика)

  • Ахо, Сети, Ульман. Компиляторы. Принципы, технологии, инструменты.
  • Белоусов, Ткачев. Дискретная математика.
  • Создание компилятора языка для .NET Framework http://msdn.microsoft.com/ru-ru/magazine/cc136756.aspx

ANTLR

MiniJava

Автор: lightsource

Источник

Поделиться

* - обязательные к заполнению поля