水島宏太
　筑波大学第三学群情報学類を卒業したのち、現在は、筑波大学大学院システム情報工学研究科コンピュータサイエンス専攻博士後期課程3年。プログラミング言語や処理系に強い興味を持っている。現在の研究テーマは、プログラミング言語の構文解析アルゴリズム。Scala勉強会を不定期で行うなど、研究の合間にScalaの普及活動を行っている。

　Scalaにはパーザコンビネータライブラリという、構文解析を行うための専用ライブラリが存在します。パーザコンビネータライブラリを使うことで、特定の用途に特化した設定ファイルやDSLのパーザを手書きで書くよりも簡単に書けるようになります。

　本記事では、Scalaのパーザコンビネータライブラリの基本的な使い方から、パーザコンビネータを使ったJSONのサブセットのパーザの実装までを解説します。構文解析の実装手法に関する知識は前提としませんが、構文解析とはどのようなものか、という事に関してはおおまかに知っていることを前提とします。

パーザコンビネータとは

　誤解を恐れずに非常におおざっぱに言ってしまうと、パーザコンビネータとは、（プログラミング言語や設定ファイルなどの）構文解析を簡単に行うためのライブラリの一種です。yaccやJavaCC、ANTLRなどのパーザジェネレータをご存じの方に対しては、パーザジェネレータの文法定義ファイルを専用の言語ではなく汎用のプログラミング言語で書くためのライブラリというとわかりやすいかもしれません。

何故パーザコンビネータを使うのか？

　yaccやJavaCCなどのパーザジェネレータをご存じの方は、何故(yacc/JavaCC/...)があるのにパーザコンビネータなどというものを使う必要があるのか、と思われたかもしれません。実際のところ、一般に、パーザコンビネータによって生成されたパーザの速度はパーザジェネレータによって生成された速度には及びません(もちろん、実装にもよりますが…)。また、(単純な文法を表現する場合の)簡潔さも劣る傾向があります。そのようなデメリットを背負ってまでパーザコンビネータを使うメリットは何でしょうか？筆者の考えでは、パーザジェネレータではなくパーザコンビネータを使うメリットは大きく分けて二つあると思います。

拡張性

　メリットの一つ目は拡張性です。例えば、最近のスクリプト言語でよく見られる、配列リテラルの文法を表現したいとします(配列リテラルの文法は、"[","]"で囲まれており、カンマを挟んで任意個の式が並べられているものとします)。JavaCCを使う場合、そのような文法を次のように書くことができます(リスト1)。

リスト1●JavaCCによる配列リテラルの表現
Expression[] arrayLiteral() :{...}{
    "[" [expression() ("," expression())*] "]" { ... }
}
Expression expression() :{...}{...}

　JavaCCの細かい文法に関しては解説しませんが、arrayLiteral()という何かが配列リテラルの文法を表現しており、expression()という何かが式の文法を表現していると思ってください。ここで、「カンマを挟んで任意個の式が並べられている」という部分は、[expression() ("," expression())*]と表現されているのですが、このような「Ａを挟んで任意個のＢが並ぶ」というパターンは、プログラミング言語の違いを超えて頻出します。しかし、JavaCCは、そのようなパターンを表現するための方法を提供していないため、同じパターンが現れるたびに同じコードを書く必要があります。

　では、そのための演算子をJavaCCの作者にお願いして追加してもらったとしたらどうでしょうか。しかし、JavaCCの作者はあらかじめどのようなパターンが文法の定義において頻出するかを完璧に予測することはできませんし、あらゆるパターンにその都度対応しようとすると、JavaCCの文法が際限なく肥大化することになります。

　一方、Scalaのパーザコンビネータでは、同様の文法を次のように表現することができます(リスト2)。

リスト2●Scalaのパーザコンビネータによる配列リテラルの表現
val expressions = "[" ~ repsep(expression, ",") ~ "]"
val expression = ...

　JavaCCバージョンと比べて、コードの重複が減ってより簡潔になっているのがわかると思います。ここで、repsep(expression, ",")というメソッド呼び出しによって、「カンマを挟んで任意個の式が並べられている」という文法が表現されていますが、repsepというメソッドがあらかじめパーザコンビネータライブラリに用意されているという事自体はどうでもよい(いや、ライブラリの使い勝手という面からすればどうでも良くは無いのですが)ことです。

　重要なのは、repsepは単なるScalaのメソッドに過ぎず、その気になればユーザーが自分自身でrepsepと同じはたらきをするメソッドを定義できるということです。パーザコンビネータライブラリにおける、一見組み込みっぽい演算子は、単にScalaの標準ライブラリ開発者によってあらかじめ定義されているのでユーザーがあらためて定義しなくても良いというだけであって、それ以外の点は通常のメソッドと全く同じです。