改善版2024）kotlin でパーサーコンビネータを実装する【追伸】

このエントリーは改善版2024）kotlin でパーサーコンビネータを実装する【後編】Bold パーサーを追加してみるの続きです。

後編では Hello, **World**! Hello, *Again*! というイタリックとボールドマークアップが混在した文字列をパースしました。このとき、パーサーはイタリックやボールドの開始・終了に相当するマークアップ文字列を見つけてそれを  や  とか  や  に変換するという発想で実装していました。

別の考え方として、イタリックのマークアップで囲まれた部分がイタリック属性を持つ文字列（ここでは Again がイタリック属性を持つ文字列）、ボールドとしてマークアップされた部分がボールド属性を持つ文字列（ここでは World ）という発想もあり得ます。直接HTMLへ変換するのではなく、いったんASTに変換したいなどといったケースでは、このような発想でパーサーを書いた方がよいでしょう。

今回は前回のコードを修正して、この 別の考え方 で実装してみます。

環境の確認

$ kotlin -version
Kotlin version 2.0.10-release-540 (JRE 17.0.12+7-Ubuntu-1ubuntu222.04)

Hello, World! Hello, Again! を変換

HtmlBlock は前回はこのように書いていました。

sealed class HtmlBlock(val value: String) {
    class Just(value: String): HtmlBlock(value)
    object ItalicStart: HtmlBlock("")
    object ItalicStop: HtmlBlock("")
    object BoldStart: HtmlBlock("")
    object BoldStop: HtmlBlock("")
}

これを修正して次のように変更します。

sealed class HtmlBlock(val value: String) {
    class Just(value: String):   HtmlBlock(value)
    class Italic(value: String): HtmlBlock(value)
    class Bold(value: String):   HtmlBlock(value)
    object Nothing: HtmlBlock("")
}

イタリックやボールドの開始タグや終了タグ狙ってパースするのではなく、イタリック部分の（またはボールド部分の）文字列を狙ってパースするという種類分けになっています。 HtmlBlock.Nothing は、マークアップそれ自体の文字列に割り当てるために用意しています。

HtmlBlock を変更したので、 toHtml 修正します。

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Just -> it.value
                is HtmlBlock.Italic -> "<i>${it.value}</i>"
                is HtmlBlock.Bold -> "<b>${it.value}</b>"
                is HtmlBlock.Nothing -> ""
            }
        }.joinToString("")
    } else {
        ""
    }
}

イタリックやボールドとしてパースされた部分を i や b タグで囲んで出力するように設定しています。

パーサー全体は次のようになります。

val text = "Hello, **World**! Hello, *Again*!"

val pItalicStart: Parser  = pWord("*", {HtmlBlock.Nothing})
val pItalicStop: Parser   = pWord("*", {HtmlBlock.Nothing})

val pBoldStart: Parser  = pWord("**", {HtmlBlock.Nothing})
val pBoldStop: Parser   = pWord("**", {HtmlBlock.Nothing})

val pItalic = 
    pItalicStart and
    zeroOrMore(pNone("*", {HtmlBlock.Italic(it)})) and
    pItalicStop

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", {HtmlBlock.Bold(it)})) and
    pBoldStop

val pJust = pAnyone({HtmlBlock.Just(it)})

val p = zeroOrMore(pBold or pItalic or pJust)
val parseResult = p(text, listOf())
println( toHtml(parseResult) )

ほとんど前回と同じですが、パースした結果どの HtmlBlock の種類に割り当てるかの部分が変更になっています。マークアップ部分のパーサー( pItalicStart, pItalicStop など) は HtmlBlock.Nothing の種類として割り当ています。そして、イタリックマークアップで囲まれた部分の文字列をパースする部分:

    zeroOrMore(pNone("*", {HtmlBlock.Italic(it)})) and

ここでパースできた文字（列）について、HtmlBlock.Italic の種類として割り当てるようにしています。

それでは実行してみます。

$ kotlin main.kts
Hello, <b>W</b><b>o</b><b>r</b><b>l</b><b>d</b>! Hello, <i>A</i><i>g</i><i>a</i><i>i</i><i>n</i>!

一応意図通りできました。文字ごとにパースしていき、パースできた文字を HtmlBlock のいずれかに割り当てるという形でパースするので、 World や Again が一文字ずつ b タグまたは i タグで囲まれて出力されます。

これを Hello, World! Hello, Again! のような自然な出力に修正できるでしょうか？

自然な出力にする

パース結果は List<HtmlBlock> から生成されている、この toHtml 関数で。

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Just -> it.value
                is HtmlBlock.Italic -> "<i>${it.value}</i>"
                is HtmlBlock.Bold -> "<b>${it.value}</b>"
                is HtmlBlock.Nothing -> ""
            }
        }.joinToString("")
    } else {
        ""
    }
}

この toHtml を修正して期待する出力を得られるようにします。考え方としては、 List<HtmlBlock> を前から順に調べて、今調べている HtmlBlock の種類が一つ前と同じ HtmlBlock のそれと同じならば、ひとつにまとめるという加工をすればよいでしょう。まとめるとなれば fold を使えばよいでしょう。

val createHtmlBlock: (HtmlBlock, String)->HtmlBlock = { htmlBlock, value->
    when(htmlBlock){
        is HtmlBlock.Just   -> HtmlBlock.Just(value)
        is HtmlBlock.Italic -> HtmlBlock.Italic(value)
        is HtmlBlock.Bold   -> HtmlBlock.Bold(value)
        is HtmlBlock.Nothing-> HtmlBlock.Nothing
    }
}

val fixHtmlBlocks: (List<HtmlBlock>)->List<HtmlBlock> = { htmlBlocks->
    htmlBlocks.fold(listOf<HtmlBlock>()) { acc, htmlBlock->
        if( acc.size==0 ){
            acc + listOf(htmlBlock)
        } else {
            val accLast = acc.last()
            if( accLast::class.simpleName == htmlBlock::class.simpleName ){
                acc.dropLast(1) + listOf(createHtmlBlock(
                    accLast,
                    (accLast.value + htmlBlock.value)))
            } else {
                acc + listOf(htmlBlock)
            }
        }
    }
}

List<HtmlBlock> を加工する fixHtmlBlocks 関数です。 fold を使って、前の HtmlBlock と同じ種類だったら畳み込み（ひとつにまとめる処理を）しています。 createHtmlBlock 補助関数は HtmlBlock の種類から適切な HtmlBlock インスタンスを生成しています。

Reflection を使ってクラス名からインスタンスが生成できればもう少し簡単に記述できるのでしょうが、今回は割愛。

あとは toHtml で:

//r.htmlBlocks.map {
fixHtmlBlocks(r.htmlBlocks).map {

このように加工済みの List<HtmlBlock> を使ってHTML出力するように変更すればOKです。

実行してみます。

$ kotlin main.kts
Hello, <b>World</b>! Hello, <i>Again</i>!

意図通りの出力を得ることができました。

まとめ

完成したコードを掲載します。

// main.kts

sealed class HtmlBlock(val value: String) {
    class Just(value: String):   HtmlBlock(value)
    class Italic(value: String): HtmlBlock(value)
    class Bold(value: String):   HtmlBlock(value)
    object Nothing: HtmlBlock("")
}

typealias ToHtmlBlock = (String)->HtmlBlock

data class ParseResult(
    val ok: Boolean,
    val next: String,
    val htmlBlocks: List<HtmlBlock>)
typealias Parser = (String, List<HtmlBlock>)->ParseResult

val toNGParseResult: (String)->ParseResult = { next->
    ParseResult(false, text, listOf())
}

val pWord: (String, ToHtmlBlock)-> Parser = { word, toHtmlBlock->
    val p: Parser = { text, htmlBlocks->
        val invalid = ( text.length < word.length )
        if( !invalid && text.substring(0, word.length)==word ){
            ParseResult(
                true, 
                text.substring(word.length),
                htmlBlocks + listOf(toHtmlBlock(word)))
        } else {
            toNGParseResult(text)
        }
    }

    p
}

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

    val p: Parser = { text, htmlBlocks->
        val parseResult0 = parser0(text, htmlBlocks)
        if( parseResult0.ok ){
            val parseResult1 = parser1(parseResult0.next, parseResult0.htmlBlocks)
            if( parseResult1.ok ){
                ParseResult(
                    true,
                    parseResult1.next,
                    parseResult1.htmlBlocks)
            } else {
                toNGParseResult(text)
            }
        } else {
            toNGParseResult(text)
        }
    }

    return  p
}

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

    val p: Parser = { text, htmlBlocks->
        val parseResult0 = parser0(text, htmlBlocks)
        val parseResult1 = parser1(text, htmlBlocks)

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

    return p
}

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

    p
}

val pAnyone: (ToHtmlBlock)->Parser = { toHtmlBlock->
    val p: Parser = { text, htmlBlocks->
        if( text.length>0 ){
            ParseResult(
                true,
                text.substring(1),
                htmlBlocks + listOf(toHtmlBlock(text[0].toString())))
        } else {
            toNGParseResult(text)
        }
    }

    p
}

val pNone: (String, ToHtmlBlock)->Parser = { token, toHtmlBlock->
    val p: Parser = { text, htmlBlocks->
        if( text.startsWith(token) ){
            toNGParseResult(text)
        } else {
            if( text.length>0 ){
                ParseResult(
                    true,
                    text.substring(1),
                    htmlBlocks + listOf(toHtmlBlock(text[0].toString())))
            } else {
                toNGParseResult(text)
            }
        }
    }

    p
}

val createHtmlBlock: (HtmlBlock, String)->HtmlBlock = { htmlBlock, value->
    when(htmlBlock){
        is HtmlBlock.Just   -> HtmlBlock.Just(value)
        is HtmlBlock.Italic -> HtmlBlock.Italic(value)
        is HtmlBlock.Bold   -> HtmlBlock.Bold(value)
        is HtmlBlock.Nothing-> HtmlBlock.Nothing
    }
}

val fixHtmlBlocks: (List<HtmlBlock>)->List<HtmlBlock> = { htmlBlocks->
    htmlBlocks.fold(listOf<HtmlBlock>()) { acc, htmlBlock->
        if( acc.size==0 ){
            acc + listOf(htmlBlock)
        } else {
            val accLast = acc.last()
            if( accLast::class.simpleName == htmlBlock::class.simpleName ){
                acc.dropLast(1) + listOf(createHtmlBlock(
                    accLast,
                    (accLast.value + htmlBlock.value)))
            } else {
                acc + listOf(htmlBlock)
            }
        }
    }
}

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        fixHtmlBlocks(r.htmlBlocks).map {
            when(it){
                is HtmlBlock.Just -> it.value
                is HtmlBlock.Italic -> "<i>${it.value}</i>"
                is HtmlBlock.Bold -> "<b>${it.value}</b>"
                is HtmlBlock.Nothing -> ""
            }
        }.joinToString("")
    } else {
        ""
    }
}


val text = "Hello, **World**! Hello, *Again*!"

val pItalicStart: Parser  = pWord("*", {HtmlBlock.Nothing})
val pItalicStop: Parser   = pWord("*", {HtmlBlock.Nothing})

val pBoldStart: Parser  = pWord("**", {HtmlBlock.Nothing})
val pBoldStop: Parser   = pWord("**", {HtmlBlock.Nothing})

val pItalic = 
    pItalicStart and
    zeroOrMore(pNone("*", {HtmlBlock.Italic(it)})) and
    pItalicStop

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", {HtmlBlock.Bold(it)})) and
    pBoldStop

val pJust = pAnyone({HtmlBlock.Just(it)})

val p = zeroOrMore(pBold or pItalic or pJust)
val parseResult = p(text, listOf())
println( toHtml(parseResult) )

改善版2024）kotlin でパーサーコンビネータを実装する【おまけ】 HtmlBlock の改良へ続きます。

改善版2024）kotlin でパーサーコンビネータを実装する 【追伸】

環境の確認

Hello, **World**! Hello, *Again*! を変換

自然な出力にする

まとめ

改善版2024）kotlin でパーサーコンビネータを実装する【追伸】

Hello, World! Hello, Again! を変換