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

  • 80
    Like
  • 0
    Comment
More than 1 year has passed since last update.

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

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

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

サンプルコード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 メソッドを実装した例です。

サンプルコード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が発生してしまいます。

  println(PostalCodeParser("1234567"))

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

サンプルコード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 を渡してみましょう。

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

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

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

サンプルコード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) のような分かりやすい形になるように実装しなおしてみます。

サンプルコード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を調べたり考えておくと、実装にとりかかりやすくなります。

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のパーサコンビネータを実装するとこのようになります:

  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をパースしてみます:

  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に変換するようにします。

  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を開発するときや、正規表現では複雑になりすぎる場合などに、パーサを作ってみてはいかがでしょうか。

関連して書いた記事