標準的なLRパーサー

標準的なLRパーサー（LR(1)パーサーとも呼ばれる）は、コンピュータサイエンスでプログラミング言語を分析および処理するために使用されるボトムアップ解析アルゴリズムの一種です。これは、「左から右、右端から逆の導出」を表す LR解析手法に基づいています。

正式には、標準的な LR パーサーはk=1のLR(k)パーサー、つまり単一の先読み終端を持つものです。このパーサーの特別な属性は、k>1 の任意の LR(k) 文法をLR(1) 文法に変換できることです。^[1]ただし、k を減らすには後方置換が必要であり、後方置換が増えると、文法はすぐに大きくなり、反復的になり、理解しにくくなります。LR(k) は、すべての決定論的文脈自由言語を処理できます。^[1] これまで、この LR(k) パーサーは、その膨大なメモリ要件のために、LALRやLL(1)パーサーなどのそれほど強力ではない代替手段に取って代わられてきました。しかし、最近では、スペース要件が LALR パーサーに近い「最小限の LR(1) パーサー」^[要出典]が、いくつかのパーサー ジェネレーターによって提供されています。

ほとんどのパーサーと同様に、LR(1)パーサーはGNU Bison、MSTA、Menhir、^[2] HYACC、^[3] LRSTARなどのコンパイラーによって自動的に生成されます。 ^[4]

1965年、ドナルド・クヌースは、既存の優先順位パーサーを一般化したシフトリデュースパーサーの一種であるLR(k)パーサー（左から右、右端の導出パーサー）を発明しました。このパーサーは、すべての決定論的文脈自由言語を認識する可能性があり、入力ファイルで検出された文の左導出と右導出の両方を生成できます。クヌースは、このパーサーがk=1のときに最大の言語認識力に達することを証明し、LR(k)、k > 1の文法をLR(1)文法に変換する方法を提供しました。^[1]

標準的なLR(1)パーサーは、内部のパーサーテーブル表現に膨大なメモリを必要とするという実際上の欠点があります。1969年に、Frank DeRemerは、LALRとSLRと呼ばれるLRパーサーの2つの簡略化されたバージョンを提案しました。これらのパーサーは、標準的なLR(1)パーサーよりもはるかに少ないメモリしか必要としませんが、言語認識能力はわずかに劣ります。^[5] LALR(1)パーサーは、LRパーサーの最も一般的な実装です。

^{しかし、1977年にDavid Pager [6]}によって「最小LR(1)パーサー」と呼ばれる新しいタイプのLR(1)パーサーが導入され、メモリ要件がLALR(1)パーサーに匹敵するLR(1)パーサーを作成できることが示されました。最近^{[いつ? ]}、一部のパーサージェネレーターは、メモリ要件の問題を解決するだけでなく、LALR(1)パーサージェネレーターに固有の不可解な競合問題も解決する最小LR(1)パーサーを提供しています。^[要出典]さらに、最小LR(1)パーサーはシフトリデュースアクションを使用できるため、標準LR(1)パーサーよりも高速になります。

LR(1)パーサーは決定論的オートマトンであり、その動作は静的状態遷移表に基づいています。これらは認識する言語の文法を体系化したもので、通常は「解析表」と呼ばれます。

LR(1)パーサの構文解析テーブルは先読みターミナルでパラメータ化される。LR (0)パーサで使用されるような単純な構文解析テーブルは、次のような文法規則を表す。

A1 → AB

つまり、入力Aの後にBが続く場合、その後に続く内容に関係なく、ペアはA1に縮小されます。このようなルールを先読みでパラメータ化すると、次のようになります。

A1 → AB、a

これは、先読み終端が である場合にのみ縮約が実行されることを意味します。これにより、先読みコンテキストに応じて単純な規則が異なる意味を持つことができる、より豊富な言語が可能になります。たとえば、LR(1) 文法では、次のすべての規則は同じ状態シーケンスに基づいているにもかかわらず、異なる縮約を実行します。

A1 → AB、a

A2 → AB、b

A3 → AB、c

A4 → AB、d

先読み終端が考慮されていない場合は、同じことは当てはまりません。構文解析エラーは、いくつかのルールをエラーとして宣言することで、パーサーが入力全体を読み込まなくても識別できます。たとえば、

E1 → BC、d

エラーとして宣言され、パーサーが停止する可能性があります。つまり、次の例のように、先読み情報を使用してエラーをキャッチすることもできます。

A1 → AB、a

A1 → AB、b

A1 → AB、c

E1 → AB、d

この場合、先読みが a、b、または c のときは AB は A1 に縮小され、先読みが d のときはエラーが報告されます。

先読みは、ルールを縮小するタイミングを決定する際にも役立ちます。先読みが有効でない場合、つまり現在の状態を前の状態ではなく次の状態と組み合わせる必要がある場合、先読みによって特定のルールが縮小されるのを防ぐことができます。つまり、次の例では

• 入力シーケンス: ABC
• ルール:

A1 → AB

A2 → BC

このシーケンスは次のように簡略化できる。

A2 の

の代わりに

A1C

パーサが状態Bに移行した後の先読みが受け入れられない場合、つまり遷移規則が存在しない場合。縮約は次のように終端から直接生成できます。

X → y

これにより、複数のシーケンスを表示できるようになります。

LR(1)パーサでは、各ルールが完全なLR(1)方式、つまり特定の先読みを伴う2つの状態のシーケンスで表現される必要がある。そのため、次のような単純なルールは

X → y

本質的には、起こり得るすべての状態と先読み終端の組み合わせを列挙する、非常に多くの人工的な規則を必要とする。同様の問題は、次のような先読み規則を実装する場合にも発生する。

A1 → AB

ここではすべての可能な先読みを列挙する必要がある。これが、LR(1)パーサが大幅なメモリ最適化なしには実質的に実装できない理由である。^[6]

LR(1)解析テーブルは、各項目に先読み終端記号が含まれるという変更を加えたLR(0)解析テーブルと同じ方法で構築されます。つまり、LR(0)パーサーとは異なり、処理する項目の後に異なる終端記号が続く場合は、異なるアクションが実行される場合があります。

言語の生成規則から始めて、まずその言語の項目セットを決定する必要があります。簡単に言えば、項目セットとは、現在処理中のシンボルが含まれる可能性のある生成規則のリストです。項目セットはパーサーの状態と 1 対 1 で対応しており、セット内の項目は次のシンボルとともに、どの状態遷移とパーサー アクションを適用するかを決定するために使用されます。各項目にはマーカーが含まれており、現在処理中のシンボルが項目が表す規則のどの時点で出現するかが示されます。LR(1) パーサーの場合、各項目は先読みターミナルに固有であるため、先読みターミナルも各項目内に示されています。

たとえば、終端記号「n」、「+」、「(」、「)」、非終端記号「E」、「T」、開始規則「S」、および次の生成規則で構成される言語を想定します。

南→東

E → T

え → ( え )

T → n

T → + T

T → T + n

アイテムセットは、LR(0)パーサーの手順と同様に生成されます。初期状態を表すアイテムセット0は、開始ルールから作成されます。

[S → • E, $]

ドット「•」は、このルール内の現在の解析位置のマーカーを示します。このルールを適用するために予想される先読みターミナルは、コンマの後に示されます。「$」記号は、開始ルールの場合と同様に、「入力の終了」が予想されることを示すために使用されます。

ただし、これは完全なアイテム セット 0 ではありません。各アイテム セットは「閉じている」必要があります。つまり、「•」に続く各非終端記号のすべての生成ルールは、それらのすべての非終端記号が処理されるまで、アイテム セットに再帰的に含める必要があります。結果として得られるアイテム セットは、開始時のアイテム セットの閉包と呼ばれます。

LR(1) では、各生成規則に対して、規則に続く可能性のある先読み終端記号ごとに項目を含める必要があります。より複雑な言語の場合、通常、この結果項目セットが非常に大きくなります。これが、LR(1) パーサーのメモリ要件が大きくなる理由です。

この例では、開始シンボルには非終端記号「E」が必要で、非終端記号には「T」が必要なので、すべての生成ルールは項目セット 0 に出現します。最初は、先読みを見つける問題を無視し、項目に先読み終端記号が含まれていない LR(0) のケースだけを見ます。したがって、項目セット 0 (先読みなし) は次のようになります。

[S → • E]

[E → • T]

[E → • ( E )]

[T → • n]

[T → • + T]

[T → • T + n]

先読み終端記号を決定するために、いわゆる FIRST 集合と FOLLOW 集合が使用されます。FIRST(A) は、非終端記号 A に一致する規則のチェーンの最初の要素として出現できる終端記号の集合です。項目 I [A → α • B β, x] の FOLLOW(I) は、非終端記号B の直後に出現できる終端記号の集合です。ここで、α、β は任意の記号文字列、x は任意の先読み終端記号です。項目集合 k と非終端記号 B の FOLLOW(k,B) は、k 内のすべての項目のうち、'•' の後に B が続く項目のフォロー集合の和集合です。FIRST 集合は、言語内のすべての非終端記号の閉包から直接決定できますが、FOLLOW 集合は、FIRST 集合の使用下にある項目から決定されます。

この例では、以下のアイテム セットの完全なリストから確認できるように、最初のセットは次のとおりです。

最初(S) = { n, '+', '(' }

最初(E) = { n, '+', '(' }

最初(T) = {n, '+'}

アイテム セット 0 内には、次のセットが含まれます。

フォロー(0,S) = { $ }

フォロー(0,E) = { $, ')'}

FOLLOW(0,T) = { $, '+', ')' }

これから、LR(0) 項目セットの各項目に対して、LHS 非終端記号のフォロー セット内の各終端記号のコピーを 1 つ作成することで、LR(1) パーサーの完全な項目セット 0 を作成できます。フォロー セットの各要素は、有効な先読み終端記号である可能性があります。

[S → • E, $]

[E → • T, $]

[E → • T, )]

[E → • ( E ), $]

[E → • ( E ), )]

[T → • n, $]

[T → • n, +]

[T → • n, )]

[T → • + T, $]

[T → • + T, +]

[T → • + T, )]

[T → • T + n, $]

[T → • T + n, +]

[T → • T + n, )]

残りのアイテムセットは次のアルゴリズムで作成できます。

1. 既存の各項目セット k 内の '•' の後に現れる各終端記号および非終端記号 A について、'•' の後に A が続く k のすべての規則を m に追加して新しい項目セット m を作成します。ただし、手順 3 の後に m が既存の項目セットと同じにならない場合に限ります。

2. 新しい項目セットの各ルールの「•」をすべて1つ右にシフトします。

3. 新しいアイテムセットのクロージャを作成する

4. 新しく作成されたすべてのアイテムセットに対して、新しいセットが表示されなくなるまで手順1から繰り返します。

この例では、項目セット 0、非終端記号 E の項目セット 1、非終端記号 T の項目セット 2、終端記号 n の項目セット 3、終端記号 '+' の項目セット 4、および '(' の項目セット 5 からさらに 5 つのセットを取得します。

アイテムセット1（E）：

[S → E •, $]

アイテムセット2（T）：

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

·

·

·

アイテムセット3 (n):

[T → n •, $]

[T → n •, +]

[T → n •, )]

アイテムセット4（'+'）：

[T → + • T, $]

[T → + • T, +]

[T → • n, $]

[T → • n, +]

[T → • + T, $]

[T → • + T, +]

[T → • T + n, $]

[T → • T + n, +]

·

·

·

アイテムセット5 ('('):

[E → ( • E )、$]

[E → • T, )]

[E → • ( E ), )]

[T → • n, )]

[T → • n, +]

[T → • + T, )]

[T → • + T, +]

[T → • T + n, )]

[T → • T + n, +]

·

·

·

アイテムセット2、4、5からは、さらにいくつかのアイテムセットが生成されます。完全なリストは非常に長いため、ここでは述べません。この文法の詳細なLR(k)処理については、たとえば[1]を参照してください。

LR(1)項目の先読みは、reduceアクションを考慮するとき（つまり、•マーカーが右端にあるとき）にのみ直接使用されます。

LR(1)項目[S → a A • B e, c]のコアはLR(0)項目S → a A • B eである。異なるLR(1)項目は同じコアを共有することがある。

例えば、アイテムセット2では

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

パーサーは、次のシンボルが '$' の場合は [E → T] の削減を実行する必要がありますが、次のシンボルが '+' の場合はシフトを実行する必要があります。LR(0) パーサーは項目のコアのみを考慮するため、この決定を行うことができず、シフト/削減の競合を報告することに注意してください。

[A → α • X β, a] を含む状態は、ラベル X を持つ [A → α X • β, a] を含む状態に移動します。

Goto によれば、すべての状態には遷移があります。

_{[A → α • b β, a]が状態I k}にあり、I _kがラベルbの状態I _mに移動する場合には、アクションを追加する。

アクション[I _k , b] = "シフトm"

[A→α •, a]が状態I _kにある場合、アクション

action[I _k , a] = 「A → α を減らす」

• 実用的な LR(k) パーサー構築 HTML ページ、David Tribble
• Python での First および Follow セットの構築 (Narayana Chikkam)