RegexParsersで手軽にScalaのパーサコンビネータを使ってみる

入門記事の一覧

About - case class HatenaDiary(id: Symbol = ’seratch2)

Scalaのバージョン

この記事が対象とする Scala のバージョンは「2.9.1.final」です。

お読みになる前に

パーサコンビネータの体系的な入門についてはこちらの記事やコップ本などの書籍等をご確認ください。

http://itpro.nikkeibp.co.jp/article/COLUMN/20100526/348498/
http://itpro.nikkeibp.co.jp/article/COLUMN/20100526/348454/

この記事は、RegexParsersを使って比較的手軽にパーサコンビネータの使い方を知るという趣旨です。

パーサのAPI

以下の scaladoc を一読すると、基本的なAPIを把握することができるかと思います。

http://www.scala-lang.org/api/current/index.html#scala.util.parsing.combinator.Parsers$Parser

蛇足ですが、以下にこの記事を読む上で必要なるものをチートシートとしてまとめます。

"null"       : リテラル
"\\s+".r     : 正規表現（暗黙の型変換されるため（後述））
P ~ Q        : PとQを逐次合成（連接）
P <~ Q       : PとQを逐次合成、左の結果のみ保持
P ~> Q       : PとQを逐次合成、右の結果のみ保持
P | Q        : PとQの選択（順番に評価）
rep(P), P*   : Pをくりかえし
repsep(P, Q) : Qの成功を区切り位置としてP
P ^^ f       : 解析結果の変換（Pが成功したらf（関数）を実行）

以下に示すサンプルの中で出てきたら適宜参照してください。

英語表記の氏名をパースするサンプル

実用性は全くないですが、できるだけ短くということで英語表記の氏名をパースするサンプルを書いてみます。

逐次合成

以下は姓名をそれぞれ英字のみの正規表現で抽出するパーサを書き、それを逐次合成しています。

なお、RegexParsersではシンボルの間にある空白文字はデフォルトでは読み飛ばすようになっているので、空白文字に対するパーサは要りません。*1

import util.parsing.combinator._
object NameParser extends RegexParsers {
  def firstName = "[a-zA-Z]+".r
  def lastName = "[a-zA-Z]+".r
  def fullName = firstName ~ lastName
  def parse(input: String) = parseAll(fullName, input)
}

val res = NameParser.parse("Martin Odersky")
println(res)        
// [1.15] parsed: (Martin~Odersky)

println(res.get._1) // Martin
println(res.get._2) // Odersky

上記のサンプルを例に基本的な内容を説明します。

パーサの単位であるParser型は、入力値を引数として受け取って ParseResult を返す関数です。

abstract class Parser[+T] extends (Input => ParseResult[T])

RegexParsers では parseAll に Parser 型とパースする対象の入力値を渡すとパース処理を実行します。

def parseAll[T](p: Parser[T], in: java.lang.CharSequence): ParseResult[T]

上記の例で使っている「~」は Parser 型に定義された逐次合成（sequential composition）を行うためのメソッドです。

parseAll に渡されている fullName は二つのパーサを逐次合成して新しいパーサを返しています。

といいつつ、firstName、lastName は Regex 型なので Parser 型ではないのですが、RegexParsers に以下のような暗黙の型変換が定義されていて

implicit def regex(r: Regex): Parser[String] = new Parser[String] {
  def apply(in: Input): ParseResult[T] = { ... }  
}

スコープ内では Regex 型も Parser[String] 型としてふるまうことが可能になっています。

そのため Regex 型をパーサとして逐次合成することができ、fullName が返す型は Parser 型となります。

なお、同様の型変換が String 型にも定義されています。

implicit def literal(s: String): Parser[String] = new Parser[String] {
  def apply(in: Input): ParseResult[T] = { ... } 
}

解析結果の変換

上記のままだと結果が少々扱いづらいので Name という型で返すよう修正してみます。

以下のように「^^」の後にマッチした結果を引数に受け取る関数を渡します。

import util.parsing.combinator._
case class Name(first: String, last: String)
object NameParser extends RegexParsers {
  def firstName = "[a-zA-Z]+".r
  def lastName = "[a-zA-Z]+".r
  def fullName = firstName ~ lastName ^^ { result => Name(result._1, result._2) }
  def parse(input: String) = parseAll(fullName, input)
}

val res = NameParser.parse("Martin Odersky")
println(res)        
// [1.15] parsed: Name(Martin,Odersky)

val name: Name = res.get
println(name.first) // Martin
println(name.last)  // Odersky

一つ前の fullName は戻り値の型を書くと以下のようになりますが

def fullName: NameParser.Parser[NameParser.~[String,String]] = firstName ~ lastName

上記の例だと

def fullName: NameParser.Parser[Name] = firstName ~ lastName ^^ { result => Name(result._1, result._2) }

となります。

くりかえし

同じ正規表現を二回使っていたので「rep」によるくりかえしで書き換えてみます。

なお「Martin Odersky」という入力の場合は挙動は変わりませんが、このパーサはその前のサンプルとは仕様が変わっています。

前のサンプルでは3つ目以降のトークンがあるとパースエラーになりますが、このパーサでは3つ目以降のトークンがあってもパースエラーにはならず、単に値を捨てるだけです。

import util.parsing.combinator._
case class Name(first: String, last: String)
object NameParser extends RegexParsers {
  def name = "[a-zA-Z]+".r
  def fullName = rep(name) ^^ { names => Name(names(0), names(1)) } // namesはList[String]
  def parse(input: String) = parseAll(fullName, input)
}

やってみよう

ミドルネームも考慮したサンプルを書いてみてください。

CSV をパースするサンプル

CSV 形式のデータをパースするサンプルを書いてみます。

行単位でパースする

まず、改行文字で区切って行単位を文字列として取得し、List[String] 型として結果が返るようパースしてみます。

なお、RegexParsers での Elem が Char 型であることから改行文字については String 型ではなく Char 型として定義する必要があります。

import util.parsing.combinator._
object LinesParser1 extends RegexParsers {
  def eol = opt('\r') <~ '\n'
  def line = ".*".r <~ eol
  def lines = rep(line)
  def parse(input: String): ParseResult[List[String]] = parseAll(lines, input)
}

val csv = """name,age,place
Andy,20,Tokyo
Brian,22,Seoul
"""

val res_line1 = LinesParser1.parse(csv)
println(res_line1) 
// [4.1] parsed: List(name,age,place, Andy,20,Tokyo, Brian,22,Seoul)

次の節の導入として String 型から単純な Line という型に変換してみます。

上でも出てきましたが同様に「^^」のあとに続く関数で Line 型に変換します。

case class Line(line: String)

object LinesParser2 extends RegexParsers {
  def eol = opt('\r') <~ '\n'
  def line = (".*".r <~ eol) ^^ { line => Line(line) }
  def lines = rep(line)
  def parse(input: String): ParseResult[List[Line]] = parseAll(lines, input)
}

CSV としてパースする

次に CSV 形式のデータをパースしてみます。まずはかなり単純なパーサです。

abstract class Row
case class HeaderRow(cells: List[String]) extends Row
case class DataRow(cells: List[String]) extends Row

object CsvParser1 extends RegexParsers {
  def eol = opt('\r') <~ '\n'
  def line = ".*".r <~ eol
  def headerRow = line ^^ { row => new HeaderRow(row.split(",").toList) }
  def dataRow = line ^^ { row => new DataRow(row.split(",").toList) }
  def all = headerRow ~ rep(dataRow)
  def parse(input: String): ParseResult[HeaderRow~List[DataRow]] = parseAll(all, input)
}

val res_csv1 = CsvParser1.parse(csv)
// [4.1] parsed: (HeaderRow(List(name, age, place))~List(DataRow(List(Andy, 20, Tokyo)), DataRow(List(Brian, 22, Seoul))))

res_csv1.get._1
// HeaderRow(List(name, age, place))
res_csv1.get._2
// List(DataRow(List(Andy, 20, Tokyo)), DataRow(List(Brian, 22, Seoul)))

このままだと扱いづらいので all に関数を渡して型変換してみます。

object CsvParser11 extends RegexParsers {
  ...
  def all = headerRow ~ rep(dataRow) ^^ { res => res._1 :: res._2 }
  def parse(input: String): ParseResult[List[Row]] = parseAll(all, input)
}

val res_csv11 = CsvParser11.parse(csv)

res_csv11.get foreach {
  case HeaderRow(cells) => println("Header:" + cells)
  case DataRow(cells) => println("Data:" + cells)
}
// Header:List(name, age, place)
// Data:List(Andy, 20, Tokyo)
// Data:List(Brian, 22, Seoul)

しかし、このパーサではセルにカンマや改行が含まれている場合などには対応できていません。

全てのセルをダブルクォートで囲んでいる CSV をパースする

次に「全てのセルをダブルクォートで囲んでいる」という条件付きの CSV をパースしてみます。

正しくハイライトできないようなのでここはハイライトなしです。

object CsvParser2 extends RegexParsers {
  def eol = opt('\r') <~ '\n'
  def cell = "\"" ~> "[^\"]*".r <~ "\""
  def row = repsep(cell, ",") <~ eol
  def headerRow = row ^^ { cells => new HeaderRow(cells) }
  def dataRow = row ^^ { cells => new DataRow(cells) }
  def all = headerRow ~ rep(dataRow) ^^ { res => res._1 :: res._2 }
  def parse(input: String): ParseResult[List[Row]] = parseAll(all, input)
}

val csv2 = """"name","age","memo"
"Andy","20","Skills
- English,Chinese
- Java,Scala
"
"Brian","22",""
"""

val res_csv2 = CsvParser2.parse(csv2)
println(res_csv2)
// [7.1] parsed: List(HeaderRow(List(name, age, memo)), DataRow(List(Andy, 20, Skills
// - English,Chinese
// - Java,Scala
// )), DataRow(List(Brian, 22, )))

意図通りパースできているようです。

ダブルクォートありなし混合の CSV をパースする

最後に以下のような CSV データをパースしてみます。ageの項目はダブルクォートで囲まれていないという混合フォーマットです。

val csv3 = """"name",age,"memo"
"Andy",20,"Skills
- English,Chinese
- Java,Scala
"
"Brian",22,""
"""

やってみよう

「ダブルクォートありなし混合のCSVをパースする」を実装してみてください。
（スクロールすると私が書いた回答例があります）

import util.parsing.combinator._

abstract class Row
case class HeaderRow(cells: List[String]) extends Row
case class DataRow(cells: List[String]) extends Row

object CsvParser3 extends RegexParsers {
  override val whiteSpace = "[ \t]+".r
  def eol = opt('\r') <~ '\n'
  def notQuotedCell = "[^\"\r\n,]*".r
  def quotedCell = "\"" ~> "[^\"]*".r <~ "\""
  def row = repsep((quotedCell | notQuotedCell), ",")
  def rows = repsep(row, eol) ^^ {
    case cellsList => {
      cellsList match {
        case Nil => Nil
        case hCells :: dCellsList => {
          val hRow = new HeaderRow(hCells)
          val dRows = dCellsList filter {
            // remove empty line
            case l => l.size != 1 || ! l(0).trim.isEmpty
          } map {
            case dr => new DataRow(dr)
          }
          hRow :: dRows
        }
      }
    }
  }
  def parse(input: String): ParseResult[List[Row]] = parseAll(rows, input)
}

val csv3 = """"name",age,"memo"
"Andy",20,"Skills
- English,Chenese
- Java,Scala
"
"Brian",22,
"Charles",33,
,33,
"""

val res_csv3 = CsvParser3.parse(csv3)
println(res_csv3)

*1:読み飛ばしたくない場合は「override val whiteSpace = "".r」のようにします。