12

私は、変数を使用して式のパーサーを作成し、それらを二次式の形式に単純化しようとしています。

これは私のパーサー文法です:

Exercise : Expr '=' Expr
Expr : Term [+-] Expr | Term
Term : Factor [*/] Term | Factor
Factor: Atom [^] Factor | Atom
Atom: Number | Identified | [- sqrt] Atom | '(' Expr ')'

解析には、再帰降下パーサーを使用しています。これを解析したいとしましょう：

「2 - 1 + 1 = 0」

結果が 0 の場合、パーサーは間違ったツリーを作成します:

  -
 / \
2   +
   / \
  1   1

この文法を左結合にするにはどうすればよいですか? 私はこれが初心者です。より多くの情報を見つけることができるソースを教えてください。再帰降下パーサーでこれを達成できますか?

4

1 に答える 1

13

Theodore Norvell による Recursive Descent による Parsing Expressions をご覧ください。

そこで彼は、問題を解決するための 3 つの方法を示しています。
1.分流アルゴリズム。
2.文法を因数分解することによる古典的な解決策。
3.優先クライミング

あなたの問題は、文法にいくつかの変更が必要であるという事実から生じています。

Exrp: ターム { [+-] Expr} | 学期

一緒に解析する必要があり、それらが 0 個以上ある可能性があることを示す{ }aroundが追加されていることに注意してください。[+-] Expr

また、デフォルトでは、ツリーを次のように構築しています

  -
 / \
2   +
   / \
  1   1

すなわち-(2,+(1,1))

同じ優先順位の左結合演算子のツリーを構築する必要がある場合

     +
    / \
   -   1
  / \
 2   1

すなわち+(-(2,1),1)

この論文ではこれを行う 3 つの方法があるため、ここでは詳しく説明しません。また、あなたはこれに慣れていないので、論文を読んで遭遇する詳細を理解するために、優れたコンパイラブックを入手する必要があると述べています. これらの方法のほとんどは一般的なプログラミング言語で実装されており、インターネットで無料で入手できますが、多くの人があなたと同じことをして間違った結果を投稿していることに注意してください.

それが正しいかどうかを確認する最良の方法は、複数の減算操作を使用して、次のようなテストを行うことです。

7-3-2 = 2

あなたが取得する場合

7-3-2 = 6 またはその他

それは間違っています。

于 2013-12-02T13:22:21.533 に答える