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

Question

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

SLRとLR（0）は1つずつ同じですか？そうでない場合、違いは何ですか？

Answer 1

LR（0）とSLR（1）パーサーの両方が ボトムアップ、方向性、予測パーサー. 。この意味は

• パーサーは、プロダクションを逆に適用して、入力文を開始記号に戻しようとします（一気飲み)
• パーサーは、左から右への入力をスキャンします（方向)
• パーサーは、すべての入力を必ずしも見ずに適用する削減を予測しようとします（予測)

LR（0）とSLR（1）の両方が パーサーをシフト/削減します, 、つまり、それらをスタックに配置することにより、および各ポイントで入力ストリームのトークンを処理することを意味します シフト スタックに押し込んでトークンまたは 削減 スタックの上にある端子と非端子のいくつかのシーケンスは、いくつかの非ターミナルシンボルに戻ります。シフト/削減パーサーを使用して、すべての文法をサージオンボトムアップで解析できることが示されますが、そのパーサーはそうではないかもしれません 決定論的. 。つまり、パーサーは、シフトまたは削減を適用するかどうかを「推測」しなければならず、間違った選択をしたことを認識するためにバックトラックする必要がある場合があります。構築する決定論的シフト/削減パーサーをどれほど強力に削減しても、すべての文法を解析することはできません。

決定論的なシフト/削減パーサーを使用して、処理できない文法を解析すると、 競合をシフト/削減します また 競合を削減/削減します, 、パーサーがどのような行動をとるべきかを知ることができない状態に入ることができます。シフト/縮小競合では、スタックに別のシンボルを追加するか、スタックの上部シンボルである程度の削減を実行する必要があるかどうかはわかりません。競合を削減/減少させると、パーサーは、スタックの上部記号をいくつかの非ターミナルに置き換える必要があることを知っていますが、どの削減を使用するかはわかりません。

これが長い博覧会である場合は謝罪しますが、LR（0）とSLR（1）の解析の違いに対処できるようにする必要があります。 LR（0）パーサーは、見た目のゼロトークンを使用して、どのアクションをとるべきかを決定するシフト/削減パーサーです（したがって0）。これは、パーサーの任意の構成では、パーサーに選択する明確なアクションが必要であることを意味します。特定のシンボルをシフトするか、特定の削減を適用します。 2つ以上の選択肢がある場合、パーサーは失敗し、文法はLR（0）ではないと言います。

可能な2つのLR競合は、シフト/削減、削減/削減であることを思い出してください。これらの両方のケースでは、LR（0）オートマトンが取得する可能性のある少なくとも2つのアクションがあり、それらのどれを使用するかはわかりません。矛盾する行動の少なくとも1つは減少であるため、合理的な攻撃ラインは、特定の削減を実行するときにパーサーにもっと注意を払わせようとすることです。より具体的には、パーサーが入力の次のトークンを調べて、シフトまたは削減するかどうかを判断できると仮定しましょう。パーサーが「理にかなっている」ときにのみ減らすことを許可する場合（「意味があります」という定義のために）、オートマトンに特別にシフトまたは削減することを選択することにより、競合を排除できる場合があります。特定のステップ。

SLR（1）（ "Simplified LR（1）"）では、パーサーは、シフトするか削減するかを決定する際に、Lookaheadの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）パーサーの構造を見ることができるため、特定の競合がスプリアスである場合、より正確に識別できます。 Linuxユーティリティ yacc と bison, 、デフォルトでは、LALR（1）パーサーを生成します。

歴史的に、LALR（1）パーサーは通常、はるかに強力なLR（1）パーサーに依存する別の方法で構築されていたため、Lalr（1）がそのように説明されることがよくあります。これを理解するには、LR（1）パーサーについて話す必要があります。 LR（0）パーサーでは、パーサーは、生産の最中にどこにあるかを追跡することで機能します。それが生産の終わりに達したことがわかったら、それは減らそうとすることを知っています。ただし、パーサーは、1つの生産の終了時と別の生産の中央にあるかどうかを判断できない場合があります。競合を減らす）。 LR（0）では、これはすぐに競合につながり、パーサーは失敗します。 SLR（1）またはLALR（1）では、パーサーはLookaheadの次のトークンに基づいてシフトまたは削減することを決定します。

LR（1）パーサーでは、パーサーは動作中に追加情報を追跡します。パーサーが使用していると考えている生産を追跡することに加えて、その生産が完了した後にトークンが表示される可能性のあるものを追跡します。パーサーは、決定を下す必要があるときだけでなく、各ステップでこの情報を追跡しているため、LR（1）パーサーは、LR（0）、SLR（1）、またはLalr（1）これまで話してきたパーサー。 LR（1）は非常に強力な解析手法であり、扱いにくい数学を使用して、決定論的に解析できる言語を使用して表示できます。 どれか Shift/Reduce Parserには、LR（1）オートマトンで解析できる文法があります。 （これはすべてを意味しないことに注意してください 文法 それは決定論的に解析される可能性があります。これは、決定論的に解析できる言語には、LR（1）文法があることを言っているだけです。ただし、このパワーには価格があり、生成されたLR（1）パーサーは、実際に使用できない可能性があるため、操作するために非常に多くの情報が必要になる場合があります。たとえば、実際のプログラミング言語用のLR（1）パーサーは、正しく動作するために数十から数百メガバイトの追加情報が必要になる場合があります。このため、LR（1）は通常実際には使用されておらず、代わりにLALR（1）やSLR（1）などの弱いパーサーが使用されます。

最近では、GLR（0）（「一般化されたLR（0）」）と呼ばれる新しい解析アルゴリズムが人気を博しています。 LR（0）パーサーに表示される競合を解決しようとするのではなく、GLR（0）パーサーは、すべての可能なオプションを並行して試行することで機能します。いくつかの巧妙なトリックを使用して、これは多くの文法に対して非常に効率的に実行するようにすることができます。さらに、GLR（0）は解析できます コンテキストフリーの文法, 、任意のkのLR（k）パーサーで解析できない文法でさえ。 GLR（0）は実際にはより速くなる傾向がありますが、他のパーサーもこれを行うことができます（たとえば、Earley ParserやCyk Parserなど）。

あなたがもっと学ぶことに興味があるなら、今年の夏に私は紹介コンパイラコースを教え、2週間弱で解析技術について話しました。 LR（0）、SLR（1）、およびその他の強力な解析技術をより厳密に紹介したい場合は、講義スライドと解析に関する宿題の割り当てをお楽しみください。すべてのコース資料が利用可能です 私の個人的なサイトで.

お役に立てれば！

Answer 2

これが私が学んだことです。通常、LR（0）パーサーはあいまいさを持つことができます。つまり、テーブルの1つのボックス（パーサーの作成に導出されます）が複数の値を持つことができます（または）パットすることができます。パーサーは、同じ入力を持つ2つの最終状態につながります。したがって、このあいまいさを削除するためにSLRパーサーが作成されます。構築するために、GOTO州につながるすべてのプロダクションを見つけ、左側の生産シンボルのフォローを見つけ、以下に存在するGOTO州のみを含めます。このインテルは、元のグラマーを使用して不可能なプロダクションを含めないことを意味します（その状態がフォローセットにないこと）