改善版) kotlin でパーサーコンビネータを実装する もあわせてご覧ください。
テキストをパーサーコンビネータを使ってパースすることを考えてみる。 ここで考えるパーサーコンビネータは、 パース対象となるテキストに出現するいろいろなパターンをパースできる小さなパーサを複数用意し、 それらを組み合わせて対象となるテキストをパースするコンビネータ。 パーサーを自在に組み合わせてパースできるから、パーサーコンビネータ。
このエントリーの最後では、簡単なマークアップをしたテキストをHTMLに変換するパーサーをつくります。
data class Html(val tagName: String, val value: String)
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
typealias Parser = (String)->ParseResult
ここで要となるのは Parser です。
typealias Parser = (String)->ParseResult
Parser は String (文字列)を受け取って ParseResult (パース結果) を返します。 ParseResult は次のように ok, html, next の値を持ちます。
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
それぞれの意味は以下になります。
foobarhoge という文字列をパースすることを考えます。 このとき、この文字列は foo / bar / hoge の3つのワードからなる、と考えることにします。 この3種類のワードをパースするパーサーを生成する関数を用意します。
val pFoo: ()-> Parser = {
val token = "foo"
{ text->
if( text.length < token.length ){
ParseResult(false, Html(""), text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
ParseResult(false, Html(""), text)
}
}
}
}
val pBar: ()->Parser = {
val token = "bar"
{ text->
if( text.length < token.length ){
ParseResult(false, Html(""), text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
ParseResult(false, Html(""), text)
}
}
}
}
val pHoge: ()-> Parser = {
val token = "hoge"
{ text->
if( text.length < token.length ){
ParseResult(false, Html(""), text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
ParseResult(false, Html(""), text)
}
}
}
}
冗長なコードすぎですが、それはあとでリファクタリングするとして、今は先にすすめます。
この pFoo, pBar, pHoge 関数リテラルを実行（適用）すると Parser が得られます。
それではちょっと試してみます。
main.kts
val text = "foobarhoge"
val fooParseResult= pFoo()(text)
println(fooParseResult)
pFoo() して得た foo をパースできる Parser を使って、foobarhoge 文字列をパース実行しようとしています。 それでは実行してみます。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>foo</para>), next=barhoge)
結果として ParseResult(ok=true, html=Html(value=<para>foo</para>), next=barhoge) を得ています。 これは ok=true でパースが成功、成功したパースの値は html=Html(value=<para>foo</para>) で、残りのパース文字列が next=barhoge になります。 意図通りパースできていますが、まだ foo をパースしただけです。
残りの barhoge 文字列を pBar() と pHoge() を使ってパースしたい。
とりあえずこのベタな実装でこてだめし。
val text = "foobarhoge"
val fooParseResult = pFoo()(text)
if( fooParseResult.ok ){
val barParseResult = pBar()(fooParseResult.next)
if( barParseResult.ok ){
val hogeParseResult = pHoge()(barParseResult.next)
println(hogeParseResult)
}
}
実行してみます。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>hoge</para>), next=)
最後の hoge までパースできました。 しかし、パース結果が最後の pHoge() パーサーでパースした部分だけになっています。
Html(value=<para>hoge</para>)
期待する結果は、次のものです。
Html(value=<para>foo</para><para>bar</para><para>hoge</para>)
このような結果を得るためには 各ステップでパース結果を足し合わせて行く必要がありました。
結果の足し合わせ処理を追加したコード:
val text = "foobarhoge"
val fooParseResult = pFoo()(text)
if( fooParseResult.ok ){
val barParseResult = pBar()(fooParseResult.next)
val barParseResultDash = ParseResult(
barParseResult.ok,
Html("${fooParseResult.html.value}${barParseResult.html.value}"),
barParseResult.next)
if( barParseResultDash.ok ){
val hogeParseResult = pHoge()(barParseResultDash.next)
val hogeParseResultDash = ParseResult(
hogeParseResult.ok,
Html("${barParseResultDash.html.value}${hogeParseResult.html.value}"),
hogeParseResult.next)
println(hogeParseResultDash)
}
}
barParseResult に対して barParseResultDash でその前の結果（fooParseResult）の HTML を足し合わせています。
実行してみます。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>foo</para><para>bar</para><para>hoge</para>), next=)
意図通の結果になりました。
pFoo, pBar, pHoge をリファクタリングします。
これらを val token = "foo/bar/hoge" の部分が異なっているだけなので、その token を指せる pWord 関数リテラルを書きます。 それから、パースに失敗した場合の ParseResult 生成処理も toNGParseResult 関数としてくくりだしました。
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, Html(""), next)
}
val pWord: (String)-> Parser = { token->
{ text->
if( text.length < token.length ){
toNGParseResult(text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
toNGParseResult(text)
}
}
}
}
val pFoo: ()->Parser = { pWord("foo") }
val pBar: ()->Parser = { pWord("bar") }
val pHoge: ()-> Parser = { pWord("hoge") }
次に pFoo(), pBar(), pHoge() の出現順にパーサーを組み合わせていた部分をリファクタリングします。 まずは pFoo(), pBar() の２つのパーサーを組み合わせできる and というコンビネータを考えます。
つまり、and があったとしたら次のように記述できるような関数です。
val fooAndBar: Parser = and(pFoo(), pBar())
2つの Parser を受けとり、一つの Parser を返す関数です。
val and: (Parser, Parser)-> Parser = { parser0, parser1->
{ text->
val parseResult0 = parser0(text)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next)
if( parseResult1.ok ){
ParseResult(
true,
Html("${parseResult0.html.value}${parseResult1.html.value}"),
parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
これは与えられた二つのパーサーを指定された順に実行して両方ともが成功してはじめてパーサー全体が成功となります。
これを使えば、pFoo() と pBar() が組み合わせできるだけでなく、pHoge() も組み合わせできます。
val text = 'foobarhoge'
val fooAndBar: Parser = and(pFoo(), pBar())
val fooAndBarAndHoge: Parser = and(fooAndBar, pHoge())
val parseResult = fooAndBarAndHoge(text)
println(parseResult)
というか、もっと簡単に次のように書けます。
val p: Parser = and(and(pFoo(), pBar()), pHoge())
val parseResult = p(text)
println(parseResult)
ただこれ、組み合わせるパーサーが増えていくと括弧が増えて ( and(and(and(and(....) ) とても読みづらくなります。 そこで infix を使って and を中置きできるように書き直しましょう。
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text->
val parseResult0 = parser0(text)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next)
if( parseResult1.ok ){
ParseResult(
true,
Html("${parseResult0.html.value}${parseResult1.html.value}"),
parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
infix の場合、関数リテラルで記述する方法がわからなかったので、普通の関数として定義しました。
これを使えば、次のようにすっきり記述することができます。
val p: Parser = pFoo() and pBar() and pHoge()
val parseResult = p(text)
println(parseResult)
infix 神か！
main.kts
data class Html(val value: String)
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
typealias Parser = (String)->ParseResult
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, Html(""), next)
}
val pWord: (String)-> Parser = { token->
{ text->
if( text.length < token.length ){
toNGParseResult(text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
toNGParseResult(text)
}
}
}
}
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text->
val parseResult0 = parser0(text)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next)
if( parseResult1.ok ){
ParseResult(
true,
Html("${parseResult0.html.value}${parseResult1.html.value}"),
parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
val pFoo: ()->Parser = { pWord("foo") }
val pBar: ()->Parser = { pWord("bar") }
val pHoge: ()-> Parser = { pWord("hoge") }
val text = "foobarhoge"
val p: Parser = pFoo() and pBar() and pHoge()
val parseResult = p(text)
println(parseResult)
実行します。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>foo</para><para>bar</para><para>hoge</para>), next=)
うまくいきました。
さて、and だけではたいしたことは何もできません。 今つくったパーサーを使って、たとえば... 文字列 foobarhoge の代わりに 文字列 hogefoobar をパースしようとしても、次のように失敗してしまいます。
$ kotlinc -script main.kts
ParseResult(ok=false, html=Html(value=), next=hogefoobar)
そこで foo / bar / hoge がどんな順番に出現しようともパースできるパーサーをつくることを考えます。
まず or コンビネータをつくります。
これは (pFoo() or pBar() or pHoge) のように使えて、foo / bar / hoge のいずれかの文字列パターンが出現する、という状況に対処できるようにします。
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
return { text->
val parseResult0 = parser0(text)
val parseResult1 = parser1(text)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
}
or は parser0 を試して成功すればその結果を返し、失敗したら parser1 を試してその結果を返しています。
さっそくこれを使ってみましょう。
val text = "hogefoobar"
val p: Parser = pFoo() or pBar() or pHoge()
val parseResult = p(text)
println(parseResult)
実行してみましょう。
kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>hoge</para>), next=foobar)
うまくいきました。 ただし、最初の hoge をパースしたところで止まっていますが。
val parseResult1 = ( p and p and p )(text)
このように記述すれば hogefoobar や barhogefoo などをパースできますが、hogefoobarhoge のように 4つのワードに増えたとたん最後までパースできなくなります。
この任意の回数 foo / bar / hoge が出現してもパースできるパーサーをつくるために必要なのは many パーサーコンビネータです。
val many: (Parser)->Parser = { ... }
指定したパーサーを 0回以上失敗するまで何度でも適用する関数です。
val many: (Parser)->Parser = { parser->
{ text->
tailrec fun f(parseResult: ParseResult): ParseResult {
val currentParseResult = parser(parseResult.next)
return if( !currentParseResult.ok ){
ParseResult(
true,
Html(parseResult.html.value),
parseResult.next)
} else {
f(
ParseResult(
true,
Html("${parseResult.html.value}${currentParseResult.html.value}"),
currentParseResult.next))
}
}
f(ParseResult(true, Html(""), text))
}
}
これは、与えられた parser を再帰をつかって繰り返しパース実行しています。 パースの結果が成功すれば、再帰処理を続行し、失敗した時点で、そこまでの結果を返しています。 0回でも成功する (たとえ一度もパースが成功しなくても many の結果としては成功を返す) ので、決して失敗しないパーサーコンビネータになります。
使ってみます。
val text = "hogefoobarhoge"
val parseResult1 = many( pFoo() or pBar() or pHoge() )(text)
println(parseResult1)
many( pFoo() or pBar() or pHoge() ) の部分で foo または bar または hoge が 0回以上出現するパーサを生成しています。
実行します。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>hoge</para><para>foo</para><para>bar</para><para>hoge</para>), next=)
うまくいきました。
ここまでは foo / bar / hoge という固定文字列が任意に出現した場合にパースできるパーサーを書いたところです。 それでは、これを応用してマークアップをHTMLに変換していきます。
Hello, *World*!
* アスタリスクで囲んだ部分をイタリックのHTMLとして出力したい。
そこでこのイタリックマークアップをパースできるパーサを生成する pItalic 関数を書きます。
val pItalic: ()->Parser = {
{ text->
val regex = "^\\*([a-zA-Z0-9]+?)\\*".toRegex()
val m = regex.find(text)
if( m!=null ){
ParseResult(
true,
Html("<i>${m.groupValues[1]}</i>"),
text.substring( m.groupValues[0].length ))
} else {
toNGParseResult(text)
}
}
}
話を簡単にするため アスタリスクで囲まれた部分は [a-zA-Z0-9] の文字しか出現しないことにしています。 実際はより複雑な条件（正規表現など）を指定すべきでしょう。
イタリック以外の部分はそのままなりゆきで出力することにします。 そのためにどんな文字（一文字）でも成功するパーサーを生成する pAnyChar 関数を書きます。
val pAnyChar: ()->Parser = {
{ text->
if( text.length>0 ){
ParseResult(
true,
Html(text[0].toString()),
text.substring(1))
} else {
toNGParseResult(text)
}
}
}
これらのパーサーを組み合わせて Hello, *World*! をパースするパーサーをつくってみます。
val text = "Hello, *World*!"
val p = many( pItalic() or pAnyChar() )
val parseResult = p(text)
println(parseResult)
or コンビネータは前にあるパーサーを先に評価(適用)するため、パーサーを指定する順に注意しましょう。 もし、pAnyChar() を最初に書いてしまうと、常にこのパーサーは成功するため、すべてが pAnyChar() でパースした（だけの）結果になってしまいます。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=Hello, <i>World</i>!), next=)
うまくいきました。 World 部分が イタリックになりました。
それでは今度はボールドについて考えます。 こんな感じで Hello 部分を ** でボールド指定したテキストをパースすることにします。
**Hello**, *World*!
pBold というボールドマークアップをパースするパーサーを生成する関数を書きます。
val pBold: ()->Parser = {
{ text->
val regex = "^\\*\\*([a-zA-Z0-9]+?)\\*\\*".toRegex()
val m = regex.find(text)
if( m!=null ){
ParseResult(
true,
Html("<b>${m.groupValues[1]}</b>"),
text.substring( m.groupValues[0].length ))
} else {
toNGParseResult(text)
}
}
}
ほとんど pItalic と同じです。 異なるのは、 regex での指定が 二重の * になったことと、結果のHTML のタグを <b> で出力するようにしたことです。
ではこの pBold を使ってパーサを組み立てます。
val p = many( pBold() or pItalic() or pAnyChar() )
val parseResult = p(text)
println(parseResult)
実行します。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<b>Hello</b>, <i>World</i>!), next=)
うまくいきました。
テキストパースには正規表現を使うことが多いと思われますが、 複雑になってくると手に負えなくなります。 そんなときに活躍するかもしれないのがパーサーコンビネータです。
Liked some of this entry? Buy me a coffee, please.