こんにちは、Sablecc
2007年2月11日
最近、SableCCを少し試してみました。「Hello World」スタイルのパーサーを動かすのに少し手間取ったので、動かすために何をしたかについてのメモをここに残しておきたいと思います。これが最良の方法だとは言いませんが、もしあなたが試してみたいと思っているなら、役に立つかもしれません。
SableCCは、Java環境向けのコンパイラコンパイラツールです。LALR(1)文法を処理します（文法カテゴリーを覚えている人のために）。言い換えれば、ボトムアップパーサーです（トップダウンのJavaCCやAntlrとは異なります）。
ほとんどのコンパイラコンパイラツールと同様に、文法ファイルで言語の文法を定義し、コンパイラコンパイラを実行して、この言語のパーサーを生成します。これはhello-worldの例なので、私の言語はコンパイラコンパイラを動かすための最小限のものです。言語は、このようなアイテムのリストです。
item camera item laser
ここで、「item」はキーワードであり、2番目の単語は名前です。パーサーがこれを、アイテムのリストを含むConfigurationクラスのインスタンスに変換することを望みます。
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"));
}
もちろん、このようなケースでコンパイラコンパイラを使用することは完全にやりすぎですが、hello-worldの例のポイントは、基本的なことが動作する状態で、興味深いケースに進むことができるように環境を動作させることです。新しいテクノロジーを試すときは、常に、興味深い側面に深く入り込む前に、まずこのようなことを試してみるのが好きです。
コンパイラコンパイラを使用すると、ビルドプロセスが少し複雑になります。最初に文法ファイルに対してコンパイラコンパイラを実行してパーサーを生成し、次にカスタムコードと生成されたパーサーの両方をコンパイルして全体的なプログラムを作成し、次に実行（およびテスト）する必要があります。したがって、この時点では、IntelliJ内ですべてを実行することはできず、実際にはantファイルを作成する必要があります。antファイルを作成するのは久しぶりだったので、ant言語の使い方を思い出すのに少し時間がかかりました。SableCCを実行するために、Javaタスクを使用しました。
<property name = "gendir" value = "gen"/>
<target name = "gen" >
<mkdir dir="${gendir}"/>
<java jar = "lib/sablecc.jar" fork = "true" failonerror="true">
<arg value = "-d"/>
<arg value = "${gendir}"/>
<arg value = "catalog.sable"/>
</java>
</target>
コードをgenディレクトリに生成して、srcおよびtestディレクトリに自分で記述したコードと分離します。次に、javacタスクでそれらをすべて一緒にコンパイルします。
<property name = "builddir" value = "classes/production/sable"/>
<path id="classpath">
<fileset dir = "lib">
<include name = "*.jar"/>
</fileset>
<pathelement path = "${builddir}"/>
</path>
<target name = "compile" depends = "gen, copyDats">
<mkdir dir="${builddir}"/>
<javac destdir="${builddir}" classpathref="classpath">
<src path = "src"/>
<src path = "${gendir}"/>
<src path = "test"/>
</javac>
</target>
コンパイルだけでなく、パーサー用の2つのデータファイルもビルドディレクトリに移動する必要があります。データには、パーサーと字句解析器に使用されるテーブルが含まれています。ビルドディレクトリは私が持っている方法でネストされているため、IntelliJとうまく連携します。（テストも別の出力ディレクトリに分離する必要があるはずですが、怠惰でした。）
<target name = "copyDats">
<mkdir dir="${builddir}"/>
<copy todir = "${builddir}">
<fileset dir = "${gendir}" includes = "**/lexer.dat"/>
<fileset dir = "${gendir}" includes = "**/parser.dat"/>
</copy>
</target>
次に、テストを実行するためのテストタスクがあります。
<target name = "test" depends="compile">
<junit haltonfailure = "on">
<formatter type="brief"/>
<classpath refid = "classpath"/>
<batchtest todir="${builddir}" >
<fileset dir = "test" includes = "**/*Tester.java"/>
</batchtest>
</junit>
</target>
パーサーを起動して動作させるには、SableCCの文法構文を使用して、簡単な言語の文法を定義する必要があります。
Package catalogParser;
Tokens
itemdef = 'item';
string = ['a' .. 'z'] +;
blank = (' ' | 13 | 10)+;
Ignored Tokens
blank;
Productions
configuration =
item *
;
item =
itemdef string
;
ほとんどのコンパイラコンパイラと同様に、SableCCは字句解析器とパーサーに作業を分割します。字句解析器は文字を読み込み、文法ファイルのTokensセクションで定義されているように、それらをトークンにチャンク化します。このケースでは、非常にシンプルです。文字列は小文字で、キーワードitemはそれ自体のトークンです。また、空白の空白を定義し、Ignores句で字句解析器にそれを破棄するように指示します。
次に、字句解析器はitemdefとstringのトークンのストリームをパーサーにフィードします。パーサーは、これに対処するために2つの生成規則を使用します。構成を複数のアイテムとして記述し、各アイテムをitemdefと文字列（その名前）として記述します。
これは入力の文法を定義しますが、入力をどのように構成オブジェクトとアイテムオブジェクトに変換するかについては何も述べていません。これを行うには、解析した内容と作成したいオブジェクト間のマッピングを行うコードをいくつか記述する必要があります。ほとんどのコンパイラコンパイラでは、文法にアクションを埋め込むことでこれを行います。ただし、SableCCは別の方法で動作します。自動的に構文木を作成し、この構文木をウォークするためのビジターを提供します。次に、ビジターをサブクラス化して、興味深いことを行うことができます。この場合、構文木をウォークするときに、構文木の各アイテムノードを取得し、それをモデル内の実際のアイテムに変換します。
public class CatalogParser extends DepthFirstAdapter {
private Configuration result;
public void outAItem(AItem itemNode) {
System.out.println("found item");
result.addItem(new Item(itemNode.getString().toString().trim()));
}
構文木は、文法を木で作成されたオブジェクトにバインドするために命名規則を使用します。したがって、文法は、文法内のアイテム生成規則と一致するようにAItemというノードを作成します。ビジターがアイテムノードを離れるときにメソッドoutAItemが呼び出され、アイテム上にあるもの、この場合は基になる文字列トークンにアクセスできるようになります。次に、その文字列を名前として使用して、モデルにアイテムを作成できます。
最後のコードは、ファイルをパーサーで実行するためのもので、カタログパーサーをコマンドオブジェクトにすることで実現します。
public static Configuration parse(Reader input) {
Configuration result = new Configuration();
new CatalogParser(input, result).run();
return result;
}
public CatalogParser(Reader input, Configuration result) {
this.input = input;
this.result = result;
}
public void run() {
try {
createParser(input).parse().apply(this);
} catch (Exception e) {
throw new RuntimeException(e);
}
}
private Parser createParser(Reader input) {
return new Parser(new Lexer(new PushbackReader(input)));
}
これが、起動して動作させるための基本です。今のところ、私はさらに深く掘り下げていないので、SableCCについての私の考えはやや予備的なものですが、このブログの全体のポイントは、未完成の考えを書き出すことです。
SableCCは少し使いにくいです。著者の論文以外にドキュメントはほとんどありません。幸いなことに、論文は私が遭遇した他の多くの論文よりもはるかに理解しやすかったので、物事を動かす方法を理解することができました。作業中に文法を間違えてしまい、診断が難しいことがわかりました。エラーメッセージはあまり情報提供的ではなく、生成されたパーサーコード内でデバッガーとプリントステートメントに頼りました。幸い、問題はトークン化にあったため、字句解析器からの出力を見ることで自分のミスに気づきました。LALRパーサーは追跡するのが非常に難しいことで知られているため、そこに深く入り込まなくてもよかったことを嬉しく思います。Antlrはこの点でより優れています。再帰下降パーサーは追跡しやすく、開発中のAntlrの本は、それを調査するのに非常に役立つはずです。
これまでのところ、パーサーアクションを削除して自動的に構文木を生成するというアプローチには納得がいきません。構文木であるため、何か便利なことを行うには、それをウォークする必要があります。Nat Pryceは、最新のSableCCの木変換ルールについて教えてくれました。これは、構文木ではなく抽象構文木を定義するため、より便利に見えます。ドメインモデルでオブジェクトを作成するためにウォークする必要はまだありますが、ウォークするのは簡単です。（最新バージョンのAntlrにも同様の機能があります。）木ウォークの利点の1つは、木ウォーカーに変更を加える場合、再生成する必要がないため、IntelliJに留まることができることです。ただし、Antlrには、IntelliJにプラグインされるAntlrWorksがあり、非常に見栄えがします。