JavaCCで独自の言語を構築する

Javaコンパイラがどのように機能するのか疑問に思ったことはありませんか?HTMLやXMLなどの標準形式にサブスクライブしないマークアップドキュメントのパーサーを作成する必要がありますか?それとも、あなたはそれのためだけにあなた自身の小さなプログラミング言語を実装したいですか?JavaCCこれらすべてをJavaで実行できます。したがって、コンパイラとインタプリタの動作について詳しく知りたい場合でも、Javaプログラミング言語の後継を作成するという具体的な野心がある場合でも、今月の探求に参加してください。JavaCC便利な小さなものの構築によって強調されています。コマンドライン計算機。

コンパイラ構築の基礎

プログラミング言語は、境界が曖昧になっていますが、コンパイルされた言語と解釈された言語に、いくぶん人工的に分割されることがよくあります。そのため、心配する必要はありません。ここで説明する概念は、コンパイルされた言語とインタープリター言語に等しく当てはまります。以下ではコンパイラという言葉を使用しますが、この記事の範囲では、インタプリタの意味が含まれます

コンパイラは、プログラムテキスト(ソースコード)が提示されたときに、3つの主要なタスクを実行する必要があります。

  1. 字句解析
  2. 構文分析
  3. コードの生成または実行

コンパイラの作業の大部分は、プログラムのソースコードを理解し、その構文の正確さを保証することを含むステップ1と2を中心にしています。これをパーサーの責任であるプロセス解析と呼びます。

字句解析(字句解析)

字句解析では、プログラムのソースコードをざっと見て、適切なトークンに分割しますトークンは、プログラムのソースコードの重要な部分です。トークンの例には、キーワード、句読点、数字などのリテラル、および文字列が含まれます。非トークンには、多くの場合無視されますがトークンを区切るために使用される空白とコメントが含まれます。

構文解析(構文解析)

構文解析中に、パーサーは、プログラムの構文の正確さを保証し、プログラムの内部表現を構築することによって、プログラムのソースコードから意味を抽出します。

コンピュータ言語理論は、プログラム、文法、および言語について話します。その意味で、プログラムはトークンのシーケンスです。リテラルは基本的なコンピューター言語要素であり、これ以上減らすことはできません。文法は、構文的に正しいプログラムを構築するためのルールを定義します。文法で定義されたルールに従って再生されるプログラムのみが正しいです。言語は、すべての文法規則を満たすすべてのプログラムのセットにすぎません。

構文分析中に、コンパイラーは、言語の文法で定義された規則に関してプログラムのソースコードを調べます。文法規則に違反している場合、コンパイラはエラーメッセージを表示します。その過程で、コンパイラーはプログラムを調べながら、コンピュータープログラムの簡単に処理できる内部表現を作成します。

コンピューター言語の文法規則は、EBNF(Extended Backus-Naur-Form)表記で明確に完全に指定できます(EBNFの詳細については、「参考文献」を参照してください)。EBNFは、生成規則の観点から文法を定義します。生成規則では、文法要素(リテラルまたは構成要素のいずれか)を他の文法要素で構成できると規定されています。既約であるリテラルは、句読記号などの静的プログラムテキストのキーワードまたはフラグメントです。構成要素は、プロダクションルールを適用することによって導出されます。プロダクションルールの一般的な形式は次のとおりです。

GRAMMAR_ELEMENT:=文法要素のリスト| 文法要素の代替リスト

例として、基本的な算術式を記述する小さな言語の文法規則を見てみましょう。

expr:=数値| expr '+' expr | expr'- 'expr | expr '*' expr | expr '/' expr | '(' expr ')' | --expr番号:=桁+( '。'桁+)?数字:= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | 「9」

3つの生成ルールが文法要素を定義します。

  • expr
  • number
  • digit

その文法で定義されている言語を使用すると、算術式を指定できます。Anexprは、2つexprのs、expr括弧内、または負に適用される4つの中置演算子の数または1つですexpr。Anumberは、オプションの小数部を持つ浮動小数点数です。adigitをおなじみの10進数の1つとして定義します。

コードの生成または実行

パーサーがエラーなしでプログラムを正常に解析すると、コンパイラーによる処理が容易な内部表現でプログラムが存在します。現在、内部表現からマシンコード(またはJavaバイトコード)を生成したり、内部表現を直接実行したりするのは比較的簡単です。前者を行う場合、コンパイルしています。後者の場合、解釈について話します。

JavaCC

JavaCCは無料で入手でき、パーサジェネレータです。プログラミング言語の文法を指定するためのJava言語拡張機能を提供します。JavaCC当初はSunMicrosystemsによって開発されましたが、現在はMetaMataによって保守されています。他のまともなプログラミングツールと同様に、JavaCC実際にはJavaCC入力形式の文法を指定するために使用されました。

さらに、JavaCCEBNFと同様の方法で文法を定義できるため、EBNF文法をJavaCC形式に簡単に変換できます。さらに、JavaCCはJavaで最も人気のあるパーサジェネレータでJavaCCあり、開始点として使用できる事前定義された文法のホストがあります。

簡単な計算機の開発

ここで、小さな算術言語を再検討して、を使用してJavaで単純なコマンドライン計算機を構築しJavaCCます。まず、EBNF文法をJavaCCフォーマットに変換し、ファイルに保存する必要がありますArithmetic.jj

オプション{LOOKAHEAD = 2; } PARSER_BEGIN(Arithmetic)public class Arithmetic {} PARSER_END(Arithmetic)SKIP: "\ t" TOKEN:double expr():{} term()( "+" expr()double term():{} "/" term ())* double unary():{} "-" element()double element():{} "(" expr() ")"  

上記のコードは、の文法を指定する方法についてのアイデアを与えるはずですJavaCCoptions上部のセクションは、その文法のオプションのセットを指定します。2の先読みを指定します。追加のオプションJavaCCは、のデバッグ機能などを制御します。または、これらのオプションをJavaCCコマンドラインで指定することもできます。

このPARSER_BEGIN句は、パーサークラスの定義が続くことを指定します。JavaCCパーサーごとに単一のJavaクラスを生成します。パーサークラスを呼び出しますArithmetic。今のところ、必要なのは空のクラス定義だけです。JavaCC後で解析関連の宣言を追加します。クラス定義はPARSER_END句で終了します。

このSKIPセクションでは、スキップする文字を識別します。私たちの場合、それらは空白文字です。次に、TOKENセクションで言語のトークンを定義します。数字と数字をトークンとして定義します。JavaCCトークンの定義と他のプロダクションルールの定義を区別することに注意してください。これはEBNFとは異なります。SKIPそしてTOKENセクションでは、この文法の字句解析を指定します。

次に、expr最上位の文法要素であるの生成ルールを定義します。その定義exprがEBNFの定義とどのように著しく異なるかに注意してください。何が起こっていますか?さて、上記のEBNF定義は、同じプログラムの複数の表現を許可するため、あいまいであることがわかります。たとえば、式を調べてみましょう1+2*3。図1のように1+2expryieldingexpr*3に一致させることができます。

または、図2に示すように、最初に結果をに一致2*3させることもできます。expr1+expr

を使用してJavaCC、文法規則を明確に指定する必要があります。その結果、我々は、の定義を抜け出すexpr文法要素を定義する、3つの生産ルールにexprtermunary、とelement。これで、1+2*3図3に示すように式が解析されます。

コマンドラインから実行JavaCCして、文法を確認できます。

javacc Arithmetic.jj Javaコンパイラコンパイラバージョン1.1(パーサジェネレータ)Copyright(c)1996-1999 Sun Microsystems、Inc。Copyright(c)1997-1999 Metamata、Inc。(ヘルプの引数なしで「javacc」と入力)ファイルからの読み取りArithmetic.jj。。。警告:オプションLOOKAHEADが1より大きいため、先読み妥当性チェックが実行されていません。オプションFORCE_LA_CHECKをtrueに設定して、チェックを強制します。0個のエラーと1個の警告で生成されたパーサー。

以下は、文法定義に問題がないかチェックし、Javaソースファイルのセットを生成します。

TokenMgrError.java ParseException.java Token.java ASCII_CharStream.java Arithmetic.java ArithmeticConstants.java ArithmeticTokenManager.java 

これらのファイルを一緒に使用して、Javaでパーサーを実装します。Arithmeticクラスのインスタンスをインスタンス化することにより、このパーサーを呼び出すことができます。

public classArithmeticはArithmeticConstantsを実装します{publicArithmetic(java.io.InputStream stream){...} public Arithmetic(java.io.Reader stream){...} public Arithmetic(ArithmeticTokenManager tm){...} static final public double expr()throws ParseException {...} static final public double term()throws ParseException {...} static final public double unary()throws ParseException {...} static final public double element()throws ParseException {。 ..} static public void ReInit(java.io.InputStream stream){...} static public void ReInit(java.io.Reader stream){...} public void ReInit(ArithmeticTokenManager tm){...} static final public Token getNextToken(){...} static final public Token getToken(int index){...} static final public ParseException generateParseException(){.. ..} static final public void enable_tracing(){...} static final public void disable_tracing(){...}}

このパーサーを使用する場合は、コンストラクターの1つを使用してインスタンスを作成する必要があります。コンストラクタは、どちらかに合格することができInputStreamReaderまたはArithmeticTokenManagerプログラムのソースコードのソースとして。次に、言語の主要な文法要素を指定します。次に例を示します。

算術パーサー= new Arithmetic(System.in); parser.expr();

ただし、ここでArithmetic.jjは文法規則のみを定義しているため、まだ何も起こりません。計算を実行するために必要なコードはまだ追加されていません。そのために、文法規則に適切なアクションを追加します。Calcualtor.jjアクションを含む完全な計算機が含まれています:

options { LOOKAHEAD=2; } PARSER_BEGIN(Calculator) public class Calculator { public static void main(String args[]) throws ParseException { Calculator parser = new Calculator(System.in); while (true) { parser.parseOneLine(); } } } PARSER_END(Calculator) SKIP :  "\t"  TOKEN:    void parseOneLine(): { double a; } { a=expr()  { System.out.println(a); } |  |  { System.exit(-1); } } double expr(): { double a; double b; } { a=term() ( "+" b=expr() { a += b; } | "-" b=expr() { a -= b; } )* { return a; } } double term(): { double a; double b; } { a=unary() ( "*" b=term() { a *= b; } | "/" b=term() { a /= b; } )* { return a; } } double unary(): { double a; } { "-" a=element() { return -a; } | a=element() { return a; } } double element(): { Token t; double a; } { t= { return Double.parseDouble(t.toString()); } | "(" a=expr() ")" { return a; } } 

The main method first instantiates a parser object that reads from standard input and then calls parseOneLine() in an endless loop. The method parseOneLine() itself is defined by an additional grammar rule. That rule simply defines that we expect every expression on a line by itself, that it is OK to enter empty lines, and that we terminate the program if we reach the end of the file.

元の文法要素の戻り値の型をreturnに変更しましたdouble。解析した場所で適切な計算を実行し、計算結果をコールツリーに渡します。また、文法要素の定義を変換して、結果をローカル変数に格納しました。たとえば、をa=element()解析しelement、結果を変数に格納しますa。これにより、右側のアクションのコードで解析された要素の結果を使用できるようになります。アクションは、関連する文法ルールが入力ストリームで一致を検出したときに実行されるJavaコードのブロックです。

電卓を完全に機能させるために追加したJavaコードがいかに少ないかに注意してください。さらに、組み込み関数や変数などの機能を追加するのも簡単です。