Home About
Kotlin , Text Processing , Parser Combinator

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

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

この方法を使ってパースした場合、 最後にHTMLを出力する段階で HtmlBlock をまとめるコードがあるのですが、 やっていることは同じ種類の HtmlBlock を一つにしているだけです。 しかし、 HtmlBlock を sealed class として用意しているので、それを まとめる だけの操作をするのにもこれだけのコードを書く必要があります。

このように:

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

... listOf(createHtmlBlock(accLast,(accLast.value + htmlBlock.value))) ...

HtmlBlock の種類が増えたら面倒すぎる。

直感的に言えば、二つの HtmlBlock を（同じ種類だったら）足し合わせることができる演算子を HtmlBlock に定義できればよい。

そこで sealed クラスとして HtmlBlock を表現するのをあきらめて普通のデータクラスにして、 代わりに BlockKind という enum class を使うことにしてみた。 このように:

enum class BlockKind { JUST, ITALIC, BOLD, NOTHING }
data class HtmlBlock(val kind: BlockKind, val value: String)

さらに、このHtmlBlock の２つを引数にとって同じ種類だったら一つにまとめる関数 concatTwoHtmlBlocks を作成:

val concatTwoHtmlBlocks: (HtmlBlock, HtmlBlock)->List<HtmlBlock> = { a, b->
    if( a.kind == b.kind ){
        listOf(HtmlBlock(a.kind, a.value + b.value))
    } else {
        listOf(a,b)
    }
}

簡単に扱えるように `+` を infix で定義:

infix fun HtmlBlock.`+`(htmlBlock1: HtmlBlock): List<HtmlBlock> {
    val htmlBlock0 = this
    return concatTwoHtmlBlocks(htmlBlock0, htmlBlock1)
}

種類が異なる場合は足さないので、単なる + 演算でもないのだが、 演算子名でよいものが思いつかなかったので。

これなら次のように HtmlBlock をまとめる処理が記述できる。

val a = HtmlBlock(BlockKind.JUST, "a")
val b = HtmlBlock(BlockKind.JUST, "b")
val c = HtmlBlock(BlockKind.ITALIC, "c")
println( a `+` b ) // => [HtmlBlock(kind=JUST, value=ab)]
println( a `+` c ) // => [HtmlBlock(kind=JUST, value=a), HtmlBlock(kind=ITALIC, value=c)]

そもそもここまでやるくらいだったら HtmlBlock の value を val ではなく var にして value を変更可能にしてしまえば 済むという話もなくはない。 var にすることで data class にはできなくなるが。 そのほか、この方法は事前に BlockKind が確定していなければいけないため、 パーサー部分だけをライブラリにしたい場合は、困るだろう。 その場合は AbstractHtmlBlock などを導入すればなんとかなるだろう。（割愛）

これを使ってパーサー部分を記述すれば、こうなります:

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

val toNothing: ToHtmlBlock = { HtmlBlock(BlockKind.NOTHING, "") }
val toItalic: ToHtmlBlock  = { HtmlBlock(BlockKind.ITALIC, it) }
val toBold: ToHtmlBlock    = { HtmlBlock(BlockKind.BOLD, it) }
val toJust: ToHtmlBlock    = { HtmlBlock(BlockKind.JUST, it) }

val pItalicStart: Parser  = pWord("*", toNothing)
val pItalicStop: Parser   = pWord("*", toNothing)

val pBoldStart: Parser  = pWord("**", toNothing)
val pBoldStop: Parser   = pWord("**", toNothing)

val pItalic = 
    pItalicStart and
    zeroOrMore(pNone("*", toItalic)) and
    pItalicStop

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", toBold)) and
    pBoldStop

val pJust = pAnyone( toJust )

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

sealed クラス使わなくてもいいのかなこれで。

まとめ

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

// main.kts

enum class BlockKind { JUST, ITALIC, BOLD, NOTHING }
data class HtmlBlock(val kind: BlockKind, val value: String)

typealias ToHtmlBlock = (String)->HtmlBlock

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


val concatTwoHtmlBlocks: (HtmlBlock, HtmlBlock)->List<HtmlBlock> = { a, b->
    if( a.kind == b.kind ){
        listOf(HtmlBlock(a.kind, a.value + b.value))
    } else {
        listOf(a,b)
    }
}

infix fun HtmlBlock.`+`(htmlBlock1: HtmlBlock): List<HtmlBlock> {
    val htmlBlock0 = this
    return concatTwoHtmlBlocks(htmlBlock0, htmlBlock1)
}

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 fixHtmlBlocks: (List<HtmlBlock>)->List<HtmlBlock> = { htmlBlocks->
    htmlBlocks.fold(listOf<HtmlBlock>()) { acc, htmlBlock->
        if( acc.size==0 ){
            acc + listOf(htmlBlock)
        } else {
            val accLast = acc.last()
            acc.dropLast(1) + (accLast `+` htmlBlock)
        }
    }
}

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        fixHtmlBlocks(r.htmlBlocks).map {
            when(it.kind){
                BlockKind.JUST -> it.value
                BlockKind.ITALIC -> "<i>${it.value}</i>"
                BlockKind.BOLD   -> "<b>${it.value}</b>"
                BlockKind.NOTHING -> ""
            }
        }.joinToString("")
    } else {
        ""
    }
}


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

val toNothing: ToHtmlBlock = { HtmlBlock(BlockKind.NOTHING, "") }
val toItalic: ToHtmlBlock  = { HtmlBlock(BlockKind.ITALIC, it) }
val toBold: ToHtmlBlock    = { HtmlBlock(BlockKind.BOLD, it) }
val toJust: ToHtmlBlock    = { HtmlBlock(BlockKind.JUST, it) }

val pItalicStart: Parser  = pWord("*", toNothing)
val pItalicStop: Parser   = pWord("*", toNothing)

val pBoldStart: Parser  = pWord("**", toNothing)
val pBoldStop: Parser   = pWord("**", toNothing)

val pItalic = 
    pItalicStart and
    zeroOrMore(pNone("*", toItalic)) and
    pItalicStop

val pBold = 
    pBoldStart and
    zeroOrMore(pNone("**", toBold)) and
    pBoldStop

val pJust = pAnyone( toJust )

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

以上です。

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