5

shift-reduce 解析について学習しようとしています。ANSI C Yacc grammarに触発された、操作の順序を強制する再帰規則を使用する次の文法があるとします。

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

4

2 に答える 2

5

あなたが説明している問題は、LR(0)パーサーの作成に関する問題です。つまり、現在解析しているシンボルを超えてシンボルを先読みしないボトムアップパーサーです。あなたが説明したLR(0)文法は文法ではないようです。そのため、先読みなしで解析しようとすると問題が発生します。ただし、 のように見えるLR(1)ので、入力の 1 シンボル先を見ることで、シフトするか削減するかを簡単に判断できます。この場合、LR(1)パーサーは、スタックに があったときに先読み1し、次のシンボルが であることを確認し、+過去を還元してはならないことを認識しますA(還元できる唯一のものであり、依然として a に一致するため)ルール+は 2 番目の位置にあります)。

文法の興味深い特性LRは、 を対象とする任意の文法LR(k)について、同等k>1の文法を構築できることです。LR(1)ただし、同じことがすべてに及ぶわけではありませんLR(0)- に変換できない多くの文法がありますLR(0)。

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

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

于 2010-04-13T03:50:24.643 に答える
1

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

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

于 2010-04-13T04:11:51.473 に答える