scala - 解析器组合器语法未产生正确的关联性

Question

我正在开发一个简单的表达式解析器，但是鉴于下面的解析器组合器声明，我似乎无法通过我的测试并且正确的关联树不断弹出。

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 的树。

上面的语法有什么问题？

Answer 1

我不使用 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 用有意义的分隔符重复。注意:分隔符是“+”和“*”等运算符，而不是空格或逗号。

参见:Functional Parsers在第 7 节中查找 chainl 和 chainr 解析器。更多解析器组合器。

For example, an arithmetical expressions, where the operators that separate the subexpressions have to be part of the parse tree. For this case we will develop the functions chainr and chainl. These functions expect that the parser for the separators yields a function (!);

The function f should operate on an element and a list of tuples, each containing an operator and an element. For example, f(e0; [(1; e1); (2; e2); (3; e3)]) should return ((eo 1 e1) 2 e2) 3 e3. You may recognize a version of foldl in this (albeit an uncurried one), where a tuple (; y) from the list and intermediate result x are combined applying x y.

在语义解析器中需要一个fold 函数，即将句法解析器的标记转换为解析器输出的部分。在您的代码中，我相信是这一部分。

{case a~b => (a /: b)((acc,f) => f(acc))}

抱歉，我不能做得更好，因为我不使用 Scala。