Bonjour,

Depuis quelques temps déjà, j'essaye de faire un parser d'expression mathématiques (en C) qui doit effectuer trois étapes que je veux distinctes les unes des autres.

• - Analyse Lexicale (Créer une liste de jetons)
• - Analyse Syntaxique (Construit l'arbre syntaxique abstrait à partir de la liste de jetons)
• - Évaluation (Calcul de l'arbre syntaxique abstrait)

Les étape 1 et 3 étant assez simples, elles furent vite résolues. Par contre l'étape 2 est un véritable casse-tête.
J'ai beau retourner le problème dans tous les sens, je n'en voit pas encore la fin. Mon but est d'obtenir un arbre qui a les opérateurs (les non terminaux) en tant que nœud et les nombres (les terminaux) en tant que feuille. Mon problème se situe surtout au niveau de la gestion des non terminaux que je n'arrive pas à insérer correctement.

     *
    / \
   2   ÷
      / \
     *   5
   /   \
  +     -
 / \   / \
2   3 2   3

       
J'aimerais donc que vous m'expliquiez comment faire pour créer l'ast (car je sèche complètement depuis un bon moment) ou que vous me proposiez un papier l'expliquant correctement.

A titre informatif, j'ai lu Analyseurs syntaxiques - Leur fonctionnement par l'exemple de Sébastien Jean Robert DOERAENE.

Et la grammaire que j'utilise est la suivante :

Expr ::= Terme ExprSuite
ExprSuite ::= + Terme ExprSuite | epsilon
Terme ::= Facteur TermeSuite
TermeSuite ::= * Facteur TermeSuite | epsilon
Facteur ::= (Expr) | nombre

Merci d'avance,
Lithrein

Voici un code qui fait la conversion liste de jetons -> AST, il est en OCaml (c'est le langage avec lequel je suis le plus à l'aise) j'espère que tu vas le comprendre, sinon demande moi.
Voici comment je m'y prend :

• Si je suis face à une parenthèse fermante, alors j'ai fini l'AST en cours, je renvoie donc l'AST fini (je considère qu'un AST est un type de jeton, c'est plus facile comme ça) suivi du reste de la liste qui n'a pas été traité (ligne 14);
• Si la parenthèse est ouvrante, alors j'applique ma fonction sur le reste de la liste, elle va donc renvoyer une liste contenant l'AST correspondant à ce qui ce situe entre les deux parenthèses suivi du reste de la liste non traité, il faut donc appliquer de nouveau la fonction pour traiter le reste (ligne 15);
• Si je suis face à un nombre, alors je transforme ce nombre en l'AST correspondant (qui contient juste une feuille) et je poursuit le traitement avec l'AST à la place du nombre;
• Si je suis face à un opérateur o (précédé d'un AST a, sinon c'est qu'il y un problème), alors je traite ce qui suit l'opérateur, le premier élément de la liste renvoyée est l'AST b tel qu'on ait l'arbre N(a,o,b). On traite ensuite le reste.

(* Je définie le type opérateur qui vaut +, -, * ou /,
le type AST qui est soit une feuille (F) soit un nœud (N) (un nœud est lui-même composé de deux AST et d'un opérateur)
et le type jeton : un ast, une parenthèse, un opérateur ou un nombre *)
type op = Plus | Moins | Fois | Divise;;
type ast = F of int | N of ast * op * ast;;
type jeton = Ast of ast | ParFermante | ParOuvrante | Op of op | Int of int;;

let ast_of_jeton = function Ast(ast) -> ast;;

(* La fonction prend en argument une liste de jetons et renvoie une liste de jeton dont le premier (et seul) élément est l'AST attendu *)
let rec fait_ast = function
	| [] -> []
	| [Ast(ast)] -> [Ast(ast)]
	| Ast(ast) :: ParFermante :: t -> Ast(ast) :: t
	| ParOuvrante :: t -> fait_ast (fait_ast t)
	| Int(n) :: t -> fait_ast (Ast(F(n)) :: t)
	| Ast(ast) :: Op(op) :: t -> let a = fait_ast t in fait_ast (Ast(N(ast, op, ast_of_jeton (List.hd a))) :: List.tl a);;

let exemple = [ParOuvrante; Int 2; Op Fois; ParOuvrante; ParOuvrante; Int 2; Op Plus; Int 3; ParFermante; Op Fois; ParOuvrante; Int 2; Op Moins; Int 3; ParFermante; ParFermante; Op Divise; Int 5; ParFermante];;

Salut,

Je suis en train de lire ce tutoriel : http://llvm.org/docs/tutorial/LangImpl2.html. Le premiere chapitre concerne l'implémentation du lexer et le deuxième celle de l'arbre syntaxique. Je trouve que c'est très compréhensible et les explications sont simples. Tu trouveras tout le code source (sans l'évaluation) à la fin du deuxième chapitre (~240 lignes de C++).

Voila, j'espere que ça t'aidera .

L'Atelier Calculatrice(s) contient de nombreux codes permettant de faire ce que tu veux.

Si vous avez de nouvelles solutions intéressantes, je vous invite d'ailleurs à y participer : un atelier n'est pas limité dans le temps.

Dans son minitutoriel Calcul d'une expression mathématique, robocop explique assez bien comment construire un parseur à partir d'une BNF fixée.


Ninety > Il existe aussi une version en OCaml du tutoriel que tu donnes en lien. Je trouve intéressant de constater que, pour ce chapitre, alors qu'elles ont été écrites par la même personne, l'implémentation en C++ prend 400 lignes, alors que l'implémentation OCaml en prend 250.

Tout d'abord, je vous remercie pour votre aide.

@Tomash : Je vais regarder de près comment tu fais car moi, dans ma version en C, ma méthode pour créer l'AST était beaucoup plus lourde et avait une fonction par non terminaux de la grammaire, or ta méthode semble bien plus astucieuse.

@Ninety : Merci pour le lien.

@Bluestorm : Je n'avais pas super bien compris le tutoriel de robocop (surtout le code OCaml car je n'ai pas vu les Streams).
Ensuite pour l'atelier Calculatrice, je vais aller un peu farfouiller dedans et j'y rajouterais ma participation quand j'aurais fini.

Lithrein > tu peux utiliser un algo pour transformer ton expression en notation polonaire inverse ce qui te permet d'avoir directement ton arbre.

Oui, enfin transformer en notation polonaise inverse (ou pas inverse) et parser, c'est la même chose en pratique : la difficulté est la même. Du coup, autant construire directement l'arbre, qui est une représentation plus agréable.

Ce qui est vrai par contre c'est que si, pour un projet donné, on ne veut pas s'embêter avec le parsing, on peut choisir d'écrire directement les expressions avec une notation postfixée ou préfixée, beaucoup moins pénible à parser que les notations mathématiques standard (avec précédence et associativité). Dans l'atelier calculatrice(s), ce genre de choses sont proposées pour commencer. Je trouve que les S-expressions (la syntaxe des langages Lisp) sont assez agréable à utiliser.

....

-
Edité par beatonsarahm 11 mars 2015 à 20:51:11