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。