===== Analyse Syntaxique =====

==== Introduction ====

Le rôle de l'analyse syntaxique est de
  - déterminer si la suite de tokens est conforme à la grammaire définissant le langage source;
  - repérer [et signaler] les erreurs syntaxiques;
  - définir l'arbre de syntaxe abstraite.

En pratique, d'autres taches sont réalisées simultanément à l'analyse syntaxique:
  - ajouter des informations dans la table des symboles;
  - réaliser des vérifications de type;
  - produire de code intermédiaire.

==== Méthodes d'analyse syntaxique ====

La plupart des méthodes d'analyse syntaxique tombent dans l'une ou l'autre de deux catégories :
  - __méthodes descendantes__ : les plus populaires car facile à construire "à la main."
  - __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''.

=== Les Méthodes Descendantes ===

  * 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<sub>g</sub> => T =><sub>g</sub> T * F =><sub>g</sub> F * F  =><sub>g</sub> ( E ) * F  =><sub>g</sub> ( E + T ) * F 

 =><sub>g</sub> ( T + T ) * F  =><sub>g</sub>( F + T ) * F  =><sub>g</sub> ( id + T ) * F  

 =><sub>g</sub> ( id + F ) * F  =><sub>g</sub>( id + id ) * F 

 =><sub>g</sub> ( id + id ) * id
=== Les Méthodes Ascendantes ===

  * 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.

== Exemple (le même ==

  (    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

===== Navigation =====

[[compil_1| <= précédent cours]] -/- [[compil_ll| cours suivant =>]] Analyse Descendante