「 テキストをパーサーコンビネータを使ってパースすることを考えてみる 」 というのを先日考えたのですが、今回はその改善版です。
many パーサーコンビネータ の再帰部分がどうにも気に入らないので見直しました。
前回 の定義はこれです。
data class Html(val tagName: String, val value: String)
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
typealias Parser = (String)->ParseResult
今回の改善版ではこの Parser を少しだけ変更します。
typealias Parser = (String, Html)->ParseResult
String を受け取って ParseResult を返していた(前回)のを改め、 String と Html を受け取って ParseResult を返すように変更しました。 つまり、パース対象のテキストだけ渡すのではなく、それまでのパース結果の成果物である Html も渡すように変更しています。(これがポイント)
それでは、この変更を反映していきます。
前回の pWord はこれです。
val pWord: (String)-> Parser = { token->
{ text->
if( text.length < token.length ){
toNGParseResult(text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html("<para>${token}</para>"), text.substring(token.length))
} else {
toNGParseResult(text)
}
}
}
}
pWord 関数は Parser を生成して返していますが { text-> ... } の部分を改善版の Parser の定義にあわせて { text, html-> ... } に変更します。
val pWord: (String)-> Parser = { token->
{ text, html->
if( text.length < token.length ){
toNGParseResult(text)
} else {
if( text.substring(0, token.length)==token ){
ParseResult(true, Html(html.value + "<para>${token}</para>"), text.substring(token.length))
} else {
toNGParseResult(text)
}
}
}
}
それから パースが成功した場合に生成する成果物である Html も変更しています。 次のように、前のパーサーが生成した成果物(html.value)を足し合わせています。
Html(html.value + "<para>${token}</para>")
さらに本題とは無関係ですが、 if が入れ子になっていて気持ち悪いので、そこもリファクタリングします。 また、token の変数名を word に変えました。 pWord 関数なので、 word という変数名を使う方が make sense だろうと。
リファクタリングした結果の pWord 関数はこれです。
val pWord: (String)-> Parser = { word->
{ text, html->
val invalid = ( text.length < word.length )
if( !invalid && text.substring(0, word.length)==word ){
ParseResult(true, Html(html.value + "<para>${word}</para>"), text.substring(word.length))
} else {
toNGParseResult(text)
}
}
}
元のコード
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text->
val parseResult0 = parser0(text)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next)
if( parseResult1.ok ){
ParseResult(
true,
Html("${parseResult0.html.value}${parseResult1.html.value}"),
parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
return { text-> ... } に代えて return { text, html-> ... } にします。 さらに Parser にパース結果の Html の値を渡していきます。
そうやって修正した新しい and 関数がこれです。
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text, html->
val parseResult0 = parser0(text, html)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.html)
if( parseResult1.ok ){
ParseResult(true, parseResult1.html, parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
パース結果を足していく処理がパーサー側に移動したので、パーサーを組み合わせる方の関数(パーサーコンビネータ)は簡単になりました。 無理やり感がなくいい感じです。
and 関数と変更ポイントは同じなので、新しいコードだけ掲載します。
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
return { text, html->
val parseResult0 = parser0(text, html)
val parseResult1 = parser1(text, html)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
}
問題の many 関数です。
元のコードは、これ。
val many: (Parser)->Parser = { parser->
{ text->
tailrec fun f(parseResult: ParseResult): ParseResult {
val currentParseResult = parser(parseResult.next)
return if( !currentParseResult.ok ){
ParseResult(
true,
Html(parseResult.html.value),
parseResult.next)
} else {
f(
ParseResult(
true,
Html("${parseResult.html.value}${currentParseResult.html.value}"),
currentParseResult.next))
}
}
f(ParseResult(true, Html(""), text))
}
}
f 関数を使って再帰処理をしていたのですが、新しい方は次のように直接 many を呼び出す(これも再帰ですが)形になりました。
fun many(parser: Parser): Parser {
return { text, html->
val parseResult = parser(text, html)
if( !parseResult.ok ){
// パースが失敗した場合:
ParseResult(true, html, text)
} else {
// パースが成功した場合:
many(parser)(parseResult.next, parseResult.html)
}
}
}
これだけ 関数リテラルではなく、 ふつうの関数 として定義しているのは、そうしないと不都合が生じるからです。説明は割愛。
パースに成功した場合は再び(再帰的に) many を呼び出すことで、繰り返し parser を適用しています。
すっきりした記述にはなったのですが、元のコードでは指定できていた tailrec fun が使えなくなってしまったので、 many の繰り返しが多すぎるとスタックオーバーフローが起きると思います。 今はこれでよいことにしよう。
以上で、Parser 型を変更したことにより影響したコードを全部修正できました。 実際にこれらを使って 文字列 hogefoobarbarfoohoge をパース実行してみます。
val EMPTY_HTML = Html("")
val text = "hogefoobarbarfoohoge"
val p: Parser = many( pFoo() or pBar() or pHoge() )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)
Parser に パース対象の文字列だけでなく Html を渡す必要があるので、空の Html("") 渡しています(初期値として)。
実行します。
$ kotlinc -script main.kts
ParseResult(ok=true, html=Html(value=<para>hoge</para><para>foo</para><para>bar</para><para>bar</para><para>foo</para><para>hoge</para>), next=)
うまくパースできました。
最後に今回の改訂バージョンのコード全体を掲載します。
main.kts
data class Html(val value: String)
data class ParseResult(val ok: Boolean, val html: Html, val next: String)
typealias Parser = (String, Html)->ParseResult
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, Html(""), next)
}
val pWord: (String)-> Parser = { word->
{ text, html->
val invalid = ( text.length < word.length )
if( !invalid && text.substring(0, word.length)==word ){
ParseResult(true, Html(html.value + "<para>${word}</para>"), text.substring(word.length))
} else {
toNGParseResult(text)
}
}
}
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text, html->
val parseResult0 = parser0(text, html)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.html)
if( parseResult1.ok ){
ParseResult(true, parseResult1.html, parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
return { text, html->
val parseResult0 = parser0(text, html)
val parseResult1 = parser1(text, html)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
}
fun many(parser: Parser): Parser {
return { text, html->
val parseResult = parser(text, html)
if( !parseResult.ok ){
ParseResult(true, html, text)
} else {
many(parser)(parseResult.next, parseResult.html)
}
}
}
val pFoo: ()->Parser = { pWord("foo") }
val pBar: ()->Parser = { pWord("bar") }
val pHoge: ()-> Parser = { pWord("hoge") }
val EMPTY_HTML = Html("")
val text = "hogefoobarbarfoohoge"
val p: Parser = many( pFoo() or pBar() or pHoge() )
val parseResult = p(text, EMPTY_HTML)
println(parseResult)
以上です。