Microsoft Word - Javacc.docx

Size: px

Start display at page:

Download "Microsoft Word - Javacc.docx"

ちえこにばし
5 years ago
Views:

1 JavaCC 実習レポート課題について以下の実習のためにコンパイラのページから 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

2 JavaCC のインストール JavaCC はからダウンロードできます 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

3 マイクロ構文の記述.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

4 マクロ構文の記述 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

5 コード生成部の記述残念ながら 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

6 トークンデータの取り出し 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

7 以下に <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

8 出力されたアセンブラの実行出力されたアセンブラは 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

Microsoft PowerPoint - Compiler15note.ppt [互換モード]

Microsoft PowerPoint - Compiler15note.ppt [互換モード] コンパイラ第 15 回コンパイラコンパイラ http://www.info.kindai.ac.jp/compiler 38 号館 4 階 N-411 内線 5459 takasi-i@info.kindai.ac.jp コンパイラ (compiler) コンパイラ原始プログラム (source program) 原始プログラム (source program) を目的プログラム (object