数理情報工学演習第二 A（ 4年生2004年夏学期）
YaccとLexとについて．
◆注目！◆
当日の授業の際に十分伝えられなかったところがあるので，このページに徐々に記載していきます．（インストールやら使い方やらにこんなに時間がかかってしまうとは…）
日程
6月 4日金曜日13時から16時まで，工学部6号64講義室にて．
レポートの提出は， 6月30日までに筧宛にemailで．
概要
構文解析器生成器の"Yacc"と字句解析器生成器の"Lex"とを使った演習を行ないます．3年生の時の演習ではJavaを使っていたことから，皆さんJavaに慣れていると思います．ですので，この演習ではJava上で動作するCUPとJLexとを使うことにします．これらは"Tiger Book"で有名なA.W. Appel教授（Princeton大学）のページで公開されています．
課題
課題1か課題2かのどちらかをemailで筧宛に提出して下さい．期限は 6月30日までとします．ちなみに，「私は別の言語でやりたい！」という場合は，それでもOKです．
- 課題1
- MinimalExampleを拡張して，例えば次のようなことができるようにしなさい．
- 小数点表記も扱えるようにする
- 演算子の種類を増やす
- 符号が使えるようにする
- 変数が扱えるようにする
- 課題2
- 正規表現式を受け取ってNFAを生成し，その後に入力される文字列が受理されるかどうかを判定するプログラムを作りなさい．また余力のある人は，生成されたNFAをDFAへと変換し，それを使って受理されるかどうかを判定させなさい．
ちなみに．サンプルとして私が作成したものを少々変更すれば課題1はできるので，課題2に挑戦して欲しいと思っています．
使い方（サンプルプログラム"minimal"）
minimal.tar.gzを使って説明します．"CLASSPATH"を設定する必要がある点に注意して下さい．さきほどのファイルを展開してみましょう．"MinimalExample"というディレクトリが作成され，その中にファイルが置かれます．そこに移動しましょう．
$ tar zxf minimal.tar.gz; cd MinimalExample
"README"ファイルには"java JLex.Main minimal.lex"とあります．これで動作するようにするには，さきほどコンパイルしたJLexおよびCUPの中のクラスファイルが参照できるようにしておく必要があります．環境変数"CLASSPATH"に，今回の演習のディレクトリを含めて下さい（上記の例であれば"200406enshu"までの完全なパスです）．代わりに，
$ javac -classpath .../200406enshu:$CLASSPATH ...
$ java -classpath .../200406enshu:$CLASSPATH ...
というように直接指定することもできます．
まずminimal.lexを処理し，ついでminimal.cupを処理します．パスが適切に設定されていれば次のように打ち込むことで処理できます．
$ java JLex.Main minimal.lex
$ java java_cup.Main minimal.cup
lexの処理で"minimal.lex.java"が，cupの処理で"parser.java"と"sym.java"とが生成されます．"README"では"minimal.lex.java"のファイル名を変更する操作が書かれていますが，特にその必要はありません．生成されたjavaのファイルをコンパイルし，生成されるディレクトリ"Example"の下にできるクラスファイルを使って以下のように実行します．
$ javac -d . *.java
$ java -classpath .:$CLASSPATH Example.parser
使い方（cup = yacc その1）
では実際にファイルの中身に目を通してみましょう．以下では補助ファイル群から入手できる"calculator.cup"，"calculator.lex"を対象として話しを進めます．
構文解析を行なうための"calculator.cup"を見てみましょう．最初の十行ほどを飛ばすと，規則の中で使われる終端記号（terminal symbols）と非終端記号（non-terminal symbols）とが定義されているのがわかります．それぞれterminal，non terminalで始まる行となっています．なお，これらの記号が返す値（の型），というのが定義できます．VARであれば文字列（String），exprであれば倍精度（Double）というように．
次いでprecedenceによって出現する演算子の結合の強さが示されます．下に書かれるものほど結合が強いものとみなされます．PLUSよりTIMESの方が結合が強い，というのは納得ができると思います．
実際の構文規則がその後に続きます．構文としてどのような構造を取り得るのか，というだけではなく，その構造であることがわかった時にどのような計算を行なうのか，を記述することができます．その計算の部分は{: :}で括られた中に記述します．その構文の部分木が返す値を使いたい場合は，構文規則の終端および非終端記号にラベルを付けることで参照できます．
42行目を見てみて下さい．statementはexpr_partとSEMIという構文規則のみをとることがわかります．その際，expr_partの返す値（non terminalでの定義から，Doubleを返すことになっています）をeとして参照し，その値を印刷している，というのがわかると思います．
使い方（cup = yacc その2）
java_cup.Mainでcupのファイルを処理した時に，どのようなjavaのファイルが生成されるのかを見てみましょう．"parser.java"を見ると，"java_cup.runtime.lr_parser"というクラスを"extends"して"parser"というクラスが定義されています．もしも付加的な情報を持たせたいと思う場合は，この"parser"のクラスおよびコンストラクタを拡張すれば良いわけです．実際，"calculator.cup"ではそのようになっていますよね．
使い方（lex）
今度は，さきほどの "calculator.cup" で "non terminal" として定義されたものが，それでは実際どのような文字列であるのかを指定するのが字句解析器の仕事で， "calculator.lex" によって指定されています．";"という文字であればSEMIというシンボルである，0から9までの文字の1個以上の繰返しであれば，NUMBERというシンボルである，となっています．このうち，NUMBERであれば，実際に値も返す必要がある（値が取り出せないと意味がない）ので，ここではDoubleを返すものとしています．なお，yytext()でその切り出された文字列がStringで返されてきます．
使い方（cup = yacc その3）
補助ファイル群には，"calculator.cup"と同じ動作をする別の構文規則 "calculator2.cup" が置いてあります．ここでは，演算の結合の強さを，precedenceではなく構文規則として記述しています．このような書き方をすることも可能です（私個人は，precedenceを使っては書こうとしないので…）．
環境設定
実際にインストールして動かしてみましょう．それぞれ最新版（CUP 0.10k，JLex 1.2.6），それから動作確認のためサンプルプログラムを入手することになりますが，負担を避けるため一時的にコピーを武市研内に置いておきます（既に消去しました；直接ダウンロードして下さい）ので，そちらから入手して下さい．
現時点で以下のみっつがあることを確認して下さい．
- java_cup_v10k.tar.gz
- Main.java
- minimal.tar.gz
まず，今回の演習に関するディレクトリを作成しましょう．そうしたら，そのディレクトリの下に"JLex"というディレクトリを作ります．Main.javaをそのJLexディレクトリの下に移動して，javacでコンパイルします．
$ mkdir 200406enshu; cd 200406enshu
-- ファイルのダウンロード
$ mkdir JLex; mv Main.java
$ cd JLex; javac Main.java
次はCUPの準備です．演習に関するディレクトリに戻り，java_cup_v10k.tar.gzを解凍・展開します．
$ cd ..
$ tar zxf java_cup_v10k.tar.gz
たくさんのファイルが展開されていると思いますが，ひとまず利用したいのは"java_cup"というディレクトリです．次のようにしてその中身をコンパイルします．これで基本的な準備が終わります．
$ javac java_cup/*.java java_cup/runtime/*.java
補遺
CUPおよびJLexのマニュアルはこちら．
Javaには他にも以下のような構文解析器があります．
| 
