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

Marsh Posté le 19-10-2002 à 23:36:23

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 !

Reply

Marsh Posté le 19-10-2002 à 23:36:23

Reply

Marsh Posté le 19-10-2002 à 23:47:27

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.

Reply

Marsh Posté le 19-10-2002 à 23:52:07

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 !

Reply

Marsh Posté le 19-10-2002 à 23:59:33

Tu connais le polymorphisme ?

Reply

Marsh Posté le 20-10-2002 à 00:02:20

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 !

Reply

Marsh Posté le 20-10-2002 à 00:04:06

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 !

Reply

Marsh Posté le 20-10-2002 à 00:06:25

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 !

Reply

Marsh Posté le 20-10-2002 à 00:46:03

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 !

Reply

Marsh Posté le 20-10-2002 à 02:19:13

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).

Reply

Marsh Posté le 20-10-2002 à 12:09:08

verdoux a écrit a écrit :

Tu connais le polymorphisme ?

+1 :heink:

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

Reply

Marsh Posté le 20-10-2002 à 12:09:08

Reply

Marsh Posté le 20-10-2002 à 16:49:44

en conclusion, faut tu cales un peu plus la POO

Reply

Marsh Posté le 20-10-2002 à 20:50:29

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 !

Reply

Marsh Posté le 20-10-2002 à 20:59:39

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 ?

Reply

Marsh Posté le 20-10-2002 à 21:08:57

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

Reply

Marsh Posté le 20-10-2002 à 21:42:06

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 !

Reply

Marsh Posté le 20-10-2002 à 22:58:49

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 !

Reply

Marsh Posté le 20-10-2002 à 23:19:49

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.

Reply

Marsh Posté le 20-10-2002 à 23:33:02

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 !

Reply

Marsh Posté le 20-10-2002 à 23:39:58

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 !

Reply

Marsh Posté le 20-10-2002 à 23:45:35

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:

Reply

Marsh Posté le 21-10-2002 à 00:05:58

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 !

Reply

Marsh Posté le 21-10-2002 à 00:22:21

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

Reply

Marsh Posté le 21-10-2002 à 00:55:52

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 !

Reply

Marsh Posté le 21-10-2002 à 09:55:11

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

Reply

Marsh Posté le 21-10-2002 à 18:14:03

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 !

Reply

Marsh Posté le

Reply

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

Sujets relatifs:

Leave a Replay