cerhu > comp.* > comp.algorithmes

Aeris (31/10/2010, 21h22)
WebShaker wrote:

> Ben si tu connais une lib (ca doit sans doute exister, mais j'ai pas
> trouvé) qui me retournerai l'automate pour que je puisse l'exploiter. Je
> suis preneur.
> Parce que j'ai pas plus envie que ca de réinventer la roue ;)


[..]
Aeris (31/10/2010, 21h27)
WebShaker wrote:

> Ben si tu connais une lib (ca doit sans doute exister, mais j'ai pas
> trouvé) qui me retournerai l'automate pour que je puisse l'exploiter. Je
> suis preneur.
> Parce que j'ai pas plus envie que ca de réinventer la roue ;)


J'oubliais aussi LA référence d'implémentation des regexp: PCRE
[..]
Pascal J. Bourguignon (01/11/2010, 01h50)
Aeris <aeris> writes:

> WebShaker wrote:
> Oui, et un théorème de la théorie des langages énonce même qu'il existe
> toujours une machine d'état déterministe équivalente pour une machine d'état
> indéterministe.
> Le soucis étant de la trouver :D
> Et un autre théorème énonce que n'importe quelle regexp peut se ramener à
> une machine d'état déterministe.
> C'est là dessus que s'est basé Perl pour fonder sa librairie de regexp
> (PCRE) extrèmement efficace et rapide.


1- "extrèmement efficace et rapide" est extrèmement rapidement dit!

cl-pcre est bien plus efficace et rapide que PCRE.

[..]

2- PCRE n'implémente pas des expressions régulières donc il ne peut pas
se baser sur ce théorème mathématique.

3- n'importe quelle bibliothère d'expressions régulière (véritables) se
base sur ce théorème mathématique.
Pascal J. Bourguignon (01/11/2010, 01h54)
WebShaker <etienne> writes:

[..]
> est quand meme assez simple) et le | (qui n'est finalement guere plus
> compliqué)
> construire des automates devient vite facile.


Les machines à état sont en effet assez triviale.

Les difficultés viennent quand on veut traiter des problème complexes
demandant un grand nombre d'état.

> Il n'y a plus qu'a regarder finalement si + ? et * peuvent être
> convertis dans cette "grammaire" (je ne sais pas si c'est bien le
> terme.)


En effet. Une machine à état reconnait si un mot appartient à un
langage. On peut utiliser une grammaire pour définir ce langage.

Si la grammaire est régulière ("de type 3"), on obtient un langage
d'expressions régulières.

[..]
(Noter le tableau en bas de page.)
Pascal J. Bourguignon (01/11/2010, 01h56)
WebShaker <etienne> writes:

> Le 31/10/2010 19:04, Aeris a écrit :
> Oui c'est exactement ça que je veux obtenir au final.
> Toute mon idée était de trouver le moyen le plus "simple" (entre
> syntaxe et code à réaliser) pour arriver à ce résultat.
> Ben si tu connais une lib (ca doit sans doute exister, mais j'ai pas
> trouvé) qui me retournerai l'automate pour que je puisse
> l'exploiter. Je suis preneur.


Lex, Bison.

> Parce que j'ai pas plus envie que ca de réinventer la roue ;)


C'est pourtant le mieux pour comprendre...
Pascal J. Bourguignon (01/11/2010, 02h08)
Aeris <aeris> writes:

> WebShaker wrote:
> Sauf que les regexp sont bien équivalentes à des arbres, comme toutes les
> grammaires générées par les machines à états finis déterministes si je ne
> fais pas d'erreur.
> Cf les AST (abstract syntax tree) pour l'analyse d'un langage de
> programmation


Il ne faut pas confondre le graphe de la machine à état avec _un_ arbre
syntaxique correspondant à la représentation de cette machine à état
comme expression régulière.

On peut avoir des machines à état dont les graphes sont des arbres.
Mais ça n'a rien à voir.

Par exemple, l'expression régulière :

a(b|c|(de))

a pour arbre syntaxique:

a b c d e
| | | \ /
| | \ s
| \ \ /
| \ \ /
\ \ o
\ \ /
\ o
\ /
s

s étant la séquence, et o l'alternative.

Mais le graphe de la machine à état correspondant va être:

+------[c]------> (final=ac)
|
|
(init) -----[a]-----> (a) -----[b]-----> (final=ab)
|
|
+--[d]---> (ad) ---[e]----> (final=ade)

C'est aussi un arbre, mais ce n'est pas dans la même catégorie que
l'arbre syntaxique, puisque c'est un graphe de machine à état.
Aeris (01/11/2010, 02h21)
Pascal J. Bourguignon wrote:

> 1- "extrèmement efficace et rapide" est extrèmement rapidement dit!
> cl-pcre est bien plus efficace et rapide que PCRE.
> [..]


Sauf que ppcre est uniquement une lib common lisp, et non une lib système
C/C++/le reste

> 2- PCRE n'implémente pas des expressions régulières donc il ne peut pas
> se baser sur ce théorème mathématique.


PCRE = "Perl-Compatible Regular Expressions"
J'ai raté un épisode dans "regular expression"?

> 3- n'importe quelle bibliothère d'expressions régulière (véritables) se
> base sur ce théorème mathématique.


Euh, j'ai vu des librairies de regexp faites "à la main", en particulier
pour faire de l'embarqué (très faible empreinte mémoire obligatoire et
absence de MMU) et qui n'utilise pas du tout ces notions mathématiques mais
des méthodes plus ad-hoc.
D'ailleurs souvent ce n'est bien souvent qu'un sous-ensemble des regexp PCRE
qui est implémenté (pas de backtracking, pas de référence, consommation lazy
uniquement, etc...).
Pascal J. Bourguignon (01/11/2010, 02h33)
Aeris <aeris> writes:

> Pascal J. Bourguignon wrote:
>> 1- "extrèmement efficace et rapide" est extrèmement rapidement dit!
>> cl-pcre est bien plus efficace et rapide que PCRE.
>> [..]

> Sauf que ppcre est uniquement une lib common lisp, et non une lib système
> C/C++/le reste


Ah, tu veux dire que les implémentations des autres langages ne sont pas
capables d'utiliser une bibliothèques Common Lisp (alors que les
implémentations de Common Lisp sont tout à fait capable elles d'utiliser
des bibliothèques écrites en C...).

C'est largement vrai. Cependant, on pourrait s'abaisser à compiler
cl-pcre avec ECL afin de fournir une bibliothèque utilisable par les
implémentations rudimentaire qu'ont les langages comme C, C++ ou le
reste.

>> 2- PCRE n'implémente pas des expressions régulières donc il ne peut pas
>> se baser sur ce théorème mathématique.

> PCRE = "Perl-Compatible Regular Expressions"
> J'ai raté un épisode dans "regular expression"?


Oui. /\(.*\):\1/ n'est pas une expression régulière, mais PCRE est
capable de la traiter. Pour celà, il ne peut pas utiliser une machine à
état (ni même un automate à pile), mais doit utiliser une machine de
Turing, c'est à dire, un ordinateur complet.

>> 3- n'importe quelle bibliothère d'expressions régulière (véritables) se
>> base sur ce théorème mathématique.

> Euh, j'ai vu des librairies de regexp faites "à la main", en particulier
> pour faire de l'embarqué (très faible empreinte mémoire obligatoire et
> absence de MMU) et qui n'utilise pas du tout ces notions mathématiques mais
> des méthodes plus ad-hoc.


En effet, on peut implémenter une machine à état simplement avec des
goto.

> D'ailleurs souvent ce n'est bien souvent qu'un sous-ensemble des regexp PCRE
> qui est implémenté (pas de backtracking, pas de référence, consommation lazy
> uniquement, etc...).


Forcément, car ces fonctionalités ne peuvent pas être implémentées sur
une machine à état! On tourne un peu en rond, n'as tu pas l'impression?
Paul Gaborit (02/11/2010, 11h12)
À (at) Mon, 01 Nov 2010 00:50:11 +0100,
pjb (Pascal J. Bourguignon) écrivait (wrote):

> Aeris <aeris> writes:
>> C'est là dessus que s'est basé Perl pour fonder sa librairie de regexp
>> (PCRE) extrèmement efficace et rapide.


Heu... PCRE n'est pas la bibliothèque d'expressions regulières de
Perl. C'est une bibliothèque autonome qui utilise la même syntaxe.

> 1- "extrèmement efficace et rapide" est extrèmement rapidement dit!
> cl-pcre est bien plus efficace et rapide que PCRE.
> [..]


Je n'ai pas vu de tests de comparaison de performance...

> 2- PCRE n'implémente pas des expressions régulières donc il ne peut pas
> se baser sur ce théorème mathématique.


Pour PCRE, je ne sais pas (mais je me doute...). Pour Perl, il est vrai
que ce sont des "expressions régulières étendues". Il y a donc des
éléments de syntaxe qui sortent des expressions régulières. Mais le
sous-ensemble qui couvre les expressions régulières utilise dans la
plupart des cas toute la puissance d'optimisation permise.

Il faut aussi savoir que pendant longtemps le moteur utilisé par Perl
est resté en l'état car plus personne ne voulait vraiment s'y
pencher... Mais depuis quelques mois (un an ou deux tou au plus), un
développeur (son nom m'échappe) a repris le flambeau et le moteur évolue
à nouveau (dans le bon sens ;-)).

> 3- n'importe quelle bibliothère d'expressions régulière (véritables) se
> base sur ce théorème mathématique.


Si c'était vrai... ;-)
WebShaker (04/11/2010, 23h03)
Le 01/11/2010 01:08, Pascal J. Bourguignon a écrit :
> Mais le graphe de la machine à état correspondant va être:
> +------[c]------> (final=ac)
> |
> |
> (init) -----[a]-----> (a) -----[b]-----> (final=ab)
> |
> |
> +--[d]---> (ad) ---[e]----> (final=ade)
> C'est aussi un arbre, mais ce n'est pas dans la même catégorie que
> l'arbre syntaxique, puisque c'est un graphe de machine à état.


Enfin ca ressemble a un arbre parce que l'expression recherchée s'y prête.

a(b|c)*d

ne peut pas être représentée par un arbre me semble t-il.

Etienne
Pascal J. Bourguignon (05/11/2010, 02h10)
WebShaker <etienne> writes:

> Le 01/11/2010 01:08, Pascal J. Bourguignon a écrit :
> Enfin ca ressemble a un arbre parce que l'expression recherchée s'y prête.
> a(b|c)*d
> ne peut pas être représentée par un arbre me semble t-il.


En fait, j'ai un peu triché. :-)

Un DFA pur n'a qu'un seul état final.

Mais dans ses applications, on augmente souvent le DFA avec une mémoire de ce
qui a été analysé, afin de pouvoir indiquer, comme je l'ai fait, quel
mot a été reçu. L'alternative serait d'appliquer des DFA séparés (en
parallèle ou l'un après l'autre), ce qui serait plus coûteux en
resources.
Paul Gaborit (05/11/2010, 09h07)
À (at) Fri, 05 Nov 2010 01:10:26 +0100,
pjb (Pascal J. Bourguignon) écrivait (wrote):

> WebShaker <etienne> writes:
> En fait, j'ai un peu triché. :-)
> Un DFA pur n'a qu'un seul état final.


Heu... Même en acceptant d'avoir plusieurs états finaux, l'usage des
quantificateurs (* ou +) ne donne plus un arbre. En fait, on pourrait
appeler cela un arbre semi-infini (un arbre infini équivalent à un
graphe fini).

> Mais dans ses applications, on augmente souvent le DFA avec une
> mémoire de ce qui a été analysé, afin de pouvoir indiquer, comme je
> l'ai fait, quel mot a été reçu. L'alternative serait d'appliquer des
> DFA séparés (en parallèle ou l'un après l'autre), ce qui serait plus
> coûteux en resources.


Le meilleur moyen de mémoriser l'ensemble du mot reconnu consiste tout
simplement à mémoriser le point de départ et le point d'arrivée dans le
flux sur lequel on applique l'expression. Ça ne change pas le graphe de
reconnaissance.
Pascal J. Bourguignon (05/11/2010, 14h08)
Paul Gaborit <Paul.Gaborit> writes:

> À (at) Fri, 05 Nov 2010 01:10:26 +0100,
> pjb (Pascal J. Bourguignon) écrivait (wrote):
> Heu... Même en acceptant d'avoir plusieurs états finaux, l'usage des
> quantificateurs (* ou +) ne donne plus un arbre. En fait, on pourrait
> appeler cela un arbre semi-infini (un arbre infini équivalent à un
> graphe fini).
> Le meilleur moyen de mémoriser l'ensemble du mot reconnu consiste tout
> simplement à mémoriser le point de départ et le point d'arrivée dans le
> flux sur lequel on applique l'expression. Ça ne change pas le graphe de
> reconnaissance.


Ça ne suffit pas. Il est trivial d'avoir la liste des caractères
reconnus. Ce que l'on veut savoir, c'est bien dans quel état "final" on
se trouve quand il a été reconnu, car c'est celà qui détermine le type
de mot, pour un parseur.

Supposons que l'on veuille scanner deux tokens:

<identificateur> = [A-Za-z0-9][A-Za-z0-9]*,
<entier> = [0-9][0-9]*,

On a là deux expressions régulières, correspondant à deux DFA (N en
général).

Afin d'éviter d'avoir à passer le flux d'entrée par N DFA, on fussionne
ces DFA. On obtient alors un DFA correspondant à l'expression
régulière suivante:

([A-Za-z0-9][A-Za-z0-9]*,^1|[0-9][0-9]*,^2)

avec deux états finaux, marqués ^1 et ^2.

[0-9]* ------(,)-------> ^2
|
v
([A-Za-z])
|
v
[A-Za-z0-9]* -----(,)-------> ^1

Il ne servirait à rien de savoir que l'on a reconnu "32BIT," ou
"32817,". Ce que l'on veut savoir, c'est si on a reconnu un
<identificateur> ou un <entier>, c'est à dire si on est dans l'état
final ^1 ou ^2.
Paul Gaborit (05/11/2010, 14h36)
À (at) Fri, 05 Nov 2010 13:08:08 +0100,
pjb (Pascal J. Bourguignon) écrivait (wrote):

> Ça ne suffit pas. Il est trivial d'avoir la liste des caractères
> reconnus.


Oui. C'est ce que je disais...

> Ce que l'on veut savoir, c'est bien dans quel état "final" on se
> trouve quand il a été reconnu, car c'est celà qui détermine le type de
> mot, pour un parseur.


[... les détails ...]

> Il ne servirait à rien de savoir que l'on a reconnu "32BIT," ou
> "32817,". Ce que l'on veut savoir, c'est si on a reconnu un
> <identificateur> ou un <entier>, c'est à dire si on est dans l'état
> final ^1 ou ^2.


Et ce que vous expliquez n'a plus rien à voir avec les expressions
régulières. C'est évidemment faisable avec certains moteurs mais qui
traitents en fait des expressions régulières /étendues/.

Discussions similaires
Algorithme de recherche

Recherche de motif?

remplacer une partie du motif recherche

algorithme de recherche de solution...


Fuseau horaire GMT +2. Il est actuellement 06h28. | Privacy Policy