C＃for .NETでのクールな教育用言語のコンパイラーの開発（パート1）

はじめに

こんにちは、Habrauser様、 .NETプラットフォームで、Cool言語で記述されたコードをCIL （Common Intermediate Language）仮想マシンのコードに変換するコンパイラーの実用的な作成に関する資料をお見せしたいと思います。 -怠のためにそれを一度に説明する



最初の部分では、ANTLR環境での演算子の優先順位を考慮に入れて、C＃言語のレクサーとパーサーを生成する文法を記述するプロセスについて説明します。 また、私の道で出会った落とし穴を調べます。 したがって、少なくとも誰かの時間を節約しようとします（将来的には自分のために）。



2番目の部分では、 セマンティックコードアナライザーの構築プロセス、コード生成 、および誰もが必要としない自作コード最適化について説明します。 また、最新のIDEのように、構文の強調表示とブロックの折りたたみを使用して、ブラックジャックと売春婦で美しいインターフェイスを作成する方法についても説明します。 もちろん、第2部の最後では、ソリューションのすべてのソースをレイアウトし、いずれにせよ、アーキテクチャとコードのさらなる改善について話します。



警告 ：このコンパイラを開発する前に、私は実際に主題の文献を勉強しませんでした。 私の興味を引くいくつかの記事を読んだり、公式WebサイトでANTLR ビデオチュートリアルを視聴したり、「いやらしい」クラスメートと話したりすることがすべて判明しました。 したがって、開発されたソフトウェアは理想とはほど遠いものです。



読者が私をよりよく理解できるように、まず最初にいくつかの定義を示します（Wikipediaから）。

• トークン - トークンに対応する、コンピューターサイエンスの字句解析における文字のシーケンス。
• 字句解析器は、出力で「トークン」と呼ばれる文字のシーケンス（文字を単語にグループ化するなど）を取得するために、文字の入力シーケンス（たとえば、プログラミング言語のソースコードなど）の分析分析のためのモジュールです。
• パーサーは、言語のトークン（単語、トークン）の線形シーケンスを正式な文法と比較するためのモジュールです。 結果は、解析ツリーまたは構文ツリーです。

habrahabrについては、数学表現や言語の文法の書き方を詳細に説明している記事がたくさんあります。そのため、環境の詳細な設定については説明しません。 また、コンパイラーの構築に関する理論的な問題については掘り下げません。なぜなら、このテーマに関する良い記事、たとえばこのサイクルも数多くあるからです。



そのため、次のプログラムとライブラリを使用してコンパイラを開発しました。

1. ANTLRWorks-文法を記述し、さまざまな言語（C、C＃、Java、JavaScript、Objective-C、Perl、Python、Rubyなど）のレクサーとパーサーのコードを生成するためのIDE。 LL（*）解析に基づいています。
2. ANTLR C＃ランタイム配布 （Antlr3.Runtime.dll）は、生成されたレクサーとパーサーで使用されます。
3. Visual Studio 2010次の記事では、構文の強調表示とコード補完のための高度なテキストエディターであるWPFのコンポーネントについて説明しますAvalonEdit ）。
4. Javaランタイム環境 （ANTLRWorksはJavaで記述されているため）。
5. IL Disassemblerは、C＃などのコンパイラがCILコードを生成する方法と、その外観を理解するために、2番目のパートで使用されます。

言語の説明Cool

クール -クラスルームオブジェクト指向言語は、その名前が示すように、クラスやオブジェクトなど、 誰も必要としない教育用プログラミング言語です。 Coolは機能的に強く型付けされた言語です。 型チェックはコンパイル段階で静的に行われます。 プログラムは、本質的にクラスのコレクションです。 クラスには、一連のフィールドと関数が含まれます（ここでは、それらをfeatureと呼びます ）。

すべてのフィールドは、基本クラスと派生クラス内に表示されます。 すべての機能はどこからでも見ることができます（パブリック）。

この言語は式に基づいています。 すべての関数は式を引数として取ることができ、すべての関数の本体は結果を返す式です。 行出力などの関数でさえ、結果、つまり呼び出し元のクラスのインスタンスを返します。

また、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

一部の演算子は、中かっこ（Cのようなもの）または単語の終わりで終わることに注意してください。 （ デッドパスカルの場合と同様）、および同じ演算子の名前を逆順（if-> fi、loop-> pool、case-> esacの場合）。

各演算子が何らかの結果を返す場合、ifは何を返す必要がありますか？ 結局のところ、彼は2つの選択肢のオプションを返すことができます。 正解：最も近い共通の祖先（教科書では、それについて何らかの形で複雑に書かれていますが、まだ特別な演算子が使用されています）。 わかりやすくするために写真を示します。



図1



ここで、クラスAおよびBの場合、最も近い共通の祖先はクラスDです。



caseステートメントは、ifステートメントが複数回適用されていることに似ています。



voidは常にwhile構造体で返されます（もちろんループがループしない限り）。



このような構成{<expr1>; ... <exprn>; }は式exprnのオブジェクト、つまり 最後の表現。



ここでの関数は、クラスとその祖先（仮想関数）だけでなく、一般にこのクラスの祖先でも呼び出すことができます。 これは、「@」演算子を使用して実行できます。 例として、図1のクラス階層を考えてみましょう。クラスEにfunc（）関数を持たせ、他のすべての子孫は独自の方法でそれを再定義します。 次に、オブジェクトAのインスタンスがあり、クラスDからfunc関数を呼び出す場合、次の構文を使用する必要があります。

result <- (new A)@D.func()
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

SELF_TYPEキーワードは 、特定の機能を記述するクラスの同義語として使用されます。 識別子selfは、現在のクラスへのポインターです（つまり、これは他の言語です）。



ローカル変数は、 let演算子を使用してCool言語で導入され、指定されたletブロック内でのみ使用できます。



void -nullの類似物。オブジェクトが作成されていないことを示します。



他のすべてのオペレーターは説明を必要としないと思います。明確でない場合は、記事の最後に示されているリンクを使用して、このクールな言語の方言のマニュアルを学習できます。

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は、この種のエラーをすぐに検出して生成します。 [致命的]ルールcompilation_unitには、altから到達可能な再帰ルール呼び出しによる非LL（*）決定があります...左ファクタリングまたは構文述語を使用して解決しますまたはbacktrack = trueオプションを使用して...そして、もちろん、ANTLRにはオプションbacktrack = trueがあり、この制限を克服できます。 しかし、それを適用すると、左再帰での表現のために、生成された宇宙船の別のノードと一致する必要があります。 それで、すべて同じように、それを取り除くことは素晴らしいことです。 さらに、この記事からわかるように、このオプションはパーサーの速度を低下させるため、著者は可能な限りパーサーを破棄することをお勧めします。
• しかし、主なことは、この形式の文法では演算子の優先順位が考慮されないことです。 左再帰がパーサーの効率にのみ影響する場合、この問題を無視すると、後で誤ったコードが生成されます（たとえば、2 + 2 * 2は6ではなく8になります）

マニュアルをさらに読みます。 そして、それはちょうど操作の優先順位について書かれています。 それらは次の形式をとります（最上位-最高、下-最優先）。

• 。
• @
• 〜
• 虚無
• * /
• +-
• <= <=
• じゃない
• <-

したがって、これらの操作を念頭に置いて文法を構築する必要があります。 これを行うために、次の構築ルールを順守します：優先度の低い演算子ごとに、この優先度の演算子と右側の優先度の高い演算子の非終端記号を含む新しいルールを作成します。混乱して聞こえるので、元の文法にこの構造を与えます。

 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. ^は 、この演算子とその子孫でマークされたトークンから、生成された構文ツリーに新しいノードを作成するために使用されます。 この演算子には2つの形式があります。
   • 後置。 たとえば、このようなルールの場合：

      relation: addition ((LE^ | LT^ | GE^ | GT^ | EQUAL^) addition)*;
           
           
     
             
             
             
           
     
         
             
             
             
           
           
     
             
             
             
           
     
         
          

     ノードが構文ツリーに挿入され、演算子のいずれかが括弧と子で示されます。additionは演算子の左側にあり、 additionは演算子の右側にあります。
   • プレフィックス。 たとえば、このようなルールの場合：

      CLASS typeName (INHERITS typeName)? LCURLY featureList RCURLY -> ^(Class typeName featureList typeName?)
           
           
     
             
             
             
           
     
         
             
             
             
           
           
     
             
             
             
           
     
         
          

     typeName featureList typeNameの子孫を持つクラスの親ノードが構文ツリーに挿入されますか？

使用されている他のすべてのANTLR演算子はコメントを必要としません（離散数学を学んだ人向け）。

1. * -反復。
2. + -正の反復。
3. ？ -左利きのトークンまたはトークンのグループは、存在する場合と存在しない場合があります。

演算子「->」および「^」を使用する場合、新しいトークンを導入する必要があることに注意してください。 これは、対応するセクショントークン{}で行われます。ところで、.gファイルには、特定のレクサーおよびパーサー言語（この場合はC＃）向けの最小限のコードが含まれていることを確認します。 それにもかかわらず、そのようなコードはまだSTRINGトークンに使用する必要がありました。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここでは、StringBuilderを使用して文字列処理を効率化します。原則として、このようなコードの他の点在は、レクサーの最適化には受け入れられますが、すべてのルールには受け入れられません。C＃レクサーおよびパーサーコードで名前空間を指定するには（たとえば、System.Text for StringBuilder）、次の構成要素が使用されます（ここでは、「不要な」警告も無効になっています）。

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

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ANTLRWorksで文法をコンパイルした後、C＃レクサーとパーサーのコードを生成する必要があります（ありがとう、cap）。



指定された設定の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（特定のトークンが「=」記号であるかどうか）ツリーをトラバースするときは、文字列を比較するよりも数値を追加する方が速いため、TextではなくTypeプロパティを使用する必要があります。すべての定数が自動的に生成されるため、エラーの可能性が減少します。
• treeNode.Line-コード内のトークン行番号
• treeNode.CharPositionInLine-行の先頭からのコード内のトークンの位置

また、C＃の文法からコードを生成するときに、 パブリック修飾子を文法の公理の前（この場合はプログラムの前）に配置して、後でコードから呼び出すことができるようにします（それ以外の場合はプライベートになります）

おわりに

この記事では、ANTLRWorksで文法を記述し、C＃レクサーとパーサーの生成に使用する方法、およびレクサーとパーサーの使用方法について説明しました。 次の記事では、言語のセマンティクスの処理（つまり、型チェック、セマンティックエラーの処理）、構文ツリーの各ノードをバイパスして、CIL命令の説明、対応する構文構成のCILコードを生成する方法、仮想マシンスタックの動作方法、組み込みの使用方法について説明しますコード生成を容易にする.NETライブラリSystem.Reflection.Emit。 もちろん、途中で出会った落とし穴について説明します（特に、System.Reflection.Emitを使用してクラス階層を作成する）。 また、 美しい壁紙を美しくモダンなインターフェイスにする方法についても説明します！ ただし、結論に書かれていることは、すでに序文で部分的に書かれています。



最後に、私はhabrasocietyに1つの質問をしたいと思います。答えは見つかりませんでした。



C＃lexerの場合、NoViableAltExceptionをスローするコードを常に生成しますが、このスローをインターセプトすることはできません。

 catch (NoViableAltException nvae) { DebugRecognitionException(nvae); throw; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この行に単なるスローではなく、たとえば例外が発生したり、レクサーが動作し続けるように、どのように文法ファイルを書くことができますか？ また、C＃コードが生成されるたびにこの行を修正する必要があります注：ANTLRで@rulecatchを使用した操作では何も起こりませんでした。



誰かがこの問題を理解し、コメントに答えを書いてくれたら嬉しいです。

推奨読書

• 確定ANTLRリファレンス、Terence Parr、2007年。
• コンパイラー 原則、技術およびツール、2008年、アルフレッドW.アホ、モニカS.ラム、ラビセティ、ジェフリーD.ウルマン

クールな言語マニュアル、拡張子が.gの文法ファイル、ANTLRWorks環境