LL 解析と LR 解析の違いは何ですか? 質問する

Question

大まかに言えば、LL 解析と LR 解析の違いは、LL パーサーは開始シンボルから開始し、生成物を適用してターゲット文字列に到達しようとするのに対し、LR パーサーはターゲット文字列から開始し、開始シンボルに戻ろうとすることです。

LL 解析は、左から右、左端の導出です。つまり、入力シンボルを左から右に検討し、左端の導出を構築しようとします。これは、開始シンボルから始めて、ターゲット文字列に到達するまで左端の非終端記号を繰り返し展開することによって行われます。LR 解析は、左から右、右端の導出です。つまり、左から右にスキャンし、右端の導出を構築しようとします。パーサーは、入力のサブ文字列を継続的に選択し、それを非終端記号に戻そうとします。

LL 解析中、パーサーは次の 2 つのアクションを継続的に選択します。

予測: 最も左の非終端記号といくつかの先読みトークンに基づいて、入力文字列に近づくためにどの生成を適用する必要があるかを選択します。
一致: 最も左の推測された終端記号を入力の最も左の未使用記号と一致させます。

例として、次の文法があるとします。

南→東
E → T + E
東→東
て→int

次に、文字列が与えられるとint + int + int、LL(2)パーサー（先読みのトークンを2つ使用）は次のように文字列を解析します。

Production       Input              Action
---------------------------------------------------------
S                int + int + int    Predict S -> E
E                int + int + int    Predict E -> T + E
T + E            int + int + int    Predict T -> int
int + E          int + int + int    Match int
+ E              + int + int        Match +
E                int + int          Predict E -> T + E
T + E            int + int          Predict T -> int
int + E          int + int          Match int
+ E              + int              Match +
E                int                Predict E -> T
T                int                Predict T -> int
int              int                Match int
                                    Accept

各ステップで、生成物の一番左のシンボルを確認することに注意してください。終端記号の場合は一致させ、非終端記号の場合は、ルールの 1 つを選択して、それが何になるかを予測します。

LR パーサーには、次の 2 つのアクションがあります。

Shift : 検討のために入力の次のトークンをバッファに追加します。
Reduce : 生成を逆にすることで、このバッファ内の終端記号と非終端記号のコレクションを非終端記号に戻します。

たとえば、LR(1)パーサー（先読みトークンが1つある）は、同じ文字列を次のように解析します。

Workspace        Input              Action
---------------------------------------------------------
                 int + int + int    Shift
int              + int + int        Reduce T -> int
T                + int + int        Shift
T +              int + int          Shift
T + int          + int              Reduce T -> int
T + T            + int              Shift
T + T +          int                Shift
T + T + int                         Reduce T -> int
T + T + T                           Reduce E -> T
T + T + E                           Reduce E -> T + E
T + E                               Reduce E -> T + E
E                                   Reduce S -> E
S                                   Accept

あなたが言及した 2 つの解析アルゴリズム (LL と LR) は、異なる特性を持つことが知られています。LL パーサーは手で書く方が簡単な傾向がありますが、LR パーサーほど強力ではなく、LR パーサーよりもはるかに少ない文法セットしか受け入れません。LR パーサーにはさまざまな種類 (LR(0)、SLR(1)、LALR(1)、LR(1)、IELR(1)、GLR(0) など) があり、はるかに強力です。また、はるかに複雑になる傾向があり、ほとんどの場合、やなどのツールによって生成されますyacc。LLbisonパーサーにもさまざまな種類 (ツールで使用される LL(*) を含む) がありますANTLRが、実際には LL(1) が最も広く使用されています。

恥ずかしげもなく宣伝しますが、LL および LR 構文解析についてさらに詳しく知りたい場合は、コンパイラーコースの指導を終えたばかりで、コースの Web サイトに構文解析に関する配布資料と講義スライドがあります。役に立つと思われる場合は、喜んで詳しく説明します。

Answer 1