パーサーコンビネータを世界一深く理解できるかも知れない解説 - 第1回

こんにちは、最近はチーフプロダクトオーナー兼アーキテクトをしている @awekuit (赤津) です。
この記事は kubell Advent Calendar 2024(シリーズ1)の3日めの記事です。2日めは奥澤さんのNANDからCPUを作る（前編）でした。

さて、僕は最近業務でコードを書く機会は減りましたが以前メッセージ記法という Chatwork 独自記法のパーサーの刷新を担当しまして、Scala, Scala.js, Kotlin, Swift などでメッセージ記法パーサーを作ったり、パーサーコンビネータライブラリ自体を作ったりしました。
その時得た知見をどこかで発信したいと思いながら時間が取れずに年月経ってしまいましたが、今日は一念発起してアドカレの勢いに乗っかって書いてみようと思います。

書きたいことは山程あるので気持ちを込めて今日は第1回としましたが、第2回があるかは評判次第なところもありますので気に入った方はぜひ SNS などでシェアして貰えればと思います！ 評判が良いと僕も記事書きやすくなるので！ よろしくお願いします！

この記事のゴールと、パーサーコンビネータの強み

今日は「多くの人が」「確信をもって自前のコンビネータを書ける」ようになる事を目指していきます。つまり「ただライブラリを活用する」というレベルより上を目指しますので、すでにライブラリを利用できている方にも役立つかと思います。
また、技術読み物としても、パーサーコンビネータという仕組みを題材にプログラミングのテクニックに様々触れていきます。
そうやって深くいろいろな方向からパーサーコンビネータを理解していき、最終的には様々な構文解析の現場で「打倒、正規表現」が果たされれば良いなと思っています！

・・正規表現は広く普及してますから、構文解析で正規表現を使っている開発現場はあるかと思います。しかし、正規表現は構文解析に向いておらず、たとえば Real world Haskell では「正規表現ではほとんどのプログラミング言語のソースコードが解析できない」と述べられていますね。その点、パーサーコンビネータは構文解析にとても向いています。

しかし、向いていたとしても習得難易度が高いとチームでは採用しづらいですよね。その採用しづらさを少しでも解消すべく、本記事ではとにかく平易な解説で本質をしっかり掴むことを目指しています。すこし説明が冗長で退屈な面もあると思いますが、「パーサーコンビネータってそんなに難しくないからチームメンバー入れ替わっても大丈夫だね」と皆が思えるようになれば良いな、と思っています。

さて、それでは始めていきましょう！ 以下の解説では、「パーサーコンビネータなるものを使うとパーサー同士が合成できるらしい」という噂だけを頼りに、とっても単純な「ifと文字列比較」からスタートして「合成ってなんだろう？ どうしたら出来るんだろう？」をあれこれ考えながら、最終的にパーサーコンビネータにたどり着きます。サンプルコードは、Scala で書かれていますが、Scala 色は抑えたのでぜひ他言語の方も読んでみてください！
(この記事は、暇な時にちょこちょこ書いていたため Scala 2 で書かれています。Scala 3 に慣れてる方は適宜読み替えてください...)

if と文字列比較だけでパースしよう

さて、唐突ですが世の中にはパーサーコンビネータなるものが存在し、それを使うとどうやら「パーサー同士を合成」できるらしいという噂を耳にしたとします。・・しかし、パーサー同士の合成だなんて言われてもどういう事か全く想像がつきませんね。仕方ないので、とりあえず if で文字列比較するだけの単純なパーサーでも書いてみましょう。

まずは、パーサーを作るために何か適当な独自記法をでっちあげてみます。今回は、次のようなアニマル記法を考えてみましょう。

[text:我が家の][cat:Tama][text:は世界一かわいい]

テキストとしてこのように書いて投稿すると、画面上には「我が家の«Tama»は世界一かわいい」のような感じで «Tama» の部分がタマのあられもない画像が差し込まれて表示されるという、そんなサービスのための独自記法です。構文としては、解析しやすいようにブラケット[...]で囲んでタグ名(text, cat)を持たせた単純なものにしています。

さて、今回、我々はこのアニマル記法の解析器(パーサー)の作成を担当します。実際にこのアニマル記法の動物タグ部分を良い感じの画像に差し替える処理は、我々の解析結果に基づいて UI 側で頑張ってもらう事にして、ここでは構文解析だけに着目していきます。

では早速始めましょう！ まずは、アニマル記法の構造をプログラミング言語上で表現するためのクラスを用意しておきます。今はまぁパースした結果を詰めておく入れ物程度に思ってください。

trait Elem
case class Dog(name: String) extends Elem
case class Cat(name: String) extends Elem
case class Text(value: String) extends Elem

Scala に馴染みのない方向けの補足
• Dog, Cat, Text クラスがそれぞれ Elem 型を継承しています

準備はできました。
宣言通り、先程のアニマル記法をまずは if と文字列比較でパースしてみましょう！
次のコードはちょっと長いですが最初の6行読んで貰えば大丈夫です。

def parser(source: String): Elem = {
  // source の先頭5文字が "[dog:" という文字列と一致するかチェック
  if (source.take(5) == "[dog:") {
    // source の先頭5文字を捨ててから、`]` までの文字を抽出
    val name = source.drop(5).takeWhile(_ != ']')
    Dog(name)
  } 
  // 以下同様
  else if (source.take(5) == "[cat:") {
    val name = source.drop(5).takeWhile(_ != ']')
    Cat(name)
  } else if (source.take(6) == "[text:") {
    val text = source.drop(6).takeWhile(_ != ']')
    Text(text)
  } else {
    throw new Exception("Parsing Failed.")
  }
}

Scala に馴染みのない方向けの補足
• source.take(n) は source の先頭から n 文字を取得します
• source.drop(n) は source の先頭から n 文字捨てたものを返します
• source.takeWhile(条件式) は source の先頭から条件を満たす文字かどうかを見ていき、条件を満たした文字をまとめて返します

早速使ってみましょう。

println(parse("[dog:Pochi]"))  // => Dog(Pochi)
println(parse("[cat:Tama]"))   // => Cat(Tama)
println(parse("[text:こんにちは]")) // => Text(こんにちは)

はい、良い感じにアニマル記法がパース出来てますね。単純ですがこれも立派なパーサーです！ dog タグや cat タグが1つしか存在しない場合なら、これで解析できます。

ただ、噂によるとパーサーコンビネータというのは「単純なパーサーを合成して、複雑なパーサーを作り上げる」ことが出来るらしいのです。 ・・これだけ聞くと何故そんな事ができるのかさっぱり想像できませんが、少なくとも今の parser 関数には、dog, cat, text という3つのタグのパース処理がまとめて書かれています。でも我々はこれから「パーサーの合成」というものにチャレンジしたいので、まずはこの3つを別々の「単純なパーサー」として分離してみましょう。そうしてから、それを合成する方法をあとで考えてみることにします。

def dogParser(source: String): Option[Dog] = {
  if (source.take(5) == "[dog:") {
    val name = source.drop(5).takeWhile(_ != ']')
    Some(Dog(name))
  } else {
    None
  }
}

単独の関数に切り出しただけですが、これでdogタグだけのパーサーができました。catParser, textParser もほぼ同じように実装出来るのでコードは省略します。

さて、切り出した単体パーサーですが Option 型を返すようにしてみました。最近は多くの言語に導入されている Option 型ですが、Scala の Option もそれらと同じで値の「あり / なし」を型で表します。あり = Some 型、なし = None 型です。Kotlin, Swift, C# などをお使いの方は Nullable な型と解釈して差し支えありません。

ここではパースに成功したら Some を、失敗したら None を返す事で、パースの成否を型で表すのに使っています。ちょっと手抜きですが今はこれでよしとします。

では、これら単純なパーサーを組み合わせて先ほどの parser 関数のように dog も cat も text もパースできる allPaserを作ってみましょう！ まずは先程同様に if ~ else で繋げてみます。

def allParser(source: String): Elem = {
  if (dogParser(source).isDefined) {
    dogParser(source).get
  } else if (catParser(source).isDefined) {
    catParser(source).get
  } else if (textParser(source).isDefined) {
    textParser(source).get
  } else {
    throw new Exception("Parsing Failed.")
  }
}

• isDefined は値が Some なら true を、None なら false を返します
• get は値が Some なら中身を返し、None なら例外を投げます

一応できました！
細かいことに目を瞑れば「単純なパーサーを用意して」「それを合成して複雑なパーサーを作る」という流れは実現できています。
実はこの1歩はすでに重要な1歩なので、少しじっくりこの実装について考察してみましょう。

まず、ポイントは「if ~ else が合成の役目を果たしている」という事です。
dogParser と catParser と textParser はそれぞれ独立しています。そんな独立したパーサー同士をくっつけて、dog も cat も text もパースできる複雑な1つのパーサーを生み出したのだから、これは立派な合成です。if は条件分岐の道具ですが、このような見方をすれば合成の道具とも言える訳ですね。

ただ、まだ「合成」というパワーワードが眩しくて馴染めないかも知れないですね？ ということで、もっと合成っぽさを醸し出すことを考えてみましょう！ たとえばこうです。

def allParser(source: String): Option[Elem] = {
  dogParser(source).orElse(catParser(source)).orElse(textParser(source))
}

allParser(source).getOrElse(throw new Exception("Parsing Failed."))

if ~ else の代わりに Scala の Option 型に備わる orElse メソッドを使ってみました。Scala でもややマイナー(？)なこの orElse メソッドは次のように実装されています(やや簡略化してます。本物はこちら)

def orElse[B >: A](alternative: Option[B]): Option[B] = {
  if (isEmpty) alternative else this
}

実際の挙動は次の通りです。

Some(1).orElse(Some(2)) // => Some(1)
Some(1).orElse(None)    // => Some(1)
None.orElse(Some(2))    // => Some(2)
None.orElse(None)       // => None

※ Scala ではドットとカッコを無くして Some(1) orElse Some(2) と書く事ができますがここでは他言語に寄せています

つまり orElse メソッドは「自身がSomeなら自身を返し、そうでないなら次の Option に委ねる」という動きをします。

ところでこれ、もっと見方を広げて我々が知る概念に例えると failover に似ています。噛み砕いて言うと「俺はもう駄目(None)だから、あとはお前に任せた」ということですね。もしくは「俺が戦場から生きて帰れなかったら(orElse)、俺のあとはお前が引き継ぐんだ...!」でも良いです。
そう考えると、一般に言う failover という概念も、ホットとスタンバイという2つのシステムを合成して1つのシステムと見なしている訳で、広義の合成と言えそうです。
そしてそれは if も同じです。if は条件に応じて then 節と else 節を結合...つまり合成している訳です。

さて、それを踏まえて上記 allParser の処理の流れをなぞってみましょう。allParser は

1. まず dogParser が駄目だったら(dog記法で書かれてなかったら) catParser に進み
2. catParser が駄目だったら textParser に進む

このように failover していく訳ですね。
そしてこれは最初に if ~ else で書いていた処理の流れと同じであり、条件に基づく分岐先の合成であり、つまり orElse メソッドは合成のためのメソッドという訳ですね！

さて、だいぶ整理できました。見えてきたのは次の2点です。

1. 条件分岐は合成である
2. パースの成否のような単純な条件で分岐を合成するなら、if ~ else を使わず専用メソッドがあった方がスマートに書ける。A orElse B のように

もっと... もっとスマートな合成を......!!

さて、orElse メソッドで合成がだいぶスマートに書けた訳ですが、まだ不満があります。それは dogParser(source).orElse(catParser(source)) のようにパーサーがそれぞれ引数 source を必要とする事です。
もし、これが次のように書けたら合成も parse の実行もずっとイケてますよね？

val allParser = dogParser.orElse(catParser).orElse(textParser)

allParser.parse(source)

こう書けたら source を渡すのは最後に parse メソッドを呼ぶ時だけです。とってもスマートですよね？ 次は、これを実現してみましょう！

さて、書きたいイメージに近づけるために何が必要か...と考えてみると、まず dogParser.orElse(catParser) と書きたいので dogParser に orElse メソッドを持たせたいですね。しかし現在の dogParser は次のようなただの関数です。

def dogParser(source: String): Option[Dog] = { ... }

関数にメソッドは持たせられないので、この関数をクラス化する必要がありそうです。例えばこんな感じに。

class Parser {
  def parse(source: String): Option[_]
}

DogParser や CatParser はこの Parser クラスを継承して先程のような文字列比較のパース処理を書くイメージです。
ではこの Parser クラスに orElse メソッドも持たせてみましょう。

class Parser {
  def parse(source: String): Option[_]
  def orElse(that: Parser): Parser // ← New !
}

先ほどの Option 型の orElse メソッドのシグネチャをそっくりマネし、自分がパースできなかった時に委ねるための that パーサーを受け取るだけにしています。実行すると、自分か that のどちらかを返り値として返すイメージです。

さて、だいたいイメージできましたね。これでうまくいくか試しにちょっと実装してみましょう。まずは orElse メソッドからです。

class Parser {
  def parse(source: String): Option[_]
  def orElse(that: Parser): Parser = {
    val result = this.parse(source) // ここで source は渡せない！！
    if (result.isDefined) {
      this
    } else {
      that
    }
  }
}

orElse メソッドの実装では、this (自分自身)と that という2つのパーサーがあり、this でパースしてみてそれが成功なら this を、失敗なら that を使うという事で、orElse でやりたい事の流れは書けています。 ただ、this.parse(source) の所で詰まってしまいました。source は引数で取ってませんから、ここでthis.parse(source) とするのはコンパイルエラーです。引数で source を取ってしまえば解決できますが、それをやってしまうと今目指してるイケてる orElse 合成ではなくなって本末転倒です。

・・実はここが本記事一番の難所なので、ちょっとゆっくり進めてみます。

まず、orElse というのは 2つの parser のうち、1つめがパースに成功すればそちらを、失敗すれば2つめのパーサーに委ねるという合成処理でした。これを実現するには、少なくとも1つ目のパーサーで一度はパースして成否を得る必要があるのでそのためには source も必要です。・・ここまでの状況を単体の orElse 関数として実装するとこうなります。

def orElse1(parser1: Parser, parser2: Parser, source: String): Parser = {
  val result = parser1.parse(source)
  result match {
    case Some(_) => parser1
    case None    => parser2
  }
}

この orElse1 関数は parser1, parser2, source を引数にとって、parser1 or parser2 のどちらかを返します。わかりやすいですね。

さて、ここで一つ発想を広げられないか、試行錯誤してみます。 まず orElse1 関数の引数型と返り値型に着目すると

(Parser, Parser, String) => Parser

という関数です。((Parser, Parser, String) が引数のそれぞれの型を、=> Parser が返り値型を示しています)
ところで Parser 型はそもそも String => Option な関数でしたね。今作っている Parser 型は def dogParser(source:String): Option[_] のような String => Option な関数をクラス化しただけなのでした。
・・ということは、上記で Parser と書いている部分は String => Option に置き換えても意味的には一緒と言えそうです。ちょっとその形で眺めてみましょう。

((String => Option), (String => Option), String) => (String => Option)

うーん、何か掴めそうなそうでもないような。まだこれではどう変形したら良いかわからないですね。でもこうやって、String と Option だけの世界で眺めてみるとちょっと違う見方が出来そうな気がしてきましたね！

この調子で更に方向を変えて orElse1 の実装も別の形がないか試行錯誤してみましょう。 たとえば、今は返り値として parser1 か parser2 のどちらかを返している訳ですが、パーサーを直接返すのではなくパース結果を返してみるとかです。こうすると返り値型が変わってきますよね。やってみましょう！

def orElse2(parser1: Parser, parser2: Parser, source: String): Option[_] = {
  val result = parser1.parse(source)
  result match {
    case Some(_) => result
    case None    => parser2.parse(source)
  }
}

出来ました。先程の orElse1 との違いは、返り値型が Parser ではなく Option[_] になったことですね。つまりこの orElse2 のシグネチャは

(Parser, Parser, String) => Option

です。
では、また先程のように Parser 型の部分を String => Option で置き換えて眺めてみましょう！

((String => Option), (String => Option), String) => Option

・・あれ？ なんだか何かが起きそうな予感がしてきませんか？！
そうです！ カッコを無視すればひたすらString => Option という順序できれいに3つ並んでいますね。もしこのカッコを良い感じに整えて(String => Option)で統一できたら、なんだか良い感じに括れて道が拓けるかも知れません！

そこで！ 今回は関数型プログラミングでたまに名前の出る「カリー化」の視点で今の状態を捉え直すことで、世界を広げて道を切り拓いていきます！！
・・ですが、カリー化を知らない方がここで脱落してしまうと勿体ないので、すこしざっくりとカリー化の解説をしておきます。

カリー化🍛について(読み飛ばし可)

まず、カリー化の説明の前に引数リストという言葉をはっきりさせておきましょう。 引数リストというのは以下の(a: Int, b: Int, c: Int)のような、引数 n 個のまとまりです。

def sum(a: Int, b: Int, c: Int): Int = a + b + c

通常、カリー化に対応していない言語の場合、関数は引数リストが1つしかないものですが、Scala の場合これを複数持てます。次のような形です。

def curriedSum1(a: Int)(b: Int)(c: Int): Int = a + b + c

引数リスト3つにしてみました。大抵は引数リスト1つで十分なので、ちょっと奇妙に見えるかも知れませんね。 ちなみに Scala の場合、関数には def キーワードを使わずに値として val キーワードを使って関数値として次のようにも書けます(書き方はいろいろあります)

val curriedSum2 = (a: Int) => (b: Int) => (c: Int) => a + b + c

次の結果はどれも 6 です。

sum(1,2,3)
curriedSum1(1)(2)(3)
curriedSum2(1)(2)(3)

さて、このカリー化ですが面白いのは、複数ある引数リストのうち、途中まで埋めたところで止めると残りが関数として返ってくる事です。 ・・言葉ではわかりにくいですね？ Scala の REPL で動かすと次のような感じです。

scala> val curriedSum = (a: Int) => (b: Int) => (c: Int) => a + b + c
curriedSum: Int => (Int => (Int => Int))

scala> curriedSum(1)
res0: Int => (Int => Int)

scala> res0(2)
res1: Int => Int

scala> res1(3)
res2: Int = 6

Scala の REPL は実行結果を変数に入れない場合 res0 という変数に自動的に入れて返します。この数字部分はオートインクリメントしていきます

さてこの curriedSum は sum(1, 2, 3) の時と同じ使い方をするならcurriedSum(1)(2)(3)といっぺんに引数を3つ渡せばもちろん同じことが出来ます。ただ、それだけではなくcurriedSum(1)という使い方ができるのがポイントです。
そうしておいて、あとから続きの (2), (3) という引数を渡したら 6 が得られます。つまり引数を分割して渡せるようにした感じです！
ただ、このように後からでも引数を渡せるようにしておくには、引数を渡すたびに毎回関数が返って来なくちゃいけません。関数が返ってこないと、次の引数が渡せませんからね。もちろん最後の引数を渡したら、関数ではなく値が返ってきます。

別の視点で捉えてみましょう。言葉で表すなら curriedSum は「関数を返す関数を返す関数」です。・・こう表現するとややこしいですが、これ、引数を分割した分だけ「〜を返す関数」って最後に付け加えてるだけなんです。引数リストが1つなら「関数」。引数リストが2つなら「関数を返す関数」になります。つまり引数リストが5つなら「関数を返す関数を返す関数を返す関数を返す関数」ですね！！！
カリー化というのはこのように、引数を分解して、一部の引数を埋めたら残りを関数として返す機能です！

・・さて、ではカリー化の理解の仕上げにあえて引数を1つずつ異なる型にした curriedConcat を眺めておきましょう！ さっきの curriedSum は、挙動はわかりやすいけど型だけで見ると Int だらけで見づらいですからね！

scala> val curriedConcat = (a: Int) => (b: Float) => (c: Double) => a.toString() + b.toString() + c.toString()
curriedConcat: Int => (Float => (Double => String))

先頭から引数を一つずつ与えながら順に関数を得ていきましょう。

scala> curriedConcat(1)
res0: Float => (Double => String)

scala> res0(2.3f)
res1: Double => String

scala> res1(4.5d)
res2: String = 12.34.5

型だけで言うと、この Int => (Float => (Double => String)) に引数 Int を渡すとその後の => の右側が返ってくる形ですね。あとは同じことの繰り返しで、最後に 12.34.5 という文字列を得ます。
・・初めてだと馴染みづらいと思いますが、今回は雰囲気が掴めていればOKです！

なお、カリー化はハスケル・カリーさんに由来する言葉であり某国民的人気食🍛とは関係ありませんのでご注意ください🍛

カリー化の視点を得て、関数の変形を自在に行おう！

では、先程の変形の続きをしてみましょう！ 最後の状態は

((String => Option), (String => Option), String) => Option

でした。ただ、カッコが多くてこれをカリー化すると見づらいのでもう一度 Parser と書ける所は Parser に戻しますね。

(Parser, Parser, String) => Option

これは「Parser 2つと Source文字列を渡せば、パース結果がOption型で返ってくる」という関数ですね。=>の左側が引数で、右側が返り値です。
この「引数が3つある」関数を早速カリー化して「引数リストが3つある」状態にしてみましょう。

Parser => (Parser => (String => Option))

カッコは増えましたが、先程 curriedSum や curriedConcat でやった事とまったく同じです。
この状態でも、Parser を1つずつ渡していって最後に Source 文字列を渡せば、パース結果が Option 型で返ってきます。
そしてそう！ 実はもうこれで先ほど望んでいた形になりましたね！
最後のところが (String => Option) になりました。これは Parser 型として表せるのでつまり

Parser => (Parser => Parser)

こうなりますね！？ 上手くいきました！！
あとはカッコの位置でしょうか。きれいな変形が出来たのでこれ以上カリー化に拘らなくてもよいので、馴染みのある「1つの引数リストで2つ引数を渡す」と「返り値が1つ返ってくる」という形に直してみます。

(Parser, Parser) => Parser

はい。パーサーを2つ引数に取ってパーサーを1つ返す関数が出来ました。やりました！
ではこの流れで実際に実装してみましょう。
まず、先程の orElse2 を再掲しますね

def orElse2(parser1: Parser, parser2: Parser, source: String): Option[_] = {
  val result = parser1.parse(source)
  result match {
    case Some(_) => result
    case None    => parser2.parse(source)
  }
}

この orElse2 はまだ「引数を3つ渡すと、値を1つ返す関数」です。
先ほどのように型だけで書くとこうです。

(Parser, Parser, String) => Option

これをまずは、こうしてみましょう！

(Parser, Parser) => (String => Option)

この変形はつまり「orElse2 の引数3つ目の source を関数の本体の方に移動せよ」ということなので...

def orElse3(parser1: Parser, parser2: Parser) = { 
  (source: String) => {
    ... /* ここで parser1 を使って source をパースしてみたりする */
  }
}

こういうイメージですね！
この orElse3 は1つ目の引数リストとしてまず parser を 2 つ渡す事になります。そうやって引数を渡すと....

(source: String) => { ... }

の部分が関数として返ってくる形です。

ちなみに Scala に不慣れな方向けに解説するとこのコードの (source: String)が引数リストで、 => が関数を表すキーワードで、 { ... } 部分が関数の本体でこの本体部分でパース処理を書いて結果を返すイメージです。こうすることで「source 引数を取ってパース結果を返す関数」になります。Scala ではこのように書く事でその場で関数値を作れるのです。

さて、ともあれこうして orElse3 全体として見ると引数リスト1が(parser1: Parser, parser2: Parser)、引数リスト2が(source: String)という形で「関数を返す関数」になりました！
こういった「関数を返す関数」は慣れないとちょっと捉えづらいと思いますが、やっている事はとても単純だったりします。慣れるまでは少し時間をかけて読んで貰えればと思います。
では最後に、先程 /*ここで parser1 を使って source をパースしてみたりする */と書いていた部分を実装して orElse3 を完成させておきましょう！

def orElse3(parser1: Parser, parser2: Parser): String => Option[_] = { 
  (source: String) => {
    val result = parser1.parse(source)
    result match {
      case Some(_) => result
      case None    => parser2.parse(source)
    }
  }
}

これで、本記事の一番の難所であるカリー化の応用部分は超えました。
あとは、String => Option を Parser 型として書き直して型を整えた orElse4 を書いてみましょう。

def orElse4(parser1: Parser, parser2: Parser): Parser = {
  new Parser {
    def parse(source: String): Option[_] = {
      val result = parser1.parse(source)
      result match {
        case Some(_) => result
        case None    => parser2.parse(source)
      }
    }
  }
}

やってることは「関数値を Parser 型で書き直しただけ」ですが書けました。これで当初の目的であった

• orElse 合成時に source: String が引数に出てこないこと

が実現できました！

一連の変形を振り返っておきましょう。orElse1 と orElse4 で何が変わったかと言うと

• orElse1 は、parser 2つと source を受け取って、その場で source をパースしてその成否に応じて2つの parser のどちらかを返した
• orElse4 は、parser 2つを受け取って、いつか Parser.parse が呼ばれた時に受け渡されてくる source に対して手持ちの parser1 でパースしてみて、その成否によっては parse2 でもパースしてみて、いずれかのパース結果を返すという新しいパーサーを作って返した

このような違いになります。
また、別の見方をするとこの orElse4 関数は Parser のファクトリー関数です。
「2つの Parser を引数に取り、それらを合成した新たな Parser を生成する」というファクトリです。これってもう「パーサーの合成」ですよね！
つまり、このように「パーサーのファクトリ関数」という形ならば、合成元となるパーサーをいくつ引数に取っても良いですし、それらを新しいパーサーの内部でどう接続するかも自由に組めます。今回の形や流れを守っておけば、このように自由自在でありながらスマートに合成やコンビネーションが出来るのです。

これこそがパーサーコンビネーターのコアに潜む性質です。

今回 orElse というパーサー合成関数を実装することで「Parser のファクトリという形なら、かなり自由自在にいろんなことができる」という感覚は掴めてきたことでしょう。そうして今後、他のコンビネータを見ていくとさらに「パース結果をどう扱っても良いし、引数にパーサーを取らなくたって良い」というのもだんだん掴めてきます。これらの感覚を掴めば、あなたはもう自分の事情に合ったコンビネータをサッと用意し、スマートに、思うままにあらゆる構文をパースする事ができることでしょう！

ちなみに、この orElse のような、いい感じにパーサー同士のコンビネーションをキメる道具をコンビネータと呼びます(ざっくり)。

Parser クラスで orElse 合成できるようにしよう！

では、話を戻してこれまでの集大成として Parser クラスを完成させ今回の目標を達成してみましょう！
まず、先ほどつまずいた所まで戻ります。先ほどはこのように orElse メソッドの実装で詰まっていたのでした。

class Parser {
  def parse(source: String): Option[_]
  def orElse(that: Parser): Parser = {
    val result = this.parse(source) // ここで source は渡せない！！
    if (result.isDefined) {
      this
    } else {
      that
    }
  }
}

では早速、先程の orElse4 を当てはめてみましょう。

class Parser {
  def parse(source: String): Option[_]
  def orElse(that: Parser): Parser = {
    new Parser {
      def parse(source: String): Option[_] = {
        val result = this.parse(source)
        result match {
          case Some(_) => result
          case None    => that.parse(source)
        }
      }
    }
  }
}

上手く行きましたね！

さて、ここまでは良いのですが parse メソッドが書けてません。ここがどうなるかでいうと・・ここには dogParser や catParser の具体的なパース処理が入る事になりますね。
つまり先ほどのこれです。

def dogParser(source: String): Option[Dog] = {
  if (source.take(5) == "[dog:") {
    val name = source.drop(5).takeWhile(_ != ']')
    Some(Dog(name))
  } else {
    None
  }
}

ということは、次のように Parser クラスの実装として dogParser のパース処理を書いてしまえば、あとは new してインスタンス生成すれば良さそうです。

val dogParse = new Parser {
  def parse(source: String): Option[_] = {
    if (source.take(5) == "[dog:") {
      val name = source.drop(5).takeWhile(_ != ']')
      Some(Dog(name))
    } else {
      None
    }
  }
}

ただ、毎回このように new Parser するのもちょっと Parser の内部を露出しすぎですし、他の言語だとこのような書き方ができない場合もあるので、もうちょっと汎用的に関数値で置き換えてみましょう。Parser のコンストラクタ引数として関数値を受け取ることにして、そこで dogParser や catParser などのパース処理をする関数を受け取ってしまえばスマートになります。そしてこれなら、関数値がある言語なら同じように書けます！

class Parser(parseFunction: String => Option[_]) {
  def parse(source: String): Option[_] = {
    parseFunction(source)
  }

  def orElse(that: Parser): Parser = {
    new Parser(source => {
      val res = this.parse(source)
      res match {
        case Some(_) => res
        case None    => that.parse(source)
      }
    })
  }
}

こうしておけば、dogParser はこのように書けます。

val dogParser: Parser = new Parser(source => {
  if (source.take(5) == "[dog:") {
    val name = source.drop(5).takeWhile(_ != ']')
    Some(Dog(name))
  } else {
    None
  }
})

ちなみに、関数値のない言語なら class DogParser extends Parser のような形で Parser 抽象クラスを継承して parse メソッドを実装する手もあります。ただ、いちいち class を定義するのも面倒ですし、最近は関数型の概念も一般的になりましたのでこの関数値のやり方を採用しようと思います。

さて、ともあれ Parser クラスがいよいよ完成しました！ それでは、お待ちかねの orElse 合成をしてみましょう！
catParser と textParser の実装は dogParser とほぼ同様なので省略しますが、それらがあればこのように合成できます。

val allParser = dogParser.orElse(catParser).orElse(textParser)

遂に！ やっと！スマートに合成できるようになりました！
実行してみましょう！

val res = allParser.parse("[cat:Tama]")

println(res) // => Some(Cat(Tama))

目論見通りにパースができるようになりました！

終わりと続き

ここまでで、最初にあげたお題「単純なパーサーを合成して、複雑なパーサーを作る」は達成できました。やりましたね。
ただこれ、パーサーとしては不完全なんですよね。ここまでだいぶ頑張りましたが、まだ dog, cat, text が複数回登場する文章はパースできません。つまり

[cat:Tama][text:の可愛さを伝えるには、この余白は狭すぎる]

のような文章をパースしても最初の [cat:Tama] しかパースできません。という事で、タグが複数回登場しても最後までパースしきるように改良しなくてはなりませんね。
・・大変そうでしょうか？ でも大丈夫。そんな一見ややこしそうな問題も簡単に解決できます。そう、パーサーコンビネータならね。

val repeatedAll = allParser.repeat(min = 0)

val result = repeatedAll.parse("[text:我が家の][cat:Tama][text:は世界一かわいい]").get()

println(result) // => List(Text(我が家の), Cat(Tama), Text(は世界一かわいい))

最終的にはこんな感じの repeat コンビネータを作れば繰り返しの問題もあっさり解決します。この repeat コンビネータは min 引数を受け取るようにしてますが、こんな感じで min だけでなく max も設定できるようにしておけば、繰り返し回数も自由自在です。そうすれば「ぴったり数字5桁にマッチする」「英数字が6-8文字続く場合だけマッチする」なんてパーサーも思いのままです。そしてそれらのルーティングも今回の orElse だけでなく andThen のようなコンビネータも登場してさらにスマートに柔軟に組めます。そういった便利なコンビネータを駆使すれば様々なパーサーをスマートかつ自由自在に合成しルーティングできるようになっていく訳です。

・・実はそういう他のコンビネータの解説も5割ほど書いたのですが、今回はタイムアップということで続きはまたいつか。
他にも面白いコンビネータは色々あるので、それらを紹介して「そっか、コンビネータってこんな感じか。これならもう自分でどうとでも好きに書けるな！」と思える人が一人でも増えたらと思います。

続きが気になる方はぜひ SNS でシェアして貰えたらと思います！ それではまたいつか！