60

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

./59 Donc ce n’est pas une expression ^^
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

61

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

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

dehors #parti voir _may_parse_c# #merci#

62

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... sad
Quelqu'un me traduira ?

63

Folco (./61) :
Sasume (./60) :
./59 Donc ce nâ&#x20AC;™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 tripo. Le pseudo code explique comment empiler les opérateurs de façon à respecter leurs priorités respectives.
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

64

Sasume (./63) :
Ah, donc câ&#x20AC;™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 (truc@numé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. grin
Sasume (./63) :
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 !

65

Sasume (./57) :
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 (./56) :
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... sad

66

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.
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

67

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

68

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

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

69

Ce n'est pas un algorithme très compliqué, il est même expliqué en français sur wikipédia smile
http://fr.wikipedia.org/wiki/Notation_polonaise_inverse
Visitez mon site : http://www.bobti89.fr.st
Testez mon forum ici

70

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.

71

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

72

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.

73

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 ^^

74

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

\o/
squalyl (./73) :
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. grin Mais je pense que je devrais aller plus vite à implémenter ça en assembleur.

75

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

76

./72 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 ./16 (ou que squalyl a repris en ./70
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

77

Est-ce que tu fais une analyse lexicale ?
avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »

78

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 ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

79

love, je le cherchais happy

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


EDIT : Waho j'vais devoir tester happy

80

La NPI ne me fait pas peur, seulement c'est sa construction qui ne me semble pas évidente.
Sasume (./76) :
Je ne suis pas sûr de voir comment ce sera appelé avec, mettons, lâ&#x20AC;™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 (./76) :
À chaque fois tu seras obligé dâ&#x20AC;™aller jeter un coup dâ&#x20AC;™Å&#x201C;il en avance dans les arguments pour voir sâ&#x20AC;™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 (./76) :
Enfin, peut-être que ton idée marche, mais pourquoi ne pas suivre lâ&#x20AC;™algorithme plus simple donné dans wikipedia ?

Je comprends pas tout aux formules classiques (sic) de WP...
b5660bfd2f65a1a3b02d35a6f948ba11.png
Sasume (./76) :
Et, surtout, est-ce quâ&#x20AC;™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...

81

Laisse tomber pour l'instant, tu y reviendras plus tard. Il vaut mieux avancer pour rester motivé.
Nan ?
avatar
Un site complet sur lequel vous trouverez des programmes et des jeux pour votre calculatrice TI 89 / Titanium / 92+ / Voyage 200 : www.ti-fr.com.
Quelques idées personnelles ici.

82

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

83

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

84

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

top

85

Folco (./84) :
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.

86

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é cry

87

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

88

Pour le code en C que tu ne comprends pas: tigcc -S. wink
avatar
Mes news pour calculatrices TI: Ti-Gen
Mes projets PC pour calculatrices TI: TIGCC, CalcForge (CalcForgeLP, Emu-TIGCC)
Mes chans IRC: #tigcc et #inspired sur irc.freequest.net (UTF-8)

Liberté, Égalité, Fraternité

89

Pas con, merci, j'y pense jamais. smile

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

90

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

avatar
« Quand le dernier arbre sera abattu, la dernière rivière empoisonnée, le dernier poisson capturé, alors vous découvrirez que l'argent ne se mange pas. »