[解決済み] LR(0)とSLRの構文解析の違いは何ですか？

質問

私はコンパイラの概念に取り組んでいますが、少し混乱しています...。 ググっても明確な答えにはたどり着けませんでした。

SLRとLR(0)パーサーは同じものなのでしょうか？そうでない場合、何が違うのでしょうか？

どのように解決するのですか？

LR(0)とSLR(1)パーサはどちらも ボトムアップ、指向性、予測型パーサー . これは次のことを意味します。

• パーサーは入力された文章を開始記号 ( ボトムアップ )
• パーサは入力を左から右へスキャンします ( 方向性 )
• パーサーは、必ずしもすべての入力を見ることなく、どのような削減を適用するかを予測しようとします ( 予測的 )

LR(0)とSLR(1)はともに シフト/リデュースパーサ であり、入力ストリームのトークンをスタックに載せて処理し、各ポイントで シフト トークンをスタックに押し出すか 減らす スタック上の端末と非端末のシーケンスをいくつかの非端末記号に戻す。 どんな文法もシフト/リデュースパーサーを使ってボトムアップで解析できることが示されているが、そのパーサーは 決定論的 . つまり、パーサーはシフトまたはリダクションを適用するかどうかを推測しなければならず、間違った選択をしたことに気付くためにバックトラックしなければならなくなる可能性があります。 どんなに強力な決定論的シフト/リダクション パーサーを構築しても、すべての文法を解析できるわけではありません。

決定論的なシフト/リデュース パーサーが、処理できない文法を解析するために使用された場合、次のような結果になります。 シフト/リデュースの競合 または コンフリクトを減らす ここでパーサーはどのようなアクションを取るべきか判断できない状態になる可能性があります。 shift/reduce 競合では、パーザはスタックに別のシンボルを追加すべきか、スタックの先頭のシンボルで何らかの削減を実行すべきかを判断できません。 reduce/reduce の競合では、パーサーはスタックの先頭の記号を何らかの非終端記号に置き換える必要があることを知っていますが、どのようなreduction を使用すべきかはわかりません。

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

LRの競合として、shift/reduceとreduce/reduceの2つが考えられることを思い出してください。 これらのケースでは、LR(0) オートマトンが取ることができる少なくとも 2 つのアクションがあり、それらのいずれを使用するかを判断することはできません。 矛盾する行動の少なくとも1つは「削減」なので、パーサーが特定の削減を実行するタイミングをより慎重に判断するように仕向けるのが合理的な方法でしょう。 具体的には、パーサーが入力の次のトークンを見て、シフトすべきかリダクションすべきかを判断することが許可されているとしましょう。 そうすることが理にかなっているときのみパーサーに削減を許可する場合 (「理にかなっている」のいくつかの定義について)、オートマトンに特定のステップでシフトまたは削減を具体的に選択させることによって、競合を排除できるかもしれません。

SLR(1) ("Simplified 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) で使用するルールよりもはるかに正確であり、結果として SLR(1) より LALR(1) がはるかに多くの文法で使用されています。 もう少し具体的に言うと、SLR(1) パーサーは文法の構造を見て、いつシフトし、いつリダクションするかという情報を知ることによって、競合を解決しようとするのです。 LALR(1) パーサーは、文法と LR(0) パーサーの両方を見て、いつシフトし、いつリデュースするかについて、さらに具体的な情報を得ようとします。 LALR(1) は LR(0) パーサの構造を見ることができるので、ある種の衝突が偽りのものである場合、より正確に識別することができます。 Linux のユーティリティである yacc と bison は、デフォルトで LALR(1) パーサーを生成します。

歴史的に、LALR(1) パーサーは通常、はるかに強力な LR(1) パーサーに依存する別の方法で構築されたため、LALR(1) がそのように説明されるのをよく見かけます。 これを理解するために、LR(1) パーサーについて説明する必要があります。 LR(0) パーサーでは、パーサーは生産の途中でどこにいるのかを追跡することによって動作します。 パーサーは、プロダクションの終わりに到達したことを確認すると、プロダクションを縮小することを決定します。 しかし、パーサーは、あるプロダクションの終わりと別のプロダクションの途中のどちらにいるのかを判断できない場合があります。これは、シフト/リデュースの競合につながりますし、2つの異なるプロダクションのうちどちらの終わりに達しているのか（リデュース/リデュースの競合）にもつながります。 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) は通常、実際には使用されず、代わりに LALR(1) や SLR(1) のような弱いパーサーが使用されます。

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

もっと学びたいのであれば、この夏、私はコンパイラー入門のコースで教え、構文解析技術について 2 週間弱を費やしました。 LR(0)、SLR(1)、およびその他の強力な構文解析技術のホストについてより厳密に紹介したい場合は、構文解析に関する私の講義スライドと宿題を楽しむことができるでしょう。 すべての教材が利用可能です この私の個人サイト .

これが役立つといいのですが!