Magnolia Tech

いつもコードのことばかり考えている人のために。

『Scala関数型デザイン&プログラミング』の演習問題をScala3で解く その13

blog.magnolia.tech

パーサーコンビネータ

scala-parser-combinators

Scalaのパーサコンビネータライブラリと言えば、元々は標準ライブラリだったscala-parser-combinatorsが有ります。今では分離され、Scalaの標準のディストリビューションとは別に開発が進められています。

github.com

言語の標準ライブラリでパーサコンビネータが用意されているのは珍しいと思ったのですが、結局Scala 2.13からは標準ライブラリからは外されました。外部DSLを作るのに便利なんですけどね。

コップ本でも第4版までは最後の方で触れられていますが、第5版では削られています。

ちなみに言語の標準ライブラリでパーサコンビネータを持つ言語と言えば、Raku (以前のPerl6)が有ります。Grammarという機能がそれに当たります。

docs.raku.org

まずはこの辺りのライブラリを使ってみて、パーサコンビネータに対する感覚をつかむと良いでしょう。

演習問題を解き進めるにあたって

本章はそれまでの章と違って、具体的な実装がなかなか出てきません。一部は出てきますが、肝心なプリミティブがほぼ終わりの頃にならないと出てこない構成になっています。そのため、実装したらすぐにテストを書く…という手法が使えません……真正面から取り組むもよし、後半に出てくるstring関数を先に実装して進めるのもよしで、まずは読み進めていきましょう。特に後半のエラーのレポート方法の改善や、JSONのパーサーの実装はなかなかの難易度で、ここで挫折する可能性も高いですが、無理だな、と思ったらとっとと先に進みましょう。

ちなみに、一番大事なプリミティブであるstringの実装例が出てきますが、sliceと整合しないので、最初から以下のコードを実装しておくと、人に拠っては理解が進んで良いかもしれません。本書の趣旨とは合わないですが、理解が進まないとどうにもならないので。

case class Result[+A](value: A, consumed: Int)
opaque type Parser[+A] = String => Either[ParseError, Result[A]]

object Parser:
  def string(s: String): Parser[String] =
    (input: String) =>
      if input.startsWith(s) then
        Right( Result(s, s.length) )
      else
        Left(Location(input).toError("Expected: " + s))

  given Conversion[String, Parser[String]] with
    def apply(s: String) = string(s)

このプリミティブさえ有れば、テストが書けるので、実装とテストを繰り返しながら理解を進めていくのにちょうど良いでしょう。