4

私は楽しみのためにGLRを書いています（前回の試行以来、いくつかのことを理解したためです）。パーサーは現在機能しており、曖昧性解消ルールを実装しています。私はうまくいくように見える方法で優先順位を処理しています。今、私は結合性に関して少し途方に暮れています。

私はこのような文法を持っているとしましょう：

E <- E '+' E (rule 1)
E <- E '-' E (rule 2)
E <- '0'     (rule 3)
E <- '1'     (rule 4)

ルール1）と2）の優先順位が同じで、結合性が残っている場合。

結合性の処理がない場合、文字列「1-1+0」は2つの解析ツリーを生成します。

   1                2
  / \              / \
 /   \            /   \
2     3          4     1
|  \                   | \
4   4                  4  3

ここで、数字は削減に使用されるルールを示します。正しい解析ツリーは最初のものであるため、これだけを保持したいと思います。

結合法則の侵害をアルゴリズムで効率的に検出する方法を考えています。

私が試したアプローチの1つは、最初のツリーの最上位ノードで、ルール2がルール1の子のリストのルール3の左側にあるのに対し、2番目のツリーではルール1がルール4の右側にあることを確認することでした。 2と1は左結合です。最初のツリーのみを保持します。

しかし、これは、より複雑な例ではそれほど遠くはありませんでした。このソリューションの制限は、別のツリーとの比較に基づいてのみツリーを破棄できることです。

このアプローチの洗練されたバージョンを使用して解決策を見つけることができると思いますか？標準的な方法は何ですか？

4

2 に答える 2

0

私の意見では、これは文法規則に統合し、あいまいさを完全に解決することによって最もよく表現されます。

E <- F
E <- E '+' F
E <- E '-' F
F <- '0'
F <- '1'

（G）LRに設定されているので、左結合性と右結合性を等しくうまく表現できるはずです。ユニットの派生による解析ツリーの深さの増加は、それらを適切に後処理することで対処できます。

これにより、新しいメカニズムの発明が完全に回避され、とにかく使用されるBNFの表現力が活用されます。代わりにあいまいな表記を支持するための強力な議論と、解決方法の個別の仕様が必要だと思います。

XQuery言語仕様は、その定義プロセス中に、曖昧さ回避ルールを追加したあいまいなEBNFの使用（2002年4月30日ドラフトを参照）から、優先順位と関連性を組み込んだ曖昧さのないルールを優先して後者を削除する（2002年8月16日ドラフトを参照）に進化しました。実装者として、私は非常に感謝しています-それは私の人生を楽にしてくれました。

于 2012-08-08T19:29:24.777 に答える
0

これをアルゴリズム的に行うには、2 つのグループを作成します。ルール 3 と 4 を含む SIMPLE と、ルール 1 と 2 を含む COMPLEX です。(COMPLEX) (サブ) ルートの右端の子が COMPLEX の場合、このツリーは (部分的に) 右結合。

于 2012-09-01T21:42:22.683 に答える