使用Kotlin与better-parse实现的算术解析器解析失败求助

我用Kotlin结合better-parse实现了简易算术表达式解析器，代码如下：

object CalcGrammar: Grammar<Int>() {
    val num by regexToken("""\d+""")
    val pls by literalToken("+")
    val min by literalToken("-")
    val mul by literalToken("*")
    val div by literalToken("/")
    val lpr by literalToken("(")
    val rpr by literalToken(")")
    val wsp by regexToken("\\s+", ignore = true)

    // expr ::= term + expr | term - expr | term
    // term ::= fact * term | fact / term | fact
    // fact ::= (expr) | -fact | int

    val fact: Parser<Int> by
        skip(lpr) and parser(::expr) and skip(rpr) or
        (skip(min) and parser(::fact) map { -it }) or
        (num map { it.text.toInt() })
    val term by
        leftAssociative(fact, mul) { a, _, b -> a * b } or
        leftAssociative(fact, div) { a, _, b -> a / b } or
        fact
    val expr by
        leftAssociative(term, pls) { a, _, b -> a + b } or
        leftAssociative(term, min) { a, _, b -> a - b } or
        term

    override val rootParser by expr
}

解析表达式-2 + 4 - 5 + 6时抛出ParseException：

Could not parse input: UnparsedRemainder(startsWith=min@8 for "-" at 7 (1:8))

错误原因 #

问题出在expr的定义逻辑上：

• 你把加法和减法拆成了两个独立的leftAssociative解析器，再加上单个term的选项
• 当解析-2 + 4时，第一个leftAssociative(term, pls)会匹配成功，得到结果2，但剩余的-5 + 6无法被后续解析：
  • 剩余的-5是一个term，但此时解析器期望的是expr的选项，而leftAssociative(term, min)要求左侧是term，但当前已解析的结果是一个完整的expr（值为2），无法和-5匹配成term - term结构；单个term选项也无法处理后续的+6，最终导致剩余内容未被解析。

简单来说，这种拆分方式无法支持连续混合加减的表达式，因为加减属于同优先级、左结合的运算符，应该被统一处理。

解决方法 #

将加法和减法合并到同一个leftAssociative解析器中，用oneOf匹配两种运算符，然后根据运算符类型执行对应的计算：

同时，为了保持一致性，term部分也应该用同样的方式合并乘除的解析，避免类似的连续乘除解析问题。

完整修正后的代码 #

object CalcGrammar: Grammar<Int>() {
    val num by regexToken("""\d+""")
    val pls by literalToken("+")
    val min by literalToken("-")
    val mul by literalToken("*")
    val div by literalToken("/")
    val lpr by literalToken("(")
    val rpr by literalToken(")")
    val wsp by regexToken("\\s+", ignore = true)

    // expr ::= term ( ( "+" | "-" ) term )*
    // term ::= fact ( ( "*" | "/" ) fact )*
    // fact ::= (expr) | -fact | int

    val fact: Parser<Int> by
        skip(lpr) and parser(::expr) and skip(rpr) or
        (skip(min) and parser(::fact) map { -it }) or
        (num map { it.text.toInt() })
        
    val term by leftAssociative(fact, oneOf(mul, div)) { a, op, b ->
        when (op.type) {
            mul -> a * b
            div -> a / b
            else -> error("Unexpected operator: ${op.type}")
        }
    }
    
    val expr by leftAssociative(term, oneOf(pls, min)) { a, op, b ->
        when (op.type) {
            pls -> a + b
            min -> a - b
            else -> error("Unexpected operator: ${op.type}")
        }
    }

    override val rootParser by expr
}

这样修改后，解析器就能正确处理-2 + 4 - 5 + 6这类连续混合加减的表达式，同时也支持连续乘除的场景，完全符合算术表达式的优先级和结合性规则。

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