Problème : on veut faire un petit programme calculette capable de

  • lire une expression arithmétique
  • calculer et afficher sa valeur.

Exemple

?  3*3 + (2+2)*(3+1)
= 25

Pour commencer on simplifie le problème, on calculera seulement des sommes et des différences de nombres, sans parenthèses.

Exemple

?  20 + 400-1
= 421

On y ajoutera ensuite les symboles * et/, et enfin les parenthèses.

Etape 1, l'analyseur lexical

Dans le premier cas l'algorithme est simple : on lit un nombre, puis on regarde si il est suivi par un opérateur + ou -, auquel cas on ajoute ou on retranche la valeur du nombre qui suite, et on recommence.

Mais pour pouvoir lire un nombre, il faut disposer d'un analyseur lexical, capable de décomposer une ligne comme

    20 + 400-1

en une suite d'éléments (lexèmes) :

    nombre 20, symbole +, nombre 400, symbole -, nombre 1, fin de ligne

tout en ignorant les espaces.

La réalisation de l'analyseur lexical est assez simple :

Il travaille sur la chaine de caractères ligne qui lui est fournie, avec une variable pos qui indique la position du prochain caractère à traiter. Au départ bien sûr, pos = 0.

Il met à disposition une fonction lire_lexeme(), qui "lit" le prochain lexème à partir de la position pos, qu'il fait avancer.

Le résultat de cette lecture est mis dans deux variables

  • type_lexeme, qui peut valoir NOMBRE, SYMBOLE ou FINDELIGNE, constantes qui sont définies par ailleurs.
  • une chaine lexeme, qui contiendra successivement 20, +, etc.

Voici le pseudo-code

au début:

  pos = 0;
fonction lire_lexeme ()
{
  lexeme = ""
  tant que  pos < longueur(ligne) et ligne[pos] est un espace
     faire  pos ++
  si pos >= longueur(ligne)
      type_lexeme = FINDELIGNE
  sinon 
     selon ligne[pos]
       si c'est un chiffre faire
           type_lexeme = NOMBRE
           tant que  pos < longueur(ligne) et ligne[pos] est un chiffre
             faire 
                lexeme += ligne[pos]
                pos ++
       sinon si c'est +,-,*,/,(,)
                 type_lexeme = SYMBOLE
                 lexeme += ligne[pos]
                 pos ++
       sinon erreur "caractère illégal"
}

Note pour la programmation : si vous programmez en C, oubliez un peu les grands principes le temps de cet exercice, et définissez ligne, pos, lexeme et type_lexeme comme des variables globales. A défaut, si ça vous embête vraiment, mettez-les dans une structure dont vous passerez l'adresse dans toutes les fonctions. Dans un langage orienté objets, ça sera des données membres de la classe Calculette sur laquelle vous travaillez.

Pour tester l'analyseur écrivez une petite fonction de test, qui affiche sa décomposition en lexèmes d'une ligne donnée en paramètre

fonction test_analyseur(uneLigne)
{
  ligne = uneLigne
  pos = 0
  ecrire "test de ", ligne
  lire_lexeme()
  tantque type_lexeme != FINDELIGNE
    écrire type_lexeme, lexeme
    lire_lexeme()

}

et faites plusieurs appels

fonction seq_tests_analyseur()
{
  test_analyseur("")
  test_analyseur("      ")
  test_analyseur("42")
  test_analyseur("    42 ")
  test_analyseur("   1111 222 33 4   ")
  test_analyseur("  1+(2-3*(4/5)) ")
}

ETAPE 2 : le programme principal

Le programme principal est une simple boucle qui

  • lit une ligne,
  • calcule la valeur de l'expression qui y figure,
  • affiche le résultat
  • et recommence.

Avant de lancer le calcul de l'expression, il faut vérifier que la ligne n'est pas vide, et donc lire un premier lexème. Après avoir lu cette expression, le lecteur devrait normalement être arrivé à la fin de la ligne. Ce qui donne le code suivant

répéter indéfiniment
  afficher "? "
  lire ligne
  lire_lexeme()
  si type_lexeme != FINDELIGNE
        v = lire_expression()
        vérifier que type_lexeme == FINDELIGNE
        afficher "= ", v

(on peut convenir d'un symbole particulier pour arrêter la boucle).

Note : dans un vrai compilateur, l'analyseur prendrait ses données dans un fichier plutôt que dans une chaîne, et reconnaîtrait d'autres catégories syntaxiques : les identificateurs, les chaînes de caractères, les nombres réels, les symboles sur plusieurs caractères (==, !=) etc., et ignorerait les commentaires. Ça sera un peu plus compliqué, mais c'est le même principe.

ETAPE 3 : sommes/différences de nombres

Si nous simplifions le problème pour ne traiter que des sommes et des différences de nombres, la fonction lire_expression() n'est pas difficile à écrire. Rappelez-vous que le premier lexème de l'expression a déjà été lu avant l'appel de la fonction.

fonction lire_expression()  retourne un nombre  // V1
{
   a = lire_nombre()
   tant que type_lexeme == SYMBOLE et lexeme = "+" ou "-"
     faire
         op = lexeme
         b = lire_nombre()
         selon op :
          si  "+" alors  a = a + b
          si  "-" alors  a = a - b
}

La fonction auxiliaire lire_nombre()vérifie que le lexème présent est un nombre, et retourne sa valeur, après avoir fait avancer le lecteur.

fonction lire_nombre() retourne un nombre
{
    si type_lexeme != NOMBRE
       alors erreur nombre attendu
    v = valeur(lexeme)
    lire_lexeme()
    retourner v
}

ETAPE 4 : avec multiplication et division

Si nous voulons traiter aussi les multiplications et divisions, il faut faire quelques changements.

On introduit le notion de "terme" : un produit/quotient de plusieurs nombres.

Pour lire un terme, on s'inspire de ce qui a déjà été fait :

fonction lire_terme()  retourne un nombre  // V1
{
   a = lire_nombre()
   tant que type_lexeme == SYMBOLE et lexeme = "*" ou "/"
     faire
         op = lexeme
         b = lire_nombre()
         selon op :
          si  "*" alors  a = a * b
          si  "/" alors  a = a / b   (erreur si b = 0)
}

et on modifie un peu lire_expression(), qui lit maintenant une somme/différence de termes, et non plus de nombres :

fonction lire_expression()  retourne un nombre // V2
{
   a = lire_terme()                          // <-- changement
   tant que type_lexeme == SYMBOLE et lexeme = "+" ou "-"
     faire
         op = lexeme
         b = lire_terme()                    // <-- changement
         selon op :
          si  "+" alors  a = a + b
          si  "-" alors  a = a - b
}

ETAPE 5 : avec les parenthèses

Si on ajoute des parenthèses, on voit que les termes ne sont pas seulement construits à partir de nombres, mais à partir de "facteurs" qui sont des nombres, ou des expressions entre parenthèses.

fonction lire_facteur() retourne un nombre
{
   si type_lexeme == SYMBOLE et lexeme = "("
      alors
          lire_lexeme()       // pour dépasser la parenthèse ouvrante
          v = lire_expression()
          verifier que type_lexeme == SYMBOLE et lexeme == ")"

lire_lexeme() // pour dépasser la parenthèse fermante

      sinon 
          v = lire_nombre()
   retourner v
}

et une toute petite modification de lire_terme() pour appeler lire_facteur()

fonction lire_terme()  retourne un nombre  // V2
{
   a = lire_facteur()                     // <--- changement
   tant que type_lexeme == SYMBOLE et lexeme = "*" ou "/"
     faire
         op = lexeme
         b = lire_facteur()               // <--- changement
         selon op :
          si  "*" alors  a = a * b
          si  "/"  alors  a = a / b   (erreur si b = 0)
}

CONCLUSION

Comme vous le voyez, lire_expression() utilise lire_terme() qui utilise lire_facteur() qui utilise lire_nombre() et lire_expression() : les fonctions sont mutuellement récursives.

Cette technique d'analyse est appelée "descente récursive", elle est très utilisée pour écrire des compilateurs : il suffit d'introduire des fonctions lire_instruction(), lire_bloc(), lire_si_alors_sinon() etc.qui s'appelleront les unes les autres selon la grammaire du langage, et qui retourneront par exemple une représentation arborescente de l'élément correspondant (arbre de syntaxe abstraite). Il est également possible (c'est ce qui se faisait dans les compilateurs Pascal) de produire à la volée la traduction du programme source en langage machine.