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; dr packrat が、あなたが抱えている 2 つの大きな問題からどのように救えるのかわかりません。それは私をstackoverflowから救いましたが、そのような露骨な左の反省はありませんでした。

つまり、再帰expr + exprは決して終了してはなりません。どこかに誘導の基盤があることを理解していますexpr = expr + expr | term。

term + expr | term最後の項が見つかったときは + 再帰の奥深くにいるため、 for 右結合によって簡単に右結合を作成できます。同様に、左結合性を作成します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))
}

スタックオーバーフロー。それは私を一度救いましたが、私はそのような露骨な左の反省を持っていませんでした. そして、あなたが尋ねる2番目の問題からどのようにあなたを救うことができるかわかりません.

とにかく、次のように変更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 に答える