以前のエントリー 改善版) kotlin でパーサーコンビネータを実装する の続きです。
そもそもの動機としては、 マークアップがネストしていたときにパーサーコンビネータを使ってパースするにはどうすればいいのだろうか？ とか考えはじめた結果の覚え書きです。
パーサーコンビネータ部分の説明は省きます。（以前のエントリーを必要なら参照のこと）
このようなテキストを対象とします。
Example: The quick brown fox jumps over the lazy dog.
このテキストを次のように（独自のローカルルールで）マークアップしたとします。
{title}Example:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}
今の関心事であるネストした部分は p タグで囲った部分に b タグが出現しているところです。 これをパーサーコンビネータを使って再帰的にパースした上で HTML へ変換してみます。
いきなり対象のテキストをパースしないで、次のような簡単な b タグのみが出現するテキストをパースすることを考えます。
Hello, {b}World{/b}!
パーサーコンビネーターのコードはこれ:
import kotlin.text.Regex
import kotlin.text.MatchResult
sealed class Token(open val value: String) {
data class AnyChar(override val value: String): Token(value)
data class Bold(override val value: String): Token(value)
}
data class ParseResult(val ok: Boolean, val tokens: List<Token>, val next: String)
typealias Parser = (String, List<Token>)->ParseResult
typealias ToToken = (MatchResult)->Token
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, listOf(), next)
}
val concatAnyCharTokens: (List<Token>)->List<Token> = { tokens->
val initialValue = mutableListOf<Token>()
val f: (MutableList<Token>, Token)-> MutableList<Token> = { acc, token->
val isAnyCharToken: (Token)->Boolean = { (it is Token.AnyChar) }
if(acc.size>0 && isAnyCharToken(token) && isAnyCharToken(acc[acc.size-1])){
val lastToken = acc[acc.size-1]
acc[acc.size-1] = Token.AnyChar("${lastToken.value}${token.value}")
acc
} else {
acc.add(token)
acc
}
}
tokens.fold(initialValue, f)
}
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text, tokens->
val parseResult0 = parser0(text, tokens)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.tokens)
if( parseResult1.ok ){
ParseResult(true, concatAnyCharTokens(parseResult1.tokens), parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
return { text, tokens->
val parseResult0 = parser0(text, tokens)
val parseResult1 = parser1(text, tokens)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
}
fun many(parser: Parser): Parser {
return { text, tokens->
val parseResult = parser(text, tokens)
if( !parseResult.ok ){
ParseResult(true, concatAnyCharTokens(tokens), text)
} else {
many(parser)(parseResult.next, parseResult.tokens)
}
}
}
val pAnyChar: ()->Parser = {
{ text, tokens->
if( text.length>0 ){
val headChar = text[0]
ParseResult(
true,
concatAnyCharTokens(tokens + listOf(Token.AnyChar(headChar.toString()))),
text.substring(1))
} else {
toNGParseResult(text)
}
}
}
val pRegex: (Regex, ToToken)->Parser = { regex, toToken->
{ text, tokens->
val m = regex.find(text)
if( m!=null ){
ParseResult(
true,
concatAnyCharTokens(tokens + listOf(toToken(m))),
text.substring( m.groupValues[0].length ))
} else {
toNGParseResult(text)
}
}
}
val pBold: ()->Parser = {
val regex = "^\\{b\\}(.*?)\\{/b\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Bold(value)
}
pRegex(regex, f)
}
簡単に説明すれば、 pAnyChar() や pRegex を拡張した pBold() を or, and, many を使って組み合わせて 対象となるテキストをパースします。
concatAnyCharTokens は、単なる便利関数で連続して出現した複数の Token.AnyChar を一つの Token.AnyChar にまとめます。
Token クラスは、 テキストをパースした結果を入れる入れ物です。 いまのところ、Token の種類は AnyChar, Bold の２種類のみです。（あとで増やします。）
この２つの種類は、sealed class として表現しています。
sealed class Token(open val value: String) { data class AnyChar(override val value: String): Token(value) data class Bold(override val value: String): Token(value) }
パーサーを組み立てます。
val parser: Parser = many( pBold() or pAnyChar() )
ボールドか任意の文字が0回以上出現するテキスト をパースすることを 想定したパーサーです。
それでは実際に Hello, World! のテキストをパースして結果を標準出力します。
val text = "Hello, {b}World{/b}!"
val parseResult: ParseResult = parser(text, listOf())
if( parseResult.ok ){
parseResult.tokens.forEach { println( "- $it") }
}
ここまでのコードを main.kts に保存して実行します。
環境の確認:
$ kotlin -version
Kotlin version 1.9.22-release-704 (JRE 17.0.10+7-Ubuntu-122.04.1)
実行:
$ kotlin main.kts
- AnyChar(value=Hello, )
- Bold(value=World)
- AnyChar(value=!)
うまくいきました。
今度は先ほどのテキスト全体を p タグで囲んだテキストをパースできるようにしてみます。
パース対象とするテキスト:
{p}Hello, {b}World{/b}!{/p}
p タグをパースできるパーサーを生成する関数 pPara を定義:
val pPara: ()->Parser = {
val regex = "^\\{p\\}(.*?)\\{/p\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Para(value)
}
pRegex(regex, f)
}
パースできたテキストを Token.Para に入れています。 これはまだ定義していないので、 Token.Para の定義を追加します。
sealed class Token(open val value: String) {
data class AnyChar(override val value: String): Token(value)
data class Bold(override val value: String): Token(value)
data class Para(override val value: String): Token(value)
}
これでパースするための準備ができたので、パーサーを組み立てます。
val parser: Parser = many( pPara() or pBold() or pAnyChar() )
このパーサーを使ってパースを実行して結果を標準出力します。
val text = "{p}Hello, {b}World{/b}!{/p}"
val parseResult: ParseResult = parser(text, listOf())
if( parseResult.ok ){
parseResult.tokens.forEach { println( "- $it") }
}
実行:
$ kotlin main.kts
- Para(value=Hello, {b}World{/b}!)
（予想できたことではありますが残念ながら） p タグ部分のみパースされて Token.Para になり、 その内側にある b タグ部分はパースできていません。
ならば、パースした結果にもう一度パーサーを適用すればよいのでは？ このように:
val parser: Parser = many( pPara() or pBold() or pAnyChar() )
val text = "{p}Hello, {b}World{/b}!{/p}"
val parseResult: ParseResult = parser(text, listOf())
if( parseResult.ok ){
parseResult.tokens.forEach { println( "- $it") }
parseResult.tokens.forEach { token->
val parseResult1 = parser(token.value, listOf())
if( parseResult1.ok ){
parseResult1.tokens.forEach { println( " - $it") }
}
}
}
実行:
$ kotlin main.kts
- Para(value=Hello, {b}World{/b}!)
- AnyChar(value=Hello, )
- Bold(value=World)
- AnyChar(value=!)
できるにはできました。
ただ、もう一段階ネストが深くなる必要があるような対象テキストを パースすることになればこのコードは機能しなくなります。 任意の階層を持ちうる深いネストにも対応するには、 この部分の処理を再帰関数にして、その結果のテキスト aToken.value が Token.AnyChar のみになったら再帰をやめる、というコードをかけばよさそうです。
再帰のストップを判定させるには こんな関数 isStopRecursion でよいでしょう。
val isStopRecursion: (Parser, Token)->Boolean = { p, token->
if( !(token is Token.AnyChar) ){
false
} else {
val text = token.value
val parseResult = p(text, listOf())
if( parseResult.ok ){
val tokens = parseResult.tokens
( tokens.size==1 && tokens.first() is Token.AnyChar )
} else {
true
}
}
}
これは次のような内容の関数です。
ParseResult の tokens は concatAnyCharTokens が適用済みで、常に複数ある連続した Token.AnyChar はひとつの Token.AnyChar にまとめられている。 したがって、 次のコードでパース結果の tokens がすべて Token.AnyChar であるかを判定できる。
( tokens.size==1 && tokens.first() is Token.AnyChar )
さて問題の再帰部分ですが、再帰しながらパースした結果( token ) を保存しておく必要があるので、 次のような Tree クラスを定義しておきます。
sealed class Tree(open val token: Token) {
data class Node(override val token: Token, val children: List<Tree>): Tree(token)
data class Leaf(override val token: Token): Tree(token)
}
以前のエントリー 木構造のノード出現順（深さ優先順）に番号を振る話 EPUB playOrderを参照。
パーサーとテキストを渡すと Tree に変換してくれる関数 buildTree を定義。
val buildTree: (Parser, String)->Tree = { parser, text->
fun f(p: Parser, token: Token): Tree {
val parseResult = p(token.value, listOf())
return if( parseResult.ok ){
if( isStopRecursion(p, token) ){
Tree.Leaf(token)
} else {
Tree.Node(token, parseResult.tokens.map { f(p, it) })
}
} else {
Tree.Leaf(token)
}
}
f(parser, Token.AnyChar(text))
}
build 関数内に 再帰しながら aToken.value が Token.AnyChar だけで構成されるようになるまで処理を繰り返す 関数 f を記述しています。
さらに、この関数を使って構築した Tree インスタンスを視覚的にわかるように標準出力する showTree 関数を用意:
val showTree: (Tree)->Unit = { tree->
val indent: (Int)->String = { l-> 0.until(l).map { " " }.joinToString("") }
val toTokenKind: (Token)->String = { token->
when(token) {
is Token.AnyChar-> "AnyChar"
is Token.Para-> "Para"
is Token.Bold-> "Bold"
}
}
fun f(acc: List<String>, t: Tree, l: Int): List<String> {
val tokenKind = toTokenKind(t.token)
val value = if(t.token is Token.AnyChar) {
"${indent(l)}- ($tokenKind)${t.token.value}"
} else {
"${indent(l)}- ($tokenKind)"
}
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree->
f(acc0, childTree, l+1)
})
}
}
}
val initialValue = listOf<String>()
val initialIndentValue = 0
val list = f(initialValue, tree, initialIndentValue)
println( list.joinToString(System.getProperty("line.separator")) )
}
それでは、 Tree を構築して表示するコードを書きます。
val parser: Parser = many( pPara() or pBold() or pAnyChar() )
val text = "{p}Hello, {b}World{/b}!{/p}"
val tree = buildTree(parser, text)
showTree(tree)
実行:
$ kotlin main.kts
- (AnyChar){p}Hello, {b}World{/b}!{/p}
- (Para)
- (AnyChar)Hello,
- (Bold)
- (AnyChar)World
- (AnyChar)!
意図通り出力できました。
この部分:
- (AnyChar){p}Hello, {b}World{/b}!{/p}
今はパース対象となるテキスト全体が Token.AnyChar になっていますが、これを Token.Document になるようにしましょう。 そのためには、まず Token に Document を追加します。
sealed class Token(open val value: String) {
data class AnyChar(override val value: String): Token(value)
data class Bold(override val value: String): Token(value)
data class Para(override val value: String): Token(value)
data class Document(override val value: String): Token(value)
}
when(token) している部分も修正必要です。
showTree
val toTokenKind: (Token)->String = { token-> when(token) { is Token.AnyChar-> "AnyChar" is Token.Para-> "Para" is Token.Bold-> "Bold" is Token.Document-> "Document" } }
さらに、 buildTree の再帰処理をはじめる部分のコードを変更。
//f(parser, Token.AnyChar(text))
f(parser, Token.Document(text))
今までは、 Token.AnyChar で対象となるテキスト全体を包んでいましたが、これに代えて Token.Document で包むことにします。
実行:
$ kotlin main.kts
- (Document)
- (Para)
- (AnyChar)Hello,
- (Bold)
- (AnyChar)World
- (AnyChar)!
うまくテキスト全体を Token.Document として表現できるようになりました。 この形式であれば、この Tree から元の文字列（マークアップを取り除いた元の文字列）を作り出すには Tree を深さ優先順でトラバースしながら AnyChar の ノードだけを出力すればよいことになります。
マークアップテキストから構築した Tree インスタンスをプレーンテキストに戻す関数 toPlainText を実装。
val toPlainText: (Tree)->String = { tree->
fun f(acc: List<String>, t: Tree): List<String> {
val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) })
}
}
}
val initialValue = listOf<String>()
f(initialValue, tree).joinToString("")
}
再帰関数 f 内で Tree をトラバースしつつ、 aTree.token が Token.AnyChar ならばその内容を出力し、 それ以外は空文字列を出力（つまりなにも出力しないという意味）しています。
val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
toPlainText を使うコード。
val parser: Parser = many( pPara() or pBold() or pAnyChar() )
val text = "{p}Hello, {b}World{/b}!{/p}"
val tree = buildTree(parser, text)
val plainText = toPlainText(tree)
println(plainText)
実行。
$ kotlin main.kts
Hello, World!
マークアップを取り除いたテキストに戻すことができました。
マークアップをストリップする toPlainText に少し手を加えれば、HTMLへ変換することができそうです。
まず最初のステップとして、Token.AnyChar 以外のノードが来たら、HTMLの開始タグを書き出す機能を追加した toHtml 関数を toPlainText をベースにしてつくってみます。
val toHtml: (Tree)->String = { tree->
val toHtmlStartTag: (Token)->String = { token->
when(token) {
is Token.Document-> "<body>"
is Token.Para-> "<p>"
is Token.Bold-> "<b>"
is Token.AnyChar-> ""
}
}
fun f(acc: List<String>, t: Tree): List<String> {
//val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
val value = if(t.token is Token.AnyChar) { t.token.value } else { toHtmlStartTag(t.token) }
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) })
}
}
}
val initialValue = listOf<String>()
f(initialValue, tree).joinToString("")
}
ポイントは次の行だけです。 いままで Token.AnyChar 以外の token は空文字列を出していたところに代えて開始タグを出力するように変更しました。
//val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
val value = if(t.token is Token.AnyChar) { t.token.value } else { toHtmlStartTag(t.token) }
実行してみます。
$ kotlin main.kts
<body><p>Hello, <b>World!
開始タグだけを入れることができました。
それでは次にHTML終了タグを出力するように toHtml 関数内の 再帰関数 f を修正します。
fun f(acc: List<String>, t: Tree): List<String> {
//val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
val value = if(t.token is Token.AnyChar) { t.token.value } else { toHtmlStartTag(t.token) }
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
//t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) })
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) }) + toHtmlStopTag(t.token)
}
}
}
変更したのは HTMLの終了タグを追加したこの部分だけです。
//t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) })
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) }) + toHtmlStopTag(t.token)
もちろん toHtmlStopTag 関数を書く必要があります。 toHtmlStartTag とほぼ同じなのでコードは省略します。
実行すると今度は閉じタグまで出力されてHTML断片として機能する文字列を組み立てることができました。
$ kotlin main.kts
<body><p>Hello, <b>World</b>!</p></body>
この仕組みを使えば HTML 以外の形式にも変換できるでしょう。たとえばマークダウンとか。
これで マークアップテキスト → AST → なにかへの変換 するためのコードはだいたいそろったので、冒頭の本来パースしたかった文字列のパースに挑戦します。
{title}Example:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}
title マークアップはまだ実装していません。 これに付随して必要なコードを追加していきましょう。
Token クラスへ Token.Title を追加:
sealed class Token(open val value: String) {
data class AnyChar(override val value: String): Token(value)
data class Bold(override val value: String): Token(value)
data class Para(override val value: String): Token(value)
data class Document(override val value: String): Token(value)
data class Title(override val value: String): Token(value)
}
toHtmlStartTag, toHtmlStopTag へ Token.Title が来たときのコードを追加:
val toHtmlStartTag: (Token)->String = { token->
when(token) {
is Token.Document-> "<body>"
is Token.Title-> "<h1>"
is Token.Para-> "<p>"
is Token.Bold-> "<b>"
is Token.AnyChar-> ""
}
}
val toHtmlStopTag: (Token)->String = { token->
when(token) {
is Token.Document-> "</body>"
is Token.Title-> "</h1>"
is Token.Para-> "</p>"
is Token.Bold-> "</b>"
is Token.AnyChar-> ""
}
}
title に対応する HTMLタグは h1 としました。
showTree 関数内の toTokenKind にも Token.Title への対処を追加:
val toTokenKind: (Token)->String = { token->
when(token) {
is Token.Document-> "Document"
is Token.Title-> "Title"
is Token.AnyChar-> "AnyChar"
is Token.Para-> "Para"
is Token.Bold-> "Bold"
}
}
title マークアップをパースするパーサーを生成する pTitle 関数:
val pTitle: ()->Parser = {
val regex = "^\\{title\\}(.*?)\\{/title\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Title(value)
}
pRegex(regex, f)
}
それでは、これらを使って該当の文字列をパースして AST にして、プレーンテキストとHTMLへ変換してみます。
val parser: Parser = many( pTitle() or pPara() or pBold() or pAnyChar() )
val text = "{title}Example:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}"
val tree = buildTree(parser, text)
val plainText = toPlainText(tree)
val html = toHtml(tree)
showTree(tree)
println(plainText)
println(html)
実行してみます。
$ kotlin main.kts
- (Document)
- (Title)
- (AnyChar)Example:
- (AnyChar)
- (Para)
- (AnyChar)The quick brown
- (Bold)
- (AnyChar)fox
- (AnyChar) jumps over the lazy
- (Bold)
- (AnyChar)dog
- (AnyChar).
Example: The quick brown fox jumps over the lazy dog.
<body><h1>Example:</h1> <p>The quick brown <b>fox</b> jumps over the lazy <b>dog</b>.</p></body>
意図通り変換できました。
さらに長い別の文字列を変換してみます。
{title}Example-1:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}{title}Example-2:{/title} {p}Pack my box with {b}five{/b} dozen liquor jugs.{/p}
実行すると次のようになりました。
$ kotlin main.kts
- (Document)
- (Title)
- (AnyChar)Example-1:
- (AnyChar)
- (Para)
- (AnyChar)The quick brown
- (Bold)
- (AnyChar)fox
- (AnyChar) jumps over the lazy
- (Bold)
- (AnyChar)dog
- (AnyChar).
- (Title)
- (AnyChar)Example-2:
- (AnyChar)
- (Para)
- (AnyChar)Pack my box with
- (Bold)
- (AnyChar)five
- (AnyChar) dozen liquor jugs.
Example-1: The quick brown fox jumps over the lazy dog.Example-2: Pack my box with five dozen liquor jugs.
<body><h1>Example-1:</h1> <p>The quick brown <b>fox</b> jumps over the lazy <b>dog</b>.</p><h1>Example-2:</h1> <p>Pack my box with <b>five</b> dozen liquor jugs.</p></body>
意図通り変換できているようです。
最後に完成したコードを掲載します。
import kotlin.text.Regex
import kotlin.text.MatchResult
sealed class Tree(open val token: Token) {
data class Node(override val token: Token, val children: List<Tree>): Tree(token)
data class Leaf(override val token: Token): Tree(token)
}
sealed class Token(open val value: String) {
data class AnyChar(override val value: String): Token(value)
data class Bold(override val value: String): Token(value)
data class Para(override val value: String): Token(value)
data class Document(override val value: String): Token(value)
data class Title(override val value: String): Token(value)
}
data class ParseResult(val ok: Boolean, val tokens: List<Token>, val next: String)
typealias Parser = (String, List<Token>)->ParseResult
typealias ToToken = (MatchResult)->Token
val toNGParseResult: (String)->ParseResult = { next->
ParseResult(false, listOf(), next)
}
val concatAnyCharTokens: (List<Token>)->List<Token> = { tokens->
val initialValue = mutableListOf<Token>()
val f: (MutableList<Token>, Token)-> MutableList<Token> = { acc, token->
val isAnyCharToken: (Token)->Boolean = { (it is Token.AnyChar) }
if(acc.size>0 && isAnyCharToken(token) && isAnyCharToken(acc[acc.size-1])){
val lastToken = acc[acc.size-1]
acc[acc.size-1] = Token.AnyChar("${lastToken.value}${token.value}")
acc
} else {
acc.add(token)
acc
}
}
tokens.fold(initialValue, f)
}
infix fun Parser.and(parser1: Parser): Parser {
val parser0 = this
return { text, tokens->
val parseResult0 = parser0(text, tokens)
if( parseResult0.ok ){
val parseResult1 = parser1(parseResult0.next, parseResult0.tokens)
if( parseResult1.ok ){
ParseResult(true, concatAnyCharTokens(parseResult1.tokens), parseResult1.next)
} else {
toNGParseResult(text)
}
} else {
toNGParseResult(text)
}
}
}
infix fun Parser.or(parser1: Parser): Parser {
val parser0 = this
return { text, tokens->
val parseResult0 = parser0(text, tokens)
val parseResult1 = parser1(text, tokens)
if( parseResult0.ok ){
parseResult0
} else if( parseResult1.ok ){
parseResult1
} else {
toNGParseResult(text)
}
}
}
fun many(parser: Parser): Parser {
return { text, tokens->
val parseResult = parser(text, tokens)
if( !parseResult.ok ){
ParseResult(true, concatAnyCharTokens(tokens), text)
} else {
many(parser)(parseResult.next, parseResult.tokens)
}
}
}
val pAnyChar: ()->Parser = {
{ text, tokens->
if( text.length>0 ){
val headChar = text[0]
ParseResult(
true,
concatAnyCharTokens(tokens + listOf(Token.AnyChar(headChar.toString()))),
text.substring(1))
} else {
toNGParseResult(text)
}
}
}
val pRegex: (Regex, ToToken)->Parser = { regex, toToken->
{ text, tokens->
val m = regex.find(text)
if( m!=null ){
ParseResult(
true,
concatAnyCharTokens(tokens + listOf(toToken(m))),
text.substring( m.groupValues[0].length ))
} else {
toNGParseResult(text)
}
}
}
val pBold: ()->Parser = {
val regex = "^\\{b\\}(.*?)\\{/b\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Bold(value)
}
pRegex(regex, f)
}
val pPara: ()->Parser = {
val regex = "^\\{p\\}(.*?)\\{/p\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Para(value)
}
pRegex(regex, f)
}
val pTitle: ()->Parser = {
val regex = "^\\{title\\}(.*?)\\{/title\\}".toRegex()
val f: ToToken = { m->
val value = m.groupValues[1]
Token.Title(value)
}
pRegex(regex, f)
}
val buildTree: (Parser, String)->Tree = { parser, text->
fun f(p: Parser, token: Token): Tree {
val parseResult = p(token.value, listOf())
return if( parseResult.ok ){
if( isStopRecursion(p, token) ){
Tree.Leaf(token)
} else {
Tree.Node(token, parseResult.tokens.map { f(p, it) })
}
} else {
Tree.Leaf(token)
}
}
f(parser, Token.Document(text))
}
val showTree: (Tree)->Unit = { tree->
val indent: (Int)->String = { l-> 0.until(l).map { " " }.joinToString("") }
val toTokenKind: (Token)->String = { token->
when(token) {
is Token.Document-> "Document"
is Token.Title-> "Title"
is Token.AnyChar-> "AnyChar"
is Token.Para-> "Para"
is Token.Bold-> "Bold"
}
}
fun f(acc: List<String>, t: Tree, l: Int): List<String> {
val tokenKind = toTokenKind(t.token)
val value = if(t.token is Token.AnyChar) {
"${indent(l)}- ($tokenKind)${t.token.value}"
} else {
"${indent(l)}- ($tokenKind)"
}
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree->
f(acc0, childTree, l+1)
})
}
}
}
val initialValue = listOf<String>()
val initialIndentValue = 0
val list = f(initialValue, tree, initialIndentValue)
println( list.joinToString(System.getProperty("line.separator")) )
}
val toPlainText: (Tree)->String = { tree->
fun f(acc: List<String>, t: Tree): List<String> {
val value = if(t.token is Token.AnyChar) { t.token.value } else { "" }
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) })
}
}
}
val initialValue = listOf<String>()
f(initialValue, tree).joinToString("")
}
val toHtml: (Tree)->String = { tree->
val toHtmlStartTag: (Token)->String = { token->
when(token) {
is Token.Document-> "<body>"
is Token.Title-> "<h1>"
is Token.Para-> "<p>"
is Token.Bold-> "<b>"
is Token.AnyChar-> ""
}
}
val toHtmlStopTag: (Token)->String = { token->
when(token) {
is Token.Document-> "</body>"
is Token.Title-> "</h1>"
is Token.Para-> "</p>"
is Token.Bold-> "</b>"
is Token.AnyChar-> ""
}
}
fun f(acc: List<String>, t: Tree): List<String> {
val value = if(t.token is Token.AnyChar) { t.token.value } else { toHtmlStartTag(t.token) }
val newAcc = acc + listOf(value)
return when( t ){
is Tree.Leaf -> { newAcc }
is Tree.Node -> {
t.children.fold(newAcc, { acc0, childTree-> f(acc0, childTree) }) + toHtmlStopTag(t.token)
}
}
}
val initialValue = listOf<String>()
f(initialValue, tree).joinToString("")
}
val isStopRecursion: (Parser, Token)->Boolean = { p, token->
if( !(token is Token.AnyChar) ){
false
} else {
val text = token.value
val parseResult = p(text, listOf())
if( parseResult.ok ){
val tokens = parseResult.tokens
( tokens.size==1 && tokens.first() is Token.AnyChar )
} else {
true
}
}
}
val parser: Parser = many( pTitle() or pPara() or pBold() or pAnyChar() )
//val text = "{p}Hello, {b}World{/b}!{/p}"
//val text = "{title}Example:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}"
val text = "{title}Example-1:{/title} {p}The quick brown {b}fox{/b} jumps over the lazy {b}dog{/b}.{/p}{title}Example-2:{/title} {p}Pack my box with {b}five{/b} dozen liquor jugs.{/p}"
val tree = buildTree(parser, text)
showTree(tree)
val plainText = toPlainText(tree)
println(plainText)
val html = toHtml(tree)
println(html)