SLR文法

SLR 文法は、Simple LR パーサーによって受け入れられる形式文法のクラスです。SLR 文法は、すべての LR(0) 文法のスーパーセットであり、すべての LALR(1) および LR(1) 文法のサブセットです。

SLR パーサーによって処理されると、SLR 文法は、LR(0) パーサー状態と予想される先読みシンボルの任意の組み合わせに対して、シフト/削減または削減/削減の競合のない解析テーブルに変換されます。文法が SLR でない場合、解析テーブルには、一部の状態と一部の先読みシンボルに対してシフト/削減の競合または削減/削減の競合があり、結果として拒否されたパーサーは決定論的ではなくなります。パーサーは、次にシフトするか削減するかを決定できず、2 つの候補削減のどちらかを決定できません。SLR パーサーは、Follow(A) 計算を使用して、完了したすべての非終端記号に対して予想される先読みシンボルを選択します。

LALR パーサーは異なる計算を使用し、同じパーサー状態に対してより小さく、よりタイトな先読みセットを生成することがあります。これらのより小さなセットは、状態のシフトアクションとの重複と、この同じ状態における他のリダクションの先読みとの重複を排除できます。SLR パーサーによって報告される重複の競合は、Follow(A) を使用した近似計算の結果であり、誤ったものになります。

曖昧な文法では、SLR を含むすべての LR 分析方法で、避けられないシフト/還元競合または還元/還元競合が発生します。コンピューター言語の文法が曖昧になる一般的な方法は、一部の非終端記号が左再帰と右再帰の両方である場合です。

式 → 式 * 値

式 → 値 + 式

式 → 値

SLR(1)オートマトンの状態にある形式B → y •のルールは、完全に展開されており、いかなるシフト遷移も受けることができないため、還元不可能または還元状態にあると言われます。この状態のルールには、RHS(右側)の右端にドット(•、現在の先読み位置)が配置されます。

SLR(1)オートマトンの 各状態sに対して、以下の条件のいずれも違反しない場合にのみ、文法はSLR(1)であると言われる。

1. 状態sにおける任意の簡約可能な規則A → a • Xb (ここでXは何らかの終端) に対して、同じ状態sにおいて、 B の追従集合に終端X が含まれるような、何らかの簡約不可能な規則B → a •が存在してはなりません。より正式には、終端X を含む集合とBの追従集合の共通部分は空でなければなりません。この規則に違反すると、シフト簡約競合が発生します。
2. s 内の任意の 2 つの完全な項目A → a •とB → b •について、Follow(A)とFollow(B)は互いに素です (それらの共通集合は空集合です)。この規則に違反すると、Reduce-Reduce Conflictが発生します。

次の単純なLRパーサアルゴリズムで曖昧さが生じない場合、その文法はSLR(1)であると言われる。

1. 状態s にA → a • Xbの形式の項目が含まれている場合( Xは終端記号、Xは入力文字列内の次のトークン)、アクションは現在の入力トークンをスタックにシフトすることになり、スタックにプッシュされる新しい状態は項目A → aX • b を含む状態になります。
2. 状態s に完全な項目A → y •が含まれ、入力文字列の次のトークンがFollow(A)にある場合、アクションは規則A → yによって還元することです。規則S' → Sによる還元( Sは開始状態) は受け入れと同等です。これは、次の入力トークンが$ の場合にのみ発生します。その他のすべての場合、新しい状態は次のように計算されます。文字列yとそれに対応するすべての状態を解析スタックから削除します。同様に、DFA でyの構築を開始した状態に戻ります。構築により、この状態には形式B → a • Abの項目が含まれている必要があります。 A をスタックにプッシュし、項目B → aA • b を含む状態をプッシュします。
3. 次の入力トークンが上記の 2 つのケースのどちらにも当てはまらない場合は、エラーが宣言されます。

• LR文法
• LL文法

• 「コンパイラ構築: 原則と実践」、Kenneth C. Louden 著。