Structure de donnée

L'arbre syntaxique utilisé dans le projet est relativement simple:

class Node:
    """ Un nœud de l'arbre syntaxique """

    def __init__(self, value, children: list["Node"]):
        """
        :pre: value est un str ou un int. children est une liste de Node. Le nœud résultant est valide.
        """
        self.value = value
        self.children = children
        assert self.is_valid()

    def is_leaf(self):
        """
        :pre: -
        :return: True si le nœud courant est une feuille. False sinon.
        """
        return len(self.children) == 0

    def is_variable(self):
        """
        :pre: -
        :return: True si le nœud 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 le nœud courant représente une constante. False sinon.
        """
        return self.is_leaf() and isinstance(self.value, int)

    def is_operation(self):
        """
        :pre: -
        :return: True si le nœud courant représente une opération valide. False sinon.
        """
        if len(self.children) == 2:
            return self.value in {"+", "-", "*", "/", "%"}
        elif len(self.children) == 3:
            return self.value == "SI0"
        else:
            return False

    def is_valid(self):
        """
        :pre: -
        :return: True si le nœud (et ses enfants, récursivement) est valide. False sinon.
        """
        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 """
        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, Node):
            return False
        return self.value == other.value and self.children == other.children

Un arbre syntaxique est donc ici répresenté par un nœud et ses enfants, eux-même des nœuds (donc eux aussi des arbres syntaxiques valides).

Le code suivant représente donc le premier exemple:

exA = Node("+", [
    Node(2, []),
    Node("-", [
        Node("x", []),
        Node(12, [])
    ])
])

Première partie

Imaginons qu’un premier outil ait parsé le langage original et ai produit un arbre syntaxique pour vous. Il vous est donné dans un format textuel, relativement simple à décoder (beaucoup plus que le langage original). En pratique il est généré par le (pseudo-)code suivant, qui effectue un parcours préfixe de l’arbre syntaxique:

def serialize(tree: Node) -> str:
    """ Crée une représentation "plate" de l'arbre, via un parcours préfixe
    :pre: tree est une Node valide
    :return: une représentation de l'arbre
    """
    out = f"{tree.value},{len(tree.children)}"
    for child in tree.children:
        out += ","
        out += serialize(child)
    return out

La sortie de cettte fonction pour les deux exemples ci-dessus sont respectivement

+,2,2,0,-,2,x,0,12,0

SI0,3,-,2,x,0,1,0,*,2,y,0,3,0,+,2,2,0,-,2,x,0,12,0

Votre première tâche est de concevoir la fonction "unserialize" qui recrée l'arbre à partir de cette version "plate".

La signature est la suivante:

def unserialize(serialized_repr) -> Node:
    """
    :pre: serialized_repr est une sortie de serialize
    :return: l'arbre qui a été donné à serialize
    pour tout arbre X, on doit avoir que X == unserialize(serialize(X)).
    """
    # Un indice: vous aurez probablement besoin de la methode `split` de la classe `str`!

Seconde partie

Maintenant que vous avez réussi à lire les arbres syntaxiques, vous pouvez maintenant créer votre propre interpréteur! Implémentez la fonction suivante:

def evaluate(tree: Node, var_values: dict[str, int]) -> int:
    """ Retourne le résultat de l'évaluation de l'arbre. Les valeurs pour les variables sont
        prises dans var_values. var_values["x"] est donc la valeur de la variable x.
        :pre: var_values contient en clé toutes les variables présente dans l'arbre
        :post: le résultat est valide
    """

Si exA est le premier exemple et exB le second, alors:

evaluate(exA, {"x": 1}) == -9
evaluate(exA, {"x": 2}) == -8
evaluate(exA, {"x": 12}) == 2

evaluate(exB, {"x": 1, "y": 3}) == 9
evaluate(exB, {"x": 1, "y": 4}) == 12
evaluate(exB, {"x": 2, "y": 3}) == -8
evaluate(exB, {"x": 2, "y": 4}) == -8
evaluate(exB, {"x": 12, "y": 3}) == 2
evaluate(exB, {"x": 12, "y": 4}) == 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, quel que soit le choix de variable:

     ┌─┐
 ┌───┤+├───┐
 │   └─┘   │
 │         │
┌▼┐       ┌▼─┐
│x│       │-3│
└─┘       └──┘

Dans un tel arbre simplifié, chaque nœud maintient la propriété suivante:

Tout nœud est soit une feuille, soit est un opérateur qui a dans sa descendance au moins une variable.

Cette condition est assez faible: il existe beaucoup d'arbres qui donnent le même résultat, peu importe le choix de variable. On vous laisse le champ libre pour implémenter la fonction simplify, qui retourne un arbre équivalent respectant la propriété ci-dessus.

def simplify(tree: Node) -> Node:
    """
    :pre: tree est un arbre syntaxique valide
    :return: un arbre syntaxique équivalent au premier, respectant la propriété suivante:
        Tout nœud de l'arbre est soit une feuille, soit est un opérateur qui a dans sa descendance au moins une variable.
    """
    # vous aurez probablement besoin de la fonction evaluate :-)
    pass