algorithm - LR（0）とSLR解析の違いは何ですか？

Question

私はコンパイラの概念に取り組んでいますが、少し混乱しています...グーグルで明確な答えを得ることができませんでした。

SLRとLR（0）パーサーは同じですか？そうでない場合、違いは何ですか？

Answer 1

LR(0) パーサーと SLR(1) パーサーはどちらも、ボトムアップ、方向性、予測パーサーです。この意味は

• パーサーは、生成を逆に適用して、入力文を開始記号 (ボトムアップ)に戻そうとします。
• パーサーは入力を左から右にスキャンします ( directional )
• パーサーは、必ずしもすべての入力を確認することなく、どのリダクションを適用するかを予測しようとします ( predictive )

LR(0) と SLR(1) はどちらもシフト/リデュース パーサーです。つまり、入力ストリームのトークンをスタックに配置して処理し、各ポイントで、トークンをスタックにプッシュするか一部を削減することでトークンをシフトします。スタック上の端末と非端末のシーケンスは、何らかの非端末記号に戻ります。シフト/リデュース パーサーを使用して、任意の文法をボトムアップで解析できることを示すことができますが、そのパーサーはdeterministicではない可能性があります。つまり、パーサーは、シフトまたはリダクションを適用するかどうかを「推測」する必要があり、間違った選択をしたことに気付くために後戻りする必要がある場合があります。どれだけ強力な決定論的 shift/reduce パーサーを作成しても、すべての文法を解析できるわけではありません。

決定論的な shift/reduce パーサーを使用して、処理できない文法を解析すると、shift/reduce conflictsまたはreduce/reduce conflictsが発生し、パーサーが実行するアクションがわからない状態になる可能性があります。シフト/リデュースの競合では、別のシンボルをスタックに追加する必要があるのか​​、スタックの一番上のシンボルに対してリダクションを実行する必要があるのか​​を判断できません。リデュース/リデュースの競合では、パーサーはスタックのトップ シンボルを非終端記号に置き換える必要があることを認識していますが、どのリダクションを使用するかはわかりません。

これが長い説明である場合は申し訳ありませんが、LR(0) と SLR(1) の解析の違いに対処できるようにするためにこれが必要です。LR(0) パーサーは、取るべきアクション (したがって 0) を決定するために、先読みのゼロ トークンを使用するシフト/リデュース パーサーです。これは、パーサーのどの構成においても、パーサーが選択する明確なアクション (特定のシンボルをシフトするか、特定の削減を適用するか) を持たなければならないことを意味します。2 つ以上の選択肢がある場合、パーサーは失敗し、文法が LR(0) ではないと言います。

考えられる 2 つの LR 競合は、shift/reduce と reduce/reduce であることを思い出してください。どちらの場合でも、LR(0) オートマトンが実行できるアクションが少なくとも 2 つありますが、どちらを使用するかはわかりません。競合するアクションの少なくとも 1 つはリダクションであるため、パーサーが特定のリダクションをいつ実行するかについて、より注意を払うようにするのが妥当な攻撃方法です。より具体的には、パーサーが入力の次のトークンを調べて、シフトまたは削減する必要があるかどうかを判断できるとします。パーサーがそうすることが「理にかなっている」場合にのみ還元を許可する場合 (「理にかなっている」の定義について)、オートマトンにシフトまたは還元のいずれかを明確に選択させることで競合を排除できる場合があります。特定のステップ。

SLR(1) (「簡略化された LR(1)」) では、パーサーは、シフトするか縮小するかを決定する際に、先読みの 1 つのトークンを調べることができます。特に、パーサーが A → w の形式 (非終端記号 A と文字列 w) の何かを削減しようとする場合、入力の次のトークンを調べます。そのトークンが何らかの派生で非終端記号 A の後に合法的に現れる可能性がある場合、パーサーは縮小します。それ以外の場合は、そうではありません。ここでの直観は、これまで見てきたトークンと今後のトークンを考えると、削減が正しくなる可能性がないため、場合によっては削減を試みても意味がないということです。

LR(0) と SLR(1) の唯一の違いは、競合が発生したときに実行するアクションを決定するのに役立つこの追加機能です。このため、LR(0) パーサーで解析できる文法は、SLR(1) パーサーで解析できます。ただし、SLR(1) パーサーは、LR(0) よりも多くの文法を解析できます。

ただし、実際には、SLR(1) は依然としてかなり弱い解析方法です。より一般的には、LALR(1) ("Lookahead LR(1)") パーサーが使用されていることがわかります。それらも LR(0) パーサーで競合を解決しようとすることで機能しますが、競合を解決するために使用する規則は SLR(1) で使用される規則よりもはるかに正確であるため、はるかに多くの文法が LALR(1) になります。 SLR(1) よりも。もう少し具体的に言うと、SLR(1) パーサーは、文法の構造を調べて、いつシフトし、いつ削減するかに関する詳細情報を学習することによって、競合を解決しようとします。LALR(1) パーサーは、文法と LR(0) パーサーの両方を調べて、いつシフトし、いつ削減するかに関するさらに具体的な情報を取得します。LALR(1) は LR(0) パーサーの構造を調べることができるため、特定の競合が誤っている場合をより正確に識別できます。yaccおよびbisonは、デフォルトで LALR(1) パーサーを生成します。

歴史的に、LALR(1) パーサーは通常、はるかに強力な LR(1) パーサーに依存する別の方法で構築されていたため、LALR(1) がそのように記述されていることがよくあります。これを理解するには、LR(1) パーサーについて話す必要があります。LR(0) パーサーでは、パーサーは、プロダクションの途中にある可能性がある場所を追跡することによって機能します。生産の終わりに達したことがわかると、削減を試みることを認識します。ただし、パーサーは、あるプロダクションの終わりと別のプロダクションの途中にあるのかどうかを判断できない場合があります。これにより、シフト/削減の競合が発生します。または、2 つの異なるプロダクションのどちらの終わりに達したか (reduce/競合を減らします）。LR(0) では、これによりすぐに競合が発生し、パーサーが失敗します。SLR(1) または LALR(1) では、

LR(1) パーサーでは、パーサーは動作中に追加情報を追跡します。パーサーは、どのプロダクションが使用されていると認識しているかを追跡するだけでなく、そのプロダクションが完了した後に出現する可能性のあるトークンを追跡します。パーサーは、決定を行う必要があるときだけでなく、各ステップでこの情報を追跡するため、LR(1) パーサーは、LR(0)、SLR(1)、またはこれまでに説明した LALR(1) パーサー。LR(1) は非常に強力な構文解析手法であり、シフト/リデュース パーサーによって決定論的に解析できる言語には、LR(1) オートマトンで解析できる文法があることを、いくつかのトリッキーな数学を使用して示すことができます。(これはすべての文法を意味するわけではないことに注意してください。決定論的に解析できるのはLR（1）です。これは、決定論的に解析できる言語が何らかの LR(1) 文法を持っていることを示しているだけです)。ただし、この能力には代償が伴い、生成された LR(1) パーサーは、動作するために非常に多くの情報を必要とし、実際には使用できない可能性があります。たとえば、実際のプログラミング言語の LR(1) パーサーは、正しく動作するために数十から数百メガバイトの追加情報を必要とする場合があります。このため、LR(1) は通常実際には使用されず、代わりに LALR(1) や SLR(1) などの弱いパーサーが使用されます。

最近では、GLR(0) ("Generalized LR(0)") と呼ばれる新しい解析アルゴリズムが人気を博しています。LR(0) パーサーに現れる競合を解決しようとするのではなく、GLR(0) パーサーは可能なすべてのオプションを並行して試すことによって機能します。いくつかの巧妙なトリックを使用して、これを多くの文法に対して非常に効率的に実行することができます。さらに、GLR(0) は、任意の k に対して LR(k) パーサーで解析できない文法であっても、任意の文脈自由文法を解析できます。他のパーサーも同様にこれを実行できます (Earley パーサーや CYK パーサーなど) が、実際には GLR(0) の方が高速になる傾向があります。

もっと詳しく知りたいという方のために、この夏、私はコンパイラの入門コースを教え、2 週間弱かけて構文解析手法について説明しました。LR(0)、SLR(1)、およびその他の多くの強力な構文解析手法のより厳密な概要を知りたい場合は、構文解析に関する講義スライドと宿題をお楽しみください。すべてのコース資料は、こちらの個人サイトから入手できます。

お役に立てれば！

Answer 2

これは私が学んだことです。通常、LR（0）パーサーにはあいまいさがあります。つまり、テーブルの1つのボックス（パーサーを作成するために派生）に複数の値（または）を含めることができます。つまり、パーサーは同じ入力で2つの最終状態になります。したがって、SLRパーサーは、このあいまいさを取り除くために作成されます。それを構築するために、goto状態につながるすべてのプロダクションを見つけ、左側のプロダクションシンボルのfollowを見つけ、followに存在するgoto状態のみを含めます。これは、元の文法を使用して不可能なプロダクションを含めないことを意味します（その状態は次のセットにありません）