Construction d'un arbre de syntaxe abstraite correspondant à une expression rationnelle

2 Construction d'un arbre de syntaxe abstraite correspondant à une expression rationnelle

La figure 2 schématise la représentation d'un arbre de syntaxe abstraite et les principales fonctions permettant sa construction à partir d'une chaîne de caractères --- prise sur l'entrée standard --- pour une grammaire simplifiée.

Figure 2 : Construction de l'arbre

Pour être plus précis, la fonction simple implante la règle

simple ::= '(' expr ')' || car

de la grammaire simplifiée.

Notez bien qu'en ce qui concerne le filtre mgrep que l'on vous demande d'implanter, la chaîne de caractères représentant l'expression rationnelle considérée n'est pas prise sur l'entrée standard. Ainsi, on vous demande d'adapter le code de la figure 2 afin d'être utilisable dans le filtre mgrep et de le compléter afin de pouvoir implanter la grammaire de la figure 1.

Les algorithmes présentés dans la suite utilisent l'arbre de syntaxe abstraite construit précédemment, auquel on a ajouté un noeud racine (de type CONCAT) ayant pour fils droit un noeud de fin end (noté # dans la figure 2) et pour fils gauche l'arbre de syntaxe abstrait originel.