253

LL 構文解析と LR 構文解析の簡単な例を教えてください。

4

4 に答える 4

526

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

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

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

  1. Predict : 左端の非終端記号といくつかの先読みトークンに基づいて、入力文字列に近づくために適用するプロダクションを選択します。
  2. Match : 左端の推測された終端記号を入力の左端の未使用記号と一致させます。

例として、次の文法を考えます。

  • 南→東
  • E → T + E
  • え→た
  • た→int

次に、 string が与えられる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 つのアクションがあります。

  1. Shift : 入力の次のトークンを検討のためにバッファに追加します。
  2. 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ますbison。LL パーサーにも多くの種類があります (ANTLRツールで使用される LL(*) を含む) が、実際には LL(1) が最も広く使用されています。

恥知らずなプラグインとして、LL および LR 構文解析について詳しく知りたい場合は、コンパイラ コースの指導を終えたばかりで、コースの Web サイトで構文解析に関する配布資料と講義スライドをいくつか用意しています。役に立つと思われる場合は、それらのいずれかについて詳しく説明していただければ幸いです。

于 2011-07-26T02:21:59.613 に答える
61

Josh Haberman は、自身の記事LL and LR Parsing Demystifiedで、LL 解析は直接ポーランド表記に対応し、LR は逆ポーランド表記に対応すると主張しています。PN と RPN の違いは、方程式のバイナリ ツリーをトラバースする順序です。

方程式の二分木

+ 1 * 2 3  // Polish (prefix) expression; pre-order traversal.
1 2 3 * +  // Reverse Polish (postfix) expression; post-order traversal.

Haberman によると、これは LL パーサーと LR パーサーの主な違いを示しています。

LL パーサーと LR パーサーの動作方法の主な違いは、LL パーサーが構文解析ツリーの前順トラバーサルを出力し、LR パーサーが後順トラバーサルを出力することです。

詳細な説明、例、および結論については、Haberman の記事を参照してください。

于 2013-08-14T18:37:36.187 に答える
11

LL 構文解析は、LR と比較すると不利です。以下は、LL パーサー ジェネレーターにとって悪夢のような文法です。

Goal           -> (FunctionDef | FunctionDecl)* <eof>                  

FunctionDef    -> TypeSpec FuncName '(' [Arg/','+] ')' '{' '}'       

FunctionDecl   -> TypeSpec FuncName '(' [Arg/','+] ')' ';'            

TypeSpec       -> int        
               -> char '*' '*'                
               -> long                 
               -> short                   

FuncName       -> IDENTIFIER                

Arg            -> TypeSpec ArgName         

ArgName        -> IDENTIFIER

FunctionDef は、';' までは FunctionDecl とまったく同じように見えます。または '{' が検出されました。

LL パーサーは 2 つのルールを同時に処理できないため、FunctionDef または FunctionDecl のいずれかを選択する必要があります。しかし、どちらが正しいかを知るには、「;」を先読みする必要があります。また '{'。文法分析時には、先読み (k) は無限に見えます。解析時には有限ですが、大きくなる可能性があります。

LR パーサーは、2 つのルールを同時に処理できるため、先読みする必要はありません。そのため、LALR(1) パーサー ジェネレーターはこの文法を簡単に処理できます。

入力コードが与えられた場合:

int main (int na, char** arg); 

int main (int na, char** arg) 
{

}

LR パーサーは、

int main (int na, char** arg)

「;」に遭遇するまで、どのルールが認識されているかを気にせずに または「{」。

LL パーサーは、どのルールが認識されているかを知る必要があるため、「int」でハングアップします。したがって、「;」を先読みする必要があります。また '{'。

LL パーサーのもう 1 つの悪夢は、文法の左再帰です。左再帰は文法では普通のことであり、LR パーサー ジェネレーターにとっては問題ありませんが、LL はそれを処理できません。

そのため、LL では不自然な方法で文法を記述しなければなりません。

于 2019-06-08T03:15:54.293 に答える