./57 Il y a un joli bloc de commentaires au début de la fonction may_parse_c

./58 Donc ce n’est pas une expression ^^

Sasume (./59) :
./58 Donc ce n’est pas une expression ^^

Sauf que :
move.l #kernel::LibsBegin+42,d0 est une expression comme une autre.

#parti voir _may_parse_c# #merci#

Oui, c'est fort intéressant en effet. Ok pour la phase 1. Par contre, pour la 2, je pige que dalle :

      Operande Stack 
      Operator Stack 
 
      Assert OpcRef == OpRef or Opcrec == OpRef-1 
 
      Add Operande (op): Op[OpRef++] = op 
      Add Operator (opc): 
            While OpcRef>=1 && Priority(opc) <= Priority(Opc[OpcRef]) 
	       code = Opc[--OpcRef] 
	       op   = code( Op[--OpRef], Op[--OpRef]) 
	       OpRef[OpRef++] = op 
	    3 Prio: +,-  *,/   ^ 
 
      Finish: 
            While OpcRef>=1 
               func = Opc[--OpcRef] 
               op   = func( Op[--OpRef], Op[--OpRef]) 
               OpRef[OpRef++] = op 
	    ASSERT (OpRef == 1)

J'aurais besoin d'un truc clair, comme pour la première phrase, et j'ai de l'algo C-like. Bref, je pige rien à cette partie, dommage car c'est elle qui traite visiblement des opérateurs, priorités etc...
Quelqu'un me traduira ?

Folco (./60) :

Sasume (./59) :
./58 Donc ce n’est pas une expression ^^

Sauf que :
move.l #kernel::LibsBegin+42,d0 est une expression comme une autre.

Ah, donc c’est une expression ^^
Dans ce cas le symbole donne son adresse, non ?

Pour may_parse_c t’as de la chance il y a plein de goto dans le code, donc ça ressemble presque à de l’asm . Le pseudo code explique comment empiler les opérateurs de façon à respecter leurs priorités respectives.

Sasume (./62) :
Ah, donc c’est une expression ^^
Dans ce cas le symbole donne son adresse, non ?

Plus que ça, et ça n'apparait pas dans mon code cité plus haut.

Je vais avoir besoin de deux tables de symboles :
- une table pour les symboles possédant seulement une valeur numérique : adresse, valeur
- une table pour les stmboles comprenant un relogement : adresse, flag (type de relogement, tios::truc, ramcall::truc, etc..), valeur numérique, numéro de relogement (trucnuméro, tios::numéro).
Je fais deux tables pour gagner en mémoire.

Donc un symbole renverra une valeur numérique, + un flag indiquant la présence éventuelle d'un relogement.

Si c'est foireux,dites-le.

Sasume (./62) :
Le pseudo code explique comment empiler les opérateurs de façon à respecter leurs priorités respectives.

Ah ! C'est précisément ça qui me manque et qui m'oblige à faire une estack dans laquelle je résoudrai en fonction des priorités !

Sasume (./56) :
Déjà, est-ce que c’est vraiment nécessaire de considérer que expr(identificateur) corresponde au produit expr × identificateur ?
Si oui, le plus simple serait d’interdire l’utilisation de a0 comme identificateur, c’est un mot réservé.

Tu as raison, je ne devrais permettre une parenthèse ouvrante que si elle n'est pas précédée d'un nombre. Sinon, c'est autre chose.

squalyl (./55) :
l'idéal c'est d'arriver à transformer une expression 1 * ( 2 + 3 ) en RPN

Je suis d'accord avec toi, c'est l'idéal, mais j'arrive ps à le concevoir...

Cherche "cours analyse syntaxique" sur un moteur de recherche. En fouinant tu devrais pouvoir dénicher une présentation qui ne rentre pas trop dans le détail et se contente des principes.

Folco: ça repose puissamment sur la récursivité.

Ce qui n'est pas pour me déplaire, aimant beaucoup le scheme. J'essaye d'imaginer.

hinhin, j'entrevois ce que ça peut donner...

Ce n'est pas un algorithme très compliqué, il est même expliqué en français sur wikipédia
http://fr.wikipedia.org/wiki/Notation_polonaise_inverse

oui mais ça il connait.

ce qu'il te faut c'est écrire un parseur de grammaire.

en gros

expression => ( expression )
expression => facteur + facteur
facteur => operande * operande

tu vois qu'il y a deux possibilités pour parser une expression
soit
-manger (
-parser expression
-manger )

soit
-manger facteur
-manger +
-manger facteur

il faut savoir qui on appelle, avec un switch()
manger_expression:
lire prochain token
si prochain token = "("
manger_expression recursivement
sinon si prochain token = nombre
manger_facteur
manger_plus
manger_facteur
generer estack
sinon
erreur de syntaxe

manger_plus:
lire prochain token
si pas +: erreur

manger facteur:
lire prochain token
si pas nombre => erreur syntaxe
s'en souvenir
lire prochain token
si * => ce sera une multiplication
sinon => erreur syntaxe
lire prochain token
si pas nombre => erreur
construire estack

etc

pour une version complète, il te faut te documenter sur les grammaires LL(1). Les grammaires LALR sont trop compliquées pour juste une expression.

Merci pour tout. Je suis très gêné et ravi de toutes l'aide que vous m'apportez tous.

Je suis en train de me rappeler mes cours d'algos récursifs, en réécrivant ce genre de trucs qui devraient m'aider à me rappeler de tout ça :

fact( n ) 
	(if	(= n 1) 
		1 
		(* n fact( n-1 )))

Bon, une heure pour pondre cet algorithme, j'aimerais savoir ce que vous en pensez. Ca m'a l'air 100 fois plus sérieux que ma proposition d'hier (déjà à moitié codée, c'est malin, je ferais bien de m'arrêter réfléchir plus...)

MainEval( EXPR ) 
Si (EXPR n'a pas d'opétateur) 
	Alors	EXPR 
	Sinon	Eval( arg1 OP arg2 )		// EXPR == arg1 OP arg2 
						// arg1 est la première valeur numérique trouvée 
						// arg2 est le reste de l'expression, et peut contenir 
						// lui-même plusieurs opérations 
						// OP est l'opérateur qui les sépare 
 
 
Eval( arg1 OP arg2 ) 
Si (arg2 n'a pas d'opérateurs) 
 
	Alors	OP( arg1 , arg2 ) 
 
	Sinon	Si Priorite( OP1 ) > Priorite( OP2 )			// On décompose alors arg2 == arg3 OP2 arg4 
 
			Alors	OP1( arg1 , arg3 ) -> arg1		// On résoud l'opérateur prioritaire 
				Eval( arg1 OP2 arg4 )			// Récursion terminale, vu qu'on a déjà 
									// le premier résultat 
 
			Sinon	OP1( arg1 , Eval( arg3 OP2 arg4 ))	// Là on a Priorite( OP1 ) < Priorite( OP2 ) 
									// Récursion profonde, vu qu'on a pas encore le 
									// résultat de arg1 OP arg2

L'idée est qu'on peut appliquer un opérateur si on en a pas de prioritaire derrière. S'il n'y en a pas, on peut résoudre ce que l'on a trouvé, sinon, il faut attendre d'avoir le résultat suivant pour pouvoir exécuter l'opération.

Ecoute, je sais pas si c'est exactement ça, mais en tout cas tu chauffes, c'est clair.

C'est là qu'il te faudrait connaitre des langages pratiques pour pouvoir tester ça avant de l'implémenter en asm ^^

squalyl (./72) :
Ecoute, je sais pas si c'est exactement ça, mais en tout cas tu chauffes, c'est clair.

\o/

squalyl (./72) :
C'est là qu'il te faudrait connaitre des langages pratiques pour pouvoir tester ça avant de l'implémenter en asm ^^

Seul le TI-Basic est à ma portée j'ai bien peur. Mais je pense que je devrais aller plus vite à implémenter ça en assembleur.

j'ai essayé d'améliorer, en descendant plus dans les détails de l'implémentation, et surtout en ajoutant les parenthèes (du moins, la parenthèse ouvrante, je pense qu'il faut un compteur pour la parenthèse fermante).

Chiffres : 
$~0123456789abcdefABCDEF 
 
Opérateurs unaires, à résoudre immédiatement : 
~ - 
 
Opérateurs, par ordre de priorité : 
[+ -] [* /] [<< >>] [& |] 
 
Opérateur mettant un flag global : 
# 
 
 
IMM MainEval( EXPR ) 
Si (EXPR n'a pas d'opétateur) 
 
	Alors	EXPR -> IMM			// Il ne s'agit que d'un chiffre ou d'un symbole à lire 
 
	Sinon	EXPR -> arg1 OP arg2		// On décompose EXPR 
						// arg1 est la première valeur numérique trouvée 
						// arg2 est le reste de l'expression, et peut contenir 
						// lui-même plusieurs opérations 
						// OP est l'opérateur qui les sépare 
		Eval( arg1 OP arg2 ) 
 
 
 
 
 
IMM Eval( arg1 OP arg2 ) 
Si (arg2 commence par une parenthèse) 
 
	Alors	Eval( arg1 OP MainEval( arg2 ))				// récursion terminale 
 
 
Si (arg2 n'a pas d'opérateur) 
 
	Alors	OP( arg1, arg2 ) 
 
	Sinon	arg2 -> arg3 OP2 arg4 					// On décompose alors arg2 == arg3 OP2 arg4 
		Si Priorite( OP1 ) > Priorite( OP2 ) 
 
			Alors	OP1( arg1 , arg3 ) -> arg1		// On résoud l'opérateur prioritaire 
				Eval( arg1 OP2 arg4 )			// Récursion terminale, vu qu'on a déjà 
									// le premier résultat 
 
			Sinon	OP1( arg1 , Eval( arg3 OP2 arg4 ))	// Là on a Priorite( OP1 ) < Priorite( OP2 ) 
									// Récursion profonde, vu qu'on a pas encore le 
									// résultat de arg1 OP arg2 
 
 
arg1 est une valeur numérique 
arg2 est un pointeur la suite de l'expression 
OP est un tag

./71 Je ne suis pas sûr de voir comment ce sera appelé avec, mettons, l’expression a + b * c en entrée ? Que vaudra arg1 ? Et que vaudra arg2 ? À chaque fois tu seras obligé d’aller jeter un coup d’œil en avance dans les arguments pour voir s’ils contiennent des expressions compliquées
Enfin, peut-être que ton idée marche, mais pourquoi ne pas suivre l’algorithme plus simple donné dans wikipedia ? Et, surtout, est-ce qu’une telle méthode te permettra de gérer les expressions contenant des labels encore inconnus ? Est-ce que tu veux pouvoir prendre en compte ce genre de choses ?
Si tu n’as pas trop d’opérateurs différents, c’est plus facile d’écrire quelque chose comme j’ai commencé à écrire en ./15 (ou que squalyl a repris en ./69

Est-ce que tu fais une analyse lexicale ?

Tiens, à la fin de l'article wikipedia, il y a un lien vers un programme TI68k assez génial : http://www.perez-franco.com/symbulator/download/rpn.html

L'utiliser quelques minutes t'aidera peut-être à appréhender la NPI ?

, je le cherchais

Ca se désinstalle comment par contre ce truc ? :s


EDIT : Waho j'vais devoir tester

La NPI ne me fait pas peur, seulement c'est sa construction qui ne me semble pas évidente.

Sasume (./75) :
Je ne suis pas sûr de voir comment ce sera appelé avec, mettons, l’expression a + b * c en entrée ? Que vaudra arg1 ? Et que vaudra arg2 ?

MainEval( a+b*c ) -> Eval( a, +, b*c ) -> Add( a, Eval( b*c ) -> Add( a, Mul( b,c ))

Sasume (./75) :
À chaque fois tu seras obligé d’aller jeter un coup d’œil en avance dans les arguments pour voir s’ils contiennent des expressions compliquées

Ouep, c'est con en effet, mais peut-être améliorable (je ne chercherai qu'un opérateur, s'il y en a un c'est marre)

Sasume (./75) :
Enfin, peut-être que ton idée marche, mais pourquoi ne pas suivre l’algorithme plus simple donné dans wikipedia ?

Je comprends pas tout aux formules classiques (sic) de WP...

Sasume (./75) :
Et, surtout, est-ce qu’une telle méthode te permettra de gérer les expressions contenant des labels encore inconnus ?

Oui. Ca fera un relogement.


ps -> ça me gave...

Laisse tomber pour l'instant, tu y reviendras plus tard. Il vaut mieux avancer pour rester motivé.
Nan ?

1. pas mon habitude
2. j'en ai besoin
3. j'essaye de décrypter la seconde partie de l'algo de PpHd

Réécriture de l'algo utilisé:

 
  /* We can have: 
     + an operator: + - * / ^ 
     + a variable: starts with a letter 
     + a function: starts with a lettre, finished by a '(' 
     + an int: starts with a number. 
     + a float: starts with a number. Contains 'E' and '.'. 
     + a list: starts with '{' 
     + a parenthesis: starts with '(' 
 
     We use: 
       + a stack of operande 
       + a stack of operator. 
 
     Read a char: 
     Phase 1: Get the new operand. 
      Skip SPACE 
      Read negate operator, and skip it. 
      If it is a letter, scans for variable/function. 
         If it is a variable, push it in the operand stack. 
	 If it is a function, parse the arguments as a list - allow list- 
	 and push it in the operand stack. 
      If it is a number, scans for 'E' or '.' while there are digits, and then: 
         Build Int and push in the operand stack. 
	 Build Float and push in the operand stack. 
      If it is a parenthesis, parse the sub-express recursively, check for and ending ')'   and push in the operand stack. 
      Else stop parsing (Pop last Operator before finishing). 
      If there was a negate operator, negate the pushed operator 
       (Well in fact, it is a little big more complicated due to -x^-2 ;) ) 
 
     Phase 2: Evaluate the old operators if needed and push the new one. 
      Skip SPACE. 
      If it is an operator, add it in the operator stack so that 
         all pushed operators have bigger priority than this one. 
	 If an already pushed operator has higher or equal priority 
	 Then eval the operator (pop it) over the two pushed operands (pop them), 
	 and push the new evaluated operand. 
      Else stop parsing. 
 
      Go to Phase 1 to read the new operand. 
 
      Phase Finish: 
        Finish by evaluating the pushed operators: 
            While OpcRef>=1 
               func = Opc[--OpcRef] 
               op   = func( Op[--OpRef], Op[--OpRef]) 
               OpRef[OpRef++] = op 

Ok. D'abord merci !

Tu marches avec deux piles, une d'opérateurs et une d'opérande. Au niveau mémoire, tu gères ça comment ? Dans la pile ? T'as une taille de pile fixe ?

Le seul truc qui me fasse chier et que j'arrive pas à résoudre dans mon algo, ce sont les parenthèses, et ta manière de t'y prendre le résoud.

Je vais tacher de réécrire ça pour voir si j'ai bien tout capté.

Folco (./83) :
T'as une taille de pile fixe ?

Oué. De 6 éléments je crois. Il suffit juste de voir que la taille max de la pile est atteinte lorsqu'on a tous les opérateurs. Il sont donc une pile de taille "nombres d'opérateurs différents" pour les opérateurs et l'autre juste +1 :
#define MAX_OPERATOR_STACK 6
#define MAX_OPERANDE_STACK MAX_OPERATOR_STACK+1
Mais la pile est locale à la fonction : ie elle est ré allouée à chaque appel récursif.

Oué chs'ui con, puisque après tu résouds au fur et à mesure que tu trouves des opérateurs de plus grande ou égale priorité, tu ne peux pas avoir deux fois le même opérateur.

Mais j'ai l'air tout con maintenant, ça a l'air facile, et j'ai pas trouvé

Bon, j'ai réussi à coucher un algo qui me semble complet (manque juste les labels, mais c'est rien, c'est résoudru par ailleurs.

Ce qui me fait suer, c'est que l'algo de PpHd me semble mieux en vitesse et en mémoire, mais j'aimerais bien essayer le mien (qui devrait rester rapide pour les expressions simples, ie dans 99% des cas).

IMM , Ptr_apres_EXPR MainEval( EXPR ) 
Si (EXPR n'a pas d'opetateur) 
  
	Alors	Si (EXPR termine par une parenthese fermante) 
			BR_COUNT--				// Erreur si <0 
		EXPR -> IMM					// Il ne s'agit que d'un chiffre ou d'un symbole à lire 
  
	Sinon	EXPR -> arg1 OP arg2				// On décompose EXPR  
								// arg1 est la premiere valeur numerique trouvee 
								// arg2 est le reste de l'expression, et peut contenir  
								// lui-meme plusieurs opérations 
								// OP est l'operateur qui les sépare 
		Eval( arg1 OP arg2 )  
 
 
 
 
IMM Eval( arg1 OP arg2 )  
Si (arg2 commence par une parenthese) 
  
	Alors	BR_COUNT++ 
		MainEval( arg2 ) -> arg2						// On stocke le resultat 
		Si (Operateur_apres_parenthese)						// Du boulot apres la parenthese ? 
 
			Alors Si( Priorite( OP ) < Priorite(Operateur_apres_parenthese)	// Si c'est prioritaire 
 
				Alors	arg2 -> arg3 OP2 arg4				// On decompose 
					OP( arg1, Eval( arg3 OP2 arg4 ))		// Et on appelle dans le bon ordre 
 
				Sinon Eval( OP1( arg1, arg2 ) OP2  arg3)		// Sinon on resoud la premiere operande 
											// avec le resultat de la parenthese 
			Sinon OP( arg, arg2 )						// Si il n'y a rien apres la parenthese, 
											// on a une simple operation a faire 
 
  
Si (arg2 n'a pas d'opérateur)  
  
	Alors	OP( arg1, arg2 )  
  
	Sinon	arg2 -> arg3 OP2 arg4 					// On decompose alors arg2 == arg3 OP2 arg4 
		Si Priorite( OP1 ) > Priorite( OP2 )  
  
			Alors	OP1( arg1 , arg3 ) -> arg1		// On resoud l'operateur prioritaire 
				Eval( arg1 OP2 arg4 )			// Recursion terminale, vu qu'on a deja 
									// le premier resultat 
  
			Sinon	OP1( arg1 , Eval( arg3 OP2 arg4 ))	// La on a Priorite( OP1 ) < Priorite( OP2 ) 
									// Recursion profonde, vu qu'on a pas encore le 
									// resultat de arg1 OP arg2 
  
  
arg1 est une valeur numerique 
arg2 est un pointeur la suite de l'expression  
OP est un tag

Ca me semble bon, même si c'est sûrement trop complexe. Mais je verrai ça demain, à tête reposée. En tout cas, je suis rassuré d'avoir la solution de PpHd au cas où, même si j'aime bien essayer de me démerder.

En tout cas, un grand merci à tous.

Pour le code en C que tu ne comprends pas: tigcc -S.

Pas con, merci, j'y pense jamais.

Mais ce que PpHd a expliqué, c'est la spec de son algo écrit en C-like, donc j'aurais eu du mal.

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