🌐LL LR SLR LALR CLRなどややこしい構文解析のアプローチ

2021年7月24日 09:08

LL、LR、SLR、LALR、CLR はパーサー（構文解析器）の種類です。パーサーは、コンパイラの一部として使用され、ソースコードを抽象構文木（AST）に変換します。これらの略語は、各パーサーがどのように構文解析を行うかを表しています。

まずはボトムアップ(LR)、トップダウン（LL）の差を知ろう

ボトムアップ(LR)

ボトムアップ構文解析では、まずテキストの最下層の細部を認識し、次に中層の構造を認識し、最上層の全体構造を最後に認識します。
ボトムアップ解析では、左下端からツリーを検出して処理し、徐々に上方および右方向に作業を進めます。パーサーは、実際のデータツリーを作成せずに、構造階層の低レベル、中間レベル、および最上レベルに対処することができます。ボトムアップ構文解析は、ある構成要素のすべての部分をスキャンして解析するまで辛抱強く待ち、結合された構成要素が何であるかを確定させます。

トップダウン(LL)

この逆がトップダウンパーシングで、入力の全体的な構造を最初に決定（または推測）してから、中間レベルの部分を処理し、すべての最下位レベルの詳細の完成を最後に残すというものである。トップダウンパーサーは、階層ツリーを発見し、上から順に処理し、まず下へ、次に右へと漸進的に作業を進めます。トップダウンパーサーは、構成要素の左端の記号をスキャンしただけで、その構成要素のどの部分もまだ解析していないときに、その構成要素が何であるかをかなり早い段階で熱心に決定します。左隅解析は、各サブツリーの左端に沿ったボトムアップと、解析ツリーの残りの部分に対するトップダウンの両方式を実行するハイブリッド手法です。

トップダウン・パーサーには、デバッグが簡単であること、文法内の任意の非終端まで解析できること、解析中に解析木の上下に値（属性）を渡すことができることなど、（より一般的な文法以外にも）多くの利点があります。

大きくLR（ボトムアップ）とLL（トップダウン）があって、LRの種類がたいへん多い

ボトムアップ構文解析はバックトラックによって行われることもあります。しかし、より一般的には、ボトムアップパーシングは LALR パーサーなどのシフトリダクションパーサーによって行われます。

構文木についても知る

コンピュータサイエンスの分野では、プログラミング言語で書かれたソースコードの抽象的な構文構造を木で表現したものを抽象構文木（AST）と呼んでいる。

LR

コンピュータサイエンスでは、LR パーサーは決定論的文脈自由言語を線形時間で解析するボトムアップパーサーの一種である

LR パーサーは決定論的であり、推測やバックトラックを行わず、線形時間内に正しい構文を 1 つだけ生成します。これはコンピュータ言語には理想的ですが、LR パーサーは人間の言語には適しておらず、より柔軟な方法が必要ですが、必然的に時間がかかることになります。

LR パーサーは先行パーサーやトップダウン LL 構文解析よりも広範囲の言語と文法を処理できます。これは LR パーサーが見つけたものに専念する前に、ある文法パターンのインスタンスの全体を見るまで待っているからです[3]。LLパーサーは、そのパターンの左端の入力記号を見ただけで、何を見たかをもっと早く決定したり推測したりする必要があります。

LL

LL文法、特にLL(1)文法はパーサーの構築が容易であり、多くのコンピュータ言語がLL(1)に設計されているため、実用上非常に興味深い[8]。また、LL文法は再帰的降下パーサーによって解析することができる

LLパーサー（Left-to-right, leftmost derivation）は制限付き文脈自由言語用のトップダウンパーサーである。

構文解析は、トークン列から文法規則に従った文の解析を行うための手法です。その中でも、LL、LR、SLR、LALR、CLRなどのアルゴリズムがあります。

LL: 左から右に読み進め、最も左の導出を採用する再帰下降パーサーを生成する手法です。左再帰に弱いという欠点がありますが、単純な文法に対して高速な処理ができるというメリットがあります。
LR: 左から右に読み進め、最も右の導出を採用するシフト-リデュースパーサーを生成する手法です。スタックを用いた構文解析手法で、強力な文法にも対応できるというメリットがありますが、パーステーブルの生成が複雑であるというデメリットがあります。
SLR: LRの一種で、ステート数を削減することで、パーステーブルのサイズを小さくすることができる手法です。しかし、LRに比べて強力な文法に対応できないというデメリットがあります。
LALR: LRの一種で、パーステーブルのサイズを小さくすることができる手法です。ステート数を削減することで、SLRに比べて強力な文法に対応できるというメリットがありますが、正確性が劣る場合があります。
CLR: LRの一種で、LRよりも強力な文法に対応できる手法です。パーステーブルのサイズが最小であるため、正確性が高いというメリットがありますが、パーステーブルの生成が非常に複雑であるというデメリットがあります。

LALRパーサーは、標準的なLRパーサーを簡略化したものです。

https://en.wikipedia.org/wiki/LALR_parser

文法が左再帰とはどういう事を言いますか？

具体的なプログラミング言語における左再帰文法の例を挙げると、C言語やその派生言語（例えばC++、Java）が良い例です。これらの言語では、特に式の解析に左再帰文法がよく用いられています

文法が左再帰であるとは、その文法の生成規則の中に、ある非終端記号が自身を含む導出規則を持ち、その再帰が左側（導出規則の始めの部分）にある状態を指します。これは構文解析時に特に注意が必要な点で、特にLLパーサーのようなトップダウン構文解析法では問題を引き起こすことがあります。

左再帰は、無限ループに陥る可能性があるため、特にトップダウン構文解析では問題となります。トップダウンパーサーは非終端記号から始めて導出を行うため、左再帰があるとパーサーが無限にその非終端記号の導出を繰り返してしまう可能性があります。

この問題を解決する一つの方法は、

左再帰の除去です。左再帰のある文法を書き換えて、同等の非左再帰的文法に変換することができます。これにより、トップダウンパーサーでも無限ループに陥ることなく、文法を解析することが可能になります。

左再帰の除去の一般的な方法は、左再帰的な規則を右再帰的な規則に書き換えることです。

LL LR SLR LALR CLRなど、コンパイル手法を操作できるツールライブラリはありますか？

コンパイラ構築で使用されるLL、LR、SLR、LALR、CLRなどのパーサ生成アルゴリズムを操作できるツールやライブラリはいくつかあります。これらは、言語の文法を定義し、その文法に基づいてソースコードを解析するパーサを自動生成するために使用されます。以下はそのようなツールやライブラリの例です：

ANTLR (ANother Tool for Language Recognition): LL(*)パーサを生成するための強力なツールです。複数の言語への出力をサポートしており、様々なプログラミング言語で使用することができます。
Bison: GNUプロジェクトの一部として開発されたBisonは、LALRパーサを生成するためのツールです。Yaccの互換性を持つため、多くのUNIXシステムで広く使用されています。
Yacc (Yet Another Compiler Compiler): 伝統的なLRパーサジェネレータであり、多くのUNIXシステムに標準で含まれています。BisonはYaccの代替品として開発されました。
Flex: レキシカルアナライザジェネレータで、BisonやYaccと組み合わせて使用されることが多いです。Flex自体はパーサを生成するものではありませんが、パーサと連携して使用されます。
Gold Parsing System: LR、LALR、およびLLパーシングアルゴリズムをサポートするパーサジェネレータです。柔軟な文法定義と複数のプログラミング言語への出力をサポートしています。
Menhir: OCamlで書かれたLR(1)パーサジェネレータで、OCamlプログラマーにとっての選択肢です。

お願い致します

🌐LL LR SLR LALR CLRなどややこしい 構文解析のアプローチ