Scala Advent Calendar jp 2011の記事です。12/07に割り振られていたことに気づいていませんでしたorz。申し訳ありません。 さて、ネタを後で考えるつもりだったので迷ったのですが、直近で面白かったネタということでパーザコンビネータのちょっと変わった 使い方について紹介したいと思います。
さて、いきなり話が飛びますが、皆様はRubyのヒアドキュメントについてご存知でしょうか？
puts <<JSON_STR
{"foo":"bar",
"bar":"baz"}
JSON_STRと書くと、
{"foo":"bar",
"bar":"baz"}と出力される、アレです。<<NAMEが出てくると、その次の行からNAMEのみの行が来るまでが文字列として取り出せる機能ですね (実際には、Rubyのヒアドキュメントの仕様はもっと複雑ですが、ここでは単純化したものを考えます)。
Rubyをご存知の方は当然のようにこの機能を使われていると思います。しかし、この機能、 解析殺し(パーザブレイカー)[^1]と呼ぶべき、構文解析屋さんにとっては面倒な機能の一つです。さて、何が面倒なの でしょうか？具体例を挙げてみましょう。以下のRubyプログラムは何を出力するでしょうか？
kamijosan = "#{<<IMAGINE}#{<<BREAKER}！！"
その幻想を
IMAGINE
ぶち殺す
BREAKER
puts kamijosan正解は、"その幻想をぶち殺す！！"です。これは、わかりやすいように文面を考えたので、どのように構文解析されたかを考えずとも
推測可能だったと思いますが、これ、解析する立場からするとかなり面倒です。普通の構文解析なら、基本的に「前から順番に」
読んでいくことができますが、上記の例では、<<IMAGINEが来た時点で、その行の残り文字列をいったん退避させて、次の行から
IMAGINEのみが出てくる行まで読み取って、それを<<IMAGINEの値として、退避していた文字列から構文解析を再開し、しかも、先ほど
読み取ったIMAGINEまでの部分は読み飛ばさなくてはいけません。つまり、いったん前に進んで成功した後、後戻りして、入力列
を改変した上で解析を再開する、と言った作業が必要になるわけです。
** (追記) 実際のRuby処理系は、字句解析器と構文解析器が連携して動作する形で構文解析を行っており、Scalaのパーザコンビネータ のように、字句解析/構文解析の区別が無い構文解析とは、実際に行っている処理はやや異なりますので、その点はご注意ください。**
さて、ここまでは前フリで、これをいかにしてScalaのパーザコンビネータで実現するか、というのが本題になります。まずは、 自作言語Toysのパーザからヒアドキュメントに関する部分を抜き出した部分をお見せしましょう。以下のようになります。
def rebuild(a: Reader[Char], newSource: String, newOffset: Int): Reader[Char] = new Reader[Char] {
def atEnd = a.atEnd
def first = a.first
def pos = a.pos
def rest = rebuild(a.rest, newSource, offset + 1)
override def source = newSource
override def offset = newOffset
}
def cat(a: Reader[Char], b: Reader[Char]): Reader[Char] = {
val aSource = a.source + b.source.subSequence(b.offset, b.source.length()).toString
if(a.atEnd) {
rebuild(b, aSource, a.offset)
} else {
new Reader[Char] {
private lazy val result = cat(a.rest, b)
def atEnd = a.atEnd
def first = a.first
def pos = a.pos
def rest = result
override def source = aSource
override def offset = a.offset
}
}
}
lazy val oneLine: Parser[String] = regex(""".*(\r\n|\r|\n|$)""".r)
lazy val hereDocument: Parser[StringVal] = ("""<<[a-zA-Z_][a-zA-Z0-9_]*""".r >> {t =>
val tag = t.substring(2)
Parser{in =>
val Success(temp, rest) = oneLine(in)
val line = new CharSequenceReader(temp, 0)
hereDocumentBody(tag).apply(rest) match {
case Success(value, next) =>
val source = cat(line, next)
Success(StringVal(value), source)
case Failure(msg, next) => Failure(msg, cat(line, next))
case Error(msg, next) => Error(msg, cat(line, next))
}
}
}) <~ SPACING
def hereDocumentBody(beginTag: String): Parser[String] = oneLine >> {line =>
if(beginTag == line.trim) "" else hereDocumentBody(beginTag) ^^ {result =>
line + result
}
}さて、以降、このコードを理解したいと思う方を対象にして解説を書いてみたいと思います。核となる部分は
lazy val hereDocument: Parser[StringVal]と
def hereDocumentBody(beginTag: String): Parser[String]です。まず、hereDocumentの方を読んでいきましょう。hereDocumentの本体は次のようになっています。
lazy val hereDocument: Parser[StringVal] = ("""<<[a-zA-Z_][a-zA-Z0-9_]*""".r >> {t =>
val tag = t.substring(2)
Parser{in =>
val Success(temp, rest) = oneLine(in)
val line = new CharSequenceReader(temp, 0)
hereDocumentBody(tag).apply(rest) match {
case Success(value, next) =>
val source = cat(line, next)
Success(StringVal(value), source)
case Failure(msg, next) => Failure(msg, cat(line, next))
case Error(msg, next) => Error(msg, cat(line, next))
}
}
}) <~ SPACINGまず、パーザコンビネータではあまり見られないであろう>>演算子が登場します。これは、どういうものかというと、^^に
似ているのですが、^^は解析結果を加工する関数fを取って、解析結果を別の値に変換するParserを返すだけなのに対して、
>>は解析結果を引数として新しいParserを返す関数fを取って、新しいParserを返すところが異なります。
次に、>>に渡された関数の中身を見てみましょう。まず、tには、"<<IAGINE"に相当する文字列が解析結果として入りますが、
そこから最初の<<を削除して、"IMAGINE"の部分だけを取り出し、変数tagをその結果に束縛します。これは、ヒアドキュメント
の解析において、"IMAGINE"のみを含む行までを読み取るために使われます。その次に、Parser{in => ... }という、これまた
あまり見慣れない関数呼び出しがあります。Parser{in => ...}は、inを入力列(Reader[Char])として、その結果を解析
して、ParseResult型の関数を返す関数fを受け取って、それを元にParserを構築する関数です。ここで着目すべきなのは、Parser
関数を使うことで、入力列を明示的にパーザコンビネータの中で取り扱うことができるようになるという点です。これが今回で一番重要
な点です。
さて、inはReader[Char]で、Parser[T]は、Reader[Char]を引数に取るapplyメソッドを持っていますから、これを使って、
パーザコンビネータ中の特定の規則を、入力を渡して明示的に呼び出すことができます。それを行っているのが、
val Success(temp, rest) = oneLine(in)という行です。ここでは、"<<IMAGINE"の終わりから、行末までを読み取り、その結果の文字列値をtemp、残りの入力列をrestに
格納しています。tempは、解析を再開するためにいったん退避しておくべき文字列で、後で使用します。restは次の行以降
を指す入力列になります。なお、
val line = new CharSequenceReader(temp, 0)では、文字列(String)であるtempをパーザコンビネータで扱えるReader[Char]形式に変換して、変数lineをそれに束縛しています。
次に、ヒアドキュメントの本体を解析する部分
hereDocumentBody(tag).apply(rest) match {
case Success(value, next) =>
val source = cat(line, next)
Success(StringVal(value), source)
case Failure(msg, next) => Failure(msg, cat(line, next))
case Error(msg, next) => Error(msg, cat(line, next))
}が出てきます。hereDocumentBodyは、ヒアドキュメントの終了を検知するため、引数として文字列を取ります。ここでは、先ほどのtagを渡してあります。これで、ヒアドキュメントの本体を解析するParserが構築されるため、それに対して、先ほど保存しておいたrestを渡して、ヒアドキュメント本体の解析を明示的に行います(apply(rest))。
その後、パターンマッチによって分岐していますが、これ自体はさほど重要ではありません。問題は、解析結果であるParseResultに
どのような情報を載せるか、という点です。ヒアドキュメントの解析が終わった後は、<<IMAGINEの次の文字から解析を再開する必要が
あるため、lineが必要になりますが、それだけでは情報として足りません。なぜなら、その場合、<<IMAGINEの行でプログラムの解析が
終了してしまうためです。それでは、「その幻想がぶち殺せない」ので困ります。
これをなんとかするには、lineと、ヒアドキュメント本体に続く入力列であるnextを「くっつける」必要があります。lineとnextの型
は両方ともReader[Char]で、Reader[Char]同士の連結演算が用意されていれば楽だったのですが、そういうわけにはいかず、くっつける
ためのメソッドcatを以下のような形で明示的に定義する必要がありました。
def cat(a: Reader[Char], b: Reader[Char]): Reader[Char] = {
val aSource = a.source + b.source.subSequence(b.offset, b.source.length()).toString
if(a.atEnd) {
rebuild(b, aSource, a.offset)
} else {
new Reader[Char] {
private lazy val result = cat(a.rest, b)
def atEnd = a.atEnd
def first = a.first
def pos = a.pos
def rest = result
override def source = aSource
override def offset = a.offset
}
}
}catメソッドの実装詳細は、あまり面白みの無いものなので、割愛しますが、ともあれ、このような技巧を駆使して、ようやくヒアドキュメント(のサブセット)がパーズできるようになりました。
さて、だらだらと書いてきましたが、今回の話で重要なポイントは、パーザコンビネータの中で入力列をいじくりまわすことができる、ということです。パーザコンビネータは関数型的な考え方に基づいて構築されているため、そのような、一見副作用っぽいものを扱うのは難しそうに見えますが、入力列を破壊的に変更するのではなく、変更された入力列を返すようにすることで、パーザコンビネータの流儀に反することなく、そのような機能を扱えるようになります。実際には、パーザコンビネータで入力列そのものを明示的に取り扱わなければいけないケースはレアでしょうが、いざというときのために、知っておいて損は無い…かもしれません。