1

だから私はScalaのパーサーを使って電卓を書こうとしてきましたが、演算子の結合性が逆方向であり、文法を左再帰にしようとすると、完全に明確であるにもかかわらず、次のようになります。スタックオーバーフロー。

明確にするために、次のようなルールがある場合：def extract：Parser [Int] = num〜 "-" 〜add {x => x._1._1 --x._2}次に、7-4-3を評価すると次のようになります。 0ではなく6。

私が実際にこれを実装した方法は、演算子が非リーフノードであり、リーフノードが数値である二分木を構成しているということです。私がツリーを評価する方法は、左の子（オペレーター）の右の子です。7-4-5のツリーを構築するとき、私がそれをどのように見せたいかは次のとおりです。

-
-   5
7   4   NULL   NULL

ここで、-はルート、その子は-と5、2番目の-の子は7と4です。

しかし、私が簡単に構築できる唯一のツリーは

-
7   -
NULL   NULL   4   5

これは違いますが、私が望むものではありません。

基本的に、簡単な括弧は7-（4-5）ですが、私は（7-4）-5が必要です。

どうすればこれをハックできますか？演算子の優先順位に関係なく、正しい演算子の優先順位で計算機を作成できるはずだと感じています。最初にすべてをトークン化してから、トークンを逆にする必要がありますか？右の子の左の子をすべて取り、右の子の親の右の子にし、親を元の右の子の左の子にすることで、ツリーを反転させても大丈夫ですか？一見良いようですが、あまり深く考えていません。足りないケースがあるに違いない気がします。

私の印象では、LLパーサーはスカラパーサーでしか作成できません。別の方法を知っているなら、教えてください！

4

2 に答える 2

7

パーサー コンビネータ (トレイト) の Scala の標準実装は、Parsers左再帰文法をサポートしていません。ただし、PackratParsers左再帰が必要な場合は使用できます。とはいえ、文法が単純な算術式パーサーである場合、左再帰はほとんど必要ありません。

編集

右再帰を使用し、左結合性を維持する方法はいくつかあります。それに興味がある場合は、算術式と再帰降下パーサーを調べてください。そしてもちろん、私が言ったように、左再帰を許可する を使用できます。PackratParsers

しかし、使用せずに結合性を処理する最も簡単な方法PackratParsersは、再帰を使用しないことです。繰り返し演算子の 1 つを使用して , を取得しList、必要に応じてfoldLeftorを取得しfoldRightます。簡単な例:

trait Tree
case class Node(op: String, left: Tree, right: Tree) extends Tree
case class Leaf(value: Int) extends Tree

import scala.util.parsing.combinator.RegexParsers

object P extends RegexParsers {
  def expr = term ~ (("+" | "-") ~ term).* ^^ mkTree
  def term = "\\d+".r ^^ (_.toInt)
  def mkTree(input: Int ~ List[String ~ Int]): Tree = input match {
    case first ~ rest => ((Leaf(first): Tree) /: rest)(combine)
  }
  def combine(acc: Tree, next: String ~ Int) = next match {
    case op ~ y => Node(op, acc, Leaf(y))
  }
}

scala-distリポジトリで、他のより完全な例を見つけることができます。

于 2012-06-03T18:17:38.343 に答える
1

私はあなたの質問を次のように解釈しています。

のようなルールを記述def expression = number ~ "-" ~ expressionし、構文ツリーの各ノードで評価すると3 - 5 - 4、 では5 - 4が最初に計算され、結果として 1 が得られ、次に3 - 1が計算されて結果として 2 が得られることがわかります。

一方、 のようなルールを記述するdef expression = expression ~ "-" ~ numberと、ルールは左再帰的になり、スタックをオーバーフローします。

この問題には、次の 3 つの解決策があります。

  1. 抽象構文ツリーを後処理して、右連想ツリーから左連想ツリーに変換します。文法規則でアクションを使用して計算をすぐに実行している場合、これはうまくいきません。

  2. ルールを次のように定義しdef expression = repsep(number, "-")、計算を評価するときに、解析された数値 (フラット リストに表示されます) を、必要な結合性を提供する方向にループします。複数の種類の演算子が表示される場合、演算子が破棄されるため、これを使用することはできません。

  3. ルールを として定義しdef expression = number ~ ( "-" ~ number) *ます。必要な方向に処理するために、最初の番号と一連の演算子と番号のペアがフラット リストに含まれます (ただし、ここでは左から右の方がおそらく簡単です)。

  4. PackratParsersダニエル・ソブラルが提案したように使用してください。これはおそらく最良かつ最も簡単な選択です。

于 2012-06-04T00:35:48.423 に答える