この記事では、Scalaのパーサコンビネータを用いて、BNF風の定義を書くだけで、オブジェクトのマッピングからパースエラーのハンドリングまでできてしまう高機能なパーサを作る方法を解説します！
パーサコンビネータとは?
Scalaにはパーサコンビネータというライブラリがあります。BNFと似たの記法で構造を定義するだけで簡単にパーサを実装することができます。たとえば、□□□-□□□□のような形式の郵便番号をパースするコードは次のように書くことができます。
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 メソッドを実装した例です。
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 型を返すようにします。
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 のエラーメッセージに行数と文字数を追加したものです。
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) のような分かりやすい形になるように実装しなおしてみます。
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を調べたり考えておくと、実装にとりかかりやすくなります。
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を開発するときや、正規表現では複雑になりすぎる場合などに、パーサを作ってみてはいかがでしょうか。