Il y deux manières de réaliser l'analyse syntaxique : descendante et ascendante. L'analyse descendante cherche à simuler le processus de production; l'analyse ascendante cherche à remonter (défaire) le processus de production.

Les analyseurs descendante peuvent être écrite manuellement ou produite automatiquement à partir d'une grammaire algébrique.

Un analyseur descendant fait main est composé d'appels récursifs, chaque appel correspondant de près à une règle de la grammaire. Cette technique ne marche que pour un ensemble limité de grammaires, et les restrictions d'appartenance à cette classe ne sont pas facilement vérifiables manuellement.

Analyseurs descendants générés utilisent le calcul préalable des règles de décision (quant aux transitions d'état) que les analyseurs récursifs descendants prennent dynamiquement; les tables de transition sans ambiguité ne sont obtenues que pour des grammaires LL(1).

Construction de la table est basée sur les ensembles FIRST et FOLLOW des non-terminaux. FIRST(N) contient tous les symboles qui peuvent apparaître au début d'une quelconque production de N, et \epsilon si N produit le mot vide. FOLLOW(N) contient tous les symboles qui peuvent suivre une production de N.

La table de transition peut être intégrée dans un analyseur récursif descendant pour en faire un analyseur prédictif, dans lequel la pile d'analyse coïncide avec la pile..¹⁾.; ou employée dans un automate à pile LL(1), dans lequel la pile est un tableau explicite.

Les conflits LL(1) peuvent être levés par factorisation à gauche, substitution, et dé-récursivation à gauche dans la grammaire, et résolus par des résolveurs ²⁾ de conflit dynamiques dans le générateur d'analyseur LL(1).

Les analyseurs LL(1) peuvent se remettre des erreurs de syntaxe rencontrées en trouvant un chemin de sortie, coupant (ne pas tenant compte) des symboles jusqu'à ce qu'un de convenable est trouvé, puis continuer sur ce chemin.

Analyseurs ascendants fonctionnent en trouvant des “handles” de façon répétée (un peu comme les analyseurs lexicaux mais avec automates à pile au lieu d'automates à états finis). Un “handle” est une liste des fils du dernier noeud dévéloppé en produisant le programme; Une fois trouvé (reconnu) l'analyseur la réduit à son noeud parent. Autrement dit, il cherche à reconnaitre dans la suite des symboles le coté droit d'une règle de production. F

La difficulté est de trouver les “handles.” il y a beaucoup de techniques approximatives.

La technique LR utilise des ensembles d'items des “handles” proposés. Leur comportment à l'égard de “shift” est similaire, leurs critères de décision de réduction diffèrent.

En LR(0) tout item réductible (suivi du point) provoque une réduction. En SLR(1),un item réductible N\rightarrow \alpha \bullet ne provoque une réduction que si le symbole suivant (look ahead) est dans FOLLOW(N). En LR(1), l'item réductible N\rightarrow \alpha \bullet \left\{\sigma\right\} provoque une réduction seulement si le symbole suivant (look ahead) est dans \sigma, un petit ensemble de symboles calculé exprès pour répondre à cette question.

Comme l'analyseur lexical, l'analyseur LR peut effectuer un shift sur le symbole suivant ou une réduction par une règle de grammaire. La décision est trouvée par consultation de la table d'ACTION, qui peut être produite par pré-calcul sur les ensembles des items. Si un shift est préconisé, le nouvel état peut être trouvé dans la table GOTO, qui peut être pré-calculée de la même façon. Pour les analyseurs LR(1), les deux table peuvent être superposées (fusionnées).

Les ensembles d'item et tables LALR(1) sont obtenus en combinant les ensembles LR(1) qui ne diffèrent que par leurs lookaheads. Ceci réduit la taille des tables à celle de LR(0) avec qu'une petite perte de puissance.

Un ensemble d'items LR a un conflit shift/reduce si un item demande un shift et un autre demande une réduction, compte tenu du symbole suivant (lookahead). Un ensemble d'items LR a un conflit reduce/reduce si deux items demandent deux réductions différentes, toujour tenant compte du symbole suivant (lookahead).

Le conflits LR shift/reduce peuvent être levés si on donne toujours priorité à shift; les conflits reduce/reduce peuvent être résolus en acceptant toujours la règle prenant la séquence de symboles la plus longue, ou en établissant des règles de précédence.

Reprise après erreurs dans l'analyse LR est difficile….