斯卡拉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（解析器組合）和左結合

回答

相關問題