JavaCC 実習レポート課題について以下の実習のために コンパイラのページ http://www.info.kindai.ac.jp/compiler/ から javacc.zip をダウンロードしてください javacc.zip は以下のファイルから成ります javacc/ sample0.k, sample1.k, samplell2.k : k 言語の例プログラム sample0.asm, sample1.asm, samplell2.asm : *.k のコンパイル後のアセンブラコード vsm : vsm インタプリタ ( システムプロジェクト I で配布しているものと同一 ) sampleexp.txt : calc.jj 用の数式例 kc/ : 構文解析器生成用ファイル一式 parser.jj, parsercode.jj, parsercodell2.jj :.jj ファイル Parser.java, ParserCode.java, ParserCodeLL2.java : 生成された Java プログラム Instruction.java, Operator.java, PseudoIseg.java, Type.java, Var.java, VatTable.java : システムプロジェクト I で配布しているものと同一 calc/ : 計算機生成用ファイル一式 calc.jj :.jjファイル Cals.java : 生成された Java プログラム JavaCC とは JavaCC は 再帰下降型構文解析する Java プログラムを生成する構文解析器生成器です マイクロ構文 マクロ構文を入力として与えると字句解析器や構文解析器を自動で生成してくれます 字句解析部 + 構文解析部の マイクロ構文 マクロ構文を記述 Java プログラム xxx.jj JavaCC yyy.java JavaCC でできること 字句解析系 マイクロ構文から有限オートマトンの作成 nexttoken() メソッドの作成 構文解析系 マクロ構文が LL(k) 文法かを判定 First 集合を求める nexttoken() メソッドの呼び出し トークンの一致判定 JavaCC でできないこと 構文解析系 左再帰性の除去 左括り出し コード生成系 全て 最適化系 全て 1
JavaCC のインストール JavaCC は https://javacc.org/ からダウンロードできます Mac へのインストールなら MacPort を使うのが楽です 詳細はコンパイラのページを見てください なお 情報学科指定ノート PC には JavaCC はインストール済みです JavaCC の入力 JavaCC の入力はマイクロ構文規則 マクロ構文規則を記述した.jj ファイルです 以下ではコンパイラのページにある parser.jj および parsercode.jj を例に挙げて説明します JavaCC による jj ファイルのコンパイル端末上で $ javacc jjfile を実行すれば.jj ファイルから Java ファイルが生成されます Java ファイルは通常通り javac でコンパイルし java で実行できます 例えば parser.jj の場合以下の手順でコンパイルできます 以下では parser.jj は ~/javacc/kc に sample0.k は ~/javacc にあるとします $ cd ~/javacc/kc $ javacc parser.jj Java Compiler Compiler Version 5.0 (Parser Generator) : Parser generated successfully... $ cd.. $ javac kc/parser.java $ java kc.parser sample0.k finished javacc により parser.jj から Parser.java が生成されます ( 同時に TokenMgrError.java 等のファイルも生成されます ) 生成された Parser.java を javac でコンパイルし sample0.k を入力として実行すれば sample0.k が構文解析できます (parser.jj は構文解析のみで parsercode.jj はコード生成も含んでいます ) 2
マイクロ構文の記述.jj ファイル中で トークンは TOKEN : < トークン名 : 生成規則 > で定義します (parser.jj の 94~116 行目参照 ) 以下に例を上げます TOKEN : <ADD: + > <INC: ++ > <INTEGER: 0 ([ 1-9 ]([ 0-9 ])*)> <IF: "if"> <WHILE: "while"> <NAME : ([ a - z ] [ A - Z ])([ 0-9 ] [ a - z ] [ A - Z ])*> ()* は 0 回以上の繰り返しを表します (EBNF 記法の と同じ ) ある文字列が複数のトークンとマッチする場合は最長一致に従います 例では ++ は INC となります また 文字数が同じ場合は 先に書いてあるものにマッチします while は WHILE と NAME にマッチしますので 先に書いてある WHILE と見做されます 空白は SKIP : < 生成規則 > で定義されます (parser.jj の 75~83 行目参照 ) ~[*] は * 以外を表します 例では // で始まり n, r 以外の文字が 0 個以上並び n, r で終わる文字列は空白 ( ラインコメント ) となります SKIP : < t n r > < // (~[ n, r ])* [ n, r ]> 表記法 意味 注記 abc 文字列 abc α β γ αまたはβまたはγ [ a ] a ([] は文字クラス ) [] 内は文字のみ [ a, b, c ] a または b または c, は [] 内のみ ~[ a, b, c ] a,b,c 以外 ~[] 任意の文字 [ a - z ] 小文字 - は [] 内のみ [ 0-9 ] 数字 - は [] 内のみ (α)? αが 0 回または 1 回 () は省略不可 (α)* αが 0 回以上 () は省略不可 (α)+ αが 1 回以上 () は省略不可 3
マクロ構文の記述 JavaCC では マクロ構文の記述はトークンを並べるだけです 例えば <If> ::= if ( <Exp> ) <State> に対するマクロ構文の定義は以下のように記述されます (parser.jj の 157~161 行目参照 ) void If() : if ( Exp() ) State() 同様に <State> ::= <If> <While> <Output> <Assgn > に対するマクロ構文は以下のように記述されます (parser.jj の 148~152 行目参照 ) void State() : If() While() Output() Assgn() トークンの一致判定や各非終端記号に対する First 集合の計算は JavaCC が自動でしてくれます 表記法 意味 注記 <ID> 終端記号 <ID> 字句解析部で定義 abc 終端記号 abc 字句解析部で定義 name() 非終端記号 αβ 連節 [α] αが 0 回または 1 回 字句解析部と異なる (α)? αが 0 回または 1 回 () は省略不可 (α)* αが 0 回以上 () は省略不可 (α)+ αが 1 回以上 () は省略不可 4
コード生成部の記述残念ながら JavaCC ではコード生成まではしてくれません 生成したいコードは.jj ファイルの各非終端記号の解析部分に記述する必要があります 例えば非終端記号 <A> に対するコードは以下のように終端記号 非終端記号の後の 内に記述されます <A> ::= token1 <B> token2 <C> token3 void A() : <A> に関する最初の処理を行う Java コード token1 token1 を処理する Java コード B() <B> を処理する Java コード token2 token2 を処理する Java コード C() <C> を処理する Java コード token3 token3 を処理する Java コード 内に記述された Java コードは 生成された Java プログラムの <A> を解析する部分に埋め込まれます parser.jj にコード生成を加えたものが parsercode.jj です 例えば if 文に対するコードは以下のように記述されます (parsercode.jj の 172~182 行目参照 ) void If() : into beqaddr, stlastaddr; if ( Exp() beqaddr = iseg.appendcode (Operator.BEQ); ) State() stlastaddr = iseg.getlastinstructionaddress(); iseg.replacecode (beqaddr, stlastaddr+1); 上記のコードを加えることにより if 文解析時に BEQ 命令が ISeg に詰まれます 5
トークンデータの取り出し JavaCC では トークンデータは Token クラスで管理されます 以下に Token クラスの UML を示します Token # トークン処理部 + begincolumn : int # トークンの先頭文字の列番号 + begnline : int # トークンの先頭文字の行番号 + endcolumn : int # トークンの末尾文字の列番号 + endline : int # トークンの末尾文字の行番号 + image : String # トークンの文字列表現 + kind : int # トークンの種類 + next : Token # 次のトークン + specialtoken : Token # 次の特殊トークン + Token() # コンストラクタ + newtoken (ofkind : int) : static Token # 新規トークン生成 + tostring() : String # image を返す この中でよく使用されるのが image フィールドです ここにはトークンの文字列がその まま入っています 例えば <WHILE> にマッチしたトークンには while が <INTEGER> にマッチしたトークンには 123 という文字列が入ります 構文規則にマッチしたトークンデータは以下のように記述すれば Token 型変数 token に代入できます token = <NAME> <NAME> の処理 上記の例では 読み込み中のトークンが <NAME> にマッチした場合 token に値が代入されます トークンデータから変数名を取り出したいのなら token = <NAME> String name = token.image; と書けばできますし 整数値を取り出したいのなら token = <INTEGER> int value = Integer.parseInt (token.image); と書けばできます 6
以下に <Facter> ::= NAME INTEGER に対するコードの例を挙げます (parsercode.jj の 255~268 行目参照 ) void Factor() : int val, addr; String name; token = <NAME> name = token.image; addr = vartable.getaddress (name); iseg.appendcode (Operator.PUSH, addr); token = <INTEGER> val = Integer.parseInt (token.image); iseg.appendcode (Operator.PUSHI, val); コード生成部を作るには システムプロジェクト I で作ったのと同じように変数表の管理や Iseg へのコード出力 出力ファイルの書き出し等が必要です parsercode.jj では VarTable.java や PseudoIseg.java を使用してこれらの処理を行っています 7
出力されたアセンブラの実行出力されたアセンブラは vsm インタプリタで実行できます 例えば parsercode.jj で生成した ParserCode.java を用いて sample0.k のコンパイル 実行は以下の手順でできます $ cd ~/javacc/kc $ javacc parsercode.jj $ cd.. $ javac kc/parsercode.java $ java kc.parsercode sample0.k finished $ cat OpCode.asm PUSHI 0 INPUT ASSGN REMOVE PUSH 0 BEQ 10 PUSH 0 PUSHI 2 MUL OUTPUT HALT $./vsm 2 4 javacc により parsercode.jj から ParserCode.java が生成されます ParserCode.java を javac でコンパイルし sample0.k を引数として実行すると アセンブリコードが OpCode.asm に出力されます 8