Soustraction dans les expressions régulières

1 réponse
Avatar
ejetzer
J'essaie depuis environ une fin de semaine de traduire les expressions
r=E9guli=E8res de la sp=E9cification XML du W3c (pour faire un parseur), et
j'ai rencontr=E9 un probl=E8me assez peu commun: le W3c utilise un
op=E9rateur de soustraction dans ses expressions r=E9guli=E8res. Y a-t-il u=
n
=E9quivalent avec le module d'expressions r=E9guli=E8res de Python?
Actuellement, j'utilise la notation (?!...)... pour =E9quivaloir =E0 la
soustraction, mais je ne suis pas sur que =E7a fonctionne, et je ne sais
pas comment le tester :S

1 réponse

Avatar
Mickaël Delahaye
On Oct 26, 12:01 am, ejetzer wrote:
J'essaie depuis environ une fin de semaine de traduire les expressions
régulières de la spécification XML du W3c (pour faire un parseur), et
j'ai rencontré un problème assez peu commun: le W3c utilise un
opérateur de soustraction dans ses expressions régulières. Y a-t-il un
équivalent avec le module d'expressions régulières de Python?
Actuellement, j'utilise la notation (?!...)... pour équivaloir à la
soustraction, mais je ne suis pas sur que ça fonctionne, et je ne sais
pas comment le tester :S



Bonjour,

Suite à un problème entre Google Groups et moi ;), mon message n'a pas
été retransmis ici. J'y indiquai à ejetzer que la soustraction
d'expression rationnelle entière est possible mais délicate. Par
exemple,
[abc]* - ([abc]* bc [abc]*) = (a|c|bb*a)*b*

Pour des expressions rationnelles classiques (sans lookahead et cie),
cette transformation est toujours possible, en passant par les
automates (sur lesquels l'intersection et le complément sont défini).
Pour le faire avec les mains: on peut partir de qui est vérifier sans
problème ici [ac]* et rajouté les cas particuliers bb*a au milieu et
b* à la fin.
Remarquez que certaine bibliothèque d'expression rationnelle et
lexeurs offrent la soustraction, mais pas 're'.

Sur un exemple tiré de la recommandation XML CharData:
CharData ::= [^<&]* - ([^<&]* ']]>' [^<&]*)

ejetzer indiquait utiliser l'expression rationnelle suivante
(?!([^<&]* ']]>' [^<&]*))( [^<&]*)



Si on lui donne une la totalité d'une chaîne cela marche bien, mais
pas si l'on veut vérifier le début d'une chaine
re.match(r'(?!([^<&]*]]>[^<&]*))([^<&]*)','debut ok]]>') --> None

Pour CharData, une solution (non formellement vérifiée) est: ([^<&]]|
][^<&]]|]][^<&>])*]*
Cette expresion doit vérifier le langage défini par CharData, mais sur
re.match(...,"debut ok]]>").group(0) -> "debut ok]]"

Est-ce vraiment ce qu'à besoin un parseur ? Dans une architecture
classique lexeur/parseur, je vous invite à regarder ce qu'on font les
lexeurs pour le traitement des chaînes entre "" ou les commentaires.

Cdt,
Mickaël Delahaye