Kotlinのパーサコンビネータ「better-parse」を使う

記念すべき一発目の記事はなるべく他で書かれていないようなことにしようと思い、
「そういえばbetter-parseについての日本語記事なかったなー」ということを思い出したのでこれについて紹介します。

better-parseとは

JetBrainsの中の人が作っているKotlinのパーサコンビネータです。
Kotlin/JS等で扱うことも出来ます。
github.com

なおパーサコンビネータに関しての説明は割愛しますが、kmizuさんのこちらの記事
qiita.com
の冒頭が非常にわかりやすいため、そちらをご覧ください。

簡単なパーサを作ってみる

それでは実際に簡単な文をパースしてみましょう。
今回はKotlin/JVMプロジェクトです。

まずbuild.gradleに追記しましょう。

repositories {
    mavenCentral()
    maven { setUrl("https://dl.bintray.com/hotkeytlt/maven") }
}

dependencies {
   implementation "com.github.h0tk3y.betterParse:better-parse-jvm:0.4.0-alpha-3"
}

今回は以下のようなif式を解釈してみましょう。

if(first()) {
  puts("First!")
} elsif(second()) {
  puts("Second!")
} else {
  puts("Other!")
}

この文を解釈してASTオブジェクトに変換してみたいと思います。

program           : expression*
expression        : primaryExpression
primaryExpression : ifExpression
                  | functionCall
                  | stringLiteral
ifExpression      : 'if' '(' expression ')' block ('elsif' '(' expression ')' block)* ('else' block)?
block             : '{' expression* '}'
functionCall      : IDENTIFIER '(' (expression (',' expression)*)? ')'
stringLiteral     : STRING_CONTENT
STRING_CONTENT    : "\".*?\""
IDENTIFIER        : "[a-zA-Z]\\w*"

一先ず定義としてはこんな感じで。少し雑ですが例ということでお許しください。
では実際に実装していきます。
まずASTオブジェクトを定義します。

sealed class AST

data class Program(val expressions: List<AST>)

data class Block(val expressions: List<AST>) : AST()

data class IfExpression(val cond: AST, val trueBody: AST, val elseBody: AST) : AST()
data class StringLiteral(val value: String) : AST()
data class FunctionCall(val name: String, val parameters: List<AST>) : AST()

パースした結果をこのオブジェクトに変えていきます。
それではパーサを実装していきましょう。

import com.github.h0tk3y.betterParse.combinators.*
import com.github.h0tk3y.betterParse.grammar.Grammar
import com.github.h0tk3y.betterParse.grammar.parser
import com.github.h0tk3y.betterParse.parser.Parser

object ExampleParser : Grammar<Program>() {
    private val LPAR by token("\\(")
    private val RPAR by token("\\)")

    private val LBRC by token("\\{")
    private val RBRC by token("}")

    private val IF by token("if\\b")
    private val ELSIF by token("elsif\\b")
    private val ELSE by token("else\\b")

    private val STRING_CONTENT by token("\".*?\"")
    private val IDENTIFIER by token("[a-zA-Z]\\w*")
    private val COMMA by token(",")

    private val WS by token("\\s+", ignore = true)

    private val stringLiteral by STRING_CONTENT use { StringLiteral(text.removeSurrounding("\"", "\"")) }

    private val block: Parser<AST> by -LBRC * zeroOrMore(parser { expression }) * -RBRC map { Block(it) }

    private val ifExpression by -IF * -LPAR * parser { expression } * -RPAR * block *
            zeroOrMore(-ELSIF * -LPAR * parser { expression } * -RPAR * block) *
            optional(-ELSE * block).map { it ?: Block(emptyList()) } map {
            (ifCond, ifBody, elif, elseBody) ->
        val elses = elif.foldRight(elseBody) { (elifCond, elifBody), el -> IfExpression(elifCond, elifBody, el) }
        IfExpression(ifCond, ifBody, elses)
    }

    private val functionCall by IDENTIFIER * -LPAR * separatedTerms(parser { expression }, COMMA, acceptZero = true) * -RPAR map {
            (name, args) ->
        FunctionCall(name.text, args)
    }

    private val primaryExpression by ifExpression or functionCall or stringLiteral
    private val expression: Parser<AST> by primaryExpression

    override val rootParser: Parser<Program> by zeroOrMore(expression) map { Program(it) }
}

気になりそうなところをいくつか見ていきましょう。

token

マッチさせたい文字列を定義します。もし定義にかかわらず、指定した文字列を無視したいのであればignore=trueとします。ここでは空白は無視するようにしています。

rootParser

ここを起点として構文を解析していきます。

zeroOrMore

そのままで、0回以上マッチすることを意味します。他に1以上を意味するoneOrMore、0か1回を意味するoptionalもあります。

map, use

左辺の構文を解析した結果を受け取って関数に渡します。useはマッチしたトークンの文字列を渡します。一つ前のパーサだけ関数を適応したい場合はA.map {}とします。

or

A or B とすることでAかBにマッチさせます。

*, (and)

A * B とすることでAの次にBのパーサを適応します。

parser { }

その時点では定義されていないパーサを参照するために使用します。

-, (skip)

マッチはさせたいが結果は捨てたい場合に使います。

separatedTerms(A, B, acceptZero)

Bを区切り文字としたAのチェーンを定義します。acceptZero=trueであれば何もマッチしなくても空のListを返します。

主要なものとしてはこんなところでしょうか。
それでは実際にこのパーサに先程のif式をパースさせてみましょう。

fun main() {
    val code = """
    if("hoge") {
        puts("hoge")
    }
    """.trimIndent()
    try {
        val result = ExampleParser.parseToEnd(code)
        println(result)
    } catch (e: ParseException) {
        e.printStackTrace()
    }
}

無事にASTオブジェクトに変換できていることが確認できると思います。