RegexParsersでパーサコンビネータ書くときの注意点

まあ、仕様とかソースをよく読めという話に帰着はするんですが、軽くサンプルを読んだのみで突き進んだ結果、思いっきりハマってしまったので、他の人が私と同じ轍を踏まなくて良いように残しておきます。パーサコンビネータの利用法というよりは、こういうところを気をつけておくとあるあるなハマりどころは回避できるよ、というレベルで。
なお、以下の注意点はRegexParsersのサンプルを読んだことが有るというレベルを想定していますので、RegexParsersの使い方については説明していません。

繰り返しは無限ループに注意

まずは、以下のソースをご覧ください。

def facilities: Parser[FacilitiesByLineType] = opt(lineType)~rep(facility)^^{
  case lineType~facilities => FacilitiesByLineType(lineType.getOrElse(null), facilities)
}

def facilitiesByMultiLines: Parser[List[FacilitiesByLineType]] = rep(facilities)^^{
  case facilitiesByMultiLines => facilitiesByMultiLines
}

これは実際に私が書いて無限ループしたコードです。無限ループしたのは、facilitiesByMultiLinesとfacilitiesでrep(opt~rep)とネストしてしまったからです。
まず、optは0 or 1、repは0以上です。この時点で両方とも0を許容するため、opt~repはどのような入力にもマッチするようになります。それをrepで繰り返しているため、空入力に延々とマッチして無限ループに陥ってしまった訳です。*1

で、Scala JPのMLで教えてもらった解決策は、

rep(facilities ~ lineFeed) 

のように行末の改行文字を含めるか、そもそもfacilitiesを空入力にマッチさせないようにするかのどちらかでした*2。

お勧めされた方法が後者であることと、パースしたい文字列の仕様が少なくとも1行はあることが前提だと気づいたので、最終的な形は以下になりました。

def facilities: Parser[FacilitiesByLineType] = opt(lineType)~rep(facility)^^{
  case lineType~facilities => FacilitiesByLineType(lineType.getOrElse(null), facilities)
}

def facilitiesByMultiLines: Parser[List[FacilitiesByLineType]] = rep(facilities)^^{
  case facilitiesByMultiLines => facilitiesByMultiLines
}

今回の例では省略していますが、再帰的に他のrepを使用しているところも同様に書きなおしました。今回の仕様としてはこれでOKかと思います。

パーサ関数はdefよりもlazy valが吉

Parser[T]はFunction1をmixinしている関数です。定義された関数を連結して呼び出してパースする訳ですが、パース関数をdefでメソッド定義すると呼び出すたびにParser[T]が生成されます。

関数オブジェクトなので、一度生成すれば基本的には問題ないはず。というわけで、lazy valで定義してしまいましょう。
lazyをつけて遅延評価するから生成のオーバーヘッドも最小限になるはずです。

先ほどのソースを使って例を出すと、以下のように変更したほうがよい、ということになります。

lazy val facilities: Parser[FacilitiesByLineType] = opt(lineType)~rep(facility)^^{
  case lineType~facilities => FacilitiesByLineType(lineType.getOrElse(null), facilities)
}

lazy val facilitiesByMultiLines: Parser[List[FacilitiesByLineType]] = rep(facilities)^^{
  case facilitiesByMultiLines => facilitiesByMultiLines
}

デフォルトでは空白を読飛ばすので注意

これが、一番「仕様読め、俺」と言いたい感じの話だったのですが、あるミドルウェアのサマリーログのパーサを書いていた時の話。
このログは、「人が見る」ということを目的としているためか、いたるところに半角空白で成形した後があるんですね。で、そのパーサを書く時に行頭やシンボルの間の半角空白をマッチして切り捨てようとしたら、空白部分でマッチしないためにエラーになる。
最初は正規表現の書き方が悪いのかと思ってうんうん唸りながら調べてたわけですが、どうにも原因はそっちじゃないような感じ。
で、色々と調べた結果たどりついた記事が以下です。

http://seratch.hatenablog.jp/entry/20111010/1318254084#f1

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

なるほど。で、実際のところがどうなってるかRegexParsersのソースを確認してみたところ、こんな感じになっていました(関係ありそうなところを抜粋)。

  /** Method called to handle whitespace before parsers.
*
* It checks `skipWhitespace` and, if true, skips anything
* matching `whiteSpace` starting from the current offset.
*
* @param source The input being parsed.
* @param offset The offset into `source` from which to match.
* @return The offset to be used for the next parser.
*/
  protected def handleWhiteSpace(source: java.lang.CharSequence, offset: Int): Int =
    if (skipWhitespace)
      (whiteSpace findPrefixMatchOf (source.subSequence(offset, source.length))) match {
        case Some(matched) => offset + matched.end
        case None => offset
      }
    else
      offset

  /** A parser that matches a literal string */
  implicit def literal(s: String): Parser[String] = new Parser[String] {
    def apply(in: Input) = {
      val source = in.source
      val offset = in.offset
      val start = handleWhiteSpace(source, offset)
      var i = 0
      var j = start
      while (i < s.length && j < source.length && s.charAt(i) == source.charAt(j)) {
        i += 1
        j += 1
      }
      if (i == s.length)
        Success(source.subSequence(start, j).toString, in.drop(j - offset))
      else {
        val found = if (start == source.length()) "end of source" else "`"+source.charAt(start)+"'"
        Failure("`"+s+"' expected but "+found+" found", in.drop(start - offset))
      }
    }
  }

  /** A parser that matches a regex string */
  implicit def regex(r: Regex): Parser[String] = new Parser[String] {
    def apply(in: Input) = {
      val source = in.source
      val offset = in.offset
      val start = handleWhiteSpace(source, offset)
      (r findPrefixMatchOf (source.subSequence(start, source.length))) match {
        case Some(matched) =>
          Success(source.subSequence(start, start + matched.end).toString,
                  in.drop(start + matched.end - offset))
        case None =>
          val found = if (start == source.length()) "end of source" else "`"+source.charAt(start)+"'"
          Failure("string matching regex `"+r+"' expected but "+found+" found", in.drop(start - offset))
      }
    }
  }

パーサを文字列や正規表現から暗黙的に型変換するときに、そのパーサに渡される文字列のオフセット位置からの連続した空白をトラップした開始位置にするようになっています。そのため、RegexParserを使う限りにおいてはマッチさせたい各パーサ間の空白は意識する必要がないわけですね。
ちなみにこれ、scaladocの最初にちゃんと書いてあります。「よく読まなかった俺が悪い」事案です。

また、RegexParserがトラップするのは各パーサの前にある連続した空白文字であって入力を空白で分割するわけではないので、当然のことながらパーサが「以降の文字すべて(空白も含む)」でマッチするようになっていると、空白で勝手に区切ってくれたりはしません。マッチするときにはパーサがちゃんと意図したところで区切ってくれるように注意しましょう。

というわけで、大方釈迦に説法的な注意点を羅列してきたわけですが、とりあえず「ちゃんとscaladocと仕様読め」に尽きるのではないかな、と思いました。まる。

*1:もそっと詳しく書くと、opt~repが空でマッチ=>空でフィード(つまり進まない)=>外側がrepなので繰り返そうとしてフィードされていない文字列を入力=>opt~repから繰り返し、という流れかな、と

*2:行末に含めるのも空入力へのマッチを回避するものなので、アプローチの違いなのかもしれませんが