シフトリデュースパーサー

シフトリデュースパーサは、コンピュータ言語や文法によって正式に定義されたその他の表記法のための、効率的なテーブル駆動型のボトムアップ解析手法の一種です。プログラミング言語の解析に最も一般的に使用される解析手法であるLR解析とそのバリエーションは、シフトリデュース手法です。^{[1] LR解析が発明される前に使用されていた}優先順位パーサ もシフトリデュース手法です。すべてのシフトリデュースパーサは、解析ツリーを構築するか特定の出力アクションを呼び出す増分順序で、同様の外向きの効果を持ちます。

シフト リデュースパーサーは、テキストを 1 回前方にスキャンして解析します。バック アップは行いません。パーサーは、推測やバック トラックを行わずに、下から上、左から右に段階的に解析ツリーを構築します。このパスの各ポイントで、パーサーは、すでに解析された入力テキストのサブツリーまたはフレーズのリストを蓄積しています。これらのサブツリーはまだ結合されていません。これは、パーサーが、それらを結合する構文パターンの右端にまだ到達していないためです。

文字列 を考えてみましょうA = B + C * 2。

例のステップ 7 では、「A = B +」のみが解析されています。解析ツリーの網掛けされた左下隅のみが存在します。8 以上の番号の解析ツリー ノードはまだ存在しません。ノード 1、2、6、および 7 は、項目 1..7 すべてをカバーする独立したサブツリーのルートです。ノード 1 は変数 A、ノード 2 は区切り文字 =、ノード 6 は加数 B、ノード 7 は演算子 + です。これらの 4 つのルート ノードは、解析スタックに一時的に保持されます。入力ストリームの残りの未解析部分は、「C * 2」です。

シフト リデュース パーサーは、シフト ステップとリデュース ステップの組み合わせを実行することによって機能するため、この名前が付けられています。

• シフトステップは、入力ストリーム内で 1 つのシンボルだけ進みます。シフトされたシンボルは、新しい単一ノードの解析ツリーになります。
• Reduceステップでは、完了した文法規則を最近の解析ツリーの一部に適用し、それらを新しいルート シンボルを持つ 1 つのツリーとして結合します。

パーサーは、すべての入力が消費され、すべての解析ツリーが完全な正当な入力を表す単一のツリーに縮小されるまで、これらの手順を続行します。

各解析ステップで、入力テキスト全体が解析スタック、現在の先読みシンボル、および残りの未スキャンテキストに分割されます。パーサーの次のアクションは、右端のスタック シンボルと先読みシンボルによって決定されます。アクションは、スタック シンボルと先読みシンボルの構文的に有効なすべての組み合わせを含むテーブルから読み取られます。

より簡単な例については ^[2]を参照してください。

文法とは、入力言語のパターンまたは構文規則のセットです。数値のサイズや、プログラム全体のコンテキストでの名前とその定義の一貫した使用など、すべての言語規則を網羅しているわけではありません。シフトリデュース パーサーは、シンボルのローカル パターンのみを扱う 文脈自由文法を使用します。

マッチングが可能な Java または C 言語の小さなサブセットとしての文法の例はA = B + C*2次のようになります。

割り当て ← id = 合計

合計 ← 合計 + 積

合計 ← 製品

製品 ← 製品 * 価値

製品 ← 価値

値 ← int

値 ← id

文法の終端記号は、字句スキャナによって入力ストリームで見つかった複数文字の記号または「トークン」です。ここでは、これらには= + *および任意の整数定数のintと、任意の識別子名のid が含まれます。文法では、 int値やid のスペルは考慮されません。また、空白や改行も考慮されません。文法ではこれらの終端記号を使用しますが、定義は行いません。これらは常に解析ツリーの一番下の茂った端にあります。

Sums のような大文字の用語は非終端記号です。これらは言語の概念またはパターンの名前です。これらは文法で定義され、入力ストリームにそれ自体が出現することはありません。これらは常に解析ツリーの最下部より上にあります。これらはパーサーが何らかの文法規則を適用した結果としてのみ出現します。一部の非終端記号は 2 つ以上の規則で定義されます。これらは代替パターンです。規則はそれ自体を参照できます。この文法では、繰り返される数学演算子を処理するために再帰規則を使用します。完全な言語の文法では、リスト、括弧で囲まれた式、ネストされたステートメントを処理するために再帰規則を使用します。

任意のコンピュータ言語は、複数の異なる文法で記述できます。シフト リデュース パーサーの文法は、それ自体が明確であるか、またはタイブレークの優先順位ルールによって拡張されている必要があります。つまり、言語の特定の正当な例に文法を適用する正しい方法は 1 つしかなく、その結果、その例に対して一意の解析ツリーと一意のシフト/リデュース アクションのシーケンスが生成されます。

テーブル駆動型パーサーは、文法に関するすべての知識をパーサーテーブルと呼ばれる不変のデータにエンコードします。パーサーのプログラムコードは、多くの文法や言語に変更なく適用される単純な汎用ループです。テーブルは、優先順位方式の場合は手動で作成できます。LR方式の場合、複雑なテーブルは、Bisonなどのパーサー生成ツールによって文法から機械的に生成されます。^{[3]パーサーテーブルは通常、文法よりもはるかに大きくなります。}再帰降下などのテーブル駆動型ではない他のパーサーでは、各言語構成要素は、その1つの構成要素の構文に特化した別のサブルーチンによって解析されます。

シフトリデュースパーサーは、バックアップを必要としないため効率的です。その合計実行時間は、入力の長さと完全な解析ツリーのサイズに比例します。バックトラックを行う他のパーサー方法では、推測が間違っていると指数関数的に時間がかかります。^{[引用が必要]}

推測を避けるために、シフトリデュース パーサーは、以前にスキャンしたシンボルの処理方法を決定する前に、次にスキャンしたシンボルを先読みすることがよくあります (左から右のテキストでは右側)。語彙スキャナは、パーサーの残りの部分よりも 1 つのシンボルを先に処理します。先読みシンボルは、各解析決定の「右側のコンテキスト」とも呼ばれます。(まれに、2 つ以上の先読みシンボルが使用されることもありますが、ほとんどの実用的な文法は 1 つの先読みシンボルを使用するように設計できます。)

シフト リデュース パーサーは、ある構造のすべての部分をスキャンして解析するまで待機してから、結合された構造を決定します。その後、パーサーはそれ以上待たずに、その組み合わせに対してすぐに処理を行います。上記の解析ツリーの例では、+ が先読みで見つかるとすぐに、フレーズ B は Value に縮小され、次にステップ 3 ～ 6 で Products と Sums に縮小されます。解析ツリーのこれらの部分を整理するためにそれ以上待つ必要はありません。B の処理方法は、パーサーとスキャナーが既に確認したものに基づいて決定され、右側にずっと後で現れるものは考慮されません。

削減は、最も最近解析されたもの、つまり先読み記号のすぐ左にあるものを再編成します。したがって、すでに解析されたもののリストはスタックのように機能します。この解析スタックは右方向に成長します。スタックのベースまたは最下部は左側にあり、最も左にある最も古い解析フラグメントを保持します。すべての削減ステップは、最も右にある最も新しい解析フラグメントにのみ作用します。(この累積的な解析スタックは、トップダウンパーサーで使用される予測的な左方向に成長する解析スタックとはまったく異なります。)

次のような文法規則がある場合

製品 ← 製品 * 価値

が適用されると、スタックトップには解析ツリー「... Products * Value」が保持されます。ルールの右側のこの見つかったインスタンスは、ハンドルと呼ばれます。reduceステップでは、ハンドル「Products * Value」を左側の非終端、この場合はより大きなProductsに置き換えます。パーサーが完全な解析ツリーを構築する場合、内部のProducts、*、およびValueの3つのツリーは、より大きなProductsの新しいツリールートによって結合されます。それ以外の場合、内部のProductsとValueの意味の詳細は、後のコンパイラパスに出力されるか、新しいProductsシンボルに結合されて保存されます。^[4]

パーサーは、新しく完了した文法規則の例がそこに見つかる限り、解析スタックの最上部に縮小を適用し続けます。適用できる規則がなくなると、パーサーは先読みシンボルを解析スタックに移動し、新しい先読みシンボルをスキャンして、再試行します。

パーサー テーブルは、最上位の解析スタック シンボルと先読みシンボルの正当な組み合わせごとに、次に何をするかを示します。次のアクションは一意である必要があります。つまり、シフトまたはリデュースのいずれかであり、両方ではありません。(これは、明確であること以外に、文法にいくつかのさらなる制限があることを意味します。) テーブルの詳細は、シフト リデュース パーサーの種類によって大きく異なります。

優先順位パーサーでは、ハンドルの右端は、最上位スタック シンボルの優先順位レベルまたは文法の厳密さを先読みシンボルの優先順位レベルまたは文法の厳密さと比較することによって検出されます。上記の例では、 int と id は、ステートメント区切り文字;と比較して、内部の文法レベルに属します。したがって、intとidはどちらも;よりも優先順位が高いと見なされ、 ;が続く場合は常に別のものに短縮される必要があります。優先順位パーサーにはさまざまな種類があり、それぞれハンドルの左端を検出して適用する正しいルールを選択する方法が異なります。

• 演算子優先順位パーサー。式には機能しますが、一般的なプログラム構文には機能しない非常に単純な数値メソッドです。
• シンプルな優先順位パーサー。1つの大きなMxNテーブルを使用して右端と左端を検索します。PL360で使用されます。 [ ^5] 一般的なプログラミング言語は処理しません。
• 弱い優先順位パーサー。優先順位テーブルをハンドルの右端を見つけるためだけに使用します。単純な優先順位よりも多くの文法を処理します。^[6]
• 拡張された優先順位パーサー。

• 混合戦略優先順位パーサー。XPLのオリジナルバージョンで使用。優先順位認識器に固有の「ダブル」を「トリプル」に拡張。SLR ほど強力ではない。優先順位メソッドによって課せられた制限を超えた文法を認識するために必要な「トリプル」が非常に多いため、XPL 自体のような比較的小さな言語でも、通常は非常に大きなテーブルを持つ。^[7]

優先順位パーサーは、処理できる文法に制限があります。決定を下すときに、解析スタックのほとんどを無視します。最上位のシンボルの名前のみを考慮し、それらのシンボルが文法のどこに出現するかという完全なコンテキストは考慮しません。優先順位では、似たようなシンボルの組み合わせは、文法全体で同じ方法で解析および使用する必要がありますが、それらの組み合わせはコンテキストに関係なく発生します。

LRパーサーはシフトリデュースパーシングのより柔軟な形式であり、より多くの文法を処理できます。^[8]

LR パーサは状態マシンのように機能し、シフトまたはリデュース アクションごとに状態遷移を実行します。これらはスタックを使用し、現在の状態はシフト アクションによってプッシュ (ダウン) されます。このスタックは、その後、リデュース アクションによってポップ (アップ) されます (同時に新しい状態がスタックされます)。このメカニズムにより、LR パーサは、優先順位文法のスーパーセットであるすべての決定論的文脈自由文法を処理できます。LR パーサは、標準 LR パーサによって完全に実装されています。Look -Ahead LRパーサとSimple LRパーサは、メモリ要件が大幅に削減された、その簡略化されたバリアントを実装しています。^{[9] [10]}最近の研究では、Knuth のテーブル構築アルゴリズムよりも大幅にテーブル要件を削減して標準 LR パーサを実装する方法が特定されています。^[11]

LR、LALR、SLR のいずれの場合でも、基本的な状態マシンは同じです。異なるのはテーブルのみで、これらのテーブルはほとんどの場合機械的に生成されます。さらに、これらのテーブルは通常、REDUCE が状態マシンの外部にある閉じたサブルーチンへの CALL となり、REDUCE される文法規則の意味によって暗示される機能を実行するように実装されます。したがって、パーサーは不変状態マシン部分と可変意味部分に分割されます。この基本的な区別により、非常に信頼性の高い高品質のパーサーの開発が促進されます。

特定のスタック状態と先読みシンボルが与えられた場合、ERROR、SHIFT、REDUCE、STOP の 4 つのアクションが正確に実行されます (以下、構成と呼びます)。構成内のドット (•) は現在の先読み位置を表し、ドットの右側に先読みシンボル (常に終端シンボルに対応) が表示され、ドットの左側に現在のスタック状態 (通常は非終端シンボルに対応) が表示されます。

パフォーマンスの向上などの実用的な理由から、テーブルは通常、2 ビット シンボルのやや大きな補助配列によって拡張されます。これは、バイト指向のマシンで効率的にアクセスできるように、明らかに 4 つの 2 ビット シンボル (1 バイト) に圧縮されており、次のようにエンコードされることがよくあります。

00 bはエラーを表す

01 bはシフトを表す

10 bはREDUCEを表す

11 bはSTOPを表す

(STOP は SHIFT の特殊なケースです)。配列全体には通常、主に ERROR 構成、文法で定義された数の SHIFT および REDUCE 構成、および 1 つの STOP 構成が含まれます。

XPL などの4 進数システム(基数 4、4 進数桁ごとに 2 ビット) の値の指定をサポートするプログラミング システムでは、これらは次のようにコード化されます。

「(2)… 0 …」はエラーを表す

「(2)… 1 …」はSHIFTを表す

「(2)… 2 …」はREDUCEを表す

「（2）… 3 …」はSTOPを表す

SHIFT テーブルと REDUCE テーブルは、配列とは別に実装されます。補助配列は、現在の状態と先読みシンボルについてのみ「プローブ」されます。(補助) 配列は「完全」ですが、(シフトおよびリデュース) テーブルは実際には非常に「まばら」である可能性があり、それらの SHIFT テーブルと REDUCE テーブルを最適に「分解」することで、大幅な効率化が達成される可能性があります (ERROR と STOP にはテーブルは必要ありません)。

SHIFT-REDUCE パーサーの基本的な定義から、SHIFT と REDUCE の構成は明らかです。

STOP は、スタックの最上部の状態と先読み終端記号が対象文法内にある構成を表し、プログラムの終了を表します。

⊥ <プログラム> • ⊥

最後の⊥を超えてシフトすることは不可能なので、概念的には

⊥ <プログラム> ⊥ •

ERROR は、スタックの最上部の状態と先読み終端記号が対象の文法内にない構成を表します。これは、エラー回復手順を呼び出す機会を提供します。おそらく、最も単純な形式では、先読み終端記号を破棄して次の終端記号を読み取りますが、スタックのプルーニング、または先読み終端記号を破棄してスタックをプルーニングするなど、他の多くのプログラムされたアクションが可能です(異常なケースでは、通常、次の操作を実行できます)。

⊥ <プログラム> • ⊥

<program> は「null ステートメント」のみで構成されます。

ほとんどの場合、スタックは意図的に事前にロード、つまり初期化され、

⊥ • <プログラム> ⊥

これによって、最初の⊥はすでに認識されているとみなされます。これはプログラムの開始を表し、それによって、概念的には

• ⊥ <プログラム> ⊥

⊥ は、文法に機械的に追加された特殊な擬似終端記号です。これは、<program> が文法に機械的に追加された特殊な擬似非終端記号であるのと同じです (プログラマーが文法に <program> を明示的に含めなかった場合、プログラマーに代わって <program> が自動的に文法に追加されます)。

明らかに、このようなパーサーには 1 つの (暗黙的な) START 構成と 1 つの (明示的な) STOP 構成がありますが、数百の SHIFT 構成と REDUCE 構成、さらには数千の ERROR 構成を持つこともできます (通常はそうします)。