INGIniousLa compilation et l’exécution de code informatique s'effectuent en de nombreuses étapes, chacune s'attaquant à une partie spécifique du problème. On peut notamment citer la séparation du "texte brut" en différents mots-clés, la vérification de la grammaire, la représentation du code sous la forme d'un arbre syntaxique, la conversion de cet arbre dans d'autres formes, la production d'un langage intermédiaire, l'optimisation des opérations en modifiant l'arbre, etc.
Dans ce projet on s'intéresse aux arbres syntaxiques. Selon Wikipedia,
"En informatique, un arbre de la syntaxe abstraite ou ASA (abstract syntax tree, ou AST, en anglais) est un arbre dont les nœuds internes sont marqués par des opérateurs et dont les feuilles (ou nœuds externes) représentent les opérandes de ces opérateurs. Autrement dit, généralement, une feuille est une variable ou une constante. "
Prenons un exemple simple:
┌─┐
┌───┤+├───┐
│ └─┘ │
│ │
┌▼┐ ┌▼┐
│2│ ┌───┤-├───┐
└─┘ │ └─┘ │
│ │
┌▼┐ ┌▼─┐
│x│ │12│
└─┘ └──┘
Cet arbre représente l'expression (2 + (x - 12)). Nous travaillons sur un langage simple, qui comprend les opérations arithmétiques usuelles +, -, *, / sur les nombres réels (le nombre \(2\) sera donc mémorisé comme un float 2.0). Ces "opérations" sont représentées par des nœuds internes de l'arbre. Les enfants sont ordonnés : si le nœud de gauche est x et que le nœud de droite est y, et que l’opération est la division /, alors cette opération représente x/y la division de x par y. Les nœuds feuilles contiennent soit un float, soit une chaîne de caractère(s) représentant une variable (uniquement des caractères alphabétiques), telle que 'x', 'y' ou 'unevariable'.
Rappelons que la structure d'un arbre est récursive. On le voit déjà dans ce premier exemple puisque le fils droit de la racine est lui-même un arbre, dont l'opérateur est celui de la soustraction -, mémorisé à la racine de ce sous-arbre. Bien sûr, nous ne sommes pas limités dans la profondeur d'un tel arbre et donc on peut très bien avoir un arbre qui représente une expression plus complexe comme (((x - 12) + 27) / ((3 * x) / ((y + 2) - z))). Essayez de dessiner sur papier l'arbre correspondant.
En plus des opérations arithmétiques, le langage utilisé inclut aussi l'opérateur ** également binaire (c-à-d qui prend 2 arguments, aussi appelés opérandes) qui représente la mise à une puissance (réelle). Donc, x ** 2.0 est le carré de la variable x et est représenté par l'arbre suivant. Pour cet opérateur, le deuxième argument (celui mémorisé dans le fils droit) est obligatoirement une constante (c-à-d un nombre mémorisé dans un float).
┌──┐
┌───┤**├───┐
│ └──┘ │
│ │
┌▼┐ ┌▼┐
│x│ │2│
└─┘ └─┘
Enfin, le langage utilisé inclut également quatre fonctions (considérées comme des opérateurs unaires, c-à-d avec un seul argument): cos, sin, tan, neg représentant respectivement la fonction cosinus, sinus, tangente, et la négation qui calcule la valeur opposée de son argument. Donc, neg(x) représente l'opposé de la valeur de x et neg(-3.0) vaut 3.0. Notons que la fonction neg a été dénommée comme cela pour la distinguer de l'opérateur (binaire) de la soustraction.
L'expression (sin (neg (x - 2)) est donc représentée par l'arbre suivant.
┌───┐
|sin|
└───┘
|
|
┌─▼─┐
|neg|
└───┘
|
|
┌─▼─┐
┌──┤ - ├───┐
│ └───┘ │
│ │
┌▼┐ ┌▼┐
│x│ │2│
└─┘ └─┘
Le projet est divisé en quatre parties distinctes:
- il vous est demandé de recréer l'arbre syntaxique à partir d'une expression parenthésée qui le représente.
- il vous est demandé, à partir d'une série de valeurs pour les variables incluses dans l'arbre, d'évaluer l'arbre globalement.
- on s'intéressera à la simplification d'un arbre.
- on s'intéressera au calcul de la dérivée de l'expression représentée par un arbre.
Structure de données
Le structure d'arbre implémentée en python est détaillée ci-dessous:
from typing import Union, List
class Tree:
""" Un arbre syntaxique """
OPERATORS_1 = {'cos', 'sin', 'tan', 'neg'} # 1 opérande
OPERATORS_2 = {'+', '-', '*', '/', '**'} # 2 opérandes
OPERATORS = OPERATORS_1 | OPERATORS_2
def __init__(self, value: Union[str,float,int] = None, children: List["Tree"] = ()):
"""
:pre: value est None, auquel cas l'arbre est vide (le cas par défaut),
ou, sinon, value (à la racine) est un str, un float ou un int, et children est une liste de Tree.
:post: l'arbre résultant est valide. si value est un int, elle est convertie en float.
"""
if not children:
children = []
self.value = float(value) if isinstance(value, int) else value
self.children = children
assert self.is_valid(), "l'arbre courant est invalide"
def is_empty(self):
"""
:pre: -
:return: True si l'arbre courant correspond à un arbre vide
"""
return self.value is None
def is_leaf(self):
"""
:pre: -
:return: True si l'arbre courant est une feuille. False sinon.
"""
return len(self.children) == 0
def is_variable(self):
"""
:pre: -
:return: True si l'arbre courant représente une variable. False sinon.
"""
return self.is_leaf() and isinstance(self.value, str) and self.value.isalpha()
def is_constant(self):
"""
:pre: -
:return: True si l'arbre courant représente une constante. False sinon.
"""
return self.is_leaf() and isinstance(self.value, float)
def is_operation(self):
"""
:pre: -
:return: True si l'arbre courant représente une opération valide. False sinon.
"""
if self.value == '**': # L'exposant doit être une constante
return (len(self.children) == 2
and self.children[1].is_constant())
if len(self.children) == 1:
return self.value in self.OPERATORS_1
elif len(self.children) == 2:
return self.value in self.OPERATORS_2
else:
return False
def is_valid(self):
"""
:pre: -
:return: True si l'arbre courant (la racine et ses enfants, récursivement) est valide. False sinon.
"""
if self.is_empty():
# self.children doit être la liste vide si l'arbre courant est vide
return not self.children
if not self.is_variable() and not self.is_constant() and not self.is_operation():
return False
for child in self.children:
if not child.is_valid():
return False
return True
def __repr__(self):
""" Donne une représentation textuelle et visuelle de l'arbre, pour le debugging """
if self.is_empty():
return ""
out = f"{self.value}"
for c in self.children:
c_repr = repr(c).split("\n")
out += "\n|> " + c_repr[0]
if len(c_repr) > 1:
out += "\n" + "\n".join(["| " + l for l in c_repr[1:]])
return out
def __str__(self):
""" Donne une représentation textuelle et visuelle de l'arbre, pour le debugging """
return repr(self)
def __eq__(self, other):
"""
:return: True si self et other ont la même structure
"""
if not isinstance(other, Tree):
return False
return self.value == other.value and self.children == other.children
Le code suivant crée l'arbre correspondant au premier exemple ci-dessus:
t1 = Tree("+", [
Tree(2),
Tree("-", [
Tree("x"),
Tree(12)
])
])
Nous avons utilisé le fait que lorsqu'un (sous-)arbre se résume à une feuille, il n'est pas nécessaire de passer le second argument, puisque celui-ci est initialisé, par défaut, à une liste vide (voir __init__).
Première partie
Imaginons qu’un premier outil a analysé le langage original et a produit un arbre syntaxique pour vous. Il vous est donné sous la forme d'une expression parenthésée, relativement simple à interpréter. En pratique, cette expression est générée par le code suivant, qui effectue un parcours infixe de l’arbre syntaxique:
def serialize(tree: Tree) -> str:
""" Crée une représentation parenthésée de l'arbre, via un parcours infixe
:pre: tree est un Tree valide
:return: une représentation parenthésée (infixe) de l'arbre,
avec ' ' comme séparateur entre opérateur et opérande(s)
"""
assert isinstance(tree, Tree), f'Incorrect argument type: {type(tree)}, Expected type: <class \'Tree.Tree\'>'
if tree.is_empty():
return ""
if tree.is_leaf():
return f'{tree.value}'
out = '('
operation = tree.value
if operation in Tree.OPERATORS_1:
out += f'{operation}' + ' ' + serialize(tree.children[0])
else:
assert operation in Tree.OPERATORS_2, f'Unexpected Operation : {operation}'
out += serialize(tree.children[0]) + ' ' + f'{operation}' + ' ' + serialize(tree.children[1])
out += ')'
return out
serialize est récursive.Les chaînes de caractères renvoyées par la fonction serialize pour les trois exemples ci-dessus sont illustrées ci-dessous. Nous pouvons constater que toutes les constantes numériques ont été représentées comme des float. Par ailleurs, comme le parcours de l'arbre est infixe, dans le cas d'un opérateur binaire, cet opérateur apparaît entre ses 2 opérandes. Par exemple, dans la première expression ci-dessous, le premier opérande est 2.0, suivi de l'opérateur +, lui-même suivi du second opérande qui est le (sous-)arbre (x - 12.0). Dans le cas d'un opérateur unaire, comme sin et neg présents dans la 3ème expression ci-dessous, leur unique opérande est représenté après l'opérateur.
(2.0 + (x - 12.0)) (x ** 2.0) (sin (neg (x - 2.0)))
Vous pouvez accéder au code de la classe Tree et à celui de la fonction serialize dans Tree.py. Ce code vous permet aussi de reproduire les exemples ci-dessus. N'hésitez pas à en créer d'autres et à les analyser !
Votre première tâche est de concevoir la fonction unserialize qui recrée un arbre à partir d'une telle expression parenthésée.
La signature de cette fonction est la suivante:
def unserialize(parent_expr) -> Tree:
"""
:pre: parent_expr est une expression parenthésée en sortie de serialize
:return: l'arbre qui a été donné à serialize
:post: pour tout arbre X, on doit avoir X == unserialize(serialize(X)).
"""
Vous pouvez consulter d'autres détails à ce propos et soumettre votre solution en suivant ce lien : partie 1.
Deuxième partie
Maintenant que vous avez réussi à lire les arbres syntaxiques, vous pouvez créer votre propre interpréteur! Dans cette deuxième partie, vous devez implémenter la fonction suivante:
from typing import Dict
def evaluate(tree: Tree, var_values: Dict[str, float], digits: int = -1) -> float:
"""
:pre: tree est un arbre syntaxique valide et non vide,
var_values contient en clé toutes les variables présentes dans l'arbre
:return: le résultat de l'évaluation de l'arbre
:post: Les valeurs pour les variables sont prises dans var_values,
var_values["x"] est donc la valeur (float) de la variable x.
Toutes les valeurs numériques sont arrondies à 'digits' décimales,
sauf si 'digits' est négatif (pas d'arrondi).
"""
Si t1 est le premier exemple ci-dessus, alors:
evaluate(t1, {"x": 1.0}) == -9.0
evaluate(t1, {"x": 2.0}) == -8.0
evaluate(t1, {"x": 12.0}) == 2.0
Vous pouvez soumettre votre solution en suivant ce lien : partie 2.
Troisième partie
Une opération de base dans tout interpréteur ou compilateur est de simplifier les arbres syntaxiques pour éviter des calculs inutiles. Prenons cet exemple:
┌─┐
┌───┤+├───┐
│ └─┘ │
│ │
┌▼┐ ┌▼┐
│x│ ┌───┤-├───┐
└─┘ │ └─┘ │
│ │
┌▼┐ ┌▼─┐
│9│ │12│
└─┘ └──┘
Clairement, si l'on souhaite évaluer plusieurs fois cet arbre pour plusieurs valeurs de x,
il est inutile de recalculer l'opérande de droite, qui vaudra toujours -3. L'arbre suivant est donc
équivalent, c'est-à-dire qu'il donne le même résultat que l'arbre précédent, quelque soit l'assignation de la variable x:
┌─┐
┌───┤+├───┐
│ └─┘ │
│ │
┌▼┐ ┌▼─┐
│x│ │-3│
└─┘ └──┘
Dans un tel arbre simplifié, chaque arbre (et ses éventuels sous-arbres) maintient la propriété suivante:
Tout arbre est soit réduit à une feuille, soit contient un opérateur à sa racine, laquelle a dans sa descendance au moins une variable.
Cette condition est assez faible: il existe plusieurs arbres qui donnent le même résultat.
On vous laisse le champ libre pour implémenter la fonction simplify, qui retourne un arbre équivalent
respectant la propriété ci-dessus.
Notez qu'un corollaire de cette propriété est que si un arbre contient des opérateurs et des valeurs numériques mais aucune variable, alors l'arbre simplifié est nécessairement réduit à une feuille qui contient la valeur numérique à laquelle l'ensemble de l'arbre est évalué.
Notez aussi que tout arbre simplifié, qui inclut des sous-arbres, est tel que ses sous-arbres sont nécessairement également simplifiés ! Le caractère récursif de cette propriété plaide (fortement !) pour une implémentation récursive de simplify.
La signature de cette fonction est la suivante :
def simplify(tree: Tree, digits:int = -1) -> Tree:
"""
:pre: tree est un arbre syntaxique valide
:return: un arbre syntaxique valide, équivalent au premier
:post: l'arbre renvoyé (et ses sous-arbres, par récursion) est soit réduit à une feuille,
soit contient un opérateur à sa racine, qui a dans sa descendance au moins une variable.
l'arbre original passé en paramètre n'est *pas* modifié, un nouvel arbre (simplifié) est renvoyé.
Les valeurs numériques dans l'arbre simplifié sont arrondies à 'digits' décimales,
sauf si 'digits' est négatif (le cas par défaut).
"""
Vous pouvez consulter d'autres simplifications à implémenter et soumettre votre solution en suivant ce lien : partie 3.
Quatrième partie
Peut-être que l'opération de dérivation d'une fonction vous a, par le passé, donné mal de tête, et même si ce n'est pas le cas, ce qui suit est joli quand même 
Imaginez la fonction mathématique suivante :
Que vaut sa dérivée par rapport à \(x\) ???
C'est là que vous allez découvrir toute la puissance des arbres représentant une expression symbolique (= contenant des variables) et que vous allez découvrir comment, par récursion, effectuer une dérivation symbolique.
Ce que nous cherchons n'est pas simplement à évaluer (numériquement) une fonction dérivée pour une valeur particulière de \(x\), comme \(x = 3.5\). Nous cherchons à construire une nouvelle fonction \(f'(x)\) qui est la dérivée de la fonction d'origine, dérivée que nous pourrons évaluer ensuite, si nous le désirons, pour n'importe quelle valeur de \(x\) (appartenant au domaine de définition de cette fonction dérivée) !
Fini le mal de tête, la solution à ce problème mathématique sera bientôt calculée automatiquement par votre programme.
S'il fonctionne, votre programme devrait vous annoncer fièrement que, dans notre exemple, la fonction dérivée vaut :
Rassurez-vous, nous allons le faire pas par pas et, surtout, la récursion le fera pour vous !
Concrètement, la dernière partie de ce projet consiste à implémenter la fonction derivate dont la signature est la suivante:
def derivate(tree: Tree, var: str) -> Tree:
"""
:pre: tree est un arbre syntaxique valide et non vide
:return: un arbre correspondant à la dérivée (symbolique) de l'arbre original,
par rapport à la variable `var`.
:post: l'arbre original n'est *pas* modifié, un nouvel arbre (dérivé) est renvoyé.
"""
Vous pouvez consulter d'autres informations sur ce calcul et soumettre votre solution en suivant ce lien : partie 4.