Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

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

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

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

Язык программирования 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>

Тут грамматика представлена правилами итога нетерминалов в цепочки языка.
Терминал – это финальный символ грамматики. Нетерминал – это символ грамматики, для которого найдётся правило итога, переводящее его в цепочку из комбинаций терминалов и/или нетерминалов, т.е. =”http://www.ssw.uni-linz.ac.at/coco/”>Coco/R, GOLD Parsing System и уйма других.
Я применял ANTLR, от того что он комфортен для написания грамматики, имеет графическую оболочку с текстовым редактором и разрешает проводить визуализацию абстрактного синтаксического дерева (среда ANTLRWorks 1.4.3, но теперь на сайте теснее возникла версия 2.0http://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 я составил объектную модель, представляющую собой всякий элемент грамматики. Классы соответствуют нетерминалам и терминалам. Диаграмма классов показана на дальнейшем рисунке.

Базовый класс BaseSymbol представляет собой символ грамматики из объединенного алфавита, от него наследуются Token – токен (терминал) и NonTerm – нетерминал. Нетерминалами являются: ProgramStatement– аксиома грамматики, MainClassDecl – основной класс, ClassDecl – класс, MethodDecl – способ,ExtendsClause – наследование класса, TypeDecl – тип, VarDecl – переменная, ExpressionDecl – выражение,StatementDecl – базовый класс операторов. Классы операторов: IfStatement – оператор данные,WhileStatement – оператор цикла whileStatementList – список операторов, 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.
Такs_permark!

Сначала получаем все нужные данные по способу (возвращаемый тип 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
Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB