LALRパーサー

コンピュータサイエンス において、LALRパーサー^[a]（先読み、左から右、右端の導出パーサー）は、人間が読めるテキストをコンピュータが読める構造化表現に変換するコンパイルプロセスの一部です。LALRパーサーは、テキストをコンパイラなどの他のプログラムが使用できる非常に特殊な内部表現に処理（解析）するソフトウェアツールです。このプロセスは、コンピュータ言語の形式文法で指定された一連の生成規則に従って行われます。

LALR パーサーは、標準的な LR パーサーの簡略化されたバージョンです。

LALRパーサは、1969年の博士論文「LR(k)言語のための実用的な翻訳者^」[1]でフランク・デレマーによって発明されました。彼は、LR(1)パーサを実装する際の当時の実際的な困難さを扱っています。彼は、LALRパーサはLR(0)パーサよりも言語認識力が高く、両方のパーサで認識できる言語の場合、LR(0)パーサと同じ数の状態しか必要としないことを示しました。これにより、LALRパーサは、LALR言語の場合、LR(1)パーサのメモリ効率の高い代替手段になります。また、LALRではないLR(1)言語が存在することも証明されました。この弱点にもかかわらず、LALRパーサの能力は、Javaを含む多くの主流のコンピュータ言語[ ^{2 ]には十分です。ただし、多くの言語の参照文法は}あいまいであるため、LALRではありません。^[2]

元の論文では、形式文法が与えられた場合にそのようなパーサーを構築するアルゴリズムは示されていませんでした。LALRパーサー生成のための最初のアルゴリズムは1973年に公開されました。^[4] 1982年に、DeRemerとTom Pennelloは、メモリ効率の高いLALRパーサーを生成するアルゴリズムを公開しました。^{[5] LALRパーサーは、} YaccやGNU BisonなどのLALRパーサージェネレータによって文法から自動的に生成できます。自動的に生成されたコードは、結果として得られるパーサーのパワーを増強するために手書きのコードで補強される場合があります。

1965 年、ドナルド・クヌースはLR パーサー(左から右、最右導出) を発明しました。LR パーサーは、線形制限時間内に任意の決定論的文脈自由言語を認識できます。 ^[6]最右導出には非常に大きなメモリ要件があり、当時のコンピュータのメモリが限られていたため、LR パーサーを実装することは非現実的でした。この欠点に対処するために、1969 年にフランク・デレマーは LR パーサーの 2 つの簡略化されたバージョン、つまりLook-Ahead LR (LALR) ^[1]とSimple LR パーサー(SLR) を提案しました。これらは言語認識能力は低くなりますが、メモリ要件ははるかに低く、LALR パーサーが最も強力な代替手段でした。^[1] 1977 年に、LR パーサーのメモリ最適化が発明されましたが^[7]、 LR パーサーは依然として簡略化された代替手段よりもメモリ効率が悪かったです。

1979年、フランク・デレマーとトム・ペネロは、LALRパーサーのメモリ効率をさらに向上させる一連の最適化を発表しました。^[8]彼らの研究は1982年に出版されました^。[5]

一般的に、LALRパーサーはLALR(1)パーサーを指します^[b]。LRパーサーが一般的にLR(1)パーサーを指すのと同じです。「(1)」は、1トークンの先読みを示し、パース中にルールパターン間の差異を解決します。同様に、2トークンの先読みを行うLALR(2)パーサーや、kトークン検索を行うLALR( k )パーサーがありますが、これらは実際に使用されることはまれです。LALRパーサーはLR(0)パーサーに基づいているため、LALR(1) = LA(1)LR(0) (1トークンの先読み、LR(0))、またはより一般的にはLALR( k ) = LA( k )LR(0) (kトークンの先読み、LR(0))と表記することもできます。実際には、 jとkのすべての組み合わせに対して、LR( j  +  k )パーサから導出できる2パラメータのLA( k )LR( j )パーサファミリが存在するが^[9] 、これらは実用化されていない。

他のタイプのLRパーサーと同様に、LALRパーサーはバックトラッキングを使用する必要がないため、入力ストリームを左から右に1回スキャンするだけで、正しいボトムアップパースを1つ見つけるのに非常に効率的です。定義上、先読みパーサーであるため、常に先読みを使用しますが、LALR(1)が最も一般的なケースです。

LALR(1)パーサーはLR(1)パーサーほど強力ではなく、SLR(1)パーサーよりも強力ですが、これらはすべて同じ生成規則を使用します。LALRパーサーが導入する単純化は、LR(0)状態構築プロセス中に先読みが不明であるため、同一のカーネル項目セットを持つ規則をマージすることです。これにより、先読みシンボルがわからないことでパーサーが次にどの文法規則を選択するかについて混乱し、reduce/reduce競合が発生する可能性があるため、パーサーの能力が低下します。LALR(1)パーサーを明確なLR(1)文法に適用する際に発生するすべての競合は、reduce/reduce競合です。SLR(1)パーサーはさらにマージを実行し、これにより追加の競合が発生します。

LALR(1)パーサで解析できない、還元/還元衝突を示すLR(1)文法の標準的な例は以下の通りである: ^{[10] [11]}

  S → a E c
    → a F d
    → bFc
    → b え d
  え → え
  F → e

LALR テーブルの構築では、2 つの状態が 1 つの状態にマージされ、後で先読みがあいまいであることが判明します。先読みのある 1 つの状態は次のとおりです。

  E → e.{c,d}
  F → e.{c,d}

LR(1) パーサーは、2 つの異なる状態 (競合しない先読みを持つ) を作成しますが、どちらもあいまいではありません。LALR パーサーでは、この 1 つの状態に競合するアクション (先読み c または d が与えられた場合、E または F に削減) があり、「削減/削減競合」が発生します。上記の文法は、LALR パーサー ジェネレーターによってあいまいであると宣言され、競合が報告されます。

回復するには、文法で F の前にある E を選択することでこの曖昧さを解決します。ただし、結果のパーサーは、b e c曖昧なシーケンスが正しい ではなくe cに短縮されるが、文法には含まれていないため、有効な入力シーケンス を認識できません。 (E → e) c(F → e) cb E c

LALR( j )パーサはLL( k )パーサと比較できません。jとkが両方とも0より大きい場合、LL( k )文法ではないLALR( j )文法があり、その逆も同様です。実際、与えられたLL(1)文法が任意のに対してLALR( k )であるかどうかは決定できません。[ ^2]${\displaystyle k>0}$

空導出の有無によって、LL(1)文法はSLR(1)文法またはLALR(1)文法と等しくなる。LL(1)文法に空導出がない場合、それはSLR(1)であり、空導出を持つすべてのシンボルが空でない導出を持つ場合、それはLALR(1)である。空導出のみを持つシンボルが存在する場合、文法はLALR(1)である場合とそうでない場合がある。^[12]

• パーサージェネレータの比較
• 文脈自由文法
• 先読み
• パーサージェネレーター
• トークンスキャナー

• 構文解析シミュレータ このシミュレータは、構文解析テーブル LALR を生成し、本書の演習問題を解くために使用されます。
• JS/CC LALR(1) パーサージェネレーターの JavaScript ベースの実装。Web ブラウザまたはコマンドラインから実行できます。
• Wayback MachineのLALR(1)チュートリアル（2021年5月7日アーカイブ）、LALR(1)解析に関するフラッシュカードのようなチュートリアル。