斯卡拉PackratParsers（解析器组合）和左结合

我使用Scala的PackratParsers（解析器组合）具有以下形式的左递归语法斯卡拉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仍然是右结合。为什么会出现这种情况，并且可以采取哪些措施来改变这种情况

我发现了大约斯卡拉解析器组合和运营商关联this讨论，但它似乎并没有给这里回答我的问题。

来源

2015-12-06 Martin Studer

我处理了同样的问题，但是我能够使用[this pdf]（http： /www.scala-archive.org/attachment/1956909/0/packrat_parsers.pdf）。页面21有一个很好的例子来构建。 –

tl; dr 我不知道packrat是如何帮你解决两个大问题的。 It did save me from stackoverflow但我没有这样公然的左倾。

我的意思是，你的递归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)) 
}

堆栈溢出。 It saved me once但我没有这样的公然左倾。而且，我不知道你怎么能从你提出的第二个问题中解救你。

不管怎样，你必须消除递归改变expr + term | term到

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

不过，无论这同样是正确的递归，因为我们看到的ident是第一个节点一次。

解决方案：你因此只需用什么所有人都：从左边使用rep分析器，它为您提供了一个列表，迭代：

产生

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

来源

2015-12-30 23:34:18

你必须使用懒惰丘壑与PackratParsers代替DEFS - 那么左递归是没有问题的本身 –

@MartinStuder它仍然是我的问题。 '对象EP延伸JavaTokenParsers与PackratParsers { \t \t懒惰VAL EXPR：解析器[_] = EXPR〜（ “+” 〜>表达式）| ident \t}; \t println（“left：”+ EP.parseAll（EP。expr，“a + b + c + d”））'溢出堆栈，我看不到哪里可以替换更多的defs到val。 –

我想你还需要PackratReader ... –

斯卡拉PackratParsers（解析器组合）和左结合

回答

相关问题