シフトリデュース:いつ削減をやめるべきか？

StackOverflow https://stackoverflow.com/questions/2626723

質問

私はshift-reduce解析について学ぼうとしています。次のような文法があり、操作の順序を強制する再帰的ルールを使用しているとします。 ANSI C Yacc 文法:

S: A;

P
    : NUMBER
    | '(' S ')'
    ;

M
    : P
    | M '*' P
    | M '/' P
    ;

A
    : M
    | A '+' M
    | A '-' M
    ;

そして、shift-reduce 解析を使用して 1+2 を解析したいと考えています。まず、1 が NUMBER としてシフトされます。私の質問は、それが P、次に M、次に A、そして最後に S に減らされるのかということです。どこで停止するかをどのようにして知るのでしょうか?

S まで減少し、その後「+」にシフトするとします。これで、以下を含むスタックが完成します。

S '+'

「2」をシフトすると、削減は次のようになります。

S '+' NUMBER
S '+' P
S '+' M
S '+' A
S '+' S

ここで、最後の行のどちらかの側で、S は P、M、A、または NUMBER の可能性がありますが、どの組み合わせでもテキストを正しく表現できるという意味では依然として有効です。パーサーはそれをどのように「認識」するのでしょうか

A '+' M

式全体を A に還元し、次に S に還元するにはどうすればよいでしょうか?言い換えれば、次のトークンをシフトする前に削減を停止することをどのようにして知ることができるのでしょうか?これは LR パーサー生成における重要な問題ですか?

編集： 質問への追加は次のとおりです.

ここで解析するとします 1+2*3. 。一部のシフト/リデュース操作は次のとおりです。

Stack    | Input | Operation
---------+-------+----------------------------------------------
         | 1+2*3 | 
NUMBER   | +2*3  | Shift
A        | +2*3  | Reduce (looking ahead, we know to stop at A)
A+       | 2*3   | Shift
A+NUMBER | *3    | Shift (looking ahead, we know to stop at M)
A+M      | *3    | Reduce (looking ahead, we know to stop at M)

これは正しいでしょうか (確かに、まだ完全には解析されていません)。さらに、1 シンボルによる先読みも削減しないように指示しますか? A+M に A, そうすると、読み取り後に避けられない構文エラーが発生するためです。 *3 ?

役に立ちましたか？

解決

あなたが説明している問題は、作成に関する問題です。 LR(0) パーサー - つまり、現在解析しているシンボル以降のシンボルの先読みを行わないボトムアップ パーサーです。あなたが説明した文法は正しい文法ではないようです LR(0) そのため、先読みせずに解析しようとすると問題が発生します。それ する そう見える LR(1), ただし、入力内で 1 シンボル先を調べることで、シフトするか削減するかを簡単に判断できます。この場合、 LR(1) パーサーは、 1 スタック上で、次のシンボルが +, 、そして過去を減らすべきではないことに気づきました A (これがルールに一致する唯一のものであるため、 + 2番目の位置にあります）。

興味深い性質 LR 文法とは、あらゆる文法のことです。 LR(k) のために k>1, を構築することが可能です。 LR(1) 同等の文法。ただし、同じことが下まで及ぶわけではありません。 LR(0) - 変換できない文法がたくさんあります LR(0).

詳細については、こちらを参照してください LR(k)-らしさ:

http://en.wikipedia.org/wiki/LR_parser

他のヒント

Yacc / Bison の解析アルゴリズムと、いつリダクションよりシフトを優先するのかは正確にはわかりませんが、Bison が LR(1) 解析をサポートしていることはわかっています。これは、先読みトークンがあることを意味します。これは、トークンがすぐにはスタックに渡されないことを意味します。むしろ、これ以上削減ができなくなるまで待つのです。次に、次のトークンをシフトすることが意味がある場合は、その操作が適用されます。

まず第一に、あなたの場合、1 + 2を評価している場合、1がシフトされます。「+」先読みトークンはそれが唯一の有効なコースであることを示すため、そのトークンは A に減らされます。これ以上のリダクションはないため、「+」トークンをスタックにシフトし、先読みとして 2 を保持します。A + M は A を生成し、式が完了するため、2 をシフトして M に減算します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top