LL対。LR解析

1. 序章

このチュートリアルでは、産業界と学界で広く採用されている2種類のパーサー（LLパーサーとLRパーサー）の違いについて説明します。 理解を深めるために、文法理論を使用してそれらを対比します。

2. コンパイルプロセスの概要

両方の種類のパーサーは、コンパイルプロセスの構文解析フェーズに適合します。 コンパイラは、それぞれ異なる入力と出力を持ついくつかの抽象化レイヤーを介してソースコードを処理します。 このパイプラインの最後の最終出力は、コンパイラが実行されたマシンのアーキテクチャを対象とした、十分に最適化されたマシンコードです。 そのため、パーサーは、実行時間の点で効率的であると同時に、元のソースコードが記述された文法を処理するのに十分強力である必要があります。

以下の古典的な定式化では、字句解析器はトークンのストリームを出力し、パーサーが主要コンポーネントである構文解析器は解析ツリーを生成します。 パーサーの実装方法、解析ツリーの構築方法、およびパーサーが処理できる文法の種類は、LLとLRの基本的な違いを特徴づけます。

3. 比較

3.1. 解析ツリーの構築

LL解析は、トップダウンパラダイムに準拠しています。 言い換えると、解析ツリーはルートから開始して構築され、各ノードは事前注文パターンで構築されます。 これは、入力文字列に適した左端の派生を見つける問題と見なすことができます。 たとえば、プロダクションルールがであり、必要な終端記号の文字列がである場合、考えられる左端の派生の1つはです。

トップダウン構文解析の各ステップで、パーサーは、指定された非終端記号に適用される生成規則を決定します。 プロダクションルールが選択されると、プロダクションルールの本体にある終端記号が入力文字列と照合されます。 次に、入力の前にある記号を調べることで正しい生成規則を選択できるかのように、文法が指定されます。 の一般的な値はです。

対照的に、LR解析はボトムアップパラダイムに準拠しています。 入力文字列の解析ツリーは、リーフから開始して構築され、ルートに到達するまで解析が上向きに続行されます。 目標は、入力文字列を文法の開始記号に減らすか、逆に右端の派生を構築することです。

解析プロセスは、開始シンボルに近づくまでの一連のシフトアクションとリデュースアクションで構成されます。 各ステップで、プロダクションルール本体に一致する特定のサブストリングが、対応する非終端記号に置き換えられます。 このような部分文字列はハンドルと呼ばれます。 たとえば、単純な数式と入力文字列を表す一連の生成ルールが与えられた場合、逆に移動します–。 この場合、は開始記号であることに注意してください。 指定と同様に、先の記号で入力を読み取ることができるかのように文法を示します。

3.2. 受け入れられた文法

またはとして指定される文法には特定の規則があります。 解析プロセス中に競合が発生することはありません。これは、文法が特定のパーサーに適していないことを意味するためです。 1つの例は、パーサーでのシフトと削減の競合の例です。この場合、あるステップで、パーサーはシフトと削減アクションのどちらかを決定的に選択できません。

文法は、非終端記号であるプロダクションルールが存在する場合にのみ、次のようになります。

• 終端記号がない場合は、で始まる文字列を実行して派生させます。
• 2つの非終端記号のうち最大で1つがヌル記号を導出できます。
• null記号を導出する場合、のセット内の終端で始まる文字列を導出することはできません。

最初の2つの条件は、として要約できます。 最後の条件は、として要約できます。ここで、およびは通常の方法で定義されます。 同様に、これらの規則は、任意の正の整数を持つ文法に対して一般化できます。

対照的に、傘の下にはさまざまなパーサーと対応する文法があります。 パーサーの能力は、受け入れられた文法のサブセットの大きさに従って定義されます。 パーサーの中で、パーサーはこのパワースケールの一番下にあります。

LRパーサーはステートオートマトンを利用します。受け入れられる文法のルールを定義するときに、ステート内のアイテムセットを考慮します。 たとえば、文法はパーサーによって受け入れられるかどうかです。これは次の条件下で発生します-：

• 各アイテムセット、およびそれらのセット内のすべてのアイテム（端末）について、セット内に完全なアイテムはありません。ここで、。 これは、shift-reduceの競合が存在できないことを意味します。
• 完全なアイテムのすべてのペアと、。 これは、reduce-reduceの競合が存在できないことを意味します。

完全なアイテムとは、ドットがプロダクションルールの最後にあるアイテムであり、パーサーがそのプロダクションルールを使用してのみreduceアクションを実行できる場合を指します。

カノニカルなどの強力なパーサーは、受け入れる文法について同様のルールを持っています。 文法は文法のサブセットであるため、パーサーはパーサーよりもパワーが少ないことに注意してください。

3.3. 制限事項

テーブル駆動型予測パーサーなどのLLパーサーは、左再帰生成ルールを持つ文法からの文字列を処理できません。 直感的には、これは、左端の派生を処理しようとしているときに無限ループになる可能性があるためです。 このような派生の以前の例では、この理由から、文法でルールを許可することはできません。 ただし、パーサーにはこのような弱点はなく、左再帰ルールを持つ文法からの入力文字列を処理できます。

人気のあるトップダウンパーサーの中で、再帰下降パーサーはセット外の文法からの文字列を処理できますが、文法がそうでない場合、実行が終了することは保証されないことに注意してください。 実際、終了したとしても、最悪の場合は指数関数的な時間がかかる場合があります。 これは、セット外の文法からの文字列をまったく処理できないテーブル駆動型予測パーサーとは対照的です。 したがって、これらは両方とも主にパーサーと見なされます。

LLパーサーとLRパーサーの両方で、あいまいな文法からの文字列の処理に問題があります。 あいまいさは構文解析プロセスに競合を挿入するため、あいまいな文法のセットは通常、/文法のセットとは別のものと見なされます。 ただし、あいまいさを処理できるパーサーはありませんが、演算子文法と呼ばれる文法のサブセットを処理できるタイプのパーサーがあります。 このパーサーは、適切には演算子優先順位パーサーと呼ばれます。

従来の意味でのあいまいさ（次に適用するルール）は、演算子文法で許可されます。 これは、プロダクションルールが相対的な優先順位を割り当てる方法でフレーム化されているためです。 演算子優先順位パーサーは、実行中にこれらの優先順位ルールを利用して、あいまいさを解消します。

4. 結論

要約すると、パーサーとパーサーの違いのいくつかについて詳しく説明しました。 より深く、より基本的な理解のために、文法理論を掘り下げました。 その過程で、いくつかの種類のパーサーについて説明しました。