パーサーコンビネータをつくる ~ FP in Scala 第9章

Jun 25, 2019 08:39 · 851 words · 4 minute read

“Scala関数型デザイン＆プログラミング ―Scalazコントリビューターによる関数型徹底ガイド”（原題: Functional Programming in Scala）の“第9章パーサーコンビネータ”のJSONパーサーを作る。

GitHubにある参考解答を参考に実装。

セットアップ

以下の環境を用意。IntelliJ IDEA でプロジェクトを作成。

Project Name: Parsing sbt: 1.2.8 Scala: 2.12.8

ファイル構成は次の通り。

📁 src
- 📁 main
  - 📁 scala
    - 📁 fpinscala
      - 📁 parsing
        
        📄Parsers.scala （パーサーコンビネータ）
        
        📄JSON.scala （JSON パーサー）
        
        📁 instances
        
        📄MyParser.scala （パーサーの実装）
- 📁 test
  - 📁 scala
    - 📁 fpinscala
      - 📁 parsing
        
        📄JSONTests.scala
        
        📁 instances
        
        📄MyParserTests.scala

パーサーコンビネータ

パースエラー時にエラー情報を返さないことにしたので、 ParseError はただの文字列を引数に持つ型。エラー情報を載せない場合、 slice, listOfN などは使わなかった。

前章で書いたテストライブラリの代わりに scalacheck を利用した。

// Parsers.scala
package fpinscala.parsing

import java.util.regex.Pattern
import scala.util.matching.Regex

import org.scalacheck.Gen
import org.scalacheck.Prop
import org.scalacheck.Prop.forAll

import language.higherKinds

case class ParseError(msg: String)

trait Parsers[Parser[+_]] { self =>
  def run[A](p: Parser[A])(input: String): Either[ParseError, A]

  implicit def string(s: String): Parser[String]

  implicit def regex(r: Regex): Parser[String]

  def succeed[A](a: A): Parser[A]

  def flatMap[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B]

  def or[A](p1: Parser[A], p2: => Parser[A]): Parser[A]

  def map[A, B](p: Parser[A])(f: A => B): Parser[B] =
    flatMap(p)(a => succeed(f(a)))

  def map2[A, B, C](p: Parser[A], p2: => Parser[B])(f: (A, B) => C): Parser[C] =
    flatMap(p)(a => map(p2)(b => f(a, b)))

  def skipL[B](p: Parser[Any], p2: => Parser[B]): Parser[B] =
    map2(p, p2)((_, b) => b)

  def skipR[A](p: Parser[A], p2: => Parser[Any]): Parser[A] =
    map2(p, p2)((a, _) => a)

  def surround[A](start: Parser[Any], stop: Parser[Any])(p: => Parser[A]) =
    skipR(skipL(start, p), stop)

  def many[A](p: Parser[A]): Parser[List[A]] =
    or(map2(p, many(p))(_ :: _), succeed(List()))

  def sep1[A](p: Parser[A], p2: Parser[Any]): Parser[List[A]] =
    map2(p, many(skipL(p2, p)))(_ :: _)

  def sep[A](p: Parser[A], p2: Parser[Any]): Parser[List[A]] =
    or(sep1(p, p2), succeed(List()))

  def double: Parser[Double] =
    map(token("[-+]?([0-9]*\\.)?[0-9]+([eE][-+]?[0-9]+)?".r))(_.toDouble)

  def whitespace: Parser[String] = "\\s*".r

  def token[A](p: Parser[A]): Parser[A] =
    skipR(p, whitespace)

  def thru(s: String): Parser[String] =
    (".*?" + Pattern.quote(s)).r

  def quoted: Parser[String] =
    skipL(string("\""), map(thru("\""))(_.dropRight(1)))

  def product[A, B](p: Parser[A], p2: => Parser[B]): Parser[(A, B)] =
    flatMap(p)(a => map(p2)(b => (a, b)))

  // string as stringParser
  implicit def operators[A](p: Parser[A]) = ParserOps[A](p)
  implicit def asStringParser[A](a: A)(implicit f: A => Parser[String]): ParserOps[String] =
    ParserOps(f(a))

  // ParserOps is for infix notation
  case class ParserOps[A](p: Parser[A]) {
    def |[B>:A](p2: => Parser[B]): Parser[B] = self.or(p, p2)
    def map[B](f: A => B): Parser[B] = self.map(p)(f)
  }

  object Laws {
    def runString(in: Gen[String]): Prop =
      forAll(in) { s: String =>
        run(string(s))(s) == Right(s)
      }

    def equal[A](p1: Parser[A], p2: Parser[A])(in: Gen[String]): Prop =
      forAll(in)(s => run(p1)(s) == run(p2)(s))

    def mapLaw[A](p: Parser[A])(in: Gen[String]): Prop =
      equal(p, p.map(a => a))(in)
  }
}

パーサーの実装

パーサーは“状態”である 入力文字列 と パース済の文字数 から“結果”である成否と パースした文字数 を返す関数として定義。 flatMap ではパースが成功したら パース済の文字数 offset を増やす。

// MyParser.scala
package fpinscala.parsing

import scala.util.matching.Regex

object MyParserTypes {
  case class ParseState(source: String, offset: Int) {
    def advanceBy(numChars: Int): ParseState =
      copy(offset = offset + numChars)

    def input: String = source.substring(offset)
  }

  trait Result[+A] {
    def advanceSuccess(n: Int): Result[A] = this match {
      case Success(a, m) => Success(a, n + m)
      case _ => this
    }
  }

  case class Success[+A](get: A, length: Int) extends Result[A]
  case class Failure(get: ParseError) extends Result[Nothing]

  type Parser[+A] = ParseState => Result[A]
}

import fpinscala.parsing.MyParserTypes._

object MyParser extends Parsers[Parser] {
  def run[A](p: Parser[A])(input: String): Either[ParseError, A] =
    p(ParseState(input, 0)) match {
      case Failure(parseError) => Left(parseError)
      case Success(a, _) => Right(a)
    }

  implicit def string(w: String): Parser[String] =
    s => if (s.input.startsWith(w)) Success(w, w.length)
    else Failure(ParseError("Not match string"))

  implicit def regex(r: Regex): Parser[String] =
    s => r.findPrefixOf(s.input) match {
      case Some(m) => Success(m, m.length)
      case None =>  Failure(ParseError("Not match regex"))
    }

  def succeed[A](a: A): Parser[A] =
    _ => Success(a, 0)

  def flatMap[A, B](p: Parser[A])(f: A => Parser[B]): Parser[B] =
    s => p(s) match {
      case Success(ma, la) =>
        f(ma)(s.advanceBy(la)).advanceSuccess(la)
      case f@Failure(_) => f
    }

  def or[A](p1: Parser[A], p2: => Parser[A]): Parser[A] =
    s => p1(s) match {
      case Failure(_) => p2(s)
      case r => r
    }
}

JSON パーサー

jsonParser の中で Parsers をインポートする。文字列リテラルを token として扱うため、 Parsers.string はインポートしない。

// JSON.scala
package fpinscala.parsing

trait JSON

object JSON {

  case object JNull extends JSON
  case class JNumber(get: Double) extends JSON
  case class JString(get: String) extends JSON
  case class JBool(get: Boolean) extends JSON
  case class JArray(get: IndexedSeq[JSON]) extends JSON
  case class JObject(get: Map[String, JSON]) extends JSON

  def jsonParser[Parser[+_]](P: Parsers[Parser]): Parser[JSON] = {
    import P.{string => _, _}
    implicit def tok(s: String) = token(P.string(s))

    def bool =
      map("true")(_ => JBool(true)) |
      map("false")(_ => JBool(false))

    def str: Parser[JSON.JString] =
      map(quoted)(JString(_))

    def lit =
      map(double)(JNumber(_)) |
        map("null")(_ => JNull) |
          bool | str

    def value: Parser[JSON] = lit | array | obj

    def array =
      surround("[","]")(
        map(sep(value, ","))(vs => JArray(vs.toIndexedSeq))
      )

    def keyval = product(quoted, skipL(":", value))

    def obj =
      surround("{","}")(
        map(sep(keyval, ","))(kvs => JObject(kvs.toMap))
      )

    skipL(whitespace, array | obj)
  }
}

テスト

実際にパースできることを確認。

// JSONTests.scala
package fpinscala.parsing

import org.scalatest.FunSuite

class JSONTests extends FunSuite {

  val jsonParser = JSON.jsonParser(MyParser)

  test("JSON 1") {
    val actual = MyParser.run(jsonParser)("[]")
    val expected = Right(JSON.JArray(IndexedSeq()))
    assert(actual == expected)
  }

  test("JSON 2") {
    val actual = MyParser.run(jsonParser)(
      """
        |[
        |  1,
        |  true,
        |  [ null, 3,  false ],
        |  4
        |] """.stripMargin)
    val expected = Right(
      JSON.JArray(IndexedSeq(
        JSON.JNumber(1),
        JSON.JBool(true),
        JSON.JArray(IndexedSeq(
          JSON.JNull,
          JSON.JNumber(3),
          JSON.JBool(false)
        )),
        JSON.JNumber(4),
      )
      )
    )
    assert(actual == expected)
  }

  test("JSON 3") {
    val input = "[\"abc\",\"d e\"]"
    val actual = MyParser.run(jsonParser)(input)
    val expected = Right(
      JSON.JArray(IndexedSeq(
        JSON.JString("abc"),
        JSON.JString("d e")
      ))
    )
    assert(actual == expected)
  }

  test("JSON 4") {
    val input = "{\"a\":\"b\",\"c\":{\"d\":1,\"e\":null}}"
    val actual = MyParser.run(jsonParser)(input)
    val expected = Right(
      JSON.JObject(Map(
        ("a", JSON.JString("b")),
        ("c", JSON.JObject(Map(
          ("d", JSON.JNumber(1)),
          ("e", JSON.JNull)
        )))
      ))
    )
    assert(actual == expected)
  }
}

ソースコード

https://github.com/h-kanazawa/fpinscala-parsing