Discussion :

[davcha]

Je suis en train d'écrire un petit programme (en fait un interprêteur) et pour ce faire, j'ai besoin de détecter facilement si un string est valide dans ce langage.

Voici le langage en question :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
X = [a-z0-9]
L = lambda X ° U
U = (U)U

Aucun problème avec X et L.

Ce n'est pas le cas de U.
(f)x avec f et x appartenant à X ne pose aucun problème.

En effet, si j'utilise cette expression régulière :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

^\s*\(\s*(?<u>.+)\s*\)(?<v>.+)\s*

alors je me retrouve avec le problème suivant :
(f)(f)x devient f)(f et x.
Et évidemment f)(f est illégal dans ce langage.

Si j'utilise cette expression régulière :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

^\s*\(\s*(?<u>.+?)\s*\)(?<v>.+)\s*

alors je me retrouve avec :
((f)f)x qui devient (f et f)x qui sont tous les deux illégaux.

Bref, existe-il un moyen efficace en utilisant une expression régulière de résoudre de problème ou bien ferais-je mieux de scanner les caractères un à un en comptant les parenthèses ouvrantes/fermantes ?

[vdumont]

Hum je suis pas sur de saisir à 100%, c'est quoi le format exact que tu veux donner à ton expression?

[zeavan]

il existe un moyen c'est sur:
pour ta solution precise je ne sais pas pas trop chercher mais regarde ici ca pourra peut etre t'aider:

http://lgmorand.developpez.com/dotnet/regex/

ou encore ce site qui comporte pas mal d'expressions ou tu pourra peut-etre trouver ton bonheur:

http://regexlib.com/Search.aspx

[davcha]

Hum je suis pas sur de saisir à 100%, c'est quoi le format exact que tu veux donner à ton expression?

En fait, mon expression doit être de la forme X, L ou U ; sachant que :

• X doit être de la forme [a-z0-9]+, donc une chaine de caractères alphanumériques en minuscule (en supprimant les espaces).
• L doit être de la forme lambda X ° U, donc le mot lambda suivi d'une expression de forme X, suivi du caractère °, suivi d'une expression de forme U.
• U doit être de la forme X, L ou (U)U, donc une expression de forme X ou L ou bien deux expressions de forme U dont la première est entre parenthèses.

En définitive, je me retrouve face à une expression régulière récursive, si tu veux.

Quelques exemples faisant partie du langage :

[*]toto87[*]lambda pouet°couic[*](toto)tati[*]((toto)tati)(pouet)couic[*]lambda f ° lambda x ° (f)x[*]lambda m ° lambda f ° lambda x ° (f)((m)f)x[*](lambda m ° lambda f ° lambda x ° (f)((m)f)x)lambda f ° lambda x ° (f)x

Quelques exemples illégaux :

[*]toto°tati[*]pouet(truc)[*](f(f)x)x[*]f)(x

Merci pour les liens, je vais regarder s'ils m'aident

[gege2061]

Bonjour,

les expressions régulières ont leurs limites et l'annalyse syntaxique en fait partie

Pourquoi tu n'utilise pas une machine à état ?

[zeavan]

+1 pour gege effectivement les etats semblent plus appropries , il y a pas mal d'example sous yacc.

[davcha]

Ouaip, je m'en suis rendu compte... Par contre....

Je vous conseille d'aller lire ceci, je vous assure que ça vaut le coût (d'autant que c'est gratuit :p).

[davcha]

J'ai résolu mon problème. Comme c'est quelque chose d'assez nouveau et tout de même très intéressant, je vous fait profiter des résultats (j'ai remplacé "\(" et "\)" par "<" et ">" pour simplifier la lecture de l'expression) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
^
(
	(?<o><)
	(
		[a-z0-9]+
		(?<c-o>>)
	)+
)+
[a-z0-9]+
(?(o)(?!))
$