2

我正在使用具有以下形式的左递归语法的 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)，即导致表单的 AST FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...)。

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

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

4

1 回答 1

1

tl; 博士，我不知道 Packrat 如何让您免于遇到的两个大问题。它确实将我从 stackoverflow 中解救了出来，但我并没有如此明目张胆的左顾右盼。

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

现在，您可以通过 for right associative 轻松建立右关联性，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)
于 2015-12-30T23:34:18.450 回答