ハローカップ
2007年5月13日
外部ドメイン固有言語のためのパーサジェネレータツールを調べているうちに、HelloAntlrとHelloSableccを試しました。パーサジェネレータを深く見ると、古くからの定番であるlexとyacc（または、そのGNU版であるflexとbison）を避けて通ることはできません。lexとyaccの動作方法を調べたいのですが、私のCの知識は錆びついてしまっています。Erich Gammaが言ったように、私は自分でゴミを出すのが面倒くさくなっているのです。幸運なことに、Java用のyaccのようなシステムの実装があり、まさにそれが必要でした。
Javaの実装は、クラシックなlexとyaccと同様に、2つの独立したツールです。JFlexとCUPです。これらは個別に開発されていますが、連携するためのフックが用意されています。
これまでの私の投稿と同様に、これは単にツールを動作させるための非常にシンプルな例です。私は次のような入力ファイルを受け取ります。
item camera item laser
そして、次のモデルを使用して、それらを構成内のアイテムオブジェクトに変換します。
public class Configuration {
private Map<String, Item> items = new HashMap<String, Item>();
public Item getItem(String key) {
return items.get(key);
}
public void addItem(Item arg) {
items.put(arg.getName(), arg);
}
public class Item {
private String name;
public Item(String name) {
this.name = name;
}
次のテストに合格するようにします。
@Test public void itemsAddedToItemList() {
Reader input = null;
try {
input = new FileReader("rules.txt");
} catch (FileNotFoundException e) {
throw new RuntimeException(e);
}
Configuration config = CatalogParser.parse(input);
assertNotNull(config.getItem("camera"));
assertNotNull(config.getItem("laser"));
}
最初に取り組むべき課題は、ビルドを正常に実行することです。これまでの例と同様に、文法入力ファイルを取得して、lexerとparserをgenディレクトリに生成したいと考えています。これまでの例とは異なり、antで直接これを行うのではなく、antを使用してrubyスクリプトを呼び出します。
--- build.xml
<target name = "gen" >
<exec executable="ruby" failonerror="true">
<arg line = "gen.rb"/>
</exec>
</target>
--- gen.rb
require 'fileutils'
include FileUtils
system "java -cp lib/JFlex.jar JFlex.Main -d gen/parser src/parser/catalog.l"
system "java -jar lib/java-cup-11a.jar src/parser/catalog.y"
%w[parser.java sym.java].each {|f| mv f, 'gen/parser'}
ええ、遠回りだということは承知していますが、多くのソースファイルがあるため、FlexibleAntlrGenerationで採用しているアプローチで生成を行っており、antでも同様に整理する手間をかけたくないのです。
(先日CITCONに参加した際、人々が私が思っていたよりもantに満足していることを知り、驚きました。ひねくれた私は、これはストックホルム症候群だと考えています。たとえひねくれていない時でも、Ravenや、ドキュメントが整備されたBuildRのようなものに注目しています。antを捨て去る準備は万端です。)
CUPは出力ファイルを現在のディレクトリに配置することに気付くでしょう。私はその動作を上書きする方法を見つけることができませんでした。そこで、それらを生成し、別のコマンドで移動させました。
コードを生成したら、antでコンパイルしてテストします。
<target name = "compile" depends = "gen">
<mkdir dir="${dir.build}"/>
<javac destdir="${dir.build}" classpathref="path.compile">
<src path = "${dir.src}"/>
<src path = "${dir.gen}"/>
<src path = "${dir.test}"/>
</javac>
</target>
<target name = "test" depends="compile">
<junit haltonfailure = "on" printsummary="on">
<formatter type="brief"/>
<classpath refid = "path.compile"/>
<batchtest todir="${dir.build}" >
<fileset dir = "test" includes = "**/*Test.java"/>
</batchtest>
</junit>
</target>
lexとyaccは、lexerとparserを異なるファイルに分離します。それぞれが独立して生成され、コンパイル中に結合されます。まずはlexerファイル（catalog.l）から始めます。冒頭で、出力ファイルのパッケージとインポートを宣言します。
package parser; import java_cup.runtime.*;
JFlexは%%マーカーを使用してファイルをセクションに分割します。2番目のセクションは、さまざまな宣言で構成されています。最初のビットは、出力クラスの名前を指定し、CUPとインターフェースするように指示します。
%% %class Lexer %cup
次のビットは、lexerに折りたたまれるコードです。ここで、Symbolオブジェクトを作成する関数を定義します。これもCUPにフックするためです。
%{
private Symbol symbol(int type) {
return new Symbol(type, yytext());
}
%}
SymbolクラスはCUPで定義されており、そのランタイムjarの一部です。シンボルとその位置に関するさまざまな情報を受け取るさまざまなコンストラクタがあります。
次に、単語と空白を定義するためのいくつかのマクロがあります。
Word = [:jletter:]* WS = [ \t\r\n]
最後のセクションは、実際のlexerのルールです。アイテムキーワードを返すものと、単純な単語をparserに返すものを定義します。
%%
"item" {return symbol(sym.K_ITEM);}
{Word} {return symbol(sym.WORD);}
{WS} {/* ignore */}
したがって、lexerはK_ITEMとWORDトークンのストリームをparserに送信します。catalog.yでparserを定義します。ここでも、パッケージとインポート宣言から始まります。
package parser; import java_cup.runtime.*; import model.*;
データを構成オブジェクトに解析しているので、結果を格納する場所を宣言する必要があります。このコードもparserオブジェクトに直接コピーされます。
parser code {: Configuration result = new Configuration(); :}
CUPでは、プロダクションで使用するすべてのルール要素を定義する必要があります。
terminal K_ITEM; terminal String WORD; non terminal catalog, item;
ターミナルはlexerから取得するトークンであり、非ターミナルは自分で構築するルールです。トークンからペイロードを取得したい場合は、その型を宣言する必要があります。したがって、WORDは文字列です。
カタログはアイテムのリストです。antlrやsableccとは異なり、ここではEBNFがないため、item*とは言えません。代わりに、再帰的なルールが必要です。
catalog ::= item | item catalog;
アイテムルール自体には、アイテムを構成に入れる埋め込みアクションが含まれています。
item ::= K_ITEM WORD:w {: parser.result.addItem(new Item(w)); :}
;
ここで注意すべき小さな点は、アクションはparserオブジェクトとは別のクラスに配置されるため、先ほど定義したresultフィールドにアクセスするには、アクションオブジェクトのparserフィールドを使用する必要があることです。また、これ以上進めるようになったら、アクションコードをシンプルに保つためにEmbedmentHelperを使用し始めることにも言及しておく必要があります。
以前にyaccを使用したことがある人は、アクションで$1、$2のyaccで使用される規約の代わりに、ルールの要素にラベルを付けて参照できることに気付くかもしれません。同様に、ルールが値を返す場合、CUPは$$ではなくRESULTを使用します。
lexとyaccの私の記憶は薄れてしまっていますが、これらのツールはそれらを使用するスタイルをかなりよく模倣しているようです。これまでのところ最大の不満はエラー処理であり、antlrよりもはるかに多くの手間がかかりました。今のところの私の感じでは、パーサジェネレータに不慣れな場合は、antlrの方が良い選択肢です（特に書籍があるため）。ただし、lexとyaccに精通している場合は、この2つは、その知識を基に構築するのに十分なほど似ています。