パーサコンビネータ

Scala

どう書くにyuinさんが投稿されたCSVパーサエロと風俗情報満載 どう抜く？を研究中。

とりあえず、私の理解しやすいように以下のような感じに書き換えてみた。

object CSVParser {
  import scala.util.parsing.combinator.{Parsers, ImplicitConversions, ~, mkTilde}
  import java.lang.Character.isISOControl

  trait Base
  case class File(records:List[Record])  extends Base
  case class Record(fields:List[Field])  extends Base
  case class Field(s:String)             extends Base { override def toString = s }

  class CSVParser extends Parsers {
    type Elem = Char

    val doubleQuote    = '"'
    val fieldSep       = ','
    val recordSep      = '\n'
    val nullString     = ""
    
    private def notMeta(c:Elem)         = c != fieldSep && c != recordSep && c != doubleQuote && !isISOControl(c)
    private def notDoubleQuote(c:Elem)  = c != doubleQuote
    private def mkString(cs:List[Any]) = cs.mkString(nullString)
    
    lazy val chars          = elem("chars",          notMeta)
    lazy val charsInQuote   = elem("chars in field", notDoubleQuote)

    lazy val quote          = doubleQuote     ^^ success
    lazy val quoteInQuote   = repN(2, quote)  ^^ {cs => doubleQuote}

    lazy val nullableField  = chars.*                                                   ^^ {cs => Field(nullString)}
    lazy val quotedField    = doubleQuote ~ (charsInQuote|quoteInQuote).* ~ doubleQuote ^^ {cs => Field(mkString(cs))}
    lazy val field          = chars.+                                                   ^^ {cs => Field(mkString(cs))}

    lazy val record         = (field|quotedField|nullableField).*(fieldSep) ^^ Record
    lazy val file           = record.*(recordSep)                           ^^ File
  }
}

//======================================
object csvtest extends Application {
  import scala.util.parsing.input.CharArrayReader
  import scala.io.Source

  val inputfilename = "testdata/test.csv"

  val parser = new CSVParser.CSVParser
  val reader = new CharArrayReader(Source.fromFile(inputfilename).toList.toArray)

  val csvfile = parser.file(reader)
  println(csvfile)

  csvfile.map{csvfile => 
    val records = csvfile.records
//    println(records)
    records.map{record =>
      val fields = record.fields
//      println(fields)
      for (i <- 1 to fields.length) {
        println(i + " => " + fields(i-1) )
      }
    }
  }
}

パーサコンビネータはなかなかすごい実装ですな

とした上で、現在の疑問点は以下の通り
（２月２２日 Lingr でmizushimaさんに講義していただいた結果を追記）

  • trait Base、case class ... extends Baseする理由（上記のコードだと、無くても動く模様）
    • おそらく、それらのクラスがCSVの構文木を表現している、ということを示すために継承したのだと思われる（ほんとのところはyuinさんに聞かなければわからない・・・）この場合、特に必要ではない。
  • type Elem = Charsとする理由
    • Parsers traitにて type Elemというのが定義されており、それにCharという実体を与えている。（抽象メソッドがあるように、Scalaは抽象型という機能を持っていて、サブクラス(やtraitを継承したクラス)で、それに実体を与えることができる）ここでは構文解析上の最小単位を指定している。
  • lazyにする理由
    • 単なるvalだと、相互参照があった場合にエラーになってしまう。具体的には、以下のようなことをする場合、lazyが無ければエラーになる。
val a = ...(bの参照) ...
val b = ...(aの参照) ...

val a = ...(bの参照) ...
val b = ...(aの参照) ...
    • パーザコンビネータとは無関係。単純に、入力ファイルから読み取るときに、SJIS前提になっている。以下の様にすることで入力時の文字コードを指定可能。
Source.fromFile(name: String, enc: String): Source
  • 「Perser#^^」関数の動作の詳細（hogehoge ^^ piyopiyoは「piyopiyo.^^(hogehoge)」？ でも、そうするとコンパイルは通るけど、実行時のエラーになる・・なぜ？）
    • 左辺の構文要素の解析結果を受け取って、右辺の関数の仮引数に渡し、新しい構文解析の結果(semantic value)を作り出すための関数。
    • lazy val quote = doubleQuote ^^ successについては、Char#^^の様に見えるが、これはParsers traitのimplicit def acceptで定義されている。
  • 「chars.+ ^^ {cs => Field(mkString(cs))}」の「^^」は？ {cs => Field(mkString(cs))}.^^(chars.+)だとコンパイルできない
    • 上記と同じ理由で。(chars.+).^^{cs => Field(mkString(cs))}だから
  • 「chars.*」の「*」は「Parser#*」？
    • Yes
  • 「chars.+」の「+」は「Parser#+」？
    • Yes
  • 「(charsInQuote|quoteInQuote)」の「|」は「Parser#|」？
    • Yes
    • クラスの位置が変わった模様。以下の修正で（現時点では）一応動くようになる。
import scala.util.parsing.combinatorold.{Parsers, ImplicitConversions, ~, mkTilde}
  • chars.* は (chars*)とも書ける