Discussion :

[visiwi]

Bonjour,

J'apprends les expressions régulières depuis quelque jours et j'ai un petit soucis.

En partant de la règle syntaxique suivante, soit pour une entité C :

Code :

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

C --> com | def | (eval C+)

| signifie ou
+ siginifie au moins 1 à n

D'après moi les exemples suivant correspondent à la syntaxe :

Code :

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

1
2
3
4
com
def
(eval def)
(eval com)

Mais aussi avec une imbrication qui peut être infini, par exemple :

Code :

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

(eval com (eval com) (eval (eval def) def com))

...

Est-il possible de traduire cela en expression régulière ? Si oui coment ?
C'est bien évidement le (eval C+) qui me pose problème.

[darkxan]

Ayant pratiqué pas mal de temps les expressions régulières, je n'ai jamais vu d'expression régulière récursive. Ton problème ressemble plutôt à une grammaire de machine à états finis.

[visiwi]

Merci de ta réponse.

je n'ai jamais vu d'expression régulière récursive.

Je m'en doutais.

une grammaire de machine à états finis

Qu'est-ce donc ?

[darkxan]

Un automate fini ou machine à états finis et une donc un système composé d'un ensemble d'états et de transitions. Cela peut paraitre compliqué mais c'est assez simple. Et justement on peut s'en servir pour reconnaître des chaînes de caractères. Et il gère parfaitement la récursivité.

La grammaire, c'est un moyen de décrire les différents états et transitions de ces automates.

L'avantage de tout cela c'est qu'on peut le transcrire en programme de manière assez direct (cela dépends tout de même du type de grammaire).

Donc cela pourrait être une solution élégante à ton problème.

[visiwi]

Merci de cette définition claire. C'est en plus intéressant.

Aurait-tu un lien de page qui en parlerait de manière pédagogique. Et surtout pour un débutant, càd quelqu'un qui ignore tout des automates finis.

Parce que quand tu dit :

Cela peut paraitre compliqué mais c'est assez simple.

Ça parait effectivement compliqué

J'ai googlisé, mais bon, je ne suis tombé que sur des choses ou tu doit déjà avoir une bonne idée de la bête pour profiter de la ressource en ligne.

[Invité]

Salut visiwi,

Si tu arrives à me remotiver pour continuer cette page tu pourras avoir un cours dessus...
Sinon ce lien là . http://www-igm.univ-mlv.fr/~desar/Cours/automates/ me parait pas mal mais j'ai pas approfondi.
Lesmots clef : Théorie des langages, Automates finis, Grammaires...

A plus