Home About
Kotlin , Text Processing , Parser Combinator

改善版2024)kotlin でパーサーコンビネータを実装する 【後編】Bold パーサーを追加してみる

このエントリーは 改善版2024)kotlin でパーサーコンビネータを実装する【前編】 からの続きです。

前編で Hello, *World*! Hello, *Again*! という文字列を自前で実装したパーサーコンビネーターを使ってHTMLに変換しました。 後編ではボールド用マークアップが混ざっていてもうまくパースできるのか調べます。

環境の確認

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

Hello, **World**! を変換

いわゆるマークダウンならボールドになるマークアップを World の前後に挿入した文字列 Hello, **World**!前編で作成したコードでパースして結果を見ます。

次のようになります。

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

Bold用のマークアップをパースするパーサーがないので当然の結果ですが、意図通り変換はできていません。 (意図した変換結果は Hello, <b>World</b>! です。)

Boldマークアップをサポートするためにコードを追加していきます。

パース結果蓄積用の 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("")
}

BoldStart, BoldStop の種類を追加しました。 これに伴い toHtml も変更が必要です。 BoldStart, BoldStop がきたときにどうように出力するか is HtmlBlock.BoldStart, is HtmlBlock.BoldStop の部分を 追記しました。

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Just -> it.value
                is HtmlBlock.ItalicStart -> "<i>"
                is HtmlBlock.ItalicStop  -> "</i>"
                is HtmlBlock.BoldStart -> "<b>"
                is HtmlBlock.BoldStop  -> "</b>"
            }
        }.joinToString("")
    } else {
        ""
    }
}

ボールドマークアップにも対応したパーサー全体はこれです。

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

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

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

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

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", {HtmlBlock.Just(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) )

イタリックにならってボールドのパーサー記述を追加しただけです。 最終的な結論としてのパーサーはこれ:

val p = zeroOrMore(pBold or pItalic or pJust)

bold か italic か ただの文字 のいずれかが0回以上の繰り返し出現する文字列をパースするパーサー、と読めます。

pBoldpItalic の出現順に注意しましょう。or は左側から順に評価されるので、 pItalicpBold より左側に書いてしまうと意図した結果をえることはできません。

実行します。

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

意図通り変換できました。

次のような文字列でボールドとイタリックのマークアップが混在してもうまくいくのか試しましょう。

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

実行。

$ 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)
    object ItalicStart: HtmlBlock("")
    object ItalicStop:  HtmlBlock("")
    object BoldStart:   HtmlBlock("")
    object BoldStop:    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, next, 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 toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Just -> it.value
                is HtmlBlock.ItalicStart -> "<i>"
                is HtmlBlock.ItalicStop  -> "</i>"
                is HtmlBlock.BoldStart -> "<b>"
                is HtmlBlock.BoldStop  -> "</b>"
            }
        }.joinToString("")
    } else {
        ""
    }
}


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

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

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

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

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", {HtmlBlock.Just(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 でパーサーコンビネータを実装する【追伸】 へ続きます。

Liked some of this entry? Buy me a coffee, please.