Documentation du programme "Formel" (Lephenixnoir pour le concours CPC #21 de Planète Casio) Structure du programme ---------------------- FORMEL Programme principal r DIFF Dérive les contenus de la matrice A r EVAL Évalue la fonction en un point (avec UI) r LEXER Extrait des tokens du flux de la string 1 r PARSER Applique la grammaire sur la matrice A r TREE Affiche un arbre décrivant la fonction stockée (avec UI) θ COPY Copie un noeud de la matrice A vers la fin de la matrice B θ COPY2 Copie un noeud de la matrice A vers la fin de la matrice A θ DELETE Supprime une ligne de la matrice A (fausse suppression) θ INSERT Insère une ligne dans la matrice A θ SIZE Calcule la taille d'un noeud de la matrice A Technique de stockage de l'arbre -------------------------------- L'arbre de l'expression sur laquelle le programme travaille est stocké dans une matrice (pas moyen de faire autrement). Chaque ligne de la matrice représente un noeud, et chaque noeud est immédiatement suivi de ses descendants (notation préfixe). Par exemple, pour l'expression `f(x, y) = x + 2 × y + 3` : Opérateur + 01 3 Opérateur + |--- Variable x 02 0 Variable x |--- Opérateur × => 03 2 Opérateur × | |--- Constante 2 04 0 Constante 2 | |--- Variable y 05 0 Variable y |--- Constante 3 06 0 Constante 3 La première colonne correspond ici à un numéro de ligne. La seconde colonne donne le nombre d'enfants du noeud. La troisième correspond au type du noeud, et la dernière à sa valeur (ces deux colonnes sont stockées sous forme d'entiers suivant une convention). Rien de mieux pour décrire plus précisément la structure que de présenter un algorithme qui la parcourt. Le programme `θ SIZE` prend en paramètre un numéro de ligne dans la matrice (passé par la variable R) et renvoie le nombre de lignes du noeud (à savoir, sa taille, plus celle de ses enfants, qui ont possiblement aussi des enfants) dans la variable S. `θ SIZE` compteur ← 1 ligne_fin ← R Tant que compteur > 0 compteur ← compteur + matrice[ligne_fin].enfants - 1 ligne_fin ← ligne_fin + 1 S ← ligne_fin - R Étant donné que les enfants d'un noeud sont immédiatement en-dessous de ce noeud, on décide de commencer à la ligne R en indiquant dans le compteur « encore un noeud à visiter ». Lorsqu'on visite ce noeud, on décrémente le compteur de 1, mais on y ajoute le nombre de ses enfants (en suivant l'exemple précédent, 3). C'est seulement lorsque les enfants auront *aussi* été parcourus que l'on aura obtenu le nombre total de lignes que prend l'opérateur. On continue donc de parcourir la matrice jusqu'à ce que le compteur tombe à 0, et la taille du noeud est obtenue par différence. (Au fond c'est un algorithme récursif rendu itératif, dont la pile d'entiers est remplacée par la somme de ses valeurs.) Structure du lexer ------------------ Le lexer prend ses entrées dans la string 1 et ajoute à la matrice A un token. Il marque les tokens de variables et de constantes comme des expressions, mais pas les opérateurs ou les noms de fonctions (voir le paragraphe sur le parser). Les tokens sont des types suivants : Type Description Convention pour la valeur associée 1 Constante Valeur de la constante obtenue avec Exp() 2 Variable Numéro de la lettre (seuls 24, 25 et 26 sont utilisés) 3 Opérateur 1 Addition + 2 Soustraction - 3 Multiplication × 4 Division ÷ 5 Exponentiation ^ 4 Fonction 1 Sinus sin(x) 2 Cosinus cos(x) 3 Tangente tan(x) 4 Logarithme ln(x) 5 Logarithme log(x) 6 Exponentielle e^x 5 Parenthèse ouvrante 6 Parenthèse fermante Structure du parser ------------------- Une colonne additionnelle est ajoutée à chaque ligne de l'arbre, en première position. Il s'agit d'un flag spécifiant si le noeud est, ou non, une expression. Une expression est l'un des éléments suivants : - Une constante - Une variable - Un opérateur avec des enfants - Une fonction avec un enfant Le parser a des aspects de LR (sauf sa complexité, qui est moins du O(n) que du O(n^3)) et a un lookahead de 1 token (noté LA). La grammaire utilise les règles suivantes : expr = var expr = constant expr = ( expr ) Aucune condition de LA expr = fun expr LA: Pas une expression expr = expr expr LA: Pas un opérateur puissance ^ expr = expr op expr LA: Conforme aux priorités opératoires Les prioritès opératoires définissent quels types de LA sont acceptables selon l'opérateur qui apparaît dans les expressions : + - LA: Opérateur +, Opérateur -, Parenthèse fermante ), ou rien LA: Pas une expression (donc + et - en tant que tokens) × ÷ ^ LA: Pas un opérateur puissance ^ L'avant-dernière règle correspond à un produit implicite type `xy` ou `2(x+y)`. Le moins unaire (-) est traité comme une constante -1 et génère un noeud de produit. Les noeuds +, -, × et ÷ sont automatiquement fusionnés si cela est possible. Par exemple (dans un cas simple) : Opérateur + Opérateur + |--- Opérateur + |--- Constante 1 | |--- Constante 1 => |--- Constante 2 | |--- Constante 2 |--- Constante 3 |--- Constante 3 Il est à noter que l'arbre de gauche n'est jamais produit, l'optimisation ayant lieu au niveau de la règle d'opérateurs du parser. Dans ce cas, les opérateurs sont considérés associatifs de gauche à droite. L'opérateur puissance ^, qui est associatif de droite à gauche, ne subit pas cette optimisation. Fonction d'évaluation --------------------- Cette fonction évite l'algorithme récursif en implémentant un calcul en notation polonaise inversée. Étant donné que l'arbre est en structure préfixe de haut en bas dans la matrice, ce sous-programme parcourt la matrice de bas en haut (donc en notation postfixe) et utilise la List Ans comme une pile. Le reste tient du classique (calcul en NPI). Fonction de dérivation ---------------------- Sans doute le plus technique. Cette fonction était trop dure à itératiser, donc elle est implémentée en récursif. La liste Ans joue le rôle de pile de données, ce qui explique qu'on y empile et dépile régulièrement des choses entre les appels récursifs. L'algorithme remplit la matrice B au fur et à mesure, en calculant la dérivée de la matrice A. La copie se fait soit directement lors des appels à `θ COPY`, soit lors de la dérivation des constantes et des variables (ou bien dans les appels récursifs, ce qui revient au même). Le programme "r DIFF" prend en entrée le dernier élément de la liste Ans, supposé désigner une ligne de la matrice A, et ajoute la dérivée de ce noeud à la fin de la matrice B, quitte à s'appeler récursivement. Différentes techniques sont utilisées pour contourner les limites de la structure de données. Par exemple, la dérivation d'une somme est assez simple : il suffit de créer un noeud de somme avec le bon nombre d'enfants et d'appeler récursivement la fonction de dérivation pour chacun des fils, qui sont disponibles dans l'arbre. Cependant la dérivation de `a ^ b` fait intervenir la dérivée de `b * ln(a)`, formule qui n'est pas explicitement écrite dans l'arbre. Le programme la crée donc en fin de matrice (sans affecter l'élément [1, 1], donc sans incidence) pour la faire dériver récursivement. La dérivation des quotients (qui n'est pas implémentée par manque de... temps x_x), prévoyait de modifier le nombre d'enfants du noeud de division pour manipuler l'instance de la fonction appelée récursivement et lui faire dériver correctement la formule.