Le rôle de l'analyse syntaxique est de

1. déterminer si la suite de tokens est conforme à la grammaire définissant le langage source;
2. repérer [et signaler] les erreurs syntaxiques;
3. définir l'arbre de syntaxe abstraite.

En pratique, d'autres taches sont réalisées simultanément à l'analyse syntaxique:

1. ajouter des informations dans la table des symboles;
2. réaliser des vérifications de type;
3. produire de code intermédiaire.

La plupart des méthodes d'analyse syntaxique tombent dans l'une ou l'autre de deux catégories :

1. méthodes descendantes : les plus populaires car facile à construire “à la main.”
2. méthodes ascendantes : ces méthodes sont plus puissantes et utilisées par les outils qui génèrent un analyseur à partir d'un grammaire (YACC).

Dans la suite, nous utiliserons les différences entre ces deux méthodes avec l'exemple des expressions arithmétiques. Le langage des expressions arithmétiques peut être décrit par la grammaire suivante G0 :

E -> E+T | T
T -> T*F | F
F -> id | (E)

où | indique “ou”. Par convention, les lettres majuscules (E,F,T) sont des non-terminaux, et les autres symboles ( ) id * + sont des terminaux (ici, des tokens).

Nous analyserons la chaîne ( id + id ) * id.

• L'arbre de syntaxe abstraite est construite en partant de la racine et allant jusqu'aux feuilles.
• L'analyse s'appuie sur les dérivations gauche de la suite des tokens. On remplace toujours en premier le non-terminal le plus à gauche.

A chaque étape, on sélectionne une règle qui permet de dériver le reste de la suite des tokens. On peut éventuellement d'être trompé et avoir choisi une mauvaise règle; dans ce cas, on fait un retour en arrière et on essaie une autre règle.

              E
              |                    R1
              T
            / | \                  R2
           T  *   F
           |      |                R2  R3
           F      id
         / | \                     R3
       (   E   )
         / | \                     R1
       E   +   T
       |       |                   R1, R2
       T       F
       |       |                   R2, R3
       F       id
       |                           R3
      id

Mais la méthode n'aurait pas construit les deux branches simultanément, elle travaille d'abord à gauche:

E_g ⇒ T ⇒_g T * F ⇒_g F * F ⇒_g ( E ) * F ⇒_g ( E + T ) * F

⇒_g ( T + T ) * F ⇒_g( F + T ) * F ⇒_g ( id + T ) * F

⇒_g ( id + F ) * F ⇒_g( id + id ) * F

⇒_g ( id + id ) * id

• L'arbre de syntaxe abstraite est construite en partant des feuilles et remontant jusqu'à la racine.
• L'analyse s'appuie sur les dérivations droite de la suite des tokens. On remplace toujours en premier le non-terminal le plus à droite.

On sélectionne une partie du début de la chaîne qui dérive d'un non-terminal et on remplace par ce non-terminal. La suite des règles utilisées correspond à une dérivation droite de la chaîne.

(    id       +      id     )  *   id
|     | 1:R3  |      | 4:R3 |  |   |
|     F       |      F      |  |   |
|     | 2:R2  |      | 5:R2 |  |   |
|     T       |      T      |  |   | 9:R3
|     | 3:R1  |      |      |  |   |
 \    E       |      |     /   |   |
  \     \     |     /     /    |   |
   \     \    |    /     /     |   |
    \     \   |   /     /      |   |
     \     \  |  /     /       |   |
      \       E    6:R1        |   |
       \      |      /         |   |
        \     |     /          |   |
         \    |    /           |   |
          \   |   /            |   |
           \  |  /             |   |
              F 7:R3           |   F
              |                |   |
        8:R2  T                |  /
                 \            /  /
                  \          /  /
                   \        /  /
                    \      /  /
                     \    /  /            
                      \  /  /    
                         T  10:R2
                         |
                         E  11:R1

• ( id + id ) * id ⇐ ( F + id ) * id ⇐ ( T + id ) * id ⇐ ( E * id) * id
• ⇐ ( E + F ) * id ⇐ ( E + T ) * id
• ⇐ ( E ) * id ⇐ F * id ⇐ T * id ⇐ T * F ⇐ T ⇐ E

<= précédent cours -/- cours suivant => Analyse Descendante