Loading article…
コンピュータサイエンスにおいて、シンプルLRまたはSLRパーサーは、小さな解析テーブルと比較的単純なパーサー生成アルゴリズムを備えたLRパーサーの一種です。他のタイプのLR(1)パーサーと同様に、SLRパーサーは、推測やバックトラックなしで、入力ストリームを左から右に1回スキャンするだけで、正しいボトムアップ解析を1つ見つけるのに非常に効率的です。パーサーは、言語の形式文法から機械的に生成されます。
SLR と、より一般的な方法であるLALR パーサーおよびCanonical LR パーサーは、解析時に同一の方法と同様のテーブルを持ちます。これらは、パーサー ジェネレーター ツールで使用される数学的な文法解析アルゴリズムのみが異なります。SLR ジェネレーターと LALR ジェネレーターは、同一サイズと同一のパーサー状態のテーブルを作成します。SLR ジェネレーターは、yaccやBisonなどの LALR ジェネレーターよりも少ない文法を受け入れます。多くのコンピューター言語は、そのままでは SLR の制限に容易に適合しません。言語の自然な文法をSLR 文法形式に曲げるには、より多くの妥協と文法のハッキングが必要です。そのため、LALR ジェネレーターは、いくぶん複雑なツールであるにもかかわらず、SLR ジェネレーターよりもはるかに広く使用されるようになりました。SLR メソッドは、大学のコンパイラ理論の授業で有用な学習ステップであり続けています。
SLR と LALR はどちらも、ドナルド・クヌースの LR パーサー理論の最初の実用化としてフランク・デレマーによって開発されました。 [引用が必要] 完全な LR 方式によって実際の文法用に作成されたテーブルは非現実的に大きく、その 10 年間のほとんどのコンピュータ メモリよりも大きく、SLR および LALR 方式よりも 100 倍以上のパーサー状態がありました。[引用が必要]。
先読みセット
SLR と LALR の違いを理解するには、それらの多くの類似点と、両方がシフト削減の決定を行う方法を理解することが重要です。(その背景については、 LR パーサーの記事から削減の先読みセットのセクションまでを参照してください。)
SLR と LALR の唯一の違いは、何らかの完了した生成規則が見つかり、縮小されるたびに、ジェネレーターが次に出現する入力シンボルの先読みセットを計算する方法です。
SLR ジェネレータは、個々のパーサー状態と遷移の詳細は無視して、文法に直接基づく簡単な近似方法でその先読みを計算します。これは、現在のパーサー状態の特定のコンテキストを無視します。非終端記号Sが文法内の複数の場所で使用されている場合、SLR はそれらの場所を個別に処理するのではなく、同じ単一の方法で扱います。SLR ジェネレータは、 SFollow(S)の出現の直後に続くことができるすべての終端記号の集合を計算します。解析テーブルでは、Sへの各還元は、Follow(S) を LR(1) 先読み集合として使用します。このようなフォロー セットは、LL トップダウン パーサーのジェネレータによっても使用されます。フォロー セットを使用するときにシフト/還元または還元/還元の競合がない文法は、SLR 文法と呼ばれます。
LALR ジェネレータは、パーサーの状態とその遷移のグラフを調べることに基づいたより正確な方法で先読みセットを計算します。この方法では、現在のパーサーの状態の特定のコンテキストを考慮します。これは、非終端記号 S の各文法出現の処理をカスタマイズします。この計算の詳細については、 LALR パーサーの記事を参照してください。LALR ジェネレータによって計算される先読みセットは、SLR ジェネレータによって計算される近似セットのサブセットです (したがって、SLR ジェネレータによって計算される近似セットよりも優れています)。文法が SLR 後続セットを使用するときにテーブル競合を持ち、LALR 後続セットを使用するときに競合がない場合、その文法は LALR 文法と呼ばれます。
例
SLR パーサーでは解析できるが LR(0) パーサーでは解析できない文法は次のとおりです。
- （０）南→東
- （１）E→1E
- （２）E→1
LR(0)パーサーの場合と同じようにアクションとgotoテーブルを構築すると、次の項目セットとテーブルが生成されます。
- アイテムセット 0
- 南→東
- + E → • 1 E
- + E → • 1
- アイテムセット1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- アイテムセット2
- 南→東 •
- アイテムセット3
- E → 1 E •
アクションと goto テーブル:
ご覧のとおり、状態 1 とターミナル '1' にはシフト削減の競合があります。これは、LR(0) パーサーのアクション テーブルが作成されるときに、削減アクションが行ごとに挿入されるために発生します。ただし、フォロー セットを使用すると、削減アクションをより細かい粒度で追加できます。この文法のフォロー セットは次のとおりです。
特定のアクション列に削減を追加する必要があるのは、そのアクションがその削減に関連付けられたフォロー セット内にある場合のみです。このアルゴリズムは、削減アクションをアクション列に追加する必要があるかどうかを示します。
関数 mustBeAdded(reduceAction, アクション) {
ルール番号 = 削減アクションの値;
ルールシンボル = ルール[ルール番号].leftHandSide;
戻り値 (followSet(ruleSymbol) 内のアクション)
}
たとえば、mustBeAdded(r2, "1")は偽です。なぜなら、ルール 2 の左側は「E」であり、1 は E のフォロー セットに含まれていないmustBeAdded(r2, "$")からです。逆に、は真です。なぜなら、「$」は E のフォロー セットに含まれるからです。
アクション テーブル内の各 Reduce アクションで mustBeAdded を使用すると、競合のないアクション テーブルが生成されます。