【Gang of Four】Interpreter

#Interpreter
目次
このパターンは構造を理解するのに時間がかかりました。難しいですね。

構文木を生成するのが目的のパターンでしょうか。
本パターンは開始タグから終了タグまでのひとまとまりを、一つのオブジェクトで表現します。
Compositeパターンを用いて解析し、まとまりごとに処理を行う感じですね。

##目的
言語に対して、文法表現と、それを使用して文を解釈するインタプリタを一緒に定義する。

##構成要素
・AbstractExpression すべてのノードの抽象クラス
・TerminalExpression 終端を表現するクラス
・NonterminalExpression 終端以外を表現するクラス
・Context 文脈・状況
・Client 利用者

##実装
階層構造になっている四則演算用データを処理するサンプルプログラムを実装します。
<+> ~ +> 足し算
<-> ~ -> 引き算
<\*> ~ \*> 掛け算
> ~ /> 割り算

対象サンプルデータ.xml

<+>
    1 
    <-> 
        2 
        3 
        4 
        5 
        6 
        <*> 
            7 
            8 
        </*> 
        9 
    </->
    10 
    11 
    </> 
        12 
        4 
    <//> 
</+>

上記サンプルデータを見慣れた形へ整形すると1 + (2 - 3 - 4 - 5 - 6 - (7 * 8) - 9) + 10 + 11 + (12 / 4)となり、解-56が期待値です。

###AbstractExpression すべてのノードの抽象クラス

Expression.kt

package interpreter

interface Expression {
    enum class Operator(val startTag: String, val endTag: String) {
        Plus("<+>", "</+>"),
        Minus("<->", "</->"),
        Multiplication("<*>", "</*>"),
        Divide("</>", "<//>"),
    }
    fun interpret(context: Context): Int

    companion object {
        fun getExpression(token: String?): Expression? {
            return when (token) {
                Operator.Plus.startTag -> {
                    PlusNonterminalExpression()
                }
                Operator.Minus.startTag -> {
                    MinusNonterminalExpression()
                }
                Operator.Multiplication.startTag -> {
                    MultiplicationExpression()
                }
                Operator.Divide.startTag -> {
                    DivideExpression()
                }
                Operator.Plus.endTag,
                Operator.Minus.endTag,
                Operator.Multiplication.endTag,
                Operator.Divide.endTag -> {
                    null
                }
                else -> {
                    TerminalExpression()
                }
            }
        }
    }
}

###TerminalExpression 終端を表現するクラス
木の末端となる要素です。本サンプルデータでは数字がそれにあたります。

TerminalExpression.kt

package interpreter

class TerminalExpression: Expression {
    private var saveToken: String? = null

    override fun interpret(context: Context): Int {
        saveToken = context.token
        context.nextToken()
        return Integer.parseInt(saveToken ?: "0")
    }

    override fun toString(): String {
        return saveToken ?: "0"
    }
}

###NonterminalExpression 終端以外を表現するクラス
木が分岐する要素です。本サンプルデータでは<+>や<->がそれにあたります。

演算クラス

CalcExpression.kt

package interpreter

import java.util.ArrayList

abstract class CalcExpression: Expression {
    protected val numList = ArrayList<Int>()
    protected val list = ArrayList<Expression>()

    override fun interpret(context: Context): Int {
        context.nextToken()
        loop@ while (!context.isEnd) {
            val childExpressions = Expression.getExpression(context.token)
            if (childExpressions == null) {
                context.nextToken()
                break@loop
            } else {
                numList.add(childExpressions.interpret(context))
                list.add(childExpressions)
            }
        }
        return calc()
    }

    abstract fun calc(): Int
    abstract override fun toString(): String
}

足し算クラス

PlusNonterminalExpression.kt

package interpreter

/**
 * 足し算(<+> ~ </+>)
 */
class PlusNonterminalExpression: CalcExpression() {
    override fun calc(): Int {
        var result = numList.first().toInt()
        for (i in 1 until numList.size) {
            result += numList[i]
        }
        return result
    }

    override fun toString(): String {
        return "+$list"
    }
}

引き算クラス

MinusNonterminalExpression.kt

package interpreter

/**
 * 引き算(<-> ~ </->)
 */
class MinusNonterminalExpression: CalcExpression() {
    override fun calc(): Int {
        var result = numList.first().toInt()
        for (i in 1 until numList.size) {
            result -= numList[i]
        }
        return result
    }

    override fun toString(): String {
        return "-$list"
    }
}

掛け算クラス

MultiplicationExpression.kt

package interpreter

/**
 * 掛け算(<*> ~ </"*>)
 */
class MultiplicationExpression: CalcExpression() {
    override fun calc(): Int {
        var result = numList.first().toInt()
        for (i in 1 until numList.size) {
            result *= numList[i]
        }
        return result
    }

    override fun toString(): String {
        return "*$list"
    }
}

割り算クラス

DivideExpression.kt

package interpreter

class DivideExpression: CalcExpression() {
    override fun calc(): Int {
        var result = numList.first().toInt()
        for (i in 1 until numList.size) {
            result /= numList[i]
        }
        return result
    }

    override fun toString(): String {
        return "/$list"
    }
}

###Context 文脈・状況

Context.kt

package interpreter

import java.util.*

class Context(source: String) {
    private val tokens: StringTokenizer = StringTokenizer(source)
    var token: String? = null
        private set

    val isEnd: Boolean
        get() = !tokens.hasMoreElements()

    init {
        nextToken()
    }

    fun nextToken() {
        var token: String? = null
        if (!isEnd) {
            token = tokens.nextToken() // 標準の .nextToken() を呼び出す
        }
        this.token = token
    }
}

###Client 利用者

Main.kt

package interpreter

import interpreter.Expression.Companion.getExpression

fun main(args: Array<String>) {
    val source = "<+> 1 <-> 2 3 4 5 6 <*> 7 8 </*> 9 </-> 10 11 </> 12 4 <//> </+>"
    val context = Context(source)
    val expression = getExpression(context.token)

    println(expression?.interpret(context))
    println(expression.toString())
}

###出力結果

[out-put]
-56
+[1, -[2, 3, 4, 5, 6, *[7, 8], 9], 10, 11, /[12, 4]]

期待通りの式、解となりました。