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