Programmation : la technique de descente récursive
Par Michel Billaud, dimanche 20 janvier 2013 à 05:31 :: Bidouilles :: #72 :: rss
Quelques explications sur la technique de "descente récursive", très utilisée pour faire des compilateurs. Explication par étapes sur un petit exemple de programme qui calcule la valeur d'une expression arithmétique entière comme "(2+2)*20 + 4*(4-1)/2" Ça peut être une idée de traduire le pseudo-code dans le langage de programmation de votre choix.
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) :
nombre20
, symbole+
, nombre400
, symbole-
, nombre1
, 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 valoirNOMBRE
,SYMBOLE
ouFINDELIGNE
, constantes qui sont définies par ailleurs.- une chaine
lexeme
, qui contiendra successivement20
,+
, 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.
Commentaires
1. Le lundi 11 février 2013 à 17:11, par OBeLix - Open_software BeOS Linux
Ajouter un commentaire
Les commentaires pour ce billet sont fermés.