我正在研究一个简单的表达式解析器，但是鉴于下面的解析器组合器声明，我似乎无法通过我的测试并且右关联树不断弹出。
def EXPR:Parser[E] = FACTOR ~ rep(SUM|MINUS) ^^ {case a~b => (a /: b)((acc,f) => f(acc))}
def SUM:Parser[E => E] = "+" ~ EXPR ^^ {case "+" ~ b => Sum(_, b)}
def MINUS:Parser[E => E] = "-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}
我一直在为此调试几个小时。我希望有人能帮我弄清楚它不正确。
"5-4-3" 将产生一个计算结果为 4 而不是预期的 -2 的树。
上面的语法有什么问题？
我不使用 Scala，但使用 F# 解析器组合器，并且还需要与中缀运算符的关联性。虽然我确信您可以执行 5-4 或 2+3，但问题在于具有相同优先级和运算符的两个或多个此类运算符的序列，即 5-4-2 或 2+3+5。如您所知，问题不会显示为 (2+3)+5 = 2+(3+5) 但 (5-4)-2 <> 5-(4-2) 。
请参阅：Monadic Parser Combinators 4.3 使用有意义的分隔符重复。注意：分隔符是“+”和“*”等运算符，而不是空格或逗号。
请参阅：函数式解析器 在第 7 节中查找 chainl 和 chainr 解析器。更多解析器组合器。
例如，算术表达式，其中分隔子表达式的运算符必须是分析树的一部分。对于这种情况，我们将开发函数chainr 和chainl。这些函数期望分隔符的解析器产生一个函数（！）；
函数 f 应该对一个元素和一个元组列表进行操作，每个元组都包含一个运算符和一个元素。例如， f(e0; [(1; e1); (2; e2); (3; e3)]) 应该返回 ((eo 1 e1) 2 e2) 3 e3。您可能会在其中识别出 foldl 的一个版本（尽管是一个未咖喱的版本），其中列表中的元组 (; y) 和中间结果 x 结合应用 x y。
您需要fold function在语义解析器中，即将标记从句法解析器转换为解析器输出的部分。在您的代码中，我相信这是这一部分。
{case a~b => (a /: b)((acc,f) => f(acc))}
对不起，我不能做得更好，因为我不使用 Scala。
"-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}
for 5-4-3, it expands to
Diff(5, 4-3)
which is
Diff(5, Diff(4, 3))
however, what you need is:
Diff(Diff(5, 4), 3))
// for 5 + 4 - 3 it should be
Diff(Sum(5, 4), 3)
you need to involve stack.
似乎使用“+”~ EXPR 使答案不正确。它应该是 FACTOR。