以前に改善版) 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 文字列パースしてみます。
最終的に組み立てたパーサーはこれです。
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 パーサーを使用しているので、 まずはこれらを （以前作成したコードをベースにして） 新しい定義にあわせて書きかえます。
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
}
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
}
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 の定義はこれ。
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, <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 について順に説明します。
以前と同じです。もちろん、今回の改良されたパーサーに合わせて修正。( 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
}
これははじめて登場するパーサーですが、内容は簡単で、任意の一文字にマッチして消費するパーサーです。
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 は指定した 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) )
改善版2024）【後編】Bold パーサーを追加してみる へ続きます。