Quelle est la différence entre l'analyse LL et LR?

Quelqu'un peut-il me donner un exemple simple de l'analyse LL par rapport à l'analyse LR?

À un niveau élevé, la différence entre l'analyse LL et l'analyse LR est que les analyseurs LL commencent au symbole de début et tentent d'appliquer des productions pour arriver à la chaîne cible, tandis que les analyseurs LR commencent à la chaîne cible et tentent de revenir au début symbole.

Une analyse LL est une dérivation de gauche à droite, la plus à gauche. Autrement dit, nous considérons les symboles d'entrée de gauche à droite et essayons de construire une dérivation la plus à gauche. Pour ce faire, commencez par le symbole de début et développez à plusieurs reprises le non terminal le plus à gauche jusqu'à ce que nous arrivions à la chaîne cible. Une analyse LR est une dérivation de gauche à droite, la plus à droite, ce qui signifie que nous balayons de gauche à droite et essayons de construire une dérivation la plus à droite. L'analyseur sélectionne en continu une sous-chaîne de l'entrée et tente de la retourner à un non terminal.

Pendant une analyse LL, l'analyseur choisit en continu entre deux actions:

1. Prédire : en fonction du jeton non terminal le plus à gauche et d'un certain nombre de jetons d'anticipation, choisissez la production à appliquer pour vous rapprocher de la chaîne d'entrée.
2. Correspondance : Faites correspondre le symbole de terminal deviné le plus à gauche avec le symbole d'entrée non consommé le plus à gauche.

À titre d'exemple, étant donné cette grammaire:

• S → E
• E → T + E
• E → T
• T → int

Puis, étant donné la chaîne int + int + int, un analyseur LL (2) (qui utilise deux jetons d'anticipation) analyserait la chaîne comme suit:

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

Notez qu'à chaque étape, nous regardons le symbole le plus à gauche de notre production. S'il s'agit d'un terminal, nous l'associons, et s'il s'agit d'un terminal non terminal, nous prédisons ce que ce sera en choisissant l'une des règles.

Dans un analyseur LR, il y a deux actions:

1. Maj : ajoutez le prochain jeton d'entrée à un tampon pour examen.
2. Réduire : réduisez une collection de terminaux et de terminaux non terminés dans ce tampon à certains terminaux non terminaux en inversant une production.

Par exemple, un analyseur LR (1) (avec un jeton d'anticipation) peut analyser la même chaîne comme suit:

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

Les deux algorithmes d'analyse que vous avez mentionnés (LL et LR) sont connus pour avoir des caractéristiques différentes. Les analyseurs LL ont tendance à être plus faciles à écrire à la main, mais ils sont moins puissants que les analyseurs LR et acceptent un ensemble de grammaires beaucoup plus petit que les analyseurs LR. Les analyseurs LR sont disponibles en plusieurs versions (LR (0), SLR (1), LALR (1), LR (1), IELR (1), GLR (0), etc.) et sont beaucoup plus puissants. Ils ont également tendance à être beaucoup plus complexes et sont presque toujours générés par des outils comme yaccou bison. Les analyseurs LL existent également dans de nombreuses versions (y compris LL (*), qui est utilisé par l' ANTLRoutil), bien qu'en pratique LL (1) soit le plus largement utilisé.

En tant que plug sans vergogne, si vous souhaitez en savoir plus sur l'analyse syntaxique LL et LR, je viens de terminer l'enseignement d'un cours de compilation et j'ai des documents et des diapositives de conférence sur l'analyse syntaxique sur le site Web du cours. Je serais ravi de vous en dire plus si vous pensez que cela serait utile.

Josh Haberman dans son article LL and LR Parsing Demystified affirme que l'analyse LL correspond directement à la notation polonaise , tandis que LR correspond à la notation polonaise inversée . La différence entre PN et RPN est l'ordre de traversée de l'arbre binaire de l'équation:

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

Selon Haberman, cela illustre la principale différence entre les analyseurs LL et LR:

La principale différence entre le fonctionnement des analyseurs LL et LR est qu'un analyseur LL génère un parcours de pré-commande de l'arbre d'analyse et un analyseur LR génère un parcours de post-ordre.

Pour une explication approfondie, des exemples et des conclusions, consultez l' article de Haberman .

Le LL utilise une approche descendante, tandis que le LR utilise une approche ascendante.

Si vous analysez une langue de programmation:

• Le LL voit un code source, qui contient des fonctions, qui contient l'expression.
• Le LR voit l'expression, qui appartient aux fonctions, qui résulte de la source complète.

L'analyse LL est handicapée par rapport à LR. Voici une grammaire qui est un cauchemar pour un générateur d'analyseur 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 

Un FunctionDef ressemble exactement à un FunctionDecl jusqu'à ce que le ';' ou '{' est rencontré.

Un analyseur LL ne peut pas gérer deux règles en même temps, il doit donc choisir FunctionDef ou FunctionDecl. Mais pour savoir ce qui est correct, il doit chercher un ';' ou '{'. Au moment de l'analyse grammaticale, l'anticipation (k) semble infinie. Au moment de l'analyse, il est fini, mais peut être volumineux.

Un analyseur LR n'a pas besoin de regarder en avant, car il peut gérer deux règles en même temps. Les générateurs d'analyseurs LALR (1) peuvent donc gérer cette grammaire avec facilité.

Étant donné le code d'entrée:

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

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

}

Un analyseur LR peut analyser le

int main (int na, char** arg)

sans se soucier de quelle règle est reconnue jusqu'à ce qu'elle rencontre un ';' ou un «{».

Un analyseur LL se bloque à l'int 'car il a besoin de savoir quelle règle est reconnue. Par conséquent, il doit chercher un ';' ou '{'.

L'autre cauchemar pour les analyseurs LL est la récursion gauche dans une grammaire. La récursivité gauche est une chose normale dans les grammaires, pas de problème pour un générateur d'analyseur LR, mais LL ne peut pas le gérer.

Vous devez donc écrire vos grammaires de manière non naturelle avec LL.

Exemple de dérivation le plus à gauche: une grammaire G qui est sans contexte a les productions

z → xXY (règle: 1) X → Ybx (règle: 2) Y → bY (règle: 3) Y → c (règle: 4)

Calculez la chaîne w = 'xcbxbc' avec la dérivation la plus à gauche.

z ⇒ xXY (règle: 1) ⇒ xYbxY (règle: 2) ⇒ xcbxY (règle: 4) ⇒ xcbxbY (règle: 3) ⇒ xcbxbc (règle: 4)

Exemple de dérivation la plus à droite: K → aKK (règle: 1) A → b (règle: 2)

Calculez la chaîne w = 'aababbb' avec la dérivation la plus à droite.

K ⇒ aKK (règle: 1) ⇒ aKb (règle: 2) ⇒ aaKKb (règle: 1) ⇒ aaKaKKb (règle: 1) ⇒ aaKaKbb (règle: 2) ⇒ aaKabbb (règle: 2) ⇒ aababbb (règle: 2)