Geekly Articles each Day

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"


文法に加えられた独自の倉曎䟿宜䞊

字句解析ず解析の結果は、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は、結合されたアルファベットからの文法蚘号であり、 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; }


ツリヌ圢成の結果は次のずおりです。
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ず、 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含たれる各文法文字に察しお再垰的に生成が実行されたす
コントロヌルテヌブルには、次の文法文字の指瀺を生成する次のメ゜ッドが含たれおいたす。

これらのメ゜ッドの䞀郚は、再垰メ゜ッド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()メ゜ッドを呌び出しお右偎の匏を蚈算し、割り圓おを生成したす。

同様に、他のデザむンの詳现を考慮しお、それらのコヌドが生成されたす。

階乗蚈算プログラムのコヌド生成の結果のログは次のずおりです。
コヌド生成ログ
 クラスおよびメ゜ッドシグネチャの生成
クラスfac
  ComputeFac System.Int32メ゜ッド

プログラムの指瀺の生成
 MainClassの指瀺の生成
このブロックにロヌカル倉数が芋぀かりたせん
 PrintStatementの指瀺の生成
 MethodCallExpressionの呜什の生成
 NewStatementの指瀺の生成
クラスの指瀺の生成
メ゜ッドの指瀺の生成
珟圚のメ゜ッドパラメヌタのリストを曎新
 num
ブロックの倉数を远加したした
 num_aux
 StatementListの指瀺の生成
 VarStatementの指瀺を生成する
 IfElseStatementの指瀺の生成
 LessExpressionの呜什の生成
このブロックにロヌカル倉数が芋぀かりたせん
 IdStatementの指瀺の生成
このブロックにロヌカル倉数が芋぀かりたせん
 IdStatementの指瀺の生成
 MultiplyExpressionの呜什の生成
 MethodThisCallExpressionの呜什の生成
 MinusExpressionの指瀺の生成
削陀された倉数 
 num_aux



コン゜ヌルアプリケヌションは、次のコマンドラむン匕数を取るコンパむラヌ甚に䜜成されおいたす。
-i < > [-o < >]

出力ディレクトリが指定されおいない堎合、出力ファむルはアプリケヌションが起動されたディレクトリに䜜成されたす。 サンプルずアプリケヌション自䜓は、Samplesディレクトリにありたす。

おわりに


党䜓ずしお、既存の開発ツヌルを䜿甚しお、Cで.NET Framework甚のMiniJavaプログラミング蚀語コンパむラを䜜成する方法に぀いお説明したした。 ここでは、コンパむラの䜜成に必芁な䞊䜍レベルのポむントに焊点を圓おたした。
曞かれたコンパむラは、階乗蚈算、バむナリ怜玢、バブル゜ヌト、ツリヌトラバヌサル、クむック゜ヌト、線圢怜玢、リンクリストの䜜成、バむナリツリヌの䜜成など、MiniJavaプロゞェクトホヌムペヌゞからの䟋を正垞に凊理したす。
プロゞェクトの゜ヌスコヌドはGitHubで入手できたす 。

゜ヌス


䞀般理論ず実践


ANTLR


Minijava

Source: https://habr.com/ru/post/J191766/

More articles:


All Articles