Loading article…
LALRパーサー[ a ]（先読み、左から右、最右導出パーサー）は、コンピュータ言語用のパーサーの一種です。これは、標準的なLRパーサーの簡略版です。
LALR パーサーは、フランク・デレマーが 1969 年の博士論文「LR(k) 言語のための実用的な翻訳器」[ 1 ]の中で、当時の LR(1) パーサーの実装における実際的な困難を扱った際に考案されました。彼は、LALR パーサーは LR(0) パーサーよりも言語認識能力が高く、両方のパーサーで認識できる言語に対して LR(0) パーサーと同じ数の状態しか必要としないことを示しました。これにより、LALR パーサーは LALR 言語に対して LR(1) パーサーのメモリ効率の良い代替手段となります。また、LALR ではない LR(1) 言語が存在することも証明されました。この弱点にもかかわらず、LALR パーサーの能力は Java [ 3 ]を含む多くの主流のコンピュータ言語[ 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 つの簡略版、すなわちルックアヘッド LR (LALR) [ 1 ]とシンプル 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)) と表記することもできます。実際には、 LR( j + k )パーサーから導出できる、jとkのすべての組み合わせに対応する2パラメータのLA( k )LR( j )パーサーのファミリーが存在するが[ 9 ] 、これらは実用化されていない。
他のタイプのLRパーサーと同様に、LALRパーサーはバックトラッキングを使用する必要がないため、入力ストリームを左から右に一度スキャンするだけで、正しいボトムアップ構文を1つ見つけるのに非常に効率的です。定義上、先読みパーサーであるため、常に先読みを使用し、LALR(1)が最も一般的なケースです。
LALR(1) パーサーは LR(1) パーサーよりは強力ではなく、SLR(1) パーサーより強力ですが、これらはすべて同じ生成規則を使用しています。LALR パーサーが導入する簡略化は、LR(0) 状態構築プロセス中に先読みが不明であるため、同一のカーネル項目セットを持つ規則をマージすることにあります。先読み記号が不明なため、パーサーは次にどの文法規則を選択すべきか混乱し、 reduce/reduce の競合が発生する可能性があるため、パーサーの能力が低下します。LALR (1) パーサーを曖昧性のない LR(1) 文法に適用する際に発生するすべての競合は、reduce/reduce の競合です。SLR(1) パーサーはさらにマージを実行するため、追加の競合が発生します。
LALR(1) パーサーでは解析できない、このような reduce/reduce の競合を示す LR(1) 文法の標準的な例は次のとおりです。[ 10 ] [ 11 ]
S → a E c → F d → b F c → b E d E → e 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 )パーサーとは比較できません。0より大きい任意のjとkに対して、 LL( k )文法ではないLALR( j )文法が存在し、その逆もまた同様です。実際、任意のjとkに対して、与えられたLL(1)文法がLALR( k )であるかどうかは決定できません。[ 2 ]
空の導出の有無によって、LL(1)文法はSLR(1)文法またはLALR(1)文法と等しくなります。LL(1)文法に空の導出がない場合、それはSLR(1)であり、空の導出を持つすべての記号が空でない導出を持つ場合、それはLALR(1)です。空の導出のみを持つ記号が存在する場合、その文法はLALR(1)である場合もそうでない場合もあります。[ 12 ]
