Discussion :

[cladsam]

Bonjour,

j'aimerais savoir s'il existe un standard concernant les Regex ou si, le fait qu'elles soient semblables dans de nombreux langages soit plus un concours de circonstance que le fruit d'une normalisation?

Si à l'occasion quelqu'un connait des bibliothèques/programmes qui gère les regex et qui soient en open source je suis preneur.

L'idée étant d'étudier la possibilité de créer une bibliothèque d'objets prenant en charge ces fameuses regex car elles manquent cruellement dans le langage que j'utilise au quotidien (ABAP)

Merci beaucoup et désolé si ce message s'avérait être à la mauvaise place, je ne savais pas du tout ou j'aurais pu le mettre d'autre ^^

[gorgonite]

je crois que c'est un standard fondé sur la syntaxe perl (à vérifier)

perl est un très bon langage si tu veux faire beaucoup d'expressions régulières... mais après tout dépend du contexte

[Jean-Marc.Bourguet]

A propos des expressions regulieres, il y a deux choses:
- il y a la theorie des langages qui etablit que trois methodes (les expressions regulieres, les automates finis, les grammaires regulieres) decrivent exactement le meme ensemble de chaine. D'apres ce que j'ai compris -- toutes mes references la-dessus sont en anglais -- le terme francais correct est "rationnel" (au moins pour les expressions, pour les grammaires je n'en sais rien) mais pas mal de gens utilisent quand meme reguliere.
- il y a des extensions a la syntaxe des expressions rationnelles qui augmente aussi la capacite de description. Ces extensions sont presentes par exemple dans emacs, sed, egrep, perl.

Perso j'ai tendance a utiliser "expression rationnelle" quand il est important que ce soit l'ensemble detectable par les automates finis, et "expression reguliere" pour tout moyen de designer de maniere compacte un ensemble de chaine.

J'aimerais savoir s'il existe un standard concernant les Regex ou si, le fait qu'elles soient semblables dans de nombreux langages soit plus un concours de circonstance que le fruit d'une normalisation?

A ma connaissance il n'y a pas une norme (POSIX decrit au moins deux syntaxes d'expression reguliere) mais toutes les implementations se sont plus ou moins copiees.

Si à l'occasion quelqu'un connait des bibliothèques/programmes qui gère les regex et qui soient en open source je suis preneur.

pcre (compatibles avec celles de perl), Spencer regexp, boost

L'idée étant d'étudier la possibilité de créer une bibliothèque d'objets prenant en charge ces fameuses regex car elles manquent cruellement dansle langage que j'utilise au quoitidien (ABAP)

Deux grandes classes de techniques sont en presence:
- interpreter l'expression reguliere directement (par exemple avec un algo recursif)
- compiler l'expression reguliere sous une forme interpretable avec une meilleure complexite (s'il s'agit d'une expression rationnelle, un automate fini)

[Jean-Marc.Bourguet]

je crois que c'est un standard fondé sur la syntaxe perl (à vérifier)

perl 1.0 date de 1987

Il y a eu beaucoup de travail theorique sur la theorie des langages a la fin des annees 50, je suis sur que l'equivalence que j'ai donnee etait connue au debut des annees 60, mais peut-etre depuis longtemps auparavent.

perl a tire l'idee et la syntaxe des expressions regulieres d'outils comme sed, grep qui ont ete decrit au plus tard dans "Software tools" par Kernighan et Plaugher dans les annees 70 et en a etendu les capacites avec celles de langages plus ou moins specialise dans le traitement de chaines comme SNOBOL 4 (fin des annees 60 si je ne me trompe pas, mais la syntaxe n'est pas celle dont on a l'habitude). Voir aussi icon pour un descendant de ces langages.

Mais effectivement, la syntaxe des expressions regulieres de perl est devenu un standard de fait (un facteur important est l'existance de pcre qui en fourni une implementation).

[Gnux]

A propos des expressions regulieres, il y a deux choses:
- il y a la theorie des langages qui etablit que trois methodes (les expressions regulieres, les automates finis, les grammaires regulieres) decrivent exactement le meme ensemble de chaine. D'apres ce que j'ai compris -- toutes mes references la-dessus sont en anglais -- le terme francais correct est "rationnel" (au moins pour les expressions, pour les grammaires je n'en sais rien) mais pas mal de gens utilisent quand meme reguliere.

Bonjour
Quelles références? Tu as des bons bouquins à conseiller sur les automates finis et les grammaires régulières?
Je me souviens que lorsque j'avais étudié perl pour débuter en prog. Ayant bcp de littéraires dans la salle, la prof (qui était une prof de linguisitique...) avait introduit les regexps via les théories (assez anciennes en fait) de Chomsky. Que je n'ai jamais lu...(j'ai plus lu les "linguistes" anglo-saxons tels que Davidson)
Pour les regexp et la question du po j'ai pas mal potassé ce bouquin: http://linux.developpez.com/livres/#L2841772365 qui est pas mal en effet.

[Jean-Marc.Bourguet]

Bonjour
Quelles références? Tu as des bons bouquins à conseiller sur les automates finis et les grammaires régulières?

Les references que j'ai sont des references d'informaticien.

A.V. Aho, and J.D. Ullmann. The Theory of Parsing Translating and Compiling.

ou n'importe quel autre bouquin sur les compilateurs. Bien que pour l'aspect theorique celui que je cite est je crois insurpasse. Comme bouquin disponible, voir par exemple: Parsing Techniques - A Practical Guide by Dick Grune and Ceriel J.H. Jacobs qui est plus recent et plus pratique (je compte me payer la deuxieme edition quand elle sortira, ce domaine etant un de mes dadas).

Il me semble me souvenir d'un autre bouquin par Aho/Ullmann que je n'ai pas lu mais encore plus axe sur la theorie du langage et moins sur la compilation. Je suis a peu pres sur qu'il est cite dans la bibliographie de The Theory of Parsing Translating and Compiling. Si ca t'interesse, envoie moi un email, je regarderai dans ma bibliotheque.

Je me souviens que lorsque j'avais étudié perl pour débuter en prog. Ayant bcp de littéraires dans la salle, la prof (qui était une prof de linguisitique...) avait introduit les regexps via les théories (assez anciennes en fait) de Chomsky.

Chomsky est le seul linguiste dont l'informaticien moyen a entendu parle.
Tout le travail theorique la dessus etait a peu pres fini a la fin des annees 60 debut des annees 70. Apres, ce ne fut que des ameliorations aux limites sans grand impacts pratiques (sauf peut-etre en linguistique justement ou pouvoir parser rapidement des grammaires ambigues a de l'interet) meme si on peut parfois le regretter (la representation compacte de tables pour LALR(k) par exemple, ou ce qui s'est fait dans le traitement des erreurs).

[cladsam]

Merci beaucoup pour vos reponses, je crois que je vais m'évertuer à éplucher le code de pcre car ca semble plutot tres complet
Lorsque j'utilisais ces petites expressions en .NEt, j'étais loin d'imaginer qu'il se cachait autant de théorie derrière ^^

[cladsam]

Chomsky est le seul linguiste dont l'informaticien moyen a entendu parle.

faux... je suis un informaticien très moyen et j'en connais necessairement d'autres.. mais ca doit etre du au fait que ma compagne a un doctorat de linguistique ...

[cladsam]

Auriez-vous des références sur les algorithmes?
parceque ce que je trouve c'est :
- comment créer des expressions rationnelles.
- comment utiliser des bibliothèques de fonctions pour demander
machaine.matches(maregex) ?

Mais derrière cela, il y a le moteur qui va prendre la chaine plus l'expression et faire la vérification. Et c'est ce fonctionnement la que j'aimerais étudier en détail.

[Gnux]

Auriez-vous des références sur les algorithmes?
parceque ce que je trouve c'est :
- comment créer des expressions rationnelles.
- comment utiliser des bibliothèques de fonctions pour demander
machaine.matches(maregex) ?

Mais derrière cela, il y a le moteur qui va prendre la chaine plus l'expression et faire la vérification. Et c'est ce fonctionnement la que j'aimerais étudier en détail.

Tu veux donc connaitre les analyses syntaxiques et lexicales que font subir les interpréteurs aux regex ? C'est ça?

[cladsam]

Oui c'est ca car le but est d'équiper de ces fonctionnalités un langage qui en est dépourvu. Evidemment, dans ce cas la, le plus simple peut être de changer de langage mais dans mon cas, cette possibilité ne s'offre pas .

[Jedai]

Habituellement ce type de problématique s'adresse en faisant une interface à PCRE (par exemple) pour le langage concerné (il n'est pas extensible en C ton langage ?). Sinon si les mécanisme t'intéresse ça m'étonnerait que tu n'aies pas les réponses à tes questions dans les bouquins que Jean-Marc Bourguet t'a conseillé, ce sont vraiment les références. Si ce n'est pas le cas, tu devras t'orienter vers la théorie des automates déterministes (et non-déterministes) à états finis et sur la théorie des grammaires et des classes de langages reconnaissables. Tu peux également lire les implémentations actuelles, elles sont libres après tout ! (mais ne lis pas trop le code traitant des regexs en Perl, nous ne garantissons pas ta santé mentale par la suite... )

--
Jedaï

[cladsam]

Et bein le langage en question peut etre interfacé avec d'autres langages seulement dans la société ou je travaille, il n'ets pa sposisble d eprendre ce genre de décision à mon niveau.
Pour information c'est de l'ABAP, le jolie langage de programmation de SAP R/3 ... mon idée était donc de construire une collection d'objets qui premettraient d'ajouter à l'Abap les fonctionnalités des regex.
Je vais regarder du côté des ouvrages que vosu avez conseillé, je pense que déjà la , je pourrai sans problème trouver de quoi faire ^^

[Jedai]

Un site rigolo à ce sujet (les expressions régulières) : http://osteele.com/tools/reanimator/ .
(cette page est faite avec OpenLaszlo, y a-t-il des personnes ici qui connaissent un peu ?)

--
Jedaï

[cladsam]

Je ne connais ni ce site ni OpenLaszlo mais ca a l'air interessant et je vais me pencher sur ce site merci beaucoup ^^