Analyse Syntaxique

Introduction

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.

Méthodes d'analyse syntaxique

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)

| 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:

Eg ⇒ 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

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

 
m1ilc/compil_2.txt · Dernière modification: 2010/01/04 17:28 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki