Scala の Parser を試したらハマったのでまとめておく。

　以前、Scala の Parser を試したんですがハマってしまったので、ハマり記念ということで記事にしておこうと思います。

ちなみに、Scala のパーサコンビネータについて知りたい人は僕のこの記事よりも @kmizu さんのスライドを読んだ方が良いように思います。

■ Scala のパーサ概要

　まず import しておきたいのは scala.util.parsing.combinator.Parsers です。

　主な手順は次の通り。
　１．Parsers オブジェクトを作る。
　２．Parsers.Parser[ Result ] のオブジェクトを作る。ここで Result はパース結果の型。
　３．２．で作ったオブジェクトにパース対象のシーケンスオブジェクトを渡す。
　４．３．の結果得られるものがパース結果。

■ 簡単なトコからいきましょ
　まず Char のシーケンスを読んで MyData を返すパーサを作ってみます。
　（少し遠回りになろうが、最初ですし泥臭く説明しますね。）

// Sample1
import scala.util.parsing.combinator.Parsers;
import scala.util.parsing.input.CharSequenceReader;

case class MyData( val d: Char, val a: Char ) {}

class MyParser extends Parsers
{
  type Elem = Char;

  // 「数字にマッチするよ！」を定義するよ！
  val isDigit = elem( "DIGIT", { case c => '0' <= c && c <= '9' } );
  // 「アルファベットにマッチするよ！」を定義するよ！
  val isAlpha = elem( "ALPHA", { case c => 'a' <= c && c <= 'z' } );

  // パースするオブジェクトを用意するよ！ 
  val parser: Parser[ MyData ] =
    isDigit ~ isAlpha ^^ { case d ~ a => MyData( d, a ) };

  // パースするよ！
  def parse( s: String ): ParseResult[ MyData ] =
    parser( new CharSequenceReader( s ) );
}

object Main extends App
{
    val p = new MyParser();
    p.parse( "5a" )      // "5a" という文字列をパースして MyData を生成する。
     .map { println _ }; // 成功したら表示。
}

実行結果： MyData(5,a)

何ていうかパースしたぞー！っていう達成感が薄いですがまずこのサンプルの詳細を説明します。

まず↓これが無いと始まらない。

class MyParser extends Parsers
{
  type Elem = Char;

  // (略)
}

Parsers を継承した MyParser を定義します。これが冒頭で書いた手順１．にあたります。Main の中で実際に new してますね。ここではパース対象の型に Char を指定しています。文字シーケンスを読むんだぞー！と明記するわけです。

で、次に肝になるのは↓ココ。

  // パースするオブジェクトを用意するよ！ 
  val parser: Parser[ MyData ] =
    isDigit ~ isAlpha ^^ { case d ~ a => MyData( d, a ) };

　ここが手順２．にあたります。
　えーと、構文知らないと全く分かんないですよね。「^^」より前の「isDigit ~ isAlpha」がこのパーサがマッチするパターンです。この例でいうと「数字があってアルファベットがある」場合にのみマッチします。そして「^^」より後の「{ case d ~ a => MyData( d, a ) };」がマッチした部分を元にパース結果オブジェクトに変換しているところです。この例でいうと「マッチした数字を d, アルファベットを a として MyData のコンストラクタ引数に渡す」ということが書かれています。
　型が Parser[ MyData ] になってるのがわかるかと思いますが、「パース結果が MyData となるようなパーサ」型という見たまんまの意味となります。

そして最後↓ココに注目。

  // パースするよ！
  def parse( s: String ): ParseResult[ MyData ] =
    parser( new CharSequenceReader( s ) );

　さっき定義した parser オブジェクトの apply() に CharSequenceReader を渡しています。これが手順３．です。戻り値は ParseResult[ MyData ] 型となってます。この型がパース結果そのものになります（手順４．）。

■ もっと実用的で複雑なパターンをパースする。

　さっきの例は「数字の次にアルファベットがあるようなパターン」でしたがそんなもんは単純すぎて if 文で書けるわけなのでもっと複雑なのをやりましょ。

　「数字か大文字アルファベットがあって、次に空白があって、その後アルファベットが続く文字列」をパースしてみます。

// Sample2
import scala.util.parsing.combinator.Parsers;
import scala.util.parsing.input.CharSequenceReader;

case class MyData( val head: Char, val name: String ) {}

class MyParser extends Parsers
{
  type Elem = Char;

  // 「数字にマッチするよ！」を定義するよ！
  val isDigit = elem( "DIGIT", { case c => '0' <= c && c <= '9' } );
  // 「大文字にマッチするよ！」を定義するよ！
  val isUpper = elem( "UPPER", { case c => 'A' <= c && c <= 'Z' } );
  // 「小文字にマッチするよ！」を定義するよ！
  val isLower = elem( "LOWER", { case c => 'a' <= c && c <= 'z' } );
  // 「アルファベットにマッチするよ！」を定義するよ！
  val isAlpha = isUpper | isLower;
  // 「空白にマッチするよ！」を定義するよ！
  val isSpace = elem( "SPACE", { _ == ' ' } );

  // パースするオブジェクトを用意するよ！ 
  val parser: Parser[ MyData ] =
    ( isDigit | isUpper ) ~ isSpace ~ isAlpha.+ ^^ { case d ~ _ ~ n => MyData( d, n.mkString ) }

  // パースするよ！
  def parse( s: String ): ParseResult[ MyData ] =
    parser( new CharSequenceReader( s ) );
}

object Main extends App
{
    val p = new MyParser();
    p.parse( "1 Apple" ).map { println _ };
    p.parse( "  Apple" ).map { println _ }; // 失敗する
    p.parse( "D Apple" ).map { println _ };
}

実行結果：
MyData(1,Apple)
MyData(D,Apple)

↓ココがまさにパターンを記述してるとこですね。

  // パースするオブジェクトを用意するよ！ 
  val parser: Parser[ MyData ] =
    ( isDigit | isUpper ) ~ isSpace ~ isAlpha.+ ^^ { case d ~ _ ~ n => MyData( d, n.mkString ) }

　・「( isDigit | isUpper )」で「数字か大文字アルファベット」
　・「isAlpha.+」で「アルファベットが 1 文字以上連続する」

をそれぞれ意味しますがこれもう見たまんまですね。
他にも、もっともっと多彩な表現ができます。

　・「a ~ b」：a の次に b がある場合にマッチ。
　・「a | b」：a または b がある場合にマッチ。
　・「a ||| b 」：a または b がある場合、長い方にマッチ。
　・「a*」：a の 0 回以上の繰り返しにマッチ。
　・「a+」：a の 1 回以上の繰り返しにマッチ。
　・「a?] ：a の 0 回または 1 回の繰り返しにマッチ。
　・「repseq( a, b )」： b で区切られた a の繰り返しにマッチ。

あと、さらっと使いましたが↓ここ。

  // 「アルファベットにマッチするよ！」を定義するよ！
  val isAlpha = isUpper | isLower;

　この isAlpha の定義に上で説明した記法を使っているのですが、isAlpha を利用するときもまた同じ記法が使えます。つまりパターンの記述は構造化することができるわけです。素晴らしい...。

■ Char 以外のシーケンスをパースする

　ここまでは Char でしたが、もっと別の型のシーケンスをパースする方法について説明します。

　「type Elem = Char;」を「type Elem = T;」にしたらいーんでねーの？

と思ったらそうでは無いようです。

　まず、Parser[].apply() に渡すシーケンスオブジェクトを用意しないといけません。Char の場合は CharSequenceReader っていう便利なものが最初から用意されてるから楽ができていただけです。シーケンスオブジェクトは scala.util.parsing.input.Reader を継承して定義します。

import scala.util.parsing.combinator.Parsers;
import scala.util.parsing.input.{ Reader, Position }; // ← ここ変えたよ！

case class MyChar( val c: Char ) {}

class MyParser extends Parsers
{
  type Elem = MyChar;

  // これがシーケンスオブジェクトの型定義。
  class MyReader( val data: Array[ MyChar ], override val offset: Int )
    extends Reader[ MyChar ]
  {
    def this( data: Array[ MyChar ] ) = this( data, 0 );

    class MyPosition( val offset: Int ) extends Position
    {
      override final val line = 1;
      override def column = offset + 1;
      override def lineContents = "";
    }

    override def atEnd = offset >= data.length;
    override def first = if( atEnd ) null else data( offset );
    override def pos = new MyPosition( offset );
    override def rest = new MyReader( data, offset + 1 );
  }

  // パースするオブジェクトを用意するよ！ 
  val parser: Parser[ MyData ] = { /*(略)*/ }

  // パースするよ！
  def parse( data: Array[ MyChar ] ): ParseResult[ MyData ] =
    parser( new MyReader( data ) );
}

　というわけで、ちょっと面倒ですがこんなコードが必要になります。
　first メソッドは atEnd のとき null を返さないと Parser が正しくシーケンス終端を認識してくれません。ScalaDoc をちらっと読んだだけではそんな説明は目に留まらなかったので僕はハマりました。それから MyPosition は line, column で現在位置を表現する型なのですがインデックスは 0 ではなく 1 から始まる決まりなので + 1 しておかないとダメです。
　っつーか、特にメモリや速度でシビアな要求が無いのであれば、MyReader の定義は上のコードのコピペで良いんじゃないかとすら思います。Char の場合はかなり楽にパーサを組めるのに、Char 以外の型になったとたんレベル上がりすぎな気がしますね。

• • • • -

追記：ふと気づきました。ここで説明した部分だけだと、やってることが正規表現と変わらないですねw 気が向いたら不足分をまた記事にします。