Sasume (./76) :
Est-ce que tu fais une analyse lexicale ?

c'en est un genre.

Oups, désolé. J'ai l'impression que je le fais au fur et à mesure. De manière assez contrainte, vu que j'exige ci ou ça après tel ou tel élément. Je sais plus comment ça se dit.

Je pense que découpler certaines responsabilités conduit à une meilleure lisibilité du code (donc un meilleur débugage), même si ça peut rajouter quelques lourdeurs.
Je te suggère de reconnaître complètement chaque token avant de le donner à manger à l’analyseur syntaxique (au lieu que tes fonctions d’analyse syntaxique avancent caractère par caractère, elles avancent token par token).

Tu approuves donc le principe de ma solution à ce niveau ?

Oui, si ça correspond à ./92 ^^ (après ce n’est que mon avis hein…)

YES !

J'ai enfin couché la forme de mon algo à partir de laquelle je vais coder !

Je suis resté sur mon idée première, mais je crois qu'à part les piles d'opérateurs/opérandes, je dois faire à peu près pareil que PpHd. J'aurai une récursion nécessairement limitée (je crois plus faible que la sienne (?), parce que je n'ai que 4 catégories de priorités dans mes opérateurs), hors évaluation d'expression entre parenthèses.

Finalement, j'ai simplifié mes deux fonctions de base, et c'est une troisième fonction, Decompose( EXPR ), qui est chargée de toute la merde, parenthèses et compagnie. Les deux premières deviennent toutes simples !

Et les symboles et labels seront gérés (différences de x labels, labels inconnus ou autres types de relogements. Je m'en faisais une montagne parce que je réfléchissais mal).
Seul petit hic, les demi/quarts de relogements. J'ai déjà mon idée (simple), mais je l'ai pas mise dans l'algo. C'est plus emmerdant qu'une addition ou une soustraction, parqu'il ne faut pas se contenter d'additionner le relogement à sa place, faut retenir qu'il faut le diviser, et par quel nombre, et ça seul le linker peut le faire.

Je mets le code, dès fois que, maintenant qu'il est devenu plus simple. Pour ceux qui regarderont, ne vous attardez pas sur Decompose() si vous voulez pas vous faire chier, sachez juste ce qu'il renvoie.

[box=algo]

Syntax: 
 
IMM	immediate 32 bits value 
OP	mathematical operator which is between the first IMM and the end of EXPR 
EXPR*	ptr to an expression 
 
--------------------------------------------------- 
 
IMM MainEval( EXPR* )						// EXPR* will be updated 
 
Decompose( EXPR )						// Create IMM, OP, EXPR2 
 
If OP == 0							// No operator ? 
	Then	IMM						// Ok, it's just a symbol or a number to evaluate 
	Else	Eval( IMM, OP, EXPR2 )				// Else evaluate the expression 
 
--------------------------------------------------- 
 
IMM Eval( IMM, OP, EXPR ) 
 
Decompose( EXPR )							// Create IMM2, OP2, EXPR2 
 
If OP2 == 0								// No operator ? 
	Then	OP( IMM, IMM2 )						// So its just an operation do to 
	Else	If OP >= OP2						// Else if priority( OP1 ) > Priority( OP2 ) 
			Then	IMM3 = OP( IMM, IMM2 )			// First perform the OP stuff 
				Eval( IMM3, OP2, EXPR2* )		// Then evaluate the end of the expression 
			Else	OP( IMM, Eval( IMM2, OP2, EXPR2* ))	// Else evaluate first the end of the expression, 
									// then perform the OP stuff 
 
--------------------------------------------------- 
 
IMM OP EXPR Decompose( EXPR ) 
 
/* 
In entry, we have an expression. 
The goal is to return : 
- its first numeric element 
- the next operator 
- a ptr to the end of the expression 
 
We can find : 
- a negate sign 
- an opening bracket 
- a number (binary, decimal or hexadecimal form) 
- a defined symbol (integer or relocated symbol) 
- an undefined symbol (label) 
- an operator 
*/ 
 
Begin: 
If NegateSign() 
	Then	SetFlagNegate()			// Local flag 
 
If OpenBracket() 
	Then	SkipBracket() 
		BracketCount++ 
		MainEval( EXPR )		// Get IMM 
		While CloseBracket() 
			BracketCount--		// Error if BRACKET_COUNT < 0 
		Goto	ReadOperator 
 
If Number() 
	Then	EvalNumber()			// Get IMM 
		Goto	ReadOperator 
 
If DefinedSymbol() 
	Then	GetSymbolValue()		// Get IMM 
		Goto	ReadOperator 
 
If UndefinedSymbol() 
	Then	AddReloc 
		SetFlagRelocType() 
		Goto Begin 
 
ReadOperator: 
 
ApplyNegate( IMM ) 
 
ReadOperator()					// Get OP 
 
Return( IMM, OP, EXPR* )			// Return

[/box]

Evidemment, tous vos conseils/critiques/remarques sont les bienvenus

Sasume -> au final, avec ça, je ne lirai qu'une fois chaque caractère de mon expression, sans aller chercher "en avant".

Comment évalues-tu l’expression « 3 - 2 + 1 » ? (j’ai l’impression que ça produira « 3 - (2 + 1) »)

Exactement :

-> MainEval( *( 3 - 2 + 1 ))			// On part de l'adresse d'une expression 
 
Decompose( *( 3 - 2 + 1 )) 			// On décompose, on obtient int 3, SIGN -, PTR *( 2 + 1 ) 
 
 
 
-> Eval(3, -, *( 2 + 1 ))			// On évalue tout ça 
 
Decompose( *( 2 + 1 ))				// On décompose, on obient int 2, SIGN +, PTR *(1) 
 
ComparePriorité( -, + )				// On compare les priorités, elles sont égales, 
 
Moins( 3, 2 ) -> 1				// Donc on résoud là première opération 
 
-> Eval( 1, +, *( 1 ))				// On continue, vu qu'on a encore au moins un opérateur à traiter 
 
Decompose( *( 1 ))				// On obtient int 1, SIGN NONE, PTR *( après 1) 
 
Return( Plus( 1, 1 ))				// Comme SIGN == NONE, on résoud l'opération et on reviens

Cool

Donc c'est faux.

C'est le problème avec le parsage LL(1), les opérations "associatives à gauche" (le plus courant) posent problème.

Ah ? Tu peux me dire en quoi ? Je ne vois pas, je suis preneur d'une explication. Si c'est associatif à gauche et pas à droite, le résultat est 0 en effet. Mais je peux le résoudre simplement, c'est un simple bhi à la place d'un bcc me semble-t-il. Ou mieux, la modification de mes constantes OPERATOR :

OP_NONE		$0000 
OP_PLUS		$0101 
OP_MINUS	$0201 
OP_MUL		$0102 
OP_DIV		$0202

L'octet inférieur, c'est la priorité, l'octet supérieur, c'est le type d'opération. Je peux mettre le - plus prioritaire que le + ($0202) puis augmenter la priorité de MUL/DIV et c'est bon.

PS -> Cette priorité dans l'associativité est nécessaire ? Ou je peux la spécifier à ma guise ? Le parseur de PpHd me sort 2 par exemple.

Normalement, + et - doivent avoir la même priorité!

Donc tu as 2 opérations de la même priorité:

x OP y OP z

On dit que l'opération ou la famille d'opérations (genre + et -) OP est associative à gauche si:

x OP y OP z = (x OP y) OP z

On dit que l'opération ou la famille d'opérations (genre + et -) OP est associative à droite si:

x OP y OP z = x OP (y OP z)

L'associativité à gauche ou à droite est une question de conventions, pas une propriété intrinsèque de l'opération, mais la convention courante est que {+,-} est associatif à gauche.

On dit que l'opération ou la famille d'opérations (genre + et -) OP est associative si:

(x OP y) OP z = x OP (y OP z)

(Là, c'est une propriété intrinsèque de l'opération.) On peut donc noter:

(x OP y) OP z = x OP (y OP z) = x OP y OP z

et par conséquent l'opération sera à la fois associative à gauche et associative à droite.

+ est associatif, mais - ne l'est pas, donc la famille {+,-} non plus! Donc si tu parses de manière associative à droite, le résultat ne correspondra pas aux conventions (associativité à gauche).

Le problème, c'est que si tu parses top-down de gauche à droite (LL), tu construis toujours des arbres associatifs à droite. Les arbres associatifs à gauche demandent une récursion (un appel récurrent) à gauche et ce n'est pas possible en parsage LL (tu tombes en une récurrence infinie). Il existe différentes bidouilles pour corriger ça, mais la méthode la plus propre est de parser en LR (bottom-up de gauche à droite). Mais pour ça, il faut construire une table, tu ne peux pas le faire avec un parseur écrit directement à la main.

Je ne comprends pas ce que dit Kevin. L'algo de Martial fini par faire "1+1". C'est bien ça la dernière opération à effectuer non ?

3-2+1 = (3-2)+1. L'algorithme de Martial donne 3-(2+1), ce qui est totalement faux.

J'ai du mal comprendre ce qu'il a répondu dans un cadre blanc pour Sasume (./97).
J'avais écrit un algo qui construisait un arbre à partir d'un expression comportant plein d'opérateurs (ceux du C), en ignorant complètement ces notions de grammaires LL1 et compagnie. Il était récursif et se contentait d'arbres (de quelle table parles-tu ? pourquoi est-ce impossible à faire soi-même ?) : ça semblait marcher quand je l'exécutais à la main (je n'ai jamais eu le temps de l'implémenter).

J'attends l'avis de PpHd pour ce qu'il convient d'implémenter. Je peux résoudre ça à coup de priorité, même si ça n'a pas la propreté attendue. Ce qui m'embête, c'est que Maylib n'agit pas comme tu le dis Kevin ...

Thibaut (./102) :
Je ne comprends pas ce que dit Kevin. L'algo de Martial fini par faire "1+1". C'est bien ça la dernière opération à effectuer non ?

Oui.

J'ai du mal comprendre ce qu'il a répondu dans un cadre blanc pour Sasume (./97).

Merde. J'ai du mal à m'expliquer, ça doit pas être clair. Le raisonnement est pourtant ultra simple.

Thibaut, c'était du parsage par découpage, peut-être, ton truc? (C'est essentiellement du bottom-up, ça, et c'est la manière de laquelle je codais intuitivement le parsage avant d'avoir appris le parsing.) Ce que j'appelle "parsage par découpage", c'est: on veut découper "x+y-z", donc on recherche + et -, en partant de la droite parce que c'est associatif à gauche. Donc on coupe en "x+y" et "z". Le problème, c'est que ça coupe les chaînes en 2 à chaque découpage, donc soit tu copies, soit tu détruis l'original en remplaçant l'opération par des \0. Et tu traverses les chaînes plusieurs fois aussi, donc l'efficacité n'est pas top. Et en plus, tu dois bidouiller quand il y a autre chose que des opérateurs, genre des parenthèses, sinon tu feras des bêtises là aussi.

Cela dit, ce que fait Folco m'a l'air de ressembler à ça, donc dans ce cas c'est facile de corriger la priorité. (Il faut rechercher à partir de la droite quand on découpe pour un opérateur associatif à gauche.)

Est-ce que le fait de dire que dans tous les cas (à droite comme à gauche) le - est prioritaire sur le + résoudrait le problème ?

Folco (./16) :
C'est surpuissant cette approche Sasume, ça permet de parser n'importe quoi avec le même code, pour peu que tu redéfinisse une nouvelle grammaire, je me trompe ?

Et puis, même question que squalyl, en plus "polissé", ai-je besoin de passer par cette étape nécessairement ? Ne puis-je pas faire quelque chose de plus intuitif ?
L'assembleur est simplissime en soi, sur une ligne, on a :

LABEL | DIRECTIVE | COMMENT
[...]

En fait tu peux le faire autrement, c'est juste super joli de coder un assembleur avec la méthode à Sasume, et ça t'évite un max d'erreurs.
En plus avec ce principe ça devient plus aisé de supporter les macros, includes et autres directives. Genre un move peut s'écrire comme ça si tu as les fonctions qui vont bien:

Jeton *j = lit(IDENTIFICATEUR);     // Génère une erreur "identificateur attendu" s'il y a autre chose 
if (j) { 
    if (!strcmp(j->texte, "move")) { 
        instr_move(); 
    } 
    else 
        erreur("instruction inconnue"); 
} 
 
void instr_move() { 
    Jeton *j; 
    int largeur, valeur; 
    enum {IMMEDIAT, REGISTRE} mode[2]; 
 
    lit(POINT);     // Je crois que c'est obligatoire, erreur sinon 
    j = lit(IDENTIFICATEUR); 
    if (!strcmp(j->texte, "b")) 
        largeur = 1; 
    else if (!strcmp(j->texte, "w")) 
        largeur = 2; 
    else if (!strcmp(j->texte, "l")) 
        largeur = 4; 
    else 
        erreur("largeur: b, w ou l attendu"); 
 
    if (prochain(DIESE)) {    // mov #imm, ... 
        lit(DIESE); 
        valeur = litEntier();    // genre atoi(lit(NOMBRE)->texte) avec support de l'hexa et autres 
        mode[0] = IMMEDIAT; 
    } 
    else if (prochain(IDENTIFICATEUR)) {    // mov reg, ... 
        ... 
    } 
    ... 
}

A noter que pour bien faire (je te préviens pour gérer les sauts et tout ça ne va pas être facile, d'où l'intérêt d'utiliser des structures faciles à maîtriser pour toi plutôt que du bidouillage) tu fais bien de générer des instructions intermédiaires, qui peuvent être liées entre elle (si elles utilisent un label en fait). Ensuite tu produis du code en fonction de ces instructions intermédiaires, et tu peux gérer des liens sans trop de peine. Le truc c'est que tu vas sûrement être amené à regénérer plusieurs fois du code, car les instructions n'ont pas une taille fixe, et tu ne sais donc pas à l'avance quelle sera l'adresse d'un label déclaré plus tard.
Je te mets un lien vers ma console virtuelle pour laquelle j'ai justement implémenté un assembleur comme ça:
http://www.playeradvance.org/forum/showthread.php?t=32838

Folco (./108) :
Est-ce que le fait de dire que dans tous les cas (à droite comme à gauche) le - est prioritaire sur le + résoudrait le problème ?

Non.
1. Si tu as x-y-z, tu n'as pas de + du tout et il faut l'associativité à gauche ici.
2. Dans x-y+z, - est prioritaire sur +, dans x+y-z, + est prioritaire sur -. C'est vraiment l'ordre des opérations qui compte (parmi + et -), pas leur nature.
(Bon OK, dans 2., le résultat sera le même pour des entiers (mais pas pour des flottants!), mais dans 1., non!) C'est vraiment une histoire d'associativité, pas de priorité.

Ok. je suis dans la merde. J'attends définitivement l'avis de PpHd, sachant que son parseur fait la même chose que le mien.

Kevin, est-ce que la solution suivante (moins pratique pour ajouter de nouveaux opérateurs — enfin des opérateurs qui auront des priorités différentes de celles déjà gérées par le système) qui consiste à écrire une grammaire des expressions :

expr := fact (('+'|'-') fact)* 
fact := val (('*'|'/') val)* 
val := identificateur | constante | '(' expr ')'

Puis à partir de ce modèle, écrire le code comme ceci :

int expr(Lexer *lexer) 
{ 
  int v = fact(lexer); 
  Token t = token(lexer) 
  while(t == '+' || t == '-') 
  { 
    if(t == '+') 
      v += fact(lexer); 
    else 
      v -= fact(lexer); 
  } 
  return v; 
}

fonctionne ? Pour moi, l’entrée « a + b - c - d » sera parsée comme ceci : « (((a + b) - c) - d) », donc avec une associativité à gauche, non ?

Merci pour tes explications Kev'. Je ne faisais pas de découpage, ça ne correspond pas a ce que tu dis. De mémoire, sur ton exemple x+y-z ça devait donner :

on lit x => construction d'une feuille représentant x
on lit + => construction d'un nœud représentant l'addition et rattachement de la feuille precedente sur la partie gauche du nœud
on lit y => construction d'une feuille représentant y et rattachement a la partie droite du nœud
on lit - => construction d'un nœud representant la soustraction et rattachement du nœud précédent sur la partie gauche du nouveau noeud
on lit z => construction d'une feuille représentant z et rattachement a la partie droite du nouveau nœud

Voilà. En réalité c'était complexe, là j'ai donné le grand principe. En réalité , c'était une fonction récursive qui s'appelait pour chaque element, que ce soit un identificateur ou un opérateur. Elle prenait en argument la feuille ou le nœud venant d'être créé afin de pouvoir le relier au nœud représentant l'opérateur a traiter. Elle retournait le nœud créé.

Je raconte ca de tête. C'était probablement un peu plus subtil.

Ouai une subtilité évidente me revient : avant de rattacher la feuille (l'identificateur) a la partie droite du noeud precedent, on lisait le token suivant. Si ce token était un opérateur de priorité supérieure à l'opérateur représenté par le nœud précédent, alors on lançait la fonction en lui donnant la feuille comme opérande de gauche, et on rattachait le nœud retourné par cette récursivité à la partie droite du nœud précédent.

Pour résumer, si je suis difficile à suivre, je construisais des sous-arbres incomplets qui se rattachaient les uns aux autres au fur à mesure de l'avancée dans l'expression (et des retours de sommets lors de la rencontre d'operateurs de priorité inférieure), et le tout se faisait en une seule passe, avec lecture de deux tokens à l'avance.

YAYAYAYAYAYAYAYAYAYAYAYAYATUOA CVZEKJTRVANJERBJTV? AEKLTDREAZLTKRGV?AZT.RVLQSKDTFAVZ?ITOAZ?VR KQSLDTKREBV2?POTR



Putain j'ai cru que j'y arriverais jamais !!

Pas testé les parenthèses encore. Ca devrait aussi marcher avec les nombres hexa et binaires (fonctions déjà testées)
J'ai implémenté que /*-+, et des fausses opérations (sur 16 bits, pas sur 32). Donc ya encore du boulot, mais le principe marche

La récursivité marche, les priorités aussi. Les parenthèses sont implémentées (d'ailleurs mon algo au-dessus est faux). Ah putain ça fait plaisir

[23:17] <Folco_> YAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
[23:17] <Folco_> PUTAN CA MARCHE !!!!!!!!!!!!!!!!!!!!!

Bravo Tu vois l'analyse grammaticale a quelque chose de jouissif !
Pedrom aussi. Il n'y manque plus que GTC et je foncerais l'installer.

Rah purée les parenthèses aussi ça marche



J'ai juste un problème avec les hexa bizarement, faut que je regarde, mais c'est sûrement trois fois rien.

Par contre, la symbole % est pas bindé sur le clavier ? Au pire, je vais remplacer quelque chose, mais faudrait prévoir ça. ^^

Pedrom aussi.

Hein t'as vu ça, il me faut que deux lignes pour récupérer ce que je passe en ligne de commande.