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

Question

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

Answer 1

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

Une analyse syntaxique LL est une dérivation de gauche à droite et de gauche à droite. C'est-à-dire que nous considérons les symboles d'entrée de gauche à droite et essayons de construire une dérivation la plus à gauche. Cela se fait en commençant par le symbole de départ et en développant de manière répétée le non terminal le plus à gauche jusqu'à ce que nous arrivions à la chaîne cible. Une analyse syntaxique 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 choisit continuellement une sous-chaîne de l'entrée et tente de l'inverser en un non-terminal.

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

1. Prévoir : Sur la base du non terminal le plus à gauche et d'un certain nombre de tokens lookahead, choisir quelle production doit être appliquée pour se rapprocher de la chaîne d'entrée.
2. Match : Faire correspondre le symbole terminal deviné le plus à gauche avec le symbole non consommé le plus à gauche de l'entrée.

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

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

Puis, étant donné la chaîne de caractères int + int + int un analyseur LL(2) (qui utilise deux tokens de lookahead) 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

Remarquez qu'à chaque étape, nous examinons le symbole le plus à gauche de notre production. Si c'est un terminal, nous le faisons correspondre, et si c'est un non-terminal, nous prédisons ce qu'il va être en choisissant une des règles.

Dans un analyseur LR, il y a deux actions :

1. Équipe : Ajouter le prochain jeton d'entrée à un tampon pour considération.
2. Réduire : Réduire une collection de terminaux et de non-terminaux dans ce tampon à un certain non-terminal en inversant une production.

Par exemple, un analyseur LR(1) (avec un token de lookahead) pourrait analyser cette 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 syntaxique 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 restreint que les analyseurs LR. Les analyseurs LR existent 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 tels que yacc ou bison . Les analyseurs syntaxiques LL existent également sous de nombreuses formes (y compris LL(*), qui est utilisé par le module ANTLR ), bien qu'en pratique, LL(1) soit le plus largement utilisé.

Si vous souhaitez en savoir plus sur l'analyse syntaxique LL et LR, je viens de terminer un cours sur les compilateurs et j'ai des documents et des diapositives de cours sur l'analyse syntaxique sur le site web du cours. Je serais heureux de développer l'un d'entre eux si vous pensez que cela peut être utile.

Answer 2

Josh Haberman dans son article L'analyse syntaxique LL et LR démystifiée prétend que l'analyse syntaxique LL correspond directement à Notation polonaise tandis que LR correspond à 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 syntaxiques LL et LR :

La principale différence entre le fonctionnement des analyseurs LL et LR est qu'un analyseur LL produit une traversée de l'arbre d'analyse dans un ordre préalable, tandis qu'un analyseur LR produit une traversée dans un ordre postérieur.

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

Answer 3

L'analyse syntaxique 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 l'on rencontre le ';' ou '{'. soit rencontrée.

Un analyseur syntaxique LL ne peut pas traiter deux règles en même temps, donc il doit choisir FunctionDef ou FunctionDecl. Mais pour savoir laquelle est correcte, il doit correcte, il doit chercher un ';' ou un '{'. Au moment de l'analyse grammaticale, le lookahead (k) semble être infini. Au moment de l'analyse syntaxique, il est fini, mais pourrait être grande.

Un analyseur LR n'a pas besoin de lookahead, parce qu'il peut traiter deux règles en même temps. Donc les générateurs d'analyseurs LALR(1) peuvent traiter 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 les fichiers

int main (int na, char** arg)

sans se soucier de la règle reconnue jusqu'à ce qu'il rencontre un ';' ou un '{'.

Un analyseur syntaxique LL est bloqué au niveau du 'int' parce qu'il a besoin de savoir quelle règle est réexaminée. règle est reconnue. Il doit donc chercher un ';' ou un '{'.

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

Vous devez donc écrire vos grammaires d'une manière non naturelle avec LL.

Answer 4

La LL utilise une approche descendante, tandis que la LR utilise une approche ascendante.

Si vous analysez un langage de programmation :

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

Answer 5

Dérivation la plus à gauche Exemple : Une grammaire G qui est sans contexte a les productions suivantes

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)

---

Dérivation de la plupart des droits Exemple : K → aKKK (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)