Evaluation

Dans la plupart des algorithmes que nous avons donnés, il a été question d'arbre de syntaxe abstraite d'une expression arithmétique. Afin d'illustrer l'intérêt de cet arbre, on peut examiner la simplicité de la fonction d'évaluation qui permet de calculer la valeur de l'expression analysée à partir de l'arbre de syntaxe abstraite.

function Evaluer(x: Arbre): integer;
    begin
    if x^.valeur = 'a' then 
        Evaluer := x^.valeur
    else if x^.valeur = '+' then 
        Evaluer := Evaluer (x^.filsG) + Evaluer (x^.filsD)
    else if x^.valeur = '-' then 
        Evaluer := Evaluer (x^.filsG) - Evaluer (x^.filsD)
    else if x^.valeur = '*' then 
        Evaluer := Evaluer (x^.filsG) * Evaluer (x^.filsD)
    end

Une fonction similaire, qui ne demanderait pas beaucoup de mal à écrire, permet de créer une suite d'instructions en langage machine traduisant le calcul de l'expression. Il faudrait remplacer les opérations +, *, -, effectuées lors de la visite d'un n ud de l'arbre, par la concaténation des listes d'instructions qui calculent le sous-arbre droit et le sous arbre gauche de ce n ud et de faire suivre cette liste par une instruction qui opère sur les deux résultats partiels. Le programme complet qui en résulte dépasse toutefois le but que nous nous fixons dans ce chapitre.