面倒くさいパーサの実装もDSLで書くだけ！そう、Scalaならね



この記事では、Scalaのパーサコンビネータを用いて、BNF風の定義を書くだけで、オブジェクトのマッピングからパースエラーのハンドリングまでできてしまう高機能なパーサを作る方法を解説します！

# パーサコンビネータとは?

Scalaにはパーサコンビネータというライブラリがあります。BNFと似たの記法で構造を定義するだけで簡単にパーサを実装することができます。たとえば、`□□□-□□□□`のような形式の郵便番号をパースするコードは次のように書くことができます。

```scala:サンプルコード1
import scala.util.parsing.combinator._

object PostalCodeParser extends RegexParsers {
  def postalCode = """\d{3}""".r ~ "-" ~ """\d{4}""".r
}

println(PostalCodeParser.parseAll(PostalCodeParser.postalCode, "123-4567").get)
```


実行結果

```
((123~-)~4567)
```

ここの A `~` B という表記は「Aの次にBが来る」というのを表現しています。

# 基本的な使用方法

* `import scala.util.parsing.combinator._` をインポートする
* `RegexParsers` トレイトを継承し、オブジェクトとして実装する
* `parseAll` にパーサと入力を渡し、結果を受け取る

# パーサには `apply` メソッドを実装しよう

サンプルコード1では、`parseAll`メソッドを外部から直接呼び出しましたが、クライアントコードを簡単にするために、`apply`メソッドを実装しておくほうがいいです。次のサンプルコード2は、サンプルコード1に `apply` メソッドを実装した例です。

```scala:サンプルコード2
  object PostalCodeParser extends RegexParsers {
    def postalCode = """\d{3}""".r ~ "-" ~ """\d{4}""".r
    def apply(input: String) = parseAll(postalCode, input).get
  }

  println(PostalCodeParser("123-4567")) // クライアントコード
```

実行結果はサンプルコード1と同じですが、クライアントコードがスッキリしました。

# Eitherを使ってパースエラーをハンドルする

サンプルコード2の実装に問題があるとしたら、パースエラーのハンドリングが無いところです。例えば次のコードのように、パースエラーになる入力を渡すと、`java.lang.RuntimeException`が発生してしまいます。

```scala
  println(PostalCodeParser("1234567"))
```

そこで、`apply` メソッドにエラーハンドリングを実装して、パースに成功した時は `Right` 型を、失敗した時は `Left` 型を返すようにします。

```scala:サンプルコード3
  object PostalCodeParser extends RegexParsers {
    def postalCode = """\d{3}""".r ~ "-" ~ """\d{4}""".r
    def apply(input: String): Either[String, Any] = parseAll(postalCode, input) match {
      case Success(postalCodeData, next) => Right(postalCodeData)
      case NoSuccess(errorMessage, next) => Left(errorMessage)
    }
  }

  println(PostalCodeParser("123-4567")) // Right(((123~-)~4567))
  println(PostalCodeParser("1234567")) // Left(`-' expected but `4' found)
```

`parseAll` メソッドはパースに成功した時は `Success` 型を、失敗した時は `NotSuccess` 型を返すので、パターンマッチングで成否を判断します。また、`NotSuccess` オブジェクトの第一引数はエラーメッセージが入っているので、そのまま活用して `Left` に渡します。

# どこがパースエラーなのか分かりにくくないか?

サンプルコード3に対して、パースエラーになる入力 `1111111` を渡してみましょう。

```scala
  println(PostalCodeParser("1111111")) // Left(`-' expected but `1' found)
```

この例では「予期しない1が出てきてパースエラー」というエラーメッセージですが、何番目の「1」に問題があるのか分かりません。つまり、「なぜエラーになったか」は分かりますが、「どこでエラーになったのか?」が分からないのです。そこで、該当箇所が何行目か何文字目か分かるよう、エラーメッセージに情報を追加します。

エラーメッセージの該当箇所の情報は、`NotSuccess(errorMessage, next)` の `next` から参照することができます。次のサンプルコード4は、`Left` のエラーメッセージに行数と文字数を追加したものです。

```scala:サンプルコード4
  object PostalCodeParser extends RegexParsers {
    def postalCode = """\d{3}""".r ~ "-" ~ """\d{4}""".r
    def apply(input: String): Either[String, Any] = parseAll(postalCode, input) match {
      case Success(postalCodeData, next) => Right(postalCodeData)
      case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
    }
  }

  println(PostalCodeParser("1111111")) // Left(`-' expected but `1' found on line 1 on column 4)
```

この例の出力結果を見て分かるように、4文字目でパースエラーになったことが分かります。

# パース結果をcase classにしたい

これまでのサンプルコードでは、パースに成功した時の戻り値が `Right(((123~-)~4567))` のような形で扱いにくい形でした。そこで、パースした結果が `PostalCode(123, 4567)` のような分かりやすい形になるように実装しなおしてみます。

```scala:サンプルコード5
  case class PostalCode(threeDigit: String, fourDigit: String)

  object PostalCodeParser extends RegexParsers {
    def postalCode = """\d{3}""".r ~ "-" ~ """\d{4}""".r ^^ { case (threeDigit ~ "-" ~ fourDigit) => PostalCode(threeDigit, fourDigit) }
    def apply(input: String): Either[String, PostalCode] = parseAll(postalCode, input) match {
      case Success(postalCodeData, next) => Right(postalCodeData)
      case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
    }
  }

  println(PostalCodeParser("123-4567")) // Right(PostalCode(123,4567))
```

`RegexParsers` の `^^` は「パースした結果を変形する」という意味で、変形する関数を与えます。ここでは `((123~-)~4567)` を `PostalCode(123, 4567)` に変換するパターンマッチングの関数を与えています。

# もっと複雑なパーサも書いてみる

郵便番号パーサの例はとてもシンプルな例でした。ここではもう少し複雑なパーサを作ってみようと思います。題材としてCSVのパーサを開発してみます。

## まずは、CSVのBNFを調べる

ScalaのRegexParsersはDSLがBNFによく似ているので、先にBNFを調べたり考えておくと、実装にとりかかりやすくなります。

```bnf:CSVのEBNF
file = [header CRLF] record (CRLF record)* [CRLF]
header = name (COMMA name)*
record = field (COMMA field)*
name = field
field = (escaped | non-escaped)
escaped = DQUOTE (TEXTDATA | COMMA | CR | LF | 2DQUOTE)* DQUOTE
2DQUOTE = DQUOTE DQUOTE
non-escaped = TEXTDATA*
COMMA = '\u002C'
CR = '\u000D'
DQUOTE = '\u0022'
LF = '\u000A'
CRLF = CR LF
TEXTDATA = #'[\u0020-\u0021\u0023-\u002B\u002D-\u007E]'
```

## BNFを元にパーサコンビネータを実装する

これをベースにScalaのパーサコンビネータを実装するとこのようになります:

```scala
  object CSVParser extends RegexParsers {

    override def skipWhitespace = false

    // file = [header CRLF] record (CRLF record)* [CRLF]
    def file = opt(header ~ CRLF) ~ repsep(record, CRLF) ~ opt(CRLF)

    // header = name (COMMA name)*
    def header = repsep(name, comma)

    // record = field (COMMA field)*
    def record = repsep(field, comma)

    // name = field
    def name = field

    // field = (escaped | non-escaped)
    def field = escaped | nonEscaped

    // escaped = DQUOTE (TEXTDATA | COMMA | CR | LF | 2DQUOTE)* DQUOTE
    def escaped = doubleQuote ~ (textdata | comma | CR | LF | twoDoubleQuote).* ~ doubleQuote

    // 2DQUOTE = DQUOTE DQUOTE
    def twoDoubleQuote = doubleQuote ~ doubleQuote

    // non-escaped = TEXTDATA*
    def nonEscaped = textdata.*

    // COMMA = '\u002C'
    def comma = ","

    // CR = ''
    def CR = "\r"

    // DQUOTE = ''
    def doubleQuote = "\""

    // LF = ''
    def LF = "\n"

    // CRLF = CR LF
    def CRLF = CR ~ LF

    // TEXTDATA = #'[\u0020-\u0021\u0023-\u002B\u002D-\u007E]'
    def textdata = """[\u0020-\u0021\u0023-\u002B\u002D-\u007E]""".r

    def apply(input: String): Either[String, Any] = parseAll(file, input) match {
      case Success(csvData, next)        => Right(csvData)
      case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
    }
  }
```

CSVをパースしてみます:

```scala
  println(CSVParser("a,b,c\r\n1,2,3\r\nz,y,z"))
```

実行結果

```
~ight(((Some((List(List(a), List(b), List(c))~(
)))~List(List(List(1), List(2), List(3)), List(List(z), List(y), List(z))))~None))
```

## case classに変換するようにする

郵便番号パーサの例と同様に、case classに変換するようにします。

```scala
  case class CSV(header: Header, rows: Seq[Record])
  case class Header(names: Seq[String])
  case class Record(fields: Seq[String])

  object CSVParser extends RegexParsers {

    override def skipWhitespace = false

    // file = [header CRLF] record (CRLF record)* [CRLF]
    def file = opt(header <~ CRLF) ~ repsep(record, CRLF) <~ opt(CRLF) ^^ {
      case Some(header) ~ records => CSV(header, records)
      case None ~ records         => CSV(Header(List()), records)
    }

    // header = name (COMMA name)*
    def header = repsep(name, comma) ^^ { names => Header(names.map(_.toString)) }

    // record = field (COMMA field)*
    def record = repsep(field, comma) ^^ { fields => Record(fields.map(_.toString)) }

    // name = field
    def name = field

    // field = (escaped | non-escaped)
    def field = escaped | nonEscaped

    // escaped = DQUOTE (TEXTDATA | COMMA | CR | LF | 2DQUOTE)* DQUOTE
    def escaped = doubleQuote ~> (textdata | comma | CR | LF | twoDoubleQuote).* <~ doubleQuote ^^ { _.mkString }

    // 2DQUOTE = DQUOTE DQUOTE
    def twoDoubleQuote = doubleQuote ~ doubleQuote ^^ { case d1 ~ d2 => d1 + d2 }

    // non-escaped = TEXTDATA*
    def nonEscaped = textdata.* ^^ { _.mkString }

    // COMMA = '\u002C'
    def comma = ","

    // CR = ''
    def CR = "\r"

    // DQUOTE = ''
    def doubleQuote = "\""

    // LF = ''
    def LF = "\n"

    // CRLF = CR LF
    def CRLF = CR ~ LF

    // TEXTDATA = #'[\u0020-\u0021\u0023-\u002B\u002D-\u007E]'
    def textdata = """[\u0020-\u0021\u0023-\u002B\u002D-\u007E]""".r

    def apply(input: String): Either[String, Any] = parseAll(file, input) match {
      case Success(csvData, next)        => Right(csvData)
      case NoSuccess(errorMessage, next) => Left(s"$errorMessage on line ${next.pos.line} on column ${next.pos.column}")
    }
  }
```

パースしてみる:

```
  println(CSVParser("a,b,c\r\n1,2,3\r\nx,y,z"))
```

実行結果:

```
Right(CSV(Header(List(a, b, c)),List(Record(List(1, 2, 3)), Record(List(x, y, z)))))
```

# 演算子・メソッド

ここでいくつか演算子・メソッドが出てきたので解説しておきます。


* `p ~ q`: p の後に q が続くパターンにマッチ
* `p | q`: p または q にマッチ(定義した順)
* `p ||| q`: p または q にマッチ(文字列が長いもの順)
* `p.*`, `rep(p)`: pが0回以上連続する場合にマッチ
* `p.+` : pが1回以上連続する場合にマッチ
* `p ^^ f`: pにマッチした値に対して関数fを適用する。主に変換などに用いる
* `p.?`, `opt(p)`: pがあるかないかどちらかにマッチ。あればSome、なければNoneが返る。
* `repsep(p, q)`: qで区切られたpの繰り返しにマッチ。配列などに使うと便利。
* `p ~> q`: p の後に q が続くパターンにマッチ。pの結果を捨てる
* `p <~ q`: p の後に q が続くパターンにマッチ。qの結果を捨てる
* `not(p) ~ q`: p の後に q が続かないパターンにマッチ

# おわりに

この記事では、Scalaのパーサコンビネータを使ったパーサの実装方法を解説しました。独自のDSLを開発するときや、正規表現では複雑になりすぎる場合などに、パーサを作ってみてはいかがでしょうか。

# 関連して書いた記事

* [Scala: パーサコンビネータの | と ^^ の組み合わせは注意 - Qiita](http://qiita.com/suin/items/48899a38af75ac358939)
* [Scala: パーサコンビネータで行数・文字数を取得しながらパースする - Qiita](http://qiita.com/suin/items/9791980080d9f2848151)