パーサーへの恐怖

2008年5月20日

最近、多くの人々とドメイン特化言語について話をする機会がありますが、外部DSLに対する一般的な反応として、パーサーの作成が難しいという意見をよく耳にします。実際、外部DSLのキャリア構文としてXMLを使用する理由の1つは、「パーサーを無料で入手できる」ということです。しかし、これは私の経験とは一致しません。パーサーはほとんどの人が考えているよりもはるかに簡単に書くことができ、XMLを解析するよりも実際には難しくないと思っています。

証拠もあります。実際には1つのケースだけですが、私の主張を裏付けるものなので、とにかく引用します。著書の入門例を書いたとき、単純な状態マシンを作成するために複数の外部DSLを開発しました。そのうちの1つはXMLを使用し（入門として）、もう1つはAntlrを使用して解析したカスタム構文でした。これらの形式を完全に解析するコードの作成にかかった時間はほぼ同じでした。

XMLパーサーは無料で入手できますが（私はElliotte Rusty Haroldの優れたXOMフレームワークを使用しました）、XMLパーサーの出力は事実上、XML DOM形式の解析ツリーです。それを活用するには、さらに処理する必要があります。DSLに関する私の実践では、明確なセマンティックモデルを中心に構築しています。そのため、この場合の解析の真の出力は、設定された状態マシンモデルです。これを行うには、XML DOMを順に処理するコードを作成する必要があります。これは特に難しいことではありません。特に、XPath式を使用して、DOMの必要な部分を選択できるためです。実際、私はDOMツリーをまったく歩いていません。興味のあるものごとに、XPathクエリを発行し、結果のノードを反復処理して、状態マシンモデルを設定するメソッドがあります。

そのため、XML処理は簡単ですが、存在しないわけではありません。約100行のコードです。数時間かかりました。しばらくXOMを使用していなかったので、少し慣れる必要がありましたが、習得と使用が非常に簡単なライブラリです。

Antlrの処理は驚くほど似ていました。Antlrには、文法ファイルにいくつかの単純なルールを記述してASTを設定できる表記法があります。ASTを処理してセマンティックモデルを設定するコードは、XMLコードと非常によく似ていました。ツリー内の適切なノードをクエリしてから、それらを処理します。文法ファイルを含め、結果のコードは約250行ですが、作成にかかった時間はほぼ同じでした。以前何度か使用したことがあったため、Antlrのほとんどは既に知っていましたが、ツリー構築機能は実際に使用したことがありませんでした。（興味があれば、著書の進行中の作業にこの例の解説があります。）

パーサージェネレーターの調査により、多くの人が考えているよりもはるかに簡単に作成できるという事実に慣れてきましたが、XMLの場合よりも実際には遅くないことに気づいたときは驚きました。より慎重に制御された例では、Antlrの例を2番目に作成したため、プログラマーなら誰でも知っているように、2番目の実装では常に処理がはるかに速くなるため、時間がかかることが予想されます。それでも、その差は多くの人が予想しているほど大きくはありません。「パーサー」という言葉が「複雑すぎる」という意味を持つ場合です。

パーサージェネレーターに慣れるには、確かに学習曲線があることは否定できません。文法ファイルと、それらがコードサンプルとどのように相互作用するかについて理解する必要があります。使用できるさまざまな戦略があります（現在、ツリー構築、埋め込み変換、埋め込み解釈と呼んでいるもの）。また、カスタム構文の構文についても考える必要があります。これは、XMLで何かを属性にするか要素にするか疑問に思うよりも多くの決定を伴います。しかし、その曲線は実際にはそれほど高くありません。最新のツールはそれをはるかに簡単にします。Antlrは現在の私のデフォルトの選択肢であり、文法式を調べてASTにどのように解析されるかを確認するのに役立つ非常に優れたIDEが付属しています。ただし、1つのパーサージェネレーターの仕組みを理解すれば、他のパーサージェネレーターを習得するのは難しくありません。

では、なぜDSLのパーサーを作成することに対する不合理な恐怖があるのでしょうか？それは、主に2つの理由に要約されると思います。

大学でコンパイラーの授業を受けていないため、パーサーは怖いと考えている。
大学でコンパイラーの授業を受けているため、パーサーは怖いと確信している。

1つ目は簡単に理解できます。人々は知らないことに対して当然不安を感じます。2つ目の理由が興味深いものです。これは、大学で人々がどのように解析に出会うかに要約されます。解析は通常、コンパイラーの授業でのみ教えられます。そこでは、完全な汎用言語を解析することが前提となっています。汎用言語の解析は、ドメイン特化言語の解析よりもはるかに困難です。少なくとも、文法がはるかに大きく、DSLでは回避できる厄介なしわくちゃが含まれていることが多いためです。

この問題は、解析と出力処理およびコード生成を複雑に絡み合わせたコードを推奨することによってさらに悪化します。私にとって、物事を整理するための鍵は、セマンティックモデルを使用することです。そのため、パーサーはそのモデルを設定すること以外は何もしません。ほとんどの場合、他のOOフレームワークと同様に、そのセマンティックモデルを実行するだけで必要なことができます。ほとんどの場合、コード生成を行う必要はなく、行う場合はセマンティックモデルに基づいて行うため、パーサーから独立しています。文法内にコード生成ステートメントがある場合、物事が密接に結合されすぎていると思います。

人々が外部DSLを効果的に使用するには、汎用言語の解析方法とはまったく異なる方法で教える必要があります。言語と言語のスクリプトの両方のサイズが小さいと、人々が通常解析に抱く懸念事項の多くが変わります。本当に必要な場合を除いて、コード生成を回避することで、複雑さの大部分を解消できます。明確なセマンティックモデルを使用することで、手順をはるかに扱いやすいチャンクに分離できます。

もちろん、問題は、これらのガイドラインに従った記述があまりないことです。（これが、私がこれほど多くの時間を費やしている理由の1つです。）パーサージェネレーターツールのドキュメントを見つけるのは困難です。Terence ParrのAntlrの本のような非常に優れたドキュメントを入手した場合でも、通常は汎用言語の考え方で書かれています。誤解しないでください。Antlrの本は非常に役立つと思っています（Antlrが私のパーサージェネレーターのデフォルトの選択肢である大きな理由です）。しかし、ドメイン特化言語ではなく汎用言語の解析を想定しているため、アプローチが難しくなっていると考えています。

しかし、これらすべてで良いことは、それでもその学習曲線を乗り越えることができるということです。パーサージェネレーターを使用したことがない場合は、試してみることをお勧めします。独自の単純なDSLを作成してみてください。最初にコード生成について心配する必要はありません。通常どおりドメインモデルを作成し、DSLにそれを設定させてください。（HelloAntlrで行ったように）本当にばかげたことから始めて、徐々にそこから積み上げていきます。DSLを使用するいくつかのオープンソースプロジェクトを調べて、何をしているかを確認してください。

私たちがしようとしているのは、コンパイラーでよく使用されるツールですが、コンパイラーとのみ関連付ける聴衆に、それよりもはるかに汎用的なツールを紹介することです。なぜなら、それが常に教えられてきた方法だからです。

-- レベッカ・パーソンズ