4

私は、コンパイラの最終試験のサンプルから試みている質問にひどく行き詰まっています。誰かが説明を手伝ってくれれば本当にありがたいです。ありがとう

以下にリストされている文法 G を考えてみましょう

  1. S = E$
  2. E = E +T | T
  3. T = T *F | ふ
  4. F = ident| (え)

+ * ident ( ) は終端記号であり、ファイル$の終わりです。a) この文法は LR( 0 ) ですか? あなたの答えを正当化してください。b) 文法は SLR( 1 ) ですか? あなたの答えを正当化してください。c) この文法は LALR( 1 ) ですか? あなたの答えを正当化してください。

4

1 に答える 1

9

文法が LR(0) であることを示すことができれば、もちろんそれは SLR(1) と LALR(1) です。なぜなら、LR(0) はより制限的だからです。

残念ながら、文法は LR(0) ではありません。

たとえば、E: を認識したとします。

S -> E . $

後に続くものがor+記号*である場合、この E を S に還元してはなりません。E+*

S -> E . $
E -> E . + T
T -> T . * F

これには、その状態で何をすべきかを知るために 1 つのトークンを先読みする必要があります: シフト (+または*) または削減 ( $)。

SLR(1) は先読みを追加し、フォロー セット情報を使用して削減を行います (何もないよりはましですが、文法からグローバルに取得されるフォロー セット情報は、LALR( の状態固有の先読みセットのように) コンテキストに依存しません( 1))。

SLR(1) では、先読み記号が の後続セットにあり、 の後続セットにあるのは EOF 記号S -> Eだけである場合にのみ削減が考慮されるため、上記の競合は解消されます。入力記号がのように でない場合、リダクションは考慮されません。還元と矛盾しないシフトが起こります。SS$$+

SLR(1)したがって、文法はその矛盾のために失敗することはありません。ただし、他の競合が発生する可能性があります。ちらりと見ても、何も見えません。しかし、「その答えを正当化する」には、すべての LR(0) 状態アイテムを生成し、SLR(1) 制約が違反されていないことを確認するルーチンを実行する必要があります。(SLR(1) には単純な LR(0) 項目を使用します。これは、SLR(1) がこれらの項目を新しい方法で拡張しないためです。競合を排除するために、文法から盗まれた次のセットの情報を使用するだけであることを忘れないでください。)

SLR(1) の場合、LALR(1) はサブセットの関係に該当します。

アップデート

The Red Dragon Book ( Compilers: Principles, Techniques and Tools、Aho、Sethi、Ullman、1988年) では、正規の LR(0) アイテム セットと関連する DFA の導出を示す一連の例でまったく同じ文法を使用しています。解析テーブルに入力する手順の一部。これは、例 4.34 から始まるセクション 4.7 にあります。

于 2012-04-13T23:46:06.847 に答える