Thursday, March 23, 2023

改善版) kotlin でパーサーコンビネータを実装する

「テキストをパーサーコンビネータを使ってパースすることを考えてみる」というのを先日考えたのですが、今回はその改善版です。

many パーサーコンビネータ の再帰部分がどうにも気に入らないので見直しました。

パーサーを定義する(改)

前回の定義はこれです。

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, Html)->ParseResult

String を受け取って ParseResult を返していた（前回）のを改め、 String と Html を受け取って ParseResult を返すように変更しました。つまり、パース対象のテキストだけ渡すのではなく、それまでのパース結果の成果物である Html も渡すように変更しています。(これがポイント)

それでは、この変更を反映していきます。

pWord

前回の pWord はこれです。

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)
            }
        }
    }
}

pWord 関数は Parser を生成して返していますが { text-> ... } の部分を改善版の Parser の定義にあわせて { text, html-> ... } に変更します。

val pWord: (String)-> Parser = { token->
    { text, html->
        if( text.length < token.length ){
            toNGParseResult(text)
        } else {
            if( text.substring(0, token.length)==token ){
                ParseResult(true, Html(html.value + "<para>${token}</para>"), text.substring(token.length))
            } else {
                toNGParseResult(text)
            }
        }
    }
}

それからパースが成功した場合に生成する成果物である Html も変更しています。次のように、前のパーサーが生成した成果物(html.value)を足し合わせています。

Html(html.value + "<para>${token}</para>")

さらに本題とは無関係ですが、 if が入れ子になっていて気持ち悪いので、そこもリファクタリングします。また、token の変数名を word に変えました。 pWord 関数なので、 word という変数名を使う方が make sense だろうと。

リファクタリングした結果の pWord 関数はこれです。

val pWord: (String)-> Parser = { word->
    { text, html->
        val invalid = ( text.length < word.length )
        if( !invalid && text.substring(0, word.length)==word ){
            ParseResult(true, Html(html.value + "<para>${word}</para>"), text.substring(word.length))
        } else {
            toNGParseResult(text)
        }
    }
}

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)
        }
    }
}

return { text-> ... } に代えて return { text, html-> ... } にします。さらに Parser にパース結果の Html の値を渡していきます。

そうやって修正した新しい and 関数がこれです。

infix fun Parser.and(parser1: Parser): Parser {
    val parser0 = this

    return { text, html->
        val parseResult0 = parser0(text, html)
        if( parseResult0.ok ){
            val parseResult1 = parser1(parseResult0.next, parseResult0.html)
            if( parseResult1.ok ){
                ParseResult(true, parseResult1.html, parseResult1.next)
            } else {
                toNGParseResult(text)
            }
        } else {
            toNGParseResult(text)
        }
    }
}

パース結果を足していく処理がパーサー側に移動したので、パーサーを組み合わせる方の関数（パーサーコンビネータ）は簡単になりました。無理やり感がなくいい感じです。

or

and 関数と変更ポイントは同じなので、新しいコードだけ掲載します。

infix fun Parser.or(parser1: Parser): Parser {
    val parser0 = this

    return { text, html->
        val parseResult0 = parser0(text, html)
        val parseResult1 = parser1(text, html)

        if( parseResult0.ok ){
            parseResult0
        } else if( parseResult1.ok ){
            parseResult1
        } else {
            toNGParseResult(text)
        }
    }
}

many

問題の many 関数です。

元のコードは、これ。

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))
    }
}

f 関数を使って再帰処理をしていたのですが、新しい方は次のように直接 many を呼び出す（これも再帰ですが）形になりました。

fun many(parser: Parser): Parser {
    return { text, html->
        val parseResult = parser(text, html)
        if( !parseResult.ok ){
            // パースが失敗した場合:
            ParseResult(true, html, text)
        } else {
            // パースが成功した場合:
            many(parser)(parseResult.next, parseResult.html)
        }
    }
}

これだけ関数リテラルではなく、 ふつうの関数 として定義しているのは、そうしないと不都合が生じるからです。説明は割愛。

パースに成功した場合は再び(再帰的に) many を呼び出すことで、繰り返し parser を適用しています。

すっきりした記述にはなったのですが、元のコードでは指定できていた tailrec fun が使えなくなってしまったので、 many の繰り返しが多すぎるとスタックオーバーフローが起きると思います。今はこれでよいことにしよう。

まとめ

以上で、Parser 型を変更したことにより影響したコードを全部修正できました。実際にこれらを使って文字列 hogefoobarbarfoohoge をパース実行してみます。

val EMPTY_HTML = Html("")

val text = "hogefoobarbarfoohoge"
val p: Parser = many( pFoo() or pBar() or pHoge() )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)

Parser にパース対象の文字列だけでなく Html を渡す必要があるので、空の Html("") 渡しています（初期値として）。

実行します。

$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>hoge</para><para>foo</para><para>bar</para><para>bar</para><para>foo</para><para>hoge</para>), next=)

うまくパースできました。

最後に今回の改訂バージョンのコード全体を掲載します。

main.kts

data class Html(val value: String)
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
typealias Parser = (String, Html)->ParseResult

val toNGParseResult: (String)->ParseResult = { next->
    ParseResult(false, Html(""), next)
}

val pWord: (String)-> Parser = { word->
    { text, html->
        val invalid = ( text.length < word.length )
        if( !invalid && text.substring(0, word.length)==word ){
            ParseResult(true, Html(html.value + "<para>${word}</para>"), text.substring(word.length))
        } else {
            toNGParseResult(text)
        }
    }
}

infix fun Parser.and(parser1: Parser): Parser {
    val parser0 = this

    return { text, html->
        val parseResult0 = parser0(text, html)
        if( parseResult0.ok ){
            val parseResult1 = parser1(parseResult0.next, parseResult0.html)
            if( parseResult1.ok ){
                ParseResult(true, parseResult1.html, parseResult1.next)
            } else {
                toNGParseResult(text)
            }
        } else {
            toNGParseResult(text)
        }
    }
}

infix fun Parser.or(parser1: Parser): Parser {
    val parser0 = this

    return { text, html->
        val parseResult0 = parser0(text, html)
        val parseResult1 = parser1(text, html)

        if( parseResult0.ok ){
            parseResult0
        } else if( parseResult1.ok ){
            parseResult1
        } else {
            toNGParseResult(text)
        }
    }
}

fun many(parser: Parser): Parser {
    return { text, html->
        val parseResult = parser(text, html)
        if( !parseResult.ok ){
            ParseResult(true, html, text)
        } else {
            many(parser)(parseResult.next, parseResult.html)
        }
    }
}

val pFoo: ()->Parser = { pWord("foo") }
val pBar: ()->Parser = { pWord("bar") }
val pHoge: ()-> Parser = { pWord("hoge") }


val EMPTY_HTML = Html("")

val text = "hogefoobarbarfoohoge"
val p: Parser = many( pFoo() or pBar() or pHoge() )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)

以上です。

Follow @osimajp