LALR パーサー ジェネレーター

先読みLR パーサー (LALR) ジェネレーターは、文脈自由文法(CFG) を読み取り、CFG で定義された 文脈自由言語で記述されたファイルを解析できるLALR パーサーを作成するソフトウェア ツールです。LALRパーサーは、他の種類のパーサーと比較して非常に高速で小さいため、望ましいものです。

パーサー ジェネレーターには、シンプル LR パーサー、LR パーサー、GLR パーサー、LL パーサー、GLL パーサー ジェネレーターなど、他にもさまざまな種類があります。それぞれの違いは、受け入れ可能な CFG の種類と、生成されたパーサーで使用される解析アルゴリズムの種類です。LALR パーサー ジェネレーターは、入力として LALR 文法を受け入れ、LALR 解析アルゴリズム (LALR パーサー テーブルによって駆動) を使用するパーサーを生成します。

実際には、LALR(1) 文法は SLR(1) よりも強力であり、ほとんどの実用的な LL(1) 文法を解析できるため、LALR は優れたソリューションを提供します。LR(1) 文法は LALR(1) よりも強力ですが、(「標準的な」) LR(1) パーサーはサイズが非常に大きくなる可能性があり、実用的ではないと考えられています。最小限の LR(1) パーサーはサイズが小さく、LALR(1) パーサーに匹敵します。

フランク・デレマーは、1969 年に MIT で「実用的な LR(k) トランスレータ」という博士論文で LALR パーサを発明しました。これは重要なブレークスルーでした。なぜなら、ドナルド・クヌースが1965 年の論文「言語の左から右への翻訳について」で定義した LR(k) トランスレータは、1960 年代と 70 年代のコンピュータ システムに実装するには大きすぎたからです。

初期のLALRパーサージェネレーターであり、おそらく長年最も人気があったのは、1975年にAT&T研究所でStephen Johnsonによって作成された「 yacc」（Yet Another Compiler Compiler）です。 ^[1] もう1つの「TWS」は、Frank DeRemerとTom Pennelloによって作成されました。今日では、多くのLALRパーサージェネレーターが利用可能であり、その多くはオリジナルのYaccに触発され、ほぼ互換性があります。たとえば、オリジナルのYacc/ YakをもじったGNU bisonです。より詳細なリストについては、 決定論的文脈自由言語パーサージェネレーターの比較を参照してください。

LALR パーサーとその代替である SLR パーサーおよびCanonical LR パーサーは、同様のメソッドと解析テーブルを備えていますが、主な違いは、パーサー生成ツールで使用される数学的な文法解析アルゴリズムにあります。LALR ジェネレーターは、SLR ジェネレーターよりも多くの文法を受け入れますが、完全な LR(1) よりも少ない文法を受け入れます。完全な LR は、はるかに大きな解析テーブルを必要とするため、特定のコンピュータ言語で明らかに必要な場合を除いて使用されません。実際のコンピュータ言語は、多くの場合、LALR(1) 文法で表現できます。それができない場合は、通常、LALR(2) 文法で十分です。パーサー ジェネレーターが LALR(1) 文法のみを許可する場合、パーサーは通常、拡張先読みを必要とする構造に遭遇するたびに、何らかの手書きのコードを呼び出します。

SLR パーサーや Canonical LR パーサー ジェネレーターと同様に、LALR パーサー ジェネレーターは最初に LR(0) 状態マシンを構築し、次に文法内のすべてのルールの先読みセットを計算して、あいまいさをチェックします。Canonical LR は完全な先読みセットを構築します。LALR はマージ セットを使用します。つまり、LR(0) コアが同じである先読みセットをマージします。SLR は、 LR(0) コアの右側を先読みターミナルに関連付ける先読みセットとしてFOLLOWセットを使用します。これは、LALR の場合よりも簡略化されています。これは、LR(0) コアが同じ右側と先読みターミナルを共有することから多くの競合が発生する可能性があり、LALR にはこのような競合が存在しないためです。これが、SLR の言語認識能力が LALR よりも低く、Canonical LR が簡略化を含まないためどちらよりも強力である理由です。

• パーサー ジェネレーターの比較 – LL、SLR、GLR、LR パーサー ジェネレーターも含まれる、より完全なリスト。

• Alfred V. Aho、Ravi Sethi、Jeffrey D. Ullman。コンパイラ：原理、テクニック、ツールAddison—Wesley、1986年。（別名The Dragon Bookでは、LALR(1)パーサーを構築するための従来のテクニックについて説明しています。）
• Richard Bornat著「Understanding and Writing Compilers」、Macmillan、1979年。（自動左から右への構文解析の原理、構文解析テーブルの構築方法、フォローセットとは何かなどを数学ではなく英語で説明しています。著者のページ[1]から無料で入手できます。）