[解決済み] LR、SLR、LALRパーサーの違いは何ですか？

質問

LR、SLR、LALRのパーサーの違いは何ですか？SLR と LALR が LR パーサーの一種であることは知っていますが、パーシング テーブルに関する限り、実際の違いは何ですか。

また、ある文法がLR、SLR、LALRのどれであるかを示すにはどうしたらよいのでしょうか。LL 文法については、解析テーブルのどのセルにも複数の生成規則があってはならないことを示せばよいのです。LALR、SLR、LRについて同様のルールがあれば教えてください。

たとえば、どのように私たちは、文法

S --> Aa | bAc | dc | bda
A --> d

はLALR(1)ですが、SLR(1)ではありませんか？

EDIT (イブンガロビル) : LALRとLRの違いは何なのか、納得のいく回答が得られませんでした。LALRの方がテーブルのサイズは小さいが、LR文法のサブセットしか認識できないということですね。LALRとLRの違いについて、もう少し詳しく教えてください。LALR(1)とLR(1)で十分だと思います。どちらも1トークンルックアヘッドと 両方とも はテーブル駆動です! どう違うのでしょうか？

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

SLR、LALR、LR パーサーはすべて、まったく同じテーブル駆動の機械を使って実装することができます。

基本的に、解析アルゴリズムは次の入力トークン T を収集し、現在の状態 S（および関連するルックアヘッド、GOTO、およびリダクション テーブル）を参照して、何を行うかを決定します。

• SHIFT：現在のテーブルがトークン T で SHIFT するように言っている場合、ペア (S,T) は解析スタックにプッシュされ、状態は現在のトークンについて GOTO テーブルが言うことに従って変更され（たとえば、GOTO（T））、別の入力トークン T' がフェッチされて、このプロセスが繰り返される。
• REDUCE：すべての状態は、0、1、または多くの可能な削減が発生する可能性があります。パーサーが LR または LALR の場合、トークンは状態のすべての有効な削減のためのルックアヘッド セットに対してチェックされる。トークンが文法規則 G = R1 R2 ... Rn の削減のためのルックアヘッドセットに一致する場合、スタック削減とシフトが発生します。G の意味アクションが呼び出され、スタックが（Rn から）n 回ポップされ、ペア（S,G）がスタックにプッシュされ、新しい状態 S' が GOTO(G) に設定されて、同じトークン T でサイクルが繰り返されます。パーサがSLRパーサである場合、状態に対する削減規則はせいぜい1つであるため、どの削減が適用されるかを検索することなく、削減動作をブラインドで行うことができる。 SLRパーサーにとって便利なのは、そのパーサーに は これは、各状態がそれに関連する削減の数を明示的に記録していれば簡単にわかりますし、そのカウントは実際には L(AL)R バージョンに必要です。
• ERROR: SHIFT も REDUCE も不可能な場合、シンタックス エラーが宣言されます。

じゃあ、全部同じ機械を使っているならば、何が言いたいの？

SLRの価値とされるものは、実装のシンプルさです。ルックアヘッドセットをチェックする可能性のあるリダクションをスキャンする必要はありません。 どのリダクションが適用されるかは、ステートに特別に添付することができるので、SLR解析装置はそれを探す必要はないのです。 実際には、L(AL)R パーサーはより多くの言語を処理することができ、実装するための余分な作業はほとんどないため、学術的な練習を除いて SLR を実装する人はいません。

LALR と LR の違いは、テーブルの ジェネレーター . LR パーサー ジェネレーターは、特定の状態とその正確なルックアヘッド セットから可能なすべての削減を追跡します。 これは、かなり大きな状態セットを構築する傾向がある。 LALRパーサーは、GOTOテーブルとルックヘッド集合が互換性があり、衝突しない場合は、状態を組み合わせることができます。 このため、LR パーサーは LALR パーサーよりも多くの言語を解析できますが、パーサー テーブルは非常に大きくなります。 実際には、状態機械のサイズを最適化する価値があるほど対象言語に近い LALR 文法が見つかることがあります。

そうなんです。3つとも同じ機械を使っています。SLR は、ほんの少しの機械は無視できるという意味では簡単ですが、その苦労に見合うものではありません。 LRはより多くの言語を解析しますが、ステートテーブルが大きくなる傾向があります。 そのため、実用的な選択肢としては LALR が残されています。

これらのことをすべて述べた上で、以下のことを知ることは価値があります。 GLR パーサー はより複雑な機械を使って、どんな文脈自由言語でも解析することができます。 しかし、全く同じテーブル (LALRで使用される小さいバージョンも含む)を使用します。つまり、GLRはLR、LALR、SLRよりも厳密に強力です。標準的なBNF文法を書くことができれば、GLRはそれに従ってパースします。機械的な違いは、GLRはGOTOテーブルとルックアヘッド・セットの間に矛盾がある場合、複数のパースを試行することです。(GLRがこれをどのように効率的に行うかは、[私ではなく]天才的な技術ですが、このSOポストには収まりません)。

私にとって、これは非常に有用な事実です。 私はプログラムアナライザやコード変換器を作っていますが、パーサーは必要ですが、興味はありません(quot; 興味があるのは、パースした結果で何をするかです。 GLRを使うと、LALRで使える形に文法をハックするのに比べて、比較的簡単に実用的な文法を構築することができるのです。 これは、C++ や Fortran などの非学術的な言語を扱おうとするときに非常に重要で、言語全体をうまく処理するために文字通り何千ものルールが必要になり、LALR（あるいは LR）の制限を満たすために文法規則をハックすることに人生を費やしたくないのです。

有名な例として、C++ は、LALR 解析を行う人々によって、解析が非常に困難であると考えられています。 C++ は、C++ リファレンス マニュアルの後ろに記載されているルールをほぼそのまま使用して、GLR マシンにより簡単にパースできます。 (私はまさにそのようなパーサーを持っており、バニラC++だけでなく、様々なベンダーの方言も扱うことができます。これは、GLR パーサーを使用しているからこそ、実際に可能なのです (IMHO)。

[編集 2011 年 11 月。 私たちはパーサーを拡張して、C++11 のすべてを扱えるようにしました。 GLR のおかげで、それがずっと簡単にできるようになったのです。EDIT 2014年8月。C++17 のすべてを扱うようになりました。 何も壊れたり悪くなったりせず、GLR は依然として猫の鳴き声です] 。