0

次の文脈自由文法を見てみましょう。

G = ( {Sum, Product, Number}, {decimal representations of numbers, +, *}, P, Sum)

Pであること：

Sum → Sum + Product
Sum → Product
Product → Product * Number
Product → Number
Number → decimal representation of a number

この文法によって生成された式を、ボトムアップ パーサーと長さ 1 のルックアヘッド バッファー (LAB) を使用して解析しようとしています (おそらく、推測やバックトラッキングなしで行う必要があります)。

ここで、スタックと LAB が与えられた場合、スタックを削減する方法、またはスタックをまったく削減するか別のトークンをプッシュするかについて、いくつかの可能性がしばしばあります。

現在、私はこの決定木を使用しています：

スタックの上位 n 個のトークンと LAB がルールの右側の開始点である場合、次のトークンをスタックにプッシュします。

それ以外の場合は、スタックの一番上にあるトークンの最大数を減らします。つまり、一番上の項目を削減すると同時に、一番上の 3 つの項目を削減できる場合は、後者を行います。

そのような削減が不可能な場合は、別のトークンをスタックにプッシュします。

すすいで繰り返します。

これは (!) 動作するように見えますが、非常に多くのルール検索、一致するプレフィックスの検索などが必要です。これを O(NM) で実行することはできません。

削減するかプッシュ（シフト）するかを決定するための標準的な（そしておそらく賢明な）アプローチは何ですか？削減の場合は、どの削減を適用しますか？

コメントと回答をお寄せいただきありがとうございます。

4

1 に答える 1

1

あなたのような文法 (基本的には式文法) の最も簡単なボトムアップ解析アプローチは、演算子優先解析です。

ボトムアップ解析では、下から左から右に解析ツリーを構築する必要があることを思い出してください。言い換えれば、解析中の任意の時点で、読み取り中の右側に終端記号のみがあり、左側に終端記号と非終端記号の組み合わせ (「プレフィックス」) がある部分的に組み立てられたツリーがあります。 . 可能な縮小は、プレフィックスのサフィックスに適用されるものだけです。削減が適用されない場合は、端末を入力からプレフィックスにシフトできなければなりません。

演算子文法には、どのプロダクションでも非終端記号が 2 つ連続しないという特徴があります。したがって、演算子文法のボトムアップ解析では、接頭辞の最後の記号が終端記号であるか、最後から 2 番目の記号が終端記号です。(どちらもあり得ます。)

演算子の優先順位パーサーは、基本的に非終端記号を認識しません。それは単にそれらを区別しません。したがって、op-prec パーサーはこれら 2 つのプロダクションのどちらを適用するかを認識できないため、右側にまったく同じ端子シーケンスが含まれる 2 つのプロダクションを使用することはできません。(これは伝統的な見方です。非終端記号が異なる場所にある場合、同じ終端記号を持つ 2 つのプロダクションを持つことができるように、それを少し拡張することは実際には可能です。これにより-、単項演算子を持つ文法が可能になります。非終端記号の名前を知らなくても、それらの存在だけ<non-terminal> - <non-terminal>で- <non-terminal>区別できます。

もう 1 つの要件は、端末間に優先関係を構築できる必要があることです。より正確には、3 つの優先順位関係を定義します。これらは通常<·,·>と(またはテーマのタイポグラフィのバリエーション) で記述され、任意の 2 つの端子およびに対して、関係,との最大 1·=·つが真であると主張します。xyx ·> yx ·=· yx <· y

大雑把に言えば、リレーションの<と>はプロダクションのエッジに対応します。言い換えると、 の場合、最初のターミナルが であるプロダクションを持つ非ターミナルが続く可能性がx <· yあることを意味します。同様に、は、最後の終端が であるプロダクションで非終端記号に続くことができることを意味します。Andは、とがこの順序で連続する終端である右側がいくつかあることを意味します(おそらく非終端記号が介在します)。xyx ·> yyxx ·=· yxy

単一関係の制限が true の場合、次のように解析できます。

Letxはプレフィックスの最後の端末 (つまり、最後または最後から 2 番目の記号) であり、letyは先読み記号であり、端末でなければなりません。その場合x ·> yは、ルールを減らして繰り返します。yそれ以外の場合は、接頭辞に移行します。

削減するには、生産の開始点を見つける必要があります。リレーションを持つ端子が見つかるまで、接頭辞を逆方向に移動し、連続する端子 (すべての端子が<·or関係を持っている必要があります) を比較します。次に、と の間の端子は、探しているプロダクションの右側であり、示されているように、非端子を右側に挿入できます。·=·<·<··>

適切な生産があるという保証はありません。存在しない場合、解析は失敗します。しかし、入力が有効な文であり、文法が演算子優先文法である場合、削減する適切な生成を見つけることができます。

ほとんどのプロダクションには 1 つ ( <non-terminal> * <non-terminal>) または 2 つ ( ( <non-terminal> )) のターミナルしかないため、通常、プロダクションを見つけるのは非常に簡単です。素朴な実装では、端末を一緒に実行して文字列にし、それをハッシュテーブルのキーとして使用するだけかもしれません。

演算子優先解析の古典的な実装は、Edsger Dijkstra によって考案された、いわゆる「Shunting Yard Algorithm」です。そのアルゴリズムでは、左優先と右優先の 2 つの関数を提供することによって、優先順位関係がモデル化されます。これらの関数は、(他の演算子についても同様に)x <· y場合にのみ真となるように端末を整数にマップします。right-precedence(x) < left-precedence(y)そのようなマッピングを常に見つけることができるとは限らず、優先関係が適用されない端末のペアが存在することがよくあるため、マッピングは実際の優先関係を覆い隠しています。それにもかかわらず、これらのマッピングが見つかることがよくあり、ほとんどの場合、単純な式の文法に当てはまります。

始めるにはこれで十分だと思います。ボトムアップ解析に関するいくつかのテキストを実際に読むことをお勧めします。なぜなら、私はすでに SO の回答にはあまりにも多くのことを書きすぎており、まだ 1 行のコードも含めていないからです。:)

于 2013-09-14T04:58:42.727 に答える