解析器组合子文法不能产生正确的结合性

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

使用"+“~ EXPR似乎使答案不正确。相反，这应该是一个因素。

Answer 2

我不使用Scala，但使用F#解析器组合器，也需要与infix操作符结合。虽然我确信您可以做5-4或2+3，但问题的顺序是两个或多个相同优先级和运算符的操作符，即5-4-2或2+3+5。问题不会以加法形式出现，如(2+3)+5 = 2+(3+5)，但如您所知(5-4)-2 <> 5-(4-2)。

参见：一元Parser组合器 4.3用有意义的分隔符重复。注意:分隔符是诸如"+“和"*”之类的运算符，而不是空格或逗号。

参见：函数解析器在第7节中查找chainl和chainr解析器。更多解析器组合子。

例如，一个算术表达式，其中分隔子表达式的操作符必须是解析树的一部分。对于这种情况，我们将开发函数chainr和chainl。这些函数期望分隔符的解析器产生一个函数(!)； 函数f应该操作一个元素和一个元组列表，每个元组都包含一个运算符和一个元素。例如，f(e0；(1；e1)；(2；e2)；(3；e3))应该返回((eo 1 e1) 2 e2) 3 e3。您可能会在这个版本中(尽管是一个未处理的版本)识别折叠，其中应用x将列表中的元组(；y)和中间结果x组合在一起。

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

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

对不起，我不能做得更好，因为我不使用Scala。

Answer 3

"-" ~ EXPR ^^ {case "-" ~ b => Diff(_, b)}

对于5-4-3，它扩展到

Diff(5, 4-3)

这就是

Diff(5, Diff(4, 3))

然而，你需要的是：

Diff(Diff(5, 4), 3))

// for 5 + 4 - 3 it should be

Diff(Sum(5, 4), 3)

你需要牵涉到堆栈。