lu,
J´ aimerais avoir des précisions sur l´ analyse syntaxique, sachant que j´ utilise un arbre syntaxique abstrait.

++

c´est un peu vague (vaste) comme question.

Tu veux savoir comment implémenter un analyseur syntaxique pour construire ton AST ? si c´est ça, tu veux le faire à la main ? en utilisant des outils prévu pour (genre yacc) ? tu veux le faire dans quel langage (je ne peut que recommender le Caml pour se genre de tâche).

Ou alors tu veux des précisions plus académique sur les différents type d´analyseur et sur ce qu´est une grammaire ?

Tu veux savoir comment implémenter un analyseur syntaxique pour construire ton AST ?

C ´est exactement sa, je souhaite le faire en C++.

"je souhaite le faire en C++."

malheur ... Mais tu veux connaître la théorie (ou en tout cas les algo qu´il y a dessus) et tu cherche des cours sur l´écriture d´un parseur (ça je peut t´aider) dans le but d´en écrire un toi même, ou alors tu veux juste obtenir un parseur en C++ en utilisant des outils fait pour ça (bison/yacc) qui permette d´utiliser un langage "plus simple" (ou en tout cas plus adapté) pour décrire une grammaire (LALR(1) pour yacc je crois) et qui te sorte un programme en C++. Dans ce cas là, je ne peut pas t´aider. Les bisons et autre outils C sont particulièrement infâmes, il doit y en avoir en C++, l´utilisation de POO ne pouvant qu´être un énorme bénéfice pour ça, mais je ne connais pas du tout. Je n´utilise ce genre d´outils qu´en Caml avec de la programmation fonctionnel.

caml et haskell powaaaaa !

/* end of troll */

Jveux bien les cours sur l´ écriture d´un parser. merci a toi Dnob.

"Mais tu veux connaître la théorie (ou en tout cas les algo qu´il y a dessus) et tu cherche des cours sur l´écriture d´un parseur (ça je peut t´aider)"

Alors c ´etait un fake ?

doucement ...

faut aussi que j´en trouve. Et pour ne pas te balancer n´importe quel lien il faut regarder un peu.
Le problème c´est qu´il y a peu de chose sur le net en accès libre (beaucoup de transparent, mais sans le prof qui va avec, c´est pas très utile), et encore moins en C++ (si tu veux un bouquin, tu peut lire "Compiler principles and tools" qui est la référence).

Pour écrire réellement un analyseur syntaxique, tu peut lire ça :
http://lambda.uta.edu/cse5317/long/ (les chapitre 1,2 et 3).
http://isoft.postech.ac.kr/Course/CS423/
http://pages.cpsc.ucalgary.ca/~robin/class/411/webnotes.html
http://www.mcs.drexel.edu/~rweaver/COURSES/MCS761/mcs761.html (très succint)

A chaque fois, c´est la partie sur le parsing qui t´intéresse.

Mais en relisant le haut, je me suis dit que ce n´est pas ce que tu veux. Si tu veux te construire une AST, le plus simple et efficace est quand même d´utiliser un outils fait pour ça. Dans ce cas là, il faut que tu t´intéresse à yacc (ou bison).

merci beaucoup. désolé de t´ avoir préssé. Je vais regarder yacc et bison mais je pense rester sur du c++.

yacc ou bison (c´est juste deux nom pour le même langage, mais dans diffrente version) c´est un outils qui permet de décrire la grammaire (dans une syntaxe proche de la notation BNF) et les actions associé (en C) et qui produit du code C en sortie.

Donc ça fait partie d´une chaîne de développement C. Ce n´est pas vraiment comme si c´était un autre langage et ça évite une énorme quantité de travail. Par contre ce n´est pas très adapté à du C++, mais des logiciels équivalents doivent exister pour le C++ (je parierais pour bison++ ou yacc++).

Dans le premier lien que m´ a filé Dnob je n´ arrive pas a appliquer la grammaire suivante :

S ::= ( L )
S ::= a
L ::= L , S
L ::= S

sur l´ expression (a,((a,a),a). Il marque bien la solution mais je ne comprend pas comment il y arrive. Si vous pouviez m´ expliquer.

merci d´ avance,

l´expression que tu nous donne est mal parenthésé, si c´est l´exemple c´est qu´il est faux, sinon, il faudrait que tu le corrige.

Dans tout les cas, la "difficulté" dans une grammaire comme ça, est fasse à un terme de type A,B,C (ou les majuscule sont des non terminaux) de savoir si, pour appliquer la règle L:=L,S tu va prendre L=A,B et S=C ou L=A et S=B,C. Ici, comme seule un L peut contenir des virgules au premier niveau, il n´y a pas d´ambiguïté et on peut avancer.

(a,((a,a),a)) excuse moi j´ ai oublié une parenthése.

Bin, ça ne me semble pas poser trop de problème :

S::=(L) où L = a,((a,a),a)
L::= L,S où L = a et S = ((a,a),a)
L::= S ou S = a (c´est fini)
S::= (L) ou L = (a,a),a
L::= L,S où L=(a,a) et S=a

et je te laisse terminer.

Et là, il n´y a même pas d´ambiguïté sur l´ordre d´application des règles.

Ok merci, je vois.
si je simule un ordi, ici je peux prendre
S::= (L) ou L = (a,a),a
L::= L,S où L = (a et S = a),a ( est-ce juste ? )
puis ensuite sa plante et je backtrack. ( est-ce juste ? )

on pourrait voir ça comme ça, sauf que ce n´est pas ainsi que fonctionne un parseur produit par yacc.

J´ai écrit ta grammaire en ocamlyacc (un dérivé de yacc pour caml) :
http://rafb.net/p/J56leR77.html
Tu ne devrais pas avoir de mal à comprendre le principe de la grammaire (on décrit juste quels sont les terminaux (ici L_PAR, R_PAR, COMMA et a) et les règles pour les non-terminaux (ici S et L).

Puis je l´ai compilé et je lui ai demandé de me sortir du pseudo code pour voir ce qu´il fait (option -v de ocamlyacc, je crois que ça marche aussi avec la version C).
Le résultat est le suivant :
http://rafb.net/p/ffSz7690.html

Il s´agit d´un automate à pile. Dans lequel il n´y a jamais de "retour arrière", car il y a suffisemment d´état différents pour que l´on puisse toujours savoir où il faut aller ensuite.
L´idée c´est que quand l´automate lis dans ton exemple :
( : là il sait qu´il est au début d´un S, c´est le seul possibilité et donc que le prochain caractère sera le début d´un L. Dans mon exemple, ça correspond à l´état 1 et on passe dans l´état 3 lorsqu´on lis le L_PAR.

Pour lire le fichier il faut voir ça :
state 3
S : L_PAR . L R_PAR (1)

L_PAR shift 3
a shift 4
. error

S goto 6
L goto 7

l´état 3 correspond à la règle S où l´on a déjà lu un L_PAR et on se trouve avant le L (le ´.´ marque l´endroit où l´on est en train de lire) puis tu as la liste des actions selon le token que tu rencontre. Les goto marque là où il faudra aller quand on reviendra dans cet état.

Ici, dans l´état 3, on lis un a, on pousse donc vers l´état 4, où l´on a rien d´autre à faire car on a fini de lire un S. n revient donc en 3 (parce que c´est là qu´on était précédemment, pas parce que c´est un numéro en dessous. C´est ce que tu pourrais appeler le back-tracking, sauf que c´est juste un retour de fonction, pas comme si on avait fait une erreur). Comme on revient en 3 et qu´on vient de lire un S, on part dans l´état 6, etc.

Et il y a suffisamment d´états différents (plus que de règles) pour que toute les possibilités soit gérées directement, sans avoir recours à du back-tracking. C´est le principe des grammaire LR(1) où tu peut toujours savoir dans quel état tu es en lisant un token devant toi. Il n´y aura donc jamais d´erreur de lecture nécessitant un retour en arrière. On peut écrire des grammaire plus générale, où ce n´est pas vrai, mais je crois qu´on a des théorème qui assure que toute grammaire valide peut se ramener à une grammaire LR(1) (mais avec une expression qui sera plus complexe).

a propos d´ automate a pile.

Quand dans l´ action table ya marqué r3 sa veut dire quoi ? je pensais reduce by rule 3 mais apparament non.

pas la moindre idée, tu peut montrer un exemple ?

dans le premier lien que tu m´ as filé, la section 3.3. Tu descends un peu et ya les tables action et goto dont je te parle.

Si c´est bien une réduction selon la règle 3, c´est dit juste au dessus du tableau en question. Ils ont juste appeler leurs règles 1, 2 et 3 au lieu de 0, 1 et 2 un peu avant je crois.