Scala PackratParsers(解析器组合子)和左结合性

Question

我使用的是Scala的PackratParsers（解析器组合子），它具有以下形式的左递归语法

lazy val expr: PackratParser[Expr] = (
    ...
  | expr ~ (":" ~ expr).+ ^^ {
      case expr ~ rest => (expr /: rest)(combineBinary)
    }
  | ...
)
def combineBinary(acc: Expr, next: String ~ Expr) = next match {
  case op ~ expr => FunctionCall(op, acc, expr)
}

我希望二进制运算符"："保持关联性，以便形式为x1:x2:...:xn的表达式将被解析为(((x1:x2):x3):...:xn)，即导致形式为FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...)的AST。

令人惊讶的是，使用上面定义的PackratParsers语法，得到的AST仍然是正确关联的。为什么会出现这种情况，可以做些什么来改变这种情况？

我发现了这个关于Scala解析器组合子和运算符关联性的讨论，但它似乎并没有回答我的问题。

Answer 1

tl；博士我不知道packrat怎么能把你从两个大问题中拯救出来。它确实救了我一命，但我并没有如此明目张胆地左回避。

我的意思是，您的递归expr + expr永远不应该终止。我知道你在某个地方有一些归纳的基础，即expr = expr + expr | term。

现在，您可以很容易地通过term + expr | term为右关联性创建右关联性，因为当找到最后一个项时，您正处于+递归之下。类似地，将左关联性设为expr + term | term。左联想导致左递归，并且永远不会到达最后一项。即使是packrat也不会从中拯救。我不明白你是如何得到结果的。矿山

object EP extends JavaTokenParsers with PackratParsers {
    def expr: Parser[_] = expr ~ ("+" ~> expr) | ident /*^^ {
          case ident ~ rest => (ident /: rest){case (acc, e) => acc + s" + (${e.toString})"}
    } | ident*/
}
List("a", "a + b", "a + b + c+ d") foreach {input => 
    println("left: " +  EP.parseAll(EP.expr, input))
}

堆栈溢出。它救了我一次，但我没有如此明目张胆地左回避。而且，我不知道这怎么能把你从你问的第二个问题中拯救出来。

无论如何，您必须消除将expr + term | term更改为的递归

def left: Parser[_] = ident ~ appendix 
def appendix = "+" ~> left | ""

但这又是正确的递归，因为我们再次看到ident是第一个节点。

---

解决方案：因此，只需使用所有人所做的：使用rep解析器，它为您提供了一个列表，可以从左边迭代：

def right: Parser[_] = ident ~ ("+" ~> right) ^^ {case head ~ tail => s"Right($head, $tail)"} | ident 
lazy val left: Parser[_] = ident ~ rep("+" ~> ident) ^^ 
    {case head ~ tail => (head /: tail){case (acc, expr) => s"Left($acc, $expr)"}}
println("right => " + parseAll(right, "a + b + c+ d"))
println("left => " + parseAll(left, "a + b + c+ d"))

产生

right => [1.13] parsed: Right(a, Right(b, Right(c, d)))
left => [1.13] parsed: Left(Left(Left(a, b), c), d)