在Kotlin开发自定义编程语言：高效处理运算符的方法求助

问题背景 #

用Kotlin开发自定义编程语言时，手动处理运算符（如加法）的代码臃肿且扩展性差，无法支持PEMDAS运算优先级，也难以处理字符串与数字混合的表达式（例如var1 = "The sum is: " + someIntegerVariable - (5 + 10) / 5 * 20 + " !"）。

当前加法处理的冗余代码示例：

// inside the lexer
val additionPattern = Regex("""(\w+)\s*=\s*((?:\"[^\"]*\"|\d+|\w+)(?:\s*\+\s*(?:\"[^\"]*\"|\d+|\w+))*)""")

additionPattern.matchEntire(code)?.let {
        val varName = it.groups[1]!!.value
        val parts = it.groups[2]!!.value.split("+").map { it.trim() }
        return listOf("multi_addition", varName) + parts
    }
// inside the interpreter function
"multi_addition" -> {
            val varName = tokens[1]
            val parts = tokens.drop(2)
            if (parts[0].startsWith("\"")) {
                var result = parts[0].removeSurrounding("\"")
                var sum = 0
                var addingNumbers = false

                for (part in parts.drop(1)) {
                    when {
                        part.toDoubleOrNull() != null -> {
                            if (!addingNumbers) {
                                addingNumbers = true
                                sum = part.toInt()
                            } else {
                                sum += part.toInt()
                            }
                        }
                        variables.containsKey(part) -> {
                            when (val value = variables[part]) {
                                is InterpreterValue.NumberValue -> {
                                    if (!addingNumbers) {
                                        addingNumbers = true
                                        sum = value.value.toInt()
                                    } else {
                                        sum += value.value.toInt()
                                    }
                                }
                                is InterpreterValue.StringValue -> {
                                    if (addingNumbers) {
                                        result += sum.toString()
                                        addingNumbers = false
                                        sum = 0
                                    }
                                    result += value.value
                                }
                                else -> throw IllegalArgumentException("Invalid token in addition: '$part'")
                            }
                        }
                        part.startsWith("\"") -> {
                            if (addingNumbers) {
                                result += sum.toString()
                                addingNumbers = false
                                sum = 0
                            }
                            result += part.removeSurrounding("\"")
                        }
                        else -> throw IllegalArgumentException("Invalid token in addition: '$part'")
                    }
                }

                if (addingNumbers) {
                    result += sum.toString()
                }

                variables[varName] = InterpreterValue.StringValue(result)
            } else {
                var sum = 0.0
                for (part in parts) {
                    when {
                        part.toDoubleOrNull() != null -> sum += part.toDouble()
                        variables.containsKey(part) -> {
                            when (val value = variables[part]) {
                                is InterpreterValue.NumberValue -> sum += value.value
                                else -> throw IllegalArgumentException("Invalid token in numeric addition: '$part'")
                            }
                        }
                        else -> throw IllegalArgumentException("Invalid token in numeric addition: '$part'")
                    }
                }
                variables[varName] = InterpreterValue.NumberValue(sum)
            }
        }

优化思路 #

采用编译器标准流程替代手动正则匹配，实现可扩展的运算符处理：

• 词法分析器（Lexer）：将代码转换为标准化Token序列
• 语法分析器（Parser）：基于Token构建抽象语法树（AST），天然支持PEMDAS优先级
• 求值器（Evaluator）：递归遍历AST，统一处理不同类型的混合运算

具体实现 #

1. 定义Token类型 #

枚举所有需要的语法单元：

enum class TokenType {
    NUMBER, STRING, IDENTIFIER,
    PLUS, MINUS, MULTIPLY, DIVIDE,
    LPAREN, RPAREN, ASSIGN, EOF
}

data class Token(val type: TokenType, val value: String)

2. 实现词法分析器（Lexer） #

将输入代码拆解为Token序列：

class Lexer(private val input: String) {
    private var pos = 0
    private var currentChar: Char? = input.getOrNull(pos)

    fun nextToken(): Token {
        while (currentChar?.isWhitespace() == true) advance()

        return when (currentChar) {
            '+' -> advanceAndReturn(TokenType.PLUS)
            '-' -> advanceAndReturn(TokenType.MINUS)
            '*' -> advanceAndReturn(TokenType.MULTIPLY)
            '/' -> advanceAndReturn(TokenType.DIVIDE)
            '(' -> advanceAndReturn(TokenType.LPAREN)
            ')' -> advanceAndReturn(TokenType.RPAREN)
            '=' -> advanceAndReturn(TokenType.ASSIGN)
            '"' -> readString()
            in '0'..'9' -> readNumber()
            in 'a'..'z', in 'A'..'Z', '_' -> readIdentifier()
            null -> Token(TokenType.EOF, "")
            else -> throw IllegalArgumentException("Unexpected character: $currentChar")
        }
    }

    private fun advance() {
        pos++
        currentChar = input.getOrNull(pos)
    }

    private fun advanceAndReturn(type: TokenType): Token {
        val char = currentChar!!
        advance()
        return Token(type, char.toString())
    }

    private fun readString(): Token {
        advance() // 跳过左引号
        val startPos = pos
        while (currentChar != '"' && currentChar != null) advance()
        val value = input.substring(startPos, pos)
        advance() // 跳过右引号
        return Token(TokenType.STRING, value)
    }

    private fun readNumber(): Token {
        val startPos = pos
        while (currentChar in '0'..'9' || currentChar == '.') advance()
        val value = input.substring(startPos, pos)
        return Token(TokenType.NUMBER, value)
    }

    private fun readIdentifier(): Token {
        val startPos = pos
        while (currentChar in 'a'..'z' || currentChar in 'A'..'Z' || currentChar == '_' || currentChar in '0'..'9') advance()
        val value = input.substring(startPos, pos)
        return Token(TokenType.IDENTIFIER, value)
    }
}

3. 定义抽象语法树（AST）节点 #

用密封类表示不同类型的表达式：

sealed class Expr {
    data class Assign(val name: String, val value: Expr) : Expr()
    data class Binary(val left: Expr, val op: TokenType, val right: Expr) : Expr()
    data class NumberLiteral(val value: Double) : Expr()
    data class StringLiteral(val value: String) : Expr()
    data class Identifier(val name: String) : Expr()
}

4. 实现语法分析器（Parser） #

构建AST并处理PEMDAS优先级：

class Parser(private val lexer: Lexer) {
    private var currentToken = lexer.nextToken()

    fun parse(): Expr {
        val expr = parseAssignment()
        if (currentToken.type != TokenType.EOF) throw IllegalArgumentException("Unexpected token after expression")
        return expr
    }

    private fun parseAssignment(): Expr {
        val expr = parseExpression()
        if (currentToken.type == TokenType.ASSIGN) {
            eat(TokenType.ASSIGN)
            val right = parseExpression()
            if (expr !is Expr.Identifier) throw IllegalArgumentException("赋值左侧必须是标识符")
            return Expr.Assign(expr.name, right)
        }
        return expr
    }

    private fun parseExpression(): Expr {
        var expr = parseTerm()
        while (currentToken.type in listOf(TokenType.PLUS, TokenType.MINUS)) {
            val op = currentToken.type
            eat(currentToken.type)
            val term = parseTerm()
            expr = Expr.Binary(expr, op, term)
        }
        return expr
    }

    private fun parseTerm(): Expr {
        var expr = parseFactor()
        while (currentToken.type in listOf(TokenType.MULTIPLY, TokenType.DIVIDE)) {
            val op = currentToken.type
            eat(currentToken.type)
            val factor = parseFactor()
            expr = Expr.Binary(expr, op, factor)
        }
        return expr
    }

    private fun parseFactor(): Expr {
        return when (currentToken.type) {
            TokenType.NUMBER -> {
                val num = Expr.NumberLiteral(currentToken.value.toDouble())
                eat(TokenType.NUMBER)
                num
            }
            TokenType.STRING -> {
                val str = Expr.StringLiteral(currentToken.value)
                eat(TokenType.STRING)
                str
            }
            TokenType.IDENTIFIER -> {
                val id = Expr.Identifier(currentToken.value)
                eat(TokenType.IDENTIFIER)
                id
            }
            TokenType.LPAREN -> {
                eat(TokenType.LPAREN)
                val expr = parseExpression()
                eat(TokenType.RPAREN)
                expr
            }
            else -> throw IllegalArgumentException("Unexpected token: ${currentToken.type}")
        }
    }

    private fun eat(type: TokenType) {
        if (currentToken.type == type) {
            currentToken = lexer.nextToken()
        } else {
            throw IllegalArgumentException("Expected token $type but got ${currentToken.type}")
        }
    }
}

5. 实现求值器（Evaluator） #

递归求值AST，处理类型混合运算：

sealed class InterpreterValue {
    data class NumberValue(val value: Double) : InterpreterValue()
    data class StringValue(val value: String) : InterpreterValue()
}

class Evaluator(private val variables: MutableMap<String, InterpreterValue>) {
    fun evaluate(expr: Expr): InterpreterValue {
        return when (expr) {
            is Expr.Assign -> {
                val value = evaluate(expr.value)
                variables[expr.name] = value
                value
            }
            is Expr.Binary -> {
                val left = evaluate(expr.left)
                val right = evaluate(expr.right)
                when (expr.op) {
                    TokenType.PLUS -> handleAddition(left, right)
                    TokenType.MINUS -> handleSubtraction(left, right)
                    TokenType.MULTIPLY -> handleMultiplication(left, right)
                    TokenType.DIVIDE -> handleDivision(left, right)
                    else -> throw IllegalArgumentException("Unsupported binary operator: ${expr.op}")
                }
            }
            is Expr.NumberLiteral -> InterpreterValue.NumberValue(expr.value)
            is Expr.StringLiteral -> InterpreterValue.StringValue(expr.value)
            is Expr.Identifier -> variables[expr.name] ?: throw IllegalArgumentException("未定义变量: ${expr.name}")
        }
    }

    private fun handleAddition(left: InterpreterValue, right: InterpreterValue): InterpreterValue {
        return when (left) {
            is InterpreterValue.StringValue -> {
                val rightStr = when (right) {
                    is InterpreterValue.StringValue -> right.value
                    is InterpreterValue.NumberValue -> right.value.toString()
                }
                InterpreterValue.StringValue(left.value + rightStr)
            }
            is InterpreterValue.NumberValue -> {
                when (right) {
                    is InterpreterValue.NumberValue -> InterpreterValue.NumberValue(left.value + right.value)
                    is InterpreterValue.StringValue -> InterpreterValue.StringValue(left.value.toString() + right.value)
                }
            }
        }
    }

    private fun handleSubtraction(left: InterpreterValue, right: InterpreterValue): InterpreterValue {
        if (left is InterpreterValue.NumberValue && right is InterpreterValue.NumberValue) {
            return InterpreterValue.NumberValue(left.value - right.value)
        }
        throw IllegalArgumentException("减法仅支持数字类型")
    }

    private fun handleMultiplication(left: InterpreterValue, right: InterpreterValue): InterpreterValue {
        if (left is InterpreterValue.NumberValue && right is InterpreterValue.NumberValue) {
            return InterpreterValue.NumberValue(left.value * right.value)
        }
        throw IllegalArgumentException("乘法仅支持数字类型")
    }

    private fun handleDivision(left: InterpreterValue, right: InterpreterValue): InterpreterValue {
        if (left is InterpreterValue.NumberValue && right is InterpreterValue.NumberValue) {
            if (right.value == 0.0) throw ArithmeticException("除以零")
            return InterpreterValue.NumberValue(left.value / right.value)
        }
        throw IllegalArgumentException("除法仅支持数字类型")
    }
}

6. 使用示例 #

fun main() {
    val code = """var1 = "The sum is: " + someIntegerVariable - (5 + 10) / 5 * 20 + " !""""
    val lexer = Lexer(code)
    val parser = Parser(lexer)
    val ast = parser.parse()
    
    val variables = mutableMapOf("someIntegerVariable" to InterpreterValue.NumberValue(100.0))
    val evaluator = Evaluator(variables)
    val result = evaluator.evaluate(ast)
    
    println(result) // 输出 StringValue(value="The sum is: 100-60 !")
}

内容的提问来源于stack exchange，提问作者EndoBotM