改善版2024) kotlin でパーサーコンビネータを実装する もあわせてご覧ください。
「 テキストをパーサーコンビネータを使ってパースすることを考えてみる 」 というのを先日考えたのですが、今回はその改善版です。
zeroOrMore パーサー の再帰部分が気に入らないので見直しました。
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, Html)->ParseResult
String を受け取って ParseResult を返していた（前回）のを改め、 String と Html を受け取って ParseResult を返すように変更しました。 つまり、パース対象のテキストだけ渡すのではなく、それまでのパース結果の成果物である Html も渡すように変更しています。(これがポイント)
それでは、この変更を反映していきます。
前回の pWord はこれです。
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
}
pWord 関数は Parser を生成して返していますが { text-> ... } の部分を改善版の Parser の定義にあわせて { text, html-> ... } に変更します。
val pWord: (String)-> Parser = { token->
val p: Parser = { text, html->
if( text.length < token.length ){
toNGParseResult(text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(
true,
text.substring(token.length),
Html(html.value + "<span>${token}</span>"))
} else {
toNGParseResult(text)
}
}
}
p
}
それから パースが成功した場合に生成する成果物である Html も変更しています。 次のように、前のパーサーが生成した成果物(html.value)を足し合わせています。
Html(html.value + "<span>${token}</span>")
さらに本題とは無関係ですが、 if が入れ子になっていて気持ち悪いので、そこもリファクタリングします。 また、token の変数名を word に変えました。 pWord 関数なので、 word という変数名を使う方が 良いだろう。
リファクタリングした結果の pWord 関数はこれです。
val pWord: (String)-> Parser = { word->
val p: Parser = { text, html->
val invalid = ( text.length < word.length )
if( !invalid && text.substring(0, word.length)==word ){
ParseResult(
true,
text.substring(word.length),
Html(html.value + "<span>${word}</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
}
{ text-> ... } に代えて { text, html-> ... } にします。 さらに Parser にパース結果の Html の値を渡していきます。
そうやって修正した新しい and 関数がこれです。
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
val p: Parser = { text, html->
val parseResult0 = parser0(text, html)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.html)
if( parseResult1.ok ){
ParseResult(true, parseResult1.next, parseResult1.html)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
return p
}
パース結果を足していく処理がパーサー側に移動したので、パーサーを組み合わせる方の関数（パーサーコンビネータ）は簡単になりました。 無理やり感がなくいい感じです。
and 関数と変更ポイントは同じなので、新しいコードだけ掲載します。
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
val p: Parser = { text, html->
val parseResult0 = parser0(text, html)
val parseResult1 = parser1(text, html)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
return p
}
問題の zeroOrMore 関数です。
元のコードは、これ。
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
}
f 関数を使って再帰処理をしていたのですが、新しい方は次のように直接 zeroOrMore を呼び出す（これも再帰ですが）形になりました。
val zeroOrMore: (Parser)->Parser = { parser->
val p: Parser = { text, html->
val parseResult = parser(text, html)
if( !parseResult.ok ){
// パースが失敗した場合:
ParseResult(true, text, html)
} else {
// パースが成功した場合:
zeroOrMore(parser)(parseResult.next, parseResult.html)
}
}
p
}
パースに成功した場合は再び(再帰的に) zeroOrMore を呼び出すことで、繰り返し指定された parser を適用しています。
すっきりした記述にはなったのですが、 この記述方法では元のコードでは指定できていた tailrec fun が使えなくなってしまったので、 zeroOrMore の繰り返しが多すぎるとスタックオーバーフローが起きると思います。 今はこれでよいことにしよう。
以上で、Parser 型を変更したことにより影響したコードを全部修正できました。 実際にこれらを使って 文字列 hogefoobarbarfoohoge をパース実行してみます。
val EMPTY_HTML = Html("")
val text = "hogefoobarbarfoohoge"
val p: Parser = zeroOrMore( pFoo or pBar or pHoge )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)
Parser に パース対象の文字列だけでなく Html を渡す必要があるので、空の Html("") 渡しています（初期値として）。
実行します。
$ kotlin main.kts
ParseResult(ok=true, next=, html=Html(value=<span>hoge</span><span>foo</span><span>bar</span><span>bar</span><span>foo</span><span>hoge</span>))
うまくパースできました。
最後に今回の改訂バージョンのコード全体を掲載します。
// main.kts
data class Html(val value: String)
data class ParseResult(
val ok: Boolean,
val next: String,
val html: Html)
typealias Parser = (String, Html)->ParseResult
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, next, Html(""))
}
val pWord: (String)-> Parser = { word->
val p: Parser = { text, html->
val invalid = ( text.length < word.length )
if( !invalid && text.substring(0, word.length)==word ){
ParseResult(
true,
text.substring(word.length),
Html(html.value + "<span>${word}</span>"))
} else {
toNGParseResult(text)
}
}
p
}
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
val p: Parser = { text, html->
val parseResult0 = parser0(text, html)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.html)
if( parseResult1.ok ){
ParseResult(true, parseResult1.next, parseResult1.html)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
return p
}
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
val p: Parser = { text, html->
val parseResult0 = parser0(text, html)
val parseResult1 = parser1(text, html)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
return p
}
val zeroOrMore: (Parser)->Parser = { parser->
val p: Parser = { text, html->
val parseResult = parser(text, html)
if( !parseResult.ok ){
// パースが失敗した場合:
ParseResult(true, text, html)
} else {
// パースが成功した場合:
zeroOrMore(parser)(parseResult.next, parseResult.html)
}
}
p
}
val EMPTY_HTML = Html("")
val text = "hogefoobarbarfoohoge"
val pFoo: Parser = pWord("foo")
val pBar: Parser = pWord("bar")
val pHoge: Parser = pWord("hoge")
val p: Parser = zeroOrMore( pFoo or pBar or pHoge )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)
以上です。
Liked some of this entry? Buy me a coffee, please.