MiniJavaプログラミング言語コンパイラ

比較的短時間でプログラミング言語のコンパイラを作成する方法。 これを行うには、プロセスを自動化する開発ツールを使用します。 .NET Framework用のMiniJavaプログラミング言語コンパイラの作成方法についてお話ししたいと思います。



コンパイラー全体を記述するプロセス全体を次の図に示します。 MiniJavaプログラミング言語のソースコードを含むファイルが入力に送られます。 出力は、CLRによって実行されるPEファイルです。







次に、説明の実際的な部分に集中したいと思います。

MiniJavaプログラミング言語

MiniJavaは、Javaプログラミング言語のサブセットです。 オーバーロードは許可されていません;コンソールへの印刷は、 System.out.println(...)



メソッドを呼び出すことによって整数によってのみ実行されます。 e.length



式は、 int[]



配列にのみ適用されます。

Beckus-Naur形式の文法の説明（言語プロジェクトのサイト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



。

MiniJavaプロジェクトのWebサイトから取得した階乗を計算するfactorial.javaプログラムの例を使用して、コンパイラを記述するプロセス（ILコードの生成まで）を検討します。

 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 ; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

字句解析

これらはコンパイラジェネレータを使用して実行されるため、コンパイラを記述するこれら2つのフェーズを組み合わせました。 現在、 ANTLR 、 GPPG 、 Coco / R 、 GOLD Parsing Systemなど、十分な数のコンパイラジェネレータがあります。

ANTLRを使用したのは、文法を書くのに便利で、テキストエディターを備えたグラフィカルシェルを備え、抽象構文ツリー（ANTLRWorks 1.4.3環境、バージョン2.0がhttp://tunnelvisionlabs.com/products/demoに既に表示されているため） / antlrworks ）。

コンパイラジェネレーターを使用すると、トークンのセットと、文法に対応する抽象構文ツリー（AST）を取得できます。

Beckus-Naur形式の文法の説明から、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



）の後の角括弧で決定されreturns



。

出力ファイルは、.NETのANTLRコンパイラコマンドを使用して生成されます（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個はここにあります）：



ASTの場合、文法の各要素を表すオブジェクトモデルをコンパイルしました。 クラスは、非端末と端末に対応します。 クラス図を次の図に示します。







基本クラスBaseSymbol



は、結合されたアルファベットからの文法記号であり、 NonTerm



トークン（端末）およびNonTerm



端末はそれから継承されます。 MainClassDecl



文法公理、 MainClassDecl



メインクラス、 ClassDecl



クラス、 MethodDecl



メソッド、 ExtendsClause



クラスの継承、 TypeDecl



タイプ、 VarDecl



変数、 ExpressionDecl



式、 StatementDecl



演算子の基本クラス。 演算子クラス： IfStatement



は条件ステートメント、 WhileStatement



はwhile



ステートメント、 StatementList



はStatementList



のリスト、 AssignVarStatement



は宣言と新しい変数の割り当て、 AssignIdStatement



は以前に宣言された識別子による変数割り当てです。

これらのクラスは、ASTLRを生成するためにANTLR文法ファイルで使用されます。

解析によって生成されたAST表現は、 ToXmlTree()



基本クラスの再帰的なToXmlTree()



メソッドを使用してxmlファイルに保存されます。 メソッドはトークンに対してのみオーバーライドされます。 基本クラス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; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ツリー形成の結果は次のとおりです。



例外をキャッチするために、 ParserException



と、 CompilerException



コンパイラ例外の基本クラスから継承されたCodeGenerationException



コードの生成に使用される例外クラスを作成しCodeGenerationException



。

したがって、構文解析の結果として、抽象構文ツリーがコンパイルされ、次のフェーズでILコードが生成されます。

ILコード生成

世代のために、私は再び車輪の再発明を開始しませんでしたが、Codeproject http://www.codeproject.com/Articles/20921/RunSharp-Reflection-Emit-Has-Never-Been-Easierに投稿された既存のRunSharpプロジェクトを利用しました。 RunSharpは、System.Reflection.Emit名前空間からのクラスメソッド呼び出しをカプセル化するプロジェクトで、ILコードの生成プロセスを簡素化します。

コード生成には、次のデータ構造が使用されます：プログラムクラステーブル（クラスのコード生成およびあるクラスのメソッドが別のクラスを参照する場合、およびその逆の場合）、各クラスのメソッドのリスト（メソッドのコード生成の場合）、ローカル変数のリスト（追跡リンクの場合） if



、 while



ブロックおよびメソッドの本体内のローカル変数、ローカル変数のスタック（単項およびバイナリ演算を実行するため）、現在のメソッドの仮パラメータのリスト。

コード生成制御テーブルも使用されます。これには、文法シンボルの名前と、コードが表示されたときにコードを生成するメソッドが含まれます。

ILコードの生成は、 Generate(BaseSymbol root)



のメインの再帰メソッドGenerate(BaseSymbol root)



ます。

 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



非終端のタイプがコントロールテーブルに含まれている場合、コントロールテーブルを生成するメソッドが実行されます。そうでない場合、 root



含まれる各文法文字に対して再帰的に生成が実行されます

コントロールテーブルには、次の文法文字の指示を生成する次のメソッドが含まれています。

• EmitMainClass-プログラムのメインクラス。
• EmitClass-プログラムのクラス（メインクラスを除く）;
• EmitClassVar-クラス変数（プライベートクラスフィールド）;
• EmitMethod-クラスメソッド。
• EmitVarStatement-新しい式変数の右側への割り当て。
• EmitNewStatement-変数のメモリ割り当て。
• EmitNewArrayStatement-配列へのメモリの割り当て。
• EmitIdStatement-右側の式への変数の割り当て。
• EmitArrayIdStatement-右側の式の配列への割り当て。
• EmitArrayIndi​​ciesStatement-配列インデックスによるアクセス。
• 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



、仮パラメーターのリスト、 methodStatementList



、メソッドの演算子のリストmethodStatementList



および戻り式returnStatement



）。 次に、現在の形式変数のリストに入力します。その後、変数_currentMethod



（RunSharpライブラリのMethodGen



など） _currentMethod



割り当てられ、メソッドが生成されます。 次に、 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()



メソッドを呼び出して右側の式を計算し、割り当てを生成します。



同様に、他のデザインの詳細を考慮して、それらのコードが生成されます。



階乗計算プログラムのコード生成の結果のログは次のとおりです。





コンソールアプリケーションは、次のコマンドライン引数を取るコンパイラー用に作成されています。

-i < > [-o < >]







出力ディレクトリが指定されていない場合、出力ファイルはアプリケーションが起動されたディレクトリに作成されます。 サンプルとアプリケーション自体は、Samplesディレクトリにあります。

おわりに

全体として、既存の開発ツールを使用して、C＃で.NET Framework用のMiniJavaプログラミング言語コンパイラを作成する方法について説明しました。 ここでは、コンパイラの作成に必要な上位レベルのポイントに焦点を当てました。

書かれたコンパイラは、階乗計算、バイナリ検索、バブルソート、ツリートラバーサル、クイックソート、線形検索、リンクリストの作成、バイナリツリーの作成など、MiniJavaプロジェクトホームページからの例を正常に処理します。

プロジェクトのソースコードはGitHubで入手できます 。

ソース

一般（理論と実践）

• アホ、ネットワークス、ウルマン。 コンパイラー 原則、技術、ツール。
• ベロソフ、トカチョフ。 離散数学。
• .NET Framework用の言語コンパイラーの作成http://msdn.microsoft.com/en-us/magazine/cc136756.aspx

ANTLR

• ANTLRチュートリアル-式言語http://meri-stuff.blogspot.ru/2011/09/antlr-tutorial-expression-language.html
• ANTLRを使用したパーサーの作成http://club.shelek.ru/viewart.php?id=39
• ANTLRに関する優れた入門プレゼンテーションhttp://fmt.cs.utwente.nl/courses/vertalerbouw/sheets/vb-04-antlr-1-4up.pdf

Minijava

• MiniJavaの概要http://www-cs-faculty.stanford.edu/~eroberts//papers/SIGCSE-2001/MiniJava.pdf
• MiniJavaタイプシステムhttp://www.cs.ucla.edu/~palsberg/course/cs132/miniJava-typesystem.pdf
• MiniJava構文http://www.cs.purdue.edu/homes/hosking/502/project/grammar.html