Kotlin , Text Processing , Parser Combinator

Tuesday, August 13, 2024

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

以前に改善版) kotlin でパーサーコンビネータを実装するを書いたのですが、その後さらに改良した。

ここでは Hello, *World*! という文字列を自前で実装したパーサーコンビネーターを使ってHTMLに変換することを考えます。

改善版2024）【後編】Bold パーサーを追加してみるへ続きます。

環境の確認

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

これを次のように修正（改良後）します。

sealed class HtmlBlock(val value: String) {
    class Foo(value: String): HtmlBlock(value)
    class Bar(value: String): HtmlBlock(value)
    class Hoge(value: String): HtmlBlock(value)
}

typealias ToHtmlBlock = (String)->HtmlBlock

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

何が変わったのかと言えば、 Html をやめて、HtmlBlock を導入したことです。

以前は、パースした結果を Html の value に文字列として蓄積していました。

data class Html(val value: String)

改良版は、それに代えて List<HtmlBlock> として蓄積することにします。それにともない、 Parser, ParseResult も変更（ HTML 部分を List<HtmlBlock> に変更した）しました。

foobarhoge のパース

この新しいパーサーを使って、まずは試しに foobarhoge 文字列パースしてみます。

最終的に組み立てたパーサーはこれです。

val text = "foobarhoge"

val pFoo: Parser  = pWord("foo", { HtmlBlock.Foo(it) })
val pBar: Parser  = pWord("bar", { HtmlBlock.Bar(it) })
val pHoge: Parser = pWord("hoge",{ HtmlBlock.Hoge(it) })
val p: Parser = zeroOrMore( pFoo or pBar or pHoge )

val parseResult = p(text, listOf())
println(parseResult)

pFoo パーサーをつくっているこの部分 {HtmlBlock.Foo(it)} は、冗長に記述すれば以下のようになる。
val toHtmlBlockFoo: ToHtmlBlock = { value-> HtmlBlock.Foo(value) }
val pFoo: Parser = pWord("foo", toHtmlBlockFoo)

次の部分がこのパーサーの結論です。

val p: Parser = zeroOrMore( pFoo or pBar or pHoge )

pFoo か pBar か pHoge が0回以上繰り返し出現する文字列をパースするパーサ、と読めます。

実行して、パースが成功したら、次のようなHTMLっぽい文字列を出力することを目指します。

<foo>foo</foo><bar>bar</bar><hoge>hoge</hoge>

ここでは pWord, zeroOrMore, or パーサーを使用しているので、まずはこれらを（以前作成したコードをベースにして）新しい定義にあわせて書きかえます。

pWord

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
}

zeroOrMore

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
}

or

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
}

補助関数 toNGParseResult

パースが失敗したときに使う補助関数 toNGParseResult の定義はこれ。

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

実行

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

$ kotlin main.kts
ParseResult(ok=true, next=, htmlBlocks=[Hoge$HtmlBlock$Foo@4e9d1119, Hoge$HtmlBlock$Bar@5d1907fb, Hoge$HtmlBlock$Hoge@6079d219])

うまくパースできているようですが、パース結果が分かりにくいので、結果をわかりやすく出力する toHtml 関数を定義します。

val toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Foo -> {
                    "<foo>${it.value}</foo>"
                }
                is HtmlBlock.Bar -> {
                    "<bar>${it.value}</bar>"
                }
                is HtmlBlock.Hoge -> {
                    "<hoge>${it.value}</hoge>"
                }
            }
        }.joinToString("")
    } else {
        ""
    }
}

それでは、 parseResult をそのまま println するのではなくて、 toHtml 経由で println します。

//println(parseResult)
println( toHtml(parseResult) )

実行。

$ kotlin main.kts
<foo>foo</foo><bar>bar</bar><hoge>hoge</hoge>

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

中間まとめ

ここまで書いてきたコードを掲載します。

// main.kts

sealed class HtmlBlock(val value: String) {
    class Foo(value: String): HtmlBlock(value)
    class Bar(value: String): HtmlBlock(value)
    class Hoge(value: String): HtmlBlock(value)
}

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.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 toHtml: (ParseResult)->String = { r->
    if( r.ok ){
        r.htmlBlocks.map {
            when(it){
                is HtmlBlock.Foo -> {
                    "<foo>${it.value}</foo>"
                }
                is HtmlBlock.Bar -> {
                    "<bar>${it.value}</bar>"
                }
                is HtmlBlock.Hoge -> {
                    "<hoge>${it.value}</hoge>"
                }
            }
        }.joinToString("")
    } else {
        ""
    }
}


val text = "foobarhoge"

val pFoo: Parser  = pWord("foo", { HtmlBlock.Foo(it) })
val pBar: Parser  = pWord("bar", { HtmlBlock.Bar(it) })
val pHoge: Parser = pWord("hoge",{ HtmlBlock.Hoge(it) })

val p: Parser = zeroOrMore( pFoo or pBar or pHoge )
val parseResult = p(text, listOf())

//println(parseResult)
println( toHtml(parseResult) )

Hello, World! を変換

いよいよ本題である Hello, *World*! 文字列をこのパーサーを使って変換してみます。期待される変換結果はこれ:

Hello, <i>World</i>!

それでは、パーサーを組み立てます。

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

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

val p = zeroOrMore(pItalic or pJust)

今まで説明していない新しいパーサーがいくつか出ていますが、あとで説明します。

ポイントになるのは、 *World* の部分のパースですが、それを担当しているのが pItalic です。

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

pItalicStart で最初の * をパース。そのあと、 zeroOrMore と pNone で次の * が出現する前までをパースします。

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

これは、* 以外の文字を０回以上（一文字ずつ）パースする、という意味になります。（そして結果は HtmlBlock.Just にいれていきます。）

あとは末尾の pItalicStop でうしろの（閉じタグ用の） * をパースします。

結論としてのまとめのパーサー記述はこのようになっています。

val p = zeroOrMore(pItalic or pJust)

イタリック or ただの文字（１文字の文字列）が０回以上出現する文字列をパースするパーサーと読めます。

それでは、ここで使用したパーサー and, pAnyone, pNone について順に説明します。

and

以前と同じです。もちろん、今回の改良されたパーサーに合わせて修正。( html を htmlBlocks に修正)

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
}

pAnyone

これははじめて登場するパーサーですが、内容は簡単で、任意の一文字にマッチして消費するパーサーです。

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
}

pNone

pNone は指定した token 以外の任意の一文字にマッチします。条件付き pAnyone というイメージです。これはほぼ pAnyone パーサーと同じ振る舞いだが、指定された token だった場合に限りパースは失敗する。

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
}

zeroOrMore パーサーと組み合わせて使うことで、指定の token が出現するまでパースする、パーサーをつくることができます。

実行

それではこれらのパーサーを組み合わせて実際に Hello, *World*! のパースを実行してみます。

パーサー全体はこれ:

val text = "Hello, *World*!"

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

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

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

新たに HtmlBlock として Just, ItalicStart, ItalicStop を利用しているので、それを追加します。

sealed class HtmlBlock(val value: String) {
    class Just(value: String): HtmlBlock(value)
    object ItalicStart: HtmlBlock("")
    object ItalicStop: HtmlBlock("")
    /*
    class Foo(value: String): HtmlBlock(value)
    class Bar(value: String): HtmlBlock(value)
    class Hoge(value: String): HtmlBlock(value)
    */
}

HtmlBlock.Foo,Bar,Hoge は今は使用しないのでコメントアウトします。

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

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>"
            }
        }.joinToString("")
    } else {
        ""
    }
}

イタリックマークアップの前と後ろで意図通りの出力になるように <i>, </i> を出力するようにしています。

それでは実行します。

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

意図通り作動しました。

パース対象のテキストを次のように変更してみます。

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

実行。

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

うまくいきました。

まとめ

コード全体を掲載します。

// main.kts

sealed class HtmlBlock(val value: String) {
    class Just(value: String): HtmlBlock(value)
    object ItalicStart: HtmlBlock("")
    object ItalicStop: 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>"
            }
        }.joinToString("")
    } else {
        ""
    }
}


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

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

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

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