Discussion :

[dessinateurttuyen]

Bonjour, je voudrais savoir comment est-ce qu'on construit un arbre syntaxique à partir d'un analyseur syntaxique.

Grosso modo mon analyseur teste la première instruction et voit si la grammaire est correcte, puis relance le test pour l'instruction suivante jusqu'à la fin du fichier.

Mon arbre est de cette structure :

arbre :
String/Int
/ \
arbre1 arbre2

Pour l'instant c'est un arbre binaire. En fait cela m'arrangerais s'il pouvait avoir n branches au lieu de 2 mais je sais pas comment faire!

Donc ma question est : comment est ce que je peux implémenter ca dans mon analyseur syntaxique? Je pense qu'il faudrait construire un bout d'arbre à chaque instruction, mais la difficulté réside dans le fait de coller le bout qu'on vient de faire l'arbre général.

merci de vos réponses, je sais pas si je me suis bien exprimé alors n'hésitez pas à me demander des précisions...

[iohack]

Je n'ai pas trop compris ton problème, mais regarde du côté du package javax.swing.tree, peut-être trouveras-tu quelque chose d'adapté à ton cas.

[thecaptain]

Salut,

à mon avis dans ton cas c'est plutot le principe de la récursivité qui vient s'appliquer non ? A moins que pour toi "abre synthaxique" est l'arbres des possibilités (du genre, si je viens de recontrer un void, les prochaines instructions possibles sont : xxxs) ?

@++

[anykeyh]

Les arbres binaires ne servent qu'à faire des recherche rapide en cherchant dans des intervalles de plus en plus petits ( ou trier des données ). Dans cette optique, il faut se dire que chaque branche de ton arbre est une partie de l'interval. Donc si tu veux faire un arbre à n branches dans ce cas de figure sa sert a rien (d'ailleurs ce genre d'arbre c'est de type 2^n pour l'indexation de données à n dimensions)

Moi non plus je n'ai pas tres bien compris ce que tu souhaite faire...

[dessinateurttuyen]

Ben en fait c'est simple, je dois écrire un programme en java qui est censé transformer du Pascal en C.

J'ai fait un analyseur lexical et un analyseur syntaxique. Maintenant dans l'analyseur syntaxique je dois construire un arbre binaire qui correspond à la représentation de mon programme en Pascal.

Ensuite je dois le parcourir et l'afficher en langage C.

Mon analyseur syntaxique parcourt la première instruction de mon programme en Pascal, puis il fait des tests pour différent type d'instruction, ex : BEGIN-END, WHILE, FOR, IF-THEN-ELSE, etc et vérifie si la grammaire est correcte.
Ca c'est fait. Maintenant je n'ai absolument aucune idée de comment implémenter l'arbre binaire. Effectivement c'est une question de récursivité.

[herve91]

A toi de définir pour chaque instruction Pascal comment tu la représentes sous forme d'arbre binaire. Par exemple IF-THEN-ELSE :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
               IF
            /     \
expression         \   
booléenne           \
                    THEN
                  /      \
         instructions   ELSE
                           /
                    instructions

La construction de l'arbre se fait naturellement à chaque étape de ton analyseur syntaxique. Si tu implémentes une analyse de type top-down, à chaque fois qu'une règle syntaxique est reconnue, tu crées un noeud de l'arbre en positionnant ses fils gauche et droit, et tu renvoies le noeud.
Pour les expressions (somme de termes) c'est qq chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
public Node expression() {
  Node expression = terme();
 
  Token token = getToken();
  while (token.isOperateur('+') || token.isOperateur('-')) {
     Node terme = terme();
     expression = new Node(expression, token, terme);
     token = getToken();
  }
 
  return expression;
}

Cette méthode construit le sous-arbre d'une expression.

[dessinateurttuyen]

ok merci herve! c sympa de m'avoir répondu!