LALR_parser_generator
「LALRパーサジェネレータ」
先読みLRパーサー（LALR）ジェネレーターは、BNF文法を読み取り、BNF文法で定義されたコンピューター言語で記述されたファイルを解析できるLALRパーサーを作成するソフトウェアツールです。LALRパーサーは、他のタイプのパーサーと比較して非常に高速で小さいため、望ましいものです。
Simple LRパーサー、LRパーサー、GLRパーサー、LLパーサー、GLLパーサージェネレーターなど、他のタイプのパーサージェネレーターが互いに異なるのは、受け入れることができるBNF文法のタイプと、生成されたパーサーで使用される構文解析アルゴリズムのタイプです。LALRパーサージェネレーターは、入力としてLALR文法を受け入れ、LALR解析アルゴリズム（LALRパーサーテーブルによって駆動される）を使用するパーサーを生成します。
実際には、LALR（1）文法はSLR（1）よりも強力であり、最も実用的なLL（1）文法を解析できるため、LALRは優れたソリューションを提供します。LR（1）文法はLALR（1）よりも強力ですが、正規LR（1）パーサーはサイズが非常に大きくなる可能性があり、実用的ではないと見なされます。最小のLR（1）パーサーはサイズが小さく、LALR（1）パーサーに匹敵します。
コンテンツ
1 歴史
2 概要
3 も参照してください
4 参考文献
5 参考文献
歴史
フランク・デレマーは、1969年にMITで「実用的なLR（k）翻訳者」と呼ばれる博士論文でLALRパーサーを発明しました。ドナルド・クヌースが1965年の論文「左から右への言語の翻訳について」で定義したLR（k）トランスレータは、1960年代と70年代のコンピュータシステムに実装するには大きすぎたため、これは重要なブレークスルーでした。
初期のLALRパーサージェネレーターであり、おそらく長年にわたって最も人気のあるジェネレーターは、1975年にAT＆T研究所でStephen Johnsonによって作成された「 yacc 」（YetAnotherCompilerCompiler）でした。もう1つの「TWS」は、FrankDeRemerとTomPennelloによって作成されました。今日、多くのLALRパーサジェネレータが利用可能であり、その多くは元のYaccに触発され、大部分が互換性がたとえば、元のYacc/ YakのしゃれであるGNUbisonなどです。詳細なリストについては、決定性文脈自由言語パーサジェネレータの比較を参照して
概要
LALRパーサーとその代替であるSLRパーサーとCanonicalLRパーサーには、同様のメソッドと解析テーブルがそれらの主な違いは、パーサー生成ツールで使用される数学的文法分析アルゴリズムにLALRジェネレーターは、SLRジェネレーターよりも多くの文法を受け入れますが、完全なLR（1）よりも少ない文法を受け入れます。フルLRには、はるかに大きな解析テーブルが含まれ、特定のコンピューター言語で明確に必要とされない限り、回避されます。実際のコンピューター言語は、LALR（1）文法として表現できることがよくそれができない場合は、通常、LALR（2）文法で十分です。パーサジェネレータがLALR（1）文法のみを許可する場合、パーサは通常、拡張先読みを必要とする構造に遭遇するたびに、手書きのコードを呼び出します。
SLRパーサーおよびCanonicalLRパーサージェネレーターと同様に、LALRパーサージェネレーターは最初にLR（0）ステートマシンを構築し、次に文法内のすべてのルールの先読みセットを計算して、あいまいさをチェックします。正規LRは、完全な先読みセットを構築します。LALRはマージセットを使用します。つまり、LR（0）コアが同じである先読みセットをマージします。SLRは、FOLLOWセットを先読みセットとして使用し、LR（0）コアの右側を先読み端子に関連付けます。これは、LALRの場合よりも大幅に単純化されています。これは、同じ右側と先読み端子を共有するLR（0）コアから多くの競合が発生する可能性があるためです。この競合は、LALRには存在しません。これが、SLRがLALRよりも言語認識能力が低く、正規LRが単純化を含まないため、両方よりも強力である理由です。
も参照してください
パーサジェネレータの比較 –より完全なリストについては、LL、SLR、GLR、およびLRパーサジェネレータも含まれています。
参考文献
^ スティーブンC.ジョンソン（1975）。「Yacc：さらに別のコンパイラ-コンパイラ」。AT＆Tベル研究所。
アルフレッドV.アホ、ラビセシィ、ジェフリーD.ウルマン。コンパイラー：原理、技法、およびツールAddison—Wesley、1986年。（別名The Dragon Bookは、LALR（1）パーサーを構築するための従来の技法について説明しています。）
Richard Bornat理解と書き込みコンパイラ、Macmillan、1979年。（自動化された左から右への解析の原則とパーサーテーブルの作成方法、次のセットとは何かなどを、数学ではなく英語で説明しています。の著者のページ。）
参考文献
クヌース、DE（1965年7月）。「言語の左から右への翻訳について」 （PDF）。情報と制御。8（6）：607–639。土井：10.1016 / S0019-9958（65）90426-2。2012年3月15日にオリジナル （PDF）からアーカイブされました。
DeRemer、Franklin L.（1969）。LR（k）言語の実用的な翻訳者 （PDF）（Ph.D.）MIT。2013年8月19日にオリジナル （PDF）からアーカイブされました。
LALR（1）先読みセットの効率的な計算、DeRemerおよびPennello、TOPLAS（1982）