Java

[Analyse syntaxique] La, faut qu'on m'explique un truc... spapossible.

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [Analyse syntaxique] La, faut qu'on m'explique un truc... spapossible.

Tetedeiench

Head Of God

Bonjour,

Je dois faire un analyseur syntaxique sur une expression arithmetique en java.

Par exemple, un truc qui analyse et qui construit l'arbre de cette expression :

2 + 3 * 2 - ( 2 / 2 + 1)

Je dois prendre en compte la priorite des operateurs ( *,/ par rapport a +,- ) et gerer les parentheses.

J'ai cette grammaire la pour bosser :

Expression -> Term | Expression + Term | Expression - Term
Term -> Factor | Term * Factor | Term / Factor
Factor -> Identifier | Literal | ( Expression )
Identifier -> (a..zA..Z)*
Literal -> (0..9)*

Bref, une grammaire qui je pense est bonne ( elle est dans mon bouquin).

Arrive la phase de codage.

Je regarde mon bouquin, et je vois une fonction toute prete qui montre comment analyser une expression.

La voila :

Code :

private Expression expression()
{
Binary b; Expression e;
e = term(); // <== LA Y A UN GROS SOUCI
while(token.value.equals("+" ) || token.value.equals("-" )){
b = new Binary();
b.term1 = e;
b.op = new Operator(token.value);
token = input.nextToken();
b.term2 = term(); // <== LA c deja plus logique
e = b; // <== Ca signifie qu'une expression est du type binaire... nan ?
}
return e;
}

Et la y a un truc que je ne pige pas.

On a une regle pour programmer une grammaire : creer une nouvelle methode pour chaque token non terminal A avec A comme type de retour.

OK, donc ca signifie que le type Expression = Binary = Term qui lui meme contient des operandes de type TERM et donc Binary...

Super pratique deja.

Si on doit coder la methode Term, on aura a peu de choses pres la meme qu'au dessus...

et on aura, selon le meme raisonnement et en matant la grammaire, Term = Binary = Factor

Et quand arrivera le moment de coder le factor...

Celui ci peut etre de type unaire ( juste un nombre ou un nom de variable), ou carrement une expression entiere...

Et la je cale.

Aidez moi, comment coder une horreur pareille ? ca fait 2 h que je suis dessus sans succes

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Publicité

verdoux

And I'm still waiting

Euh oui, c'est dans tous les cours de débutants en info.
Je vois pas où est le pb.
Si tu tombes sur une parenthèse, tu construis l'objet expression contenu.

Tetedeiench

Head Of God

Le probleme est qu'ils filent pas la gueule de leur classes Expression, Term etc.

Car la :

e = term();

On a bien Objet type Expression = Objet type TERM

Donc les types sont egaux.

Ensuite, on a :

e = b;

Ici, Objet type Binary = Objet type Expression.

Donc Expression = Binary = Term , tu me suis ?

Dans Binary, on voit :

b.term1 = e;

Donc le type Binary contient un objet de type Expression, un objet de type Operand et un objet de type Expression.

Et la, je cale, desole, je pige pas comment tu veux coder un truc avec 15 000 types identiques qui s'enchainent comme ca.

Franchement, je cale rien.

Explique verdoux vu que c'est si simple, l'analse d'un Term et d'un Factor, ca ressemble a quoi, alors, vu l;ecnhevetrement de types ?

Je cale decidement pas.

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

verdoux

And I'm still waiting

Tu connais le polymorphisme ?

Tetedeiench

Head Of God

non.

Pas du tout.

Et y a aussi un truc que je cale pas ( merci d'etre plus detaille).

ici :

Expression -> Term | Expression + Term | Expression - Term

T'es OBLIGE de lire 2 tokens ( le premier + le second) pour savoir si tu va passer dans la 1ere regle ( et appeler la fonction TERM) ou la seconde (appeler la fonction Expression).

J'ai faux ?

Comment tu veux faire ca ?

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

Et meme, ca se tiens pas, car si tu as ca sur leur fonction de depart :

( 2 + 2 ) + 2

Leur fonction plante.

je ne comprends pas.

Et apres, comment tu veux analyser l'horreur generee pour aboutir au resultat ?

Putain, comprends pas.

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

Vu que c'est basique verdoux, et vu que tu as l'air de caler ca rapidement...

tu pourrai pas essayer d'expliquer plutot que de me balancer des mots style polymorphisme and co ?

Car la, je vois mal comment programmer ca sans faire de type error, et encore moins comment se balader dans l'entite abjecte generee (je vois meme pas ce que ca peux generer d'ailleurs, meme si en oubliant les trucs de type etc je suis a *peu* pres OK, je vois mal comment ca peux marcher) pour aboutir a un resultat coherent.

Comprends pas.

Message édité par Tetedeiench le 20-10-2002 à 00:07:08

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

Bon je viens de regarder le polymorphisme, ok, je comprends deja beaucoup mieux.

En fait les classes Expression, Term et factor ne sont que des "synonymes" de Binary.

Et doivent etre compatibles entre eux.

le blem, le voici :

Expression --> Term --> Factor --> Binary

Jusque la no soucy.

MAIS a un moment donne on doit assigner a un factor une expression (matez la derniere regle).

Ca donne Expression --> Term --> Factor --> Binary --> Expression

Et la redondance, java veut pas...

Comment que je fais moi alors ?

Message édité par Tetedeiench le 20-10-2002 à 00:46:31

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

mrbebert

C'est pas juste une histoire d'héritage ?
Expression est une classe générique, alors que Binary et Term sont des classes dérivées de Expression.
Binary a ceci de particulier qu'elle prend un opérateur et 2 objets Expression (pouvant être indifféremment de type Binary ou Term).

darklord

You're welcome

verdoux a écrit a écrit :

Tu connais le polymorphisme ?

+1 :heink:

---------------
Just because you feel good does not make you right

Publicité

bobuse

en conclusion, faut tu cales un peu plus la POO

Tetedeiench

Head Of God

Ouai, mais la, comment je peux m'en sortir ?

Ca fait de la redondance...

Expression => Term => Factor => Binary => Expression ...

:??:

Avec un cast ?

Message édité par Tetedeiench le 20-10-2002 à 20:51:30

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

mrbebert

En fait, tu as une classe Expression, et plusieurs autres classes qui dérivent toutes de Expression (Term, Binary, Factor).
Le but est donc de construire un arbre constitué d'objets de classe Expression. Bien sur, chaque élément sera de l'une des classes dérivées (quand tu trouves un "+", tu construits un Binary, quand tu trouves un "*", tu construits un Factor...).

Tu vois bien ce que c'est l'héritage, où je parle dans le vide ?

verdoux

And I'm still waiting

Et puis quand tu tombes sur une parathèse t'instancies un objet Paranthèse qui lui même agrège un objet expression.

Tetedeiench

Head Of God

mrbebert a écrit a écrit :

En fait, tu as une classe Expression, et plusieurs autres classes qui dérivent toutes de Expression (Term, Binary, Factor).
Le but est donc de construire un arbre constitué d'objets de classe Expression. Bien sur, chaque élément sera de l'une des classes dérivées (quand tu trouves un "+", tu construits un Binary, quand tu trouves un "*", tu construits un Factor...).

Tu vois bien ce que c'est l'héritage, où je parle dans le vide ?

Moi je vois ca plus comme une classe Binary, de laquelle derivent toutes les classes Expression, Term, Factor.

Apres je devrais evaluer l'arbre cree et j'aurai besoin d'utiliser des Binary quoiqu'il arrive...

Le souci est que Expression doit deriver de Term ( car je dois assigner un objet type term a un objet de type Expression ), un Term doit deriver de Factor ( meme raison), et un Factor doit deriver d'une Expression (meme raison).

Car a un moment ou a un autre, j'aurai :

Code :

private Expression readExpression()
{
Expression e;
...
e = readTerm();
}
private Term readTerm()
{
Term t;
...
t = readFactor();
}
private Factor readFactor()
{
Factor f;
...
f = readExpression(); // celui ci si y a des parentheses par exemple
}

Vous voyez ce que je dois faire ?

Message édité par Tetedeiench le 20-10-2002 à 21:46:04

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

Up j'ai vraiment besoin d'une reponse

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

mrbebert

Je vois pas pourquoi Term devrait dériver de Binary :??:
Term c'est un nombre tout seul, Binary c'est 2 Expression avec un opérateur.

Tetedeiench

Head Of God

mrbebert a écrit a écrit :

Je vois pas pourquoi Term devrait dériver de Binary :??:

Term c'est un nombre tout seul, Binary c'est 2 Expression avec un opérateur.

regarde la grammaire en haut...

Term doit deriver de Binary...

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Tetedeiench

Head Of God

mais tout ce que je veux moi, c'est bosser avec une classe Binary, et que Expression, Term et Factor soie des synonymes, qu'ils me fassent pas de merde quand je leur demande que Expression = Term , ou Expression = Binary, ou Factor = Expression, etc...

C'est pourtant tout con...

Pourquoi java est aussi merdiiiiiiiiique :cry:

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Zzozo

Un peu, passionément, à la fol

Tetedeiench a écrit a écrit :

mais tout ce que je veux moi, c'est bosser avec une classe Binary, et que Expression, Term et Factor soie des synonymes, qu'ils me fassent pas de merde quand je leur demande que Expression = Term , ou Expression = Binary, ou Factor = Expression, etc...

C'est pourtant tout con...

Pourquoi java est aussi merdiiiiiiiiique :cry:

rejettes pas la faute sur Java s'te plait ... :sarcastic:

Tetedeiench

Head Of God

Zzozo a écrit a écrit :

rejettes pas la faute sur Java s'te plait ... :sarcastic:

Oui je sais ct de l'ironie

Bon, voila le code, en bossant QU'AVEC du type binary ( et ca marche )

Ma classe Binary ( elle est laide, je sais, ct que pour tester )

Code :

public class Binary
{
int type;
public char op;
public Binary term1;
public Binary term2;
public int nval;
public String sval;
public Binary()
{
type = 0;
}
public Binary(int i)
{
type = 1;
nval = i;
}
public Binary(String s)
{
type = 2;
sval = s;
}
public void printcontent()
{
if (type == 1)
System.out.println("nval : " + nval);
else
if (type == 2)
System.out.println("sval : " + sval);
else
{
System.out.println("Operator : " + op);
term1.printcontent();
term2.printcontent();
}
}
}

Elle me sert a me souvenir :

-Des binaires : 2 + 3 par exemple
-Des valeurs : 2, 3, etc
-Des variables : x, y, z...

Elle est un peu fourre tout.

Voice ensute la partie analyse :

Code :

private Binary readExpression() throws IOException
{
Binary b; Binary e;
e = readTerm();
while (st.ttype == '+' || st.ttype == '-')
{
b = new Binary();
b.term1 = e;
b.op = (char) st.ttype;
st.nextToken();
b.term2 = readTerm();
e=b;
}
return e;
}
private Binary readTerm() throws IOException
{
Binary b; Binary t;
t = readFactor();
while (st.ttype == '*' || st.ttype == '/')
{
b = new Binary();
b.term1 = t;
b.op = (char) st.ttype;
st.nextToken();
b.term2 = readFactor();
t=b;
}
return t;
}
private Binary readFactor() throws IOException
{
Binary b; Binary f = new Binary();
if (st.ttype == '(')
{
st.nextToken();
f = readExpression();
if (st.ttype == ')')
st.nextToken();
}
else
{
if (st.ttype == StreamTokenizer.TT_WORD)
{
b = new Binary(st.sval);
f = b;
st.nextToken();
}
else
{
if (st.ttype == StreamTokenizer.TT_NUMBER)
{
b = new Binary((int)st.nval);
f = b;
st.nextToken();
}
}
}
return f;
}

Encore une fois c'est laid, mais pour etre sur que ce soit bon je me suis calque sur le code du bouquin.

Vous devriez pouvoir apprehender ce que je dois faire now.

Comment rendre ca plus beau niveau typage, avec un type Expression, Factor, Term et Binary, sachat que readExpression doit retourner une Expression ( qui est en fait un binary), que Factor doit retourner un Factr ( qui est en fait un Binary), et Term pareil ?

Merci

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

mrbebert

Ton type Binary regroupe 2 choses distinctes :
- une addition/soustraction
- un élément terminal (un nombre ou une variable)

Je pense qu'il faut enlever le deuxième cas (c'est la classe Term qui s'en occupe).

Ca donnerait pour Binary

Code :

public class Binary extends Expression
{
public char op;
public Expression term1;
public Expression term2;
}

un objet Binary, c'est uniquement un opérateur (+ ou -) et deux expressions. term1 et term2 sont les 2 expressions à additionner ou soustraire.
Edit : en fait, l'objet Binary pourrait aussi traiter les multiplications/divisions

Pour Term, ce serait un truc comme ca

Code :

public class Term extend Expression
{
int type;
public int nval;
public String sval;
public Term() {
type = 0;
}
public Term(int i) {
type = 1;
nval = i;
}
public Term(String s) {
type = 2;
sval = s;
}
}

La fonction readExpression serait remontée au niveau de Expression.

Message édité par mrbebert le 21-10-2002 à 00:35:14

Tetedeiench

Head Of God

Attention, ne pas confondre TERM et TERMINAL

Term est comme un "terme" lors d'une pultiplication.

C'est un mot-clef au meme niveau qu'une expression.

Je rapelle la grammaire que j'utilise :

Expression -> Term | Expression + Term | Expression - Term
Term -> Factor | Term * Factor | Term / Factor
Factor -> Identifier | Literal | ( Expression )
Identifier -> (a..zA..Z)*
Literal -> (0..9)*

Les terminaux sont Identifier et Literal...

Pas Term, qui designe juste soit un factor, soit une operation * ou / ( t'es oblige de passer par la pour avoir la case gestion des priorites des operateurs).

Tu comprends mieux mon dilemne la mrbebert ?

base toi sur la grammaire au dessus, et dis toi que theoriquement, je dois implementer un type pour chaque ligne de la grammaire ( sauf les deux dernieres bien sur...).

Ah oui, il faudrait ( ce serait bien) que l'arbre ainsi genere soit facile pour se balader dedans Style pas trop de casts...

Par exemple un arbre avec des enchevetrements d'un seul type + des terminaux ca me semble pas mal ^^ mais faut savoir quand on va tomber sur un terminal quand on ne va pas tomber sur un terminal, et c pour ca que Binary fait les 2 dans mon raisonnement ( sinon erreur de type )

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

mrbebert

Forcément, on parlait pas la même langue

Mais je pense que 2 objets (ou 3 si tu fais la distinction Identifier/Literal) suffisent. Tu construis un arbre avec Binary pour les noeuds, et Identifier/Literal pour les feuilles.
A moins que tu ne veuilles distinguer addition/soustraction/muliplication/division en utilisant des objets différents.

Pour l'évaluation, c'est là qu'intervient l'héritage. Si les objets héritent de Expression, tu peux y définir une méthode evaluer qui sera implantée différemment selon l'objet :
- renvoie la valeur directement dans le cas d'une feuille
- renvoie term1.evaluer (+ ou - ou * ou /) term2.evaluer dans le cas d'un Binary.
Au moment de l'appel de term1.evaluer, tu ne sais pas si term1 est une feuille ou un Binary, mais ca n'a aucune importance. Pour toi, c'est une Expression, et la bonne méthode sera appellée en fonction de l'objet qui a été créé.

Pour ce qui est de la construction de l'arbre (avec les priorités des opérateurs) ca avait pas l'air mal. J'ai pas eu le temps de tout comprendre mais ca m'intéresse

D'après ce que j'ai compris, il n'y aurait pas grand chose à modifier :
- toutes les fonctions renvoient un objet de type Expression
- dans les 2 derniers cas, tu construis une feuille au lieu d'un Binary

Message édité par mrbebert le 21-10-2002 à 10:15:02

Tetedeiench

Head Of God

Je voulais juste faire ca plus "propre" avec des objets de type Expression, Factor... m'enfin la j'ai tout fait avec mon objet de type Binary et ca fonctionne d'enfer, alors je me dis que ce n'est pas la peine

Pour comprendre la grammaire sur le coup de la priorite, regarde bien comment elle marche en faisant l'arbre : Avec elle, les * et / seront toujours "plus bas" que les + et -, et donc seront evalues avant

---------------
L'ingénieur chipset nortiaux : Une iFricandelle svp ! "Spa du pâté, hin!" ©®Janfynette | "La plus grosse collec vivante de bans abusifs sur pattes" | OCCT v12 OUT !

Publicité

FORUM HardWare.fr

Programmation

Java

[Analyse syntaxique] La, faut qu'on m'explique un truc... spapossible.

Sujets relatifs
[java]Erreur que j explique pas!![/java]	Un truc tout simple je pense...
VBA cherche a faire un truc pas evident	Peut on faire un truc du style wait() dans un .bat ?
[flash] un truc tout bete, recuperer la valeur d'un bouton radio	Encore un truc à la mords moi le noeud!!!!
[Vb]truc tout bete	Quoi comme prog pour faire du java (dois bidouiller 1 truc dans *.jar)
[LISP] coloration syntaxique sous MS visual studio ?	un truc stupide .. lol une idée folle
Plus de sujets relatifs à : [Analyse syntaxique] La, faut qu'on m'explique un truc... spapossible.

Page générée en 0.097 secondes