De sorte à me faciliter l'écriture de petits programmes identifiant
l'éventuelle validité de certaines données par rapport aux
spécifications proposées par les RFCs, je cherche un moyen simple et sûr
de convertir une description faite en notation ABNF en une expression
régulière.
Google signale l'existence d'un produit écrit en Ruby, dont l'usage
serait prohibitif pour tout autre langage de script supportant déjà les
expressions régulières.
Existe-t-il un jeu de règles de substitutions à base d'expressions
régulières permettant d'associer à une notation ABNF arbitraire
l'expression régulière équivalente ? ou existe-t-il une raison que je ne
comprends pas pour laquelle cela serait impossible ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Alain Ketterlin
Antoine Bellot writes:
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression des grammaires ABNF est superieure a celle des expressions regulieres. (Exemple : n'importe quel langage contenant des parentheses equilibrees.)
Par contre, il est possible (en theorie) de passer d'une ABNF a (par exemple) un fichier yacc/bison. En pratique cela peut etre plus complique.
-- Alain.
Antoine Bellot <Antoine.Bellot@eat-it.ath.cx> writes:
Existe-t-il un jeu de règles de substitutions à base d'expressions
régulières permettant d'associer à une notation ABNF arbitraire
l'expression régulière équivalente ? ou existe-t-il une raison que je ne
comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression
des grammaires ABNF est superieure a celle des expressions regulieres.
(Exemple : n'importe quel langage contenant des parentheses
equilibrees.)
Par contre, il est possible (en theorie) de passer d'une ABNF a (par
exemple) un fichier yacc/bison. En pratique cela peut etre plus
complique.
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression des grammaires ABNF est superieure a celle des expressions regulieres. (Exemple : n'importe quel langage contenant des parentheses equilibrees.)
Par contre, il est possible (en theorie) de passer d'une ABNF a (par exemple) un fichier yacc/bison. En pratique cela peut etre plus complique.
-- Alain.
Pascal Bourguignon
Antoine Bellot writes:
Bonjour à tous,
De sorte à me faciliter l'écriture de petits programmes identifiant l'éventuelle validité de certaines données par rapport aux spécifications proposées par les RFCs, je cherche un moyen simple et sûr de convertir une description faite en notation ABNF en une expression régulière.
Google signale l'existence d'un produit écrit en Ruby, dont l'usage serait prohibitif pour tout autre langage de script supportant déjà les expressions régulières.
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ça dépend de la grammaire écrite en ABNF. En toute généralité, c'est impossible: il y a des languages analysés par une grammaire context-free qui ne peuvent pas être analysés par des expressions régulières. Par exemple, quand il y a des règles récusives. Essaye d'écrire une regexp qui accepte et qui refuse les mêmes mots que:
( ( 'a' 'b' 'c' '(' ')' '+' '-' '*' '/' ) ( E F T I ) E ( E --> F + F | F - F . F --> T * T | T / T . T --> ( E ) | I . I --> a | b | c . ))
Antoine Bellot <Antoine.Bellot@eat-it.ath.cx> writes:
Bonjour à tous,
De sorte à me faciliter l'écriture de petits programmes identifiant
l'éventuelle validité de certaines données par rapport aux
spécifications proposées par les RFCs, je cherche un moyen simple et
sûr de convertir une description faite en notation ABNF en une
expression régulière.
Google signale l'existence d'un produit écrit en Ruby, dont l'usage
serait prohibitif pour tout autre langage de script supportant déjà
les expressions régulières.
Existe-t-il un jeu de règles de substitutions à base d'expressions
régulières permettant d'associer à une notation ABNF arbitraire
l'expression régulière équivalente ? ou existe-t-il une raison que je
ne comprends pas pour laquelle cela serait impossible ?
Ça dépend de la grammaire écrite en ABNF. En toute généralité, c'est
impossible: il y a des languages analysés par une grammaire
context-free qui ne peuvent pas être analysés par des expressions
régulières. Par exemple, quand il y a des règles récusives. Essaye
d'écrire une regexp qui accepte et qui refuse les mêmes mots que:
( ( 'a' 'b' 'c' '(' ')' '+' '-' '*' '/' )
( E F T I )
E
(
E --> F + F | F - F .
F --> T * T | T / T .
T --> ( E ) | I .
I --> a | b | c .
))
De sorte à me faciliter l'écriture de petits programmes identifiant l'éventuelle validité de certaines données par rapport aux spécifications proposées par les RFCs, je cherche un moyen simple et sûr de convertir une description faite en notation ABNF en une expression régulière.
Google signale l'existence d'un produit écrit en Ruby, dont l'usage serait prohibitif pour tout autre langage de script supportant déjà les expressions régulières.
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ça dépend de la grammaire écrite en ABNF. En toute généralité, c'est impossible: il y a des languages analysés par une grammaire context-free qui ne peuvent pas être analysés par des expressions régulières. Par exemple, quand il y a des règles récusives. Essaye d'écrire une regexp qui accepte et qui refuse les mêmes mots que:
( ( 'a' 'b' 'c' '(' ')' '+' '-' '*' '/' ) ( E F T I ) E ( E --> F + F | F - F . F --> T * T | T / T . T --> ( E ) | I . I --> a | b | c . ))
À (at) 06 Nov 2003 07:26:10 +0100, Alain Ketterlin écrivait (wrote):
Antoine Bellot writes:
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression des grammaires ABNF est superieure a celle des expressions regulieres. (Exemple : n'importe quel langage contenant des parentheses equilibrees.)
Mais certains langages de scripts (au moins Ruby et Perl) ont des moteurs de regexp étendues qui permettent (tout du moins en théorie) de le faire.
Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
Pour Perl, j'ai cherché mais je n'ai pas trouvé. Il faut dire que toutes les extensions du moteur de regexp ne sont pas encore officiellement stabilisées (que ce soit sur leur syntaxe ou sur leur sémantique exacte)
Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python) me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en théorie ;-) automatisable.
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
À (at) 06 Nov 2003 07:26:10 +0100,
Alain Ketterlin <alain@dpt-info.u-strasbg.fr> écrivait (wrote):
Antoine Bellot <Antoine.Bellot@eat-it.ath.cx> writes:
Existe-t-il un jeu de règles de substitutions à base d'expressions
régulières permettant d'associer à une notation ABNF arbitraire
l'expression régulière équivalente ? ou existe-t-il une raison que je ne
comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression
des grammaires ABNF est superieure a celle des expressions regulieres.
(Exemple : n'importe quel langage contenant des parentheses
equilibrees.)
Mais certains langages de scripts (au moins Ruby et Perl) ont des moteurs de
regexp étendues qui permettent (tout du moins en théorie) de le faire.
Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
Pour Perl, j'ai cherché mais je n'ai pas trouvé. Il faut dire que toutes les
extensions du moteur de regexp ne sont pas encore officiellement stabilisées
(que ce soit sur leur syntaxe ou sur leur sémantique exacte)
Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le
résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille
grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python)
me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en
théorie ;-) automatisable.
--
Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
À (at) 06 Nov 2003 07:26:10 +0100, Alain Ketterlin écrivait (wrote):
Antoine Bellot writes:
Existe-t-il un jeu de règles de substitutions à base d'expressions régulières permettant d'associer à une notation ABNF arbitraire l'expression régulière équivalente ? ou existe-t-il une raison que je ne comprends pas pour laquelle cela serait impossible ?
Ca n'existe pas parce que c'est impossible. La puissance d'expression des grammaires ABNF est superieure a celle des expressions regulieres. (Exemple : n'importe quel langage contenant des parentheses equilibrees.)
Mais certains langages de scripts (au moins Ruby et Perl) ont des moteurs de regexp étendues qui permettent (tout du moins en théorie) de le faire.
Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
Pour Perl, j'ai cherché mais je n'ai pas trouvé. Il faut dire que toutes les extensions du moteur de regexp ne sont pas encore officiellement stabilisées (que ce soit sur leur syntaxe ou sur leur sémantique exacte)
Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python) me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en théorie ;-) automatisable.
-- Paul Gaborit - <http://www.enstimac.fr/~gaborit/>
Pascal Bourguignon
Paul GABORIT writes:
[...] Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
[...] Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python) me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en théorie ;-) automatisable.
Oui! Yaqu'à voir le résultat dans l'URL indiqué!
Et surtout, hormis les cas les plus simples, s'il y a une grammaire, c'est qu'il y a des éléments à identifier et à traiter indépendament des autres. Un regexp, ça dit seulement si ça passe ou si ça casse (avec seulement une maigre possibilité de retour de quelques sous-expressions, mais sans savoir vraiment où les rattacher dans l'arbre syntaxique...).
Paul GABORIT <Paul.Gaborit@invalid.invalid> writes:
[...]
Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
[...]
Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le
résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille
grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python)
me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en
théorie ;-) automatisable.
Oui! Yaqu'à voir le résultat dans l'URL indiqué!
Et surtout, hormis les cas les plus simples, s'il y a une grammaire,
c'est qu'il y a des éléments à identifier et à traiter indépendament
des autres. Un regexp, ça dit seulement si ça passe ou si ça casse
(avec seulement une maigre possibilité de retour de quelques
sous-expressions, mais sans savoir vraiment où les rattacher dans
l'arbre syntaxique...).
[...] Pour Ruby, on trouve effectivement <http://cvs.m17n.org/~akr/abnf/>.
[...] Et puis, il ne suffit pas de convertir automatiquement. Encore faut-il que le résultat soit efficace. Et là, j'ai quand même un doute. Une bonne vieille grammaire passée par yacc ou bison (ou leur équivalent Perl, Ruby ou Python) me semble quand même plus optimisée. Et ça, c'est sûrement (encore une fois en théorie ;-) automatisable.
Oui! Yaqu'à voir le résultat dans l'URL indiqué!
Et surtout, hormis les cas les plus simples, s'il y a une grammaire, c'est qu'il y a des éléments à identifier et à traiter indépendament des autres. Un regexp, ça dit seulement si ça passe ou si ça casse (avec seulement une maigre possibilité de retour de quelques sous-expressions, mais sans savoir vraiment où les rattacher dans l'arbre syntaxique...).
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas applicables à mon cas, puisque je cherchais surtout à intégrer les RFCs elles-mêmes dans un lot de fichiers sources pour générer à la vérification des dépendances des expressions régulières qu'utiliseraient directement des sources C pour "inspirer confiance" en employant une méthode simple et robuste (et sans pour autant créer de dépendance externe à un énième interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF (que je souhaitais éviter de devoir connaître), il sera certainement possible de faire quelque chose de moins élégant dans ce cas particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
-- Antoine Bellot Extensibility : the inability to get it right up front.
<snip d'excellentes contributions>
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver
seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas applicables
à mon cas, puisque je cherchais surtout à intégrer les RFCs elles-mêmes
dans un lot de fichiers sources pour générer à la vérification des
dépendances des expressions régulières qu'utiliseraient directement des
sources C pour "inspirer confiance" en employant une méthode simple et
robuste (et sans pour autant créer de dépendance externe à un énième
interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF
(que je souhaitais éviter de devoir connaître), il sera certainement
possible de faire quelque chose de moins élégant dans ce cas
particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
--
Antoine Bellot
Extensibility : the inability to get it right up front.
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas applicables à mon cas, puisque je cherchais surtout à intégrer les RFCs elles-mêmes dans un lot de fichiers sources pour générer à la vérification des dépendances des expressions régulières qu'utiliseraient directement des sources C pour "inspirer confiance" en employant une méthode simple et robuste (et sans pour autant créer de dépendance externe à un énième interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF (que je souhaitais éviter de devoir connaître), il sera certainement possible de faire quelque chose de moins élégant dans ce cas particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
-- Antoine Bellot Extensibility : the inability to get it right up front.
Pascal Bourguignon
Antoine Bellot writes:
<snip d'excellentes contributions>
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas applicables à mon cas, puisque je cherchais surtout à intégrer les RFCs elles-mêmes dans un lot de fichiers sources pour générer à la vérification des dépendances des expressions régulières qu'utiliseraient directement des sources C pour "inspirer confiance" en employant une méthode simple et robuste (et sans pour autant créer de dépendance externe à un énième interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF (que je souhaitais éviter de devoir connaître), il sera certainement possible de faire quelque chose de moins élégant dans ce cas particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
Un minimum de théorie des grammaires formelles est indispensable pour faire un bon informaticien. Est ce que tu veux rester un "utilisateur" toute ta vie?
Antoine Bellot <Antoine.Bellot@eat-it.ath.cx> writes:
<snip d'excellentes contributions>
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver
seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas
applicables à mon cas, puisque je cherchais surtout à intégrer les
RFCs elles-mêmes dans un lot de fichiers sources pour générer à la
vérification des dépendances des expressions régulières
qu'utiliseraient directement des sources C pour "inspirer confiance"
en employant une méthode simple et robuste (et sans pour autant créer
de dépendance externe à un énième interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF
(que je souhaitais éviter de devoir connaître), il sera certainement
possible de faire quelque chose de moins élégant dans ce cas
particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
Un minimum de théorie des grammaires formelles est indispensable pour
faire un bon informaticien. Est ce que tu veux rester un
"utilisateur" toute ta vie?
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
En pratique, la plupart des solutions proposées ne sont pas applicables à mon cas, puisque je cherchais surtout à intégrer les RFCs elles-mêmes dans un lot de fichiers sources pour générer à la vérification des dépendances des expressions régulières qu'utiliseraient directement des sources C pour "inspirer confiance" en employant une méthode simple et robuste (et sans pour autant créer de dépendance externe à un énième interprète).
En pratique, vu l'usage souvent très limité que font les RFCs d'ABNF (que je souhaitais éviter de devoir connaître), il sera certainement possible de faire quelque chose de moins élégant dans ce cas particulier, mais j'espérais bien ne pas avoir à le faire moi-même :-)
Un minimum de théorie des grammaires formelles est indispensable pour faire un bon informaticien. Est ce que tu veux rester un "utilisateur" toute ta vie?
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
Bah, si tu essayes simplement de vérifier que tu as autant de parenthèses fermantes que de parenthèses ouvrantes, tu vois que tu ne peux pas le faire avec une expression rationelle :
A -> ( A ) | null
Antoine Bellot <Antoine.Bellot@eat-it.ath.cx> écrit:
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver
seul du fait de mes lacunes académiques.
Bah, si tu essayes simplement de vérifier que tu as autant de
parenthèses fermantes que de parenthèses ouvrantes, tu vois que tu ne
peux pas le faire avec une expression rationelle :
Merci pour l'ensemble des précisions que je n'aurais jamais pu trouver seul du fait de mes lacunes académiques.
Bah, si tu essayes simplement de vérifier que tu as autant de parenthèses fermantes que de parenthèses ouvrantes, tu vois que tu ne peux pas le faire avec une expression rationelle :
A -> ( A ) | null
Antoine Bellot
Pascal Bourguignon a écrit:
Un minimum de théorie des grammaires formelles est indispensable pour faire un bon informaticien.
Trop tard pour devenir bon hélas : je suis déjà professionnel.
-- Antoine Bellot
Pascal Bourguignon a écrit:
Un minimum de théorie des grammaires formelles est indispensable pour
faire un bon informaticien.
Trop tard pour devenir bon hélas : je suis déjà professionnel.
