このポスト 2024年改訂版) データ変換を Writer Monad 的に処理する を書いていて このパーサーコンビネーター( 改善版2024）kotlin でパーサーコンビネータを実装する 【おまけ】 HtmlBlock の改良) は Writer モナド的な発想で書けばもう少しパーサーのインタフェースがシンプルになることに気づいた。
その覚え書きです。
$ kotlin -version
Kotlin version 2.0.20-release-360 (JRE 17.0.12+7-Ubuntu-1ubuntu222.04)
// main.kts
sealed class HtmlBlock {
data class Just(val c: Char): HtmlBlock()
object Nothing: HtmlBlock()
}
typealias Parser = (List<Char>)->HtmlWriter
data class ParseResult(val ok: Boolean, val xs: List<HtmlBlock>)
class HtmlWriter(val cs: List<Char>, val r: ParseResult) {
constructor(cs: List<Char>): this(cs, ParseResult(true, listOf()))
val parse:(Parser)->HtmlWriter = { p->
val w = p(cs)
HtmlWriter(w.cs, appendResult(this.r, w.r))
}
}
appendResult は補助関数で、パース結果(ParseResult)を足し合わせるものです。 このように:
fun appendResult(r1: ParseResult, r2: ParseResult): ParseResult { return if( r1.ok && r2.ok ){ ParseResult(true, r1.xs + r2.xs) } else { ParseResult(false, r1.xs + r2.xs) } }
以前書いたパーサーでは次のようになっていました。
data class ParseResult(
val ok: Boolean,
val next: String,
val htmlBlocks: List<HtmlBlock>)
typealias Parser = (String, List<HtmlBlock>)->ParseResult
パース結果の List<HtmlBlock> をパーサー同士で引き渡して維持する形にしていました。 新しいパーサーではこれを改め、 このパース結果を維持する役割を HtmlWriter クラスにまかせることにしてパーサー側では、 それを気にしなくていいようにしました。
typealias Parser = (List<Char>)->HtmlWriter
data class ParseResult(val ok: Boolean, val xs: List<HtmlBlock>)
class HtmlWriter(val cs: List<Char>, val r: ParseResult) {
...
このように、パーサーが直接 ParseResult を返すのではなく、HtmlWriter を経由することで、 Parser は List<HtmlBlock> を受け取る必要がなくなりました。
ちなみに、以前はパース対象を String としていましたが、 ここでは、List<Char> にしています。
今まではパーサー側でパースできた結果を足し合わせ処理をしていましたが、 このコードが（パーサー側からは）不要になった。 （まあ、それだけといえばそれだけの話）
このパーサーが機能することを確認するために、 letter と zeroOrMore だけ実装します。
// main.kts
fun ngHtmlWriter(cs: List<Char>): HtmlWriter{
return HtmlWriter(cs, ParseResult(false, listOf()))
}
fun okHtmlWriter(cs: List<Char>, xs:List<HtmlBlock>): HtmlWriter{
return HtmlWriter(cs, ParseResult(true, xs))
}
typealias ToHtmlBlock = (Char)->HtmlBlock
fun letter(toHtmlBlock: ToHtmlBlock): Parser {
val p: Parser = { cs->
if( cs.isEmpty() ){
ngHtmlWriter(cs)
} else {
val c = cs.first()
val matchResult = "[a-zA-z]".toRegex().find( "${c}" )
if( matchResult!=null ){
okHtmlWriter(cs.drop(1), listOf(toHtmlBlock(c)))
} else {
ngHtmlWriter(cs)
}
}
}
return p
}
fun zeroOrMore(parser0: Parser): Parser {
tailrec fun f(parser: Parser, cs: List<Char>, acc: List<HtmlBlock>): Pair<List<Char>, List<HtmlBlock>>{
return if( cs.size==0 ){
Pair(cs, acc)
} else {
val w: HtmlWriter = parser(cs)
if( w.r.ok ){
f(parser, w.cs, acc + w.r.xs)
} else {
Pair(cs, acc)
}
}
}
val p: Parser = { cs0->
val (cs1, xs1) = f(parser0, cs0, listOf())
okHtmlWriter(cs1, xs1)
}
return p
}
Hello 文字列をパースしてみます。
パーサーの実装:
val p: Parser = zeroOrMore(letter({ HtmlBlock.Just(it)}))
val toCharList:(String)->List<Char> = { text->
text.toCharArray().toList()
}
val result = HtmlWriter(toCharList("Hello")).parse( p )
println( result.r.xs )
実行:
$ kotlin main.kts
[Just(c=H), Just(c=e), Just(c=l), Just(c=l), Just(c=o)]
できました。
HtmlBlock の部分は変換タスクによって変わります。 テキストをHTMLに変換するのであれば HtmlBlock で（名称的には）いいのですが、 それにしても、そのHtmlBlock の実装は毎回異なるでしょう。 テキストをJSONに変換するのであれば HtmlBlock の部分が... たとえば JsonBlock にしたくなる。 今のコードのように、その部分がハードコーディングされているのは困ります。 そこで、 HtmlWriter を HtmlWriter<T> として実装します。
今までは main.kts に書いてきましたが、ライブラリとして使うことを想定して、 parser.kt にこのジェネリクス版の HtmlWriter を書いていきます。
// parser.kt
// 補助関数
val toCharList:(String)->List<Char> = { text->
text.toCharArray().toList()
}
// 以下、パーサーの実装
typealias Parser<T> = (List<Char>)->HtmlWriter<T>
data class ParseResult<T>(val ok: Boolean, val xs: List<T>)
fun <T> appendResult(r1:ParseResult<T>, r2:ParseResult<T>):ParseResult<T> {
return if( r1.ok && r2.ok ){
ParseResult<T>(true, r1.xs + r2.xs)
} else {
ParseResult<T>(false, r1.xs + r2.xs)
}
}
class HtmlWriter<T>(val cs: List<Char>, val r: ParseResult<T>) {
constructor(cs: List<Char>): this(cs, ParseResult<T>(true, listOf()))
val parse:(Parser<T>)->HtmlWriter<T> = { p->
val w = p(cs)
HtmlWriter<T>(w.cs, appendResult(this.r, w.r))
}
}
fun <T> ngHtmlWriter(cs: List<Char>): HtmlWriter<T>{
return HtmlWriter<T>(cs, ParseResult<T>(false, listOf()))
}
fun <T> okHtmlWriter(cs: List<Char>, xs:List<T>): HtmlWriter<T>{
return HtmlWriter<T>(cs, ParseResult<T>(true, xs))
}
typealias ToSomeone<T> = (Char)->T
fun <T> letter(toSomeone: ToSomeone<T>): Parser<T> {
val p: Parser<T> = { cs->
if( cs.isEmpty() ){
ngHtmlWriter(cs)
} else {
val c = cs.first()
val matchResult = "[a-zA-z]".toRegex().find( "${c}" )
if( matchResult!=null ){
okHtmlWriter(cs.drop(1), listOf(toSomeone(c)))
} else {
ngHtmlWriter(cs)
}
}
}
return p
}
fun <T> zeroOrMore(parser0: Parser<T>): Parser<T> {
tailrec fun f(parser: Parser<T>, cs: List<Char>, acc: List<T>): Pair<List<Char>, List<T>>{
return if( cs.size==0 ){
Pair(cs, acc)
} else {
val w: HtmlWriter<T> = parser(cs)
if( w.r.ok ){
f(parser, w.cs, acc + w.r.xs)
} else {
Pair(cs, acc)
}
}
}
val p: Parser<T> = { cs0->
val (cs1, xs1) = f(parser0, cs0, listOf())
okHtmlWriter(cs1, xs1)
}
return p
}
パーサーを parser.jar としてビルド:
$ kotlinc parser.kt -d parser.jar
それでは、このパーサーを使うコードを用意します。
// main.kts
sealed class HtmlBlock {
data class Just(val c: Char): HtmlBlock()
object Nothing: HtmlBlock()
}
val p: Parser<HtmlBlock> = zeroOrMore(letter({ HtmlBlock.Just(it)}))
val result = HtmlWriter<HtmlBlock>(toCharList("Hello")).parse( p )
println( result.r.xs )
実行:
$ kotlin -cp parser.jar main.kts
[Just(c=H), Just(c=e), Just(c=l), Just(c=l), Just(c=o)]
うまくいきました。
HtmlWriter の導入で、パーサー側の実装が少し簡単になりました。 パース結果の維持に気を配る必要は本来パーサーの責任ではないので、 これでよいのかな、たぶん。
Liked some of this entry? Buy me a coffee, please.