[Regex] reconnaitre une chaîne non complète

Version imprimable

08/07/2004, 17h22
EdoBvD

[Regex] reconnaitre une chaîne non complète

Bonjour !

comment puis je faire pour reconnaître une chaine incomplète avec une expression régulière en java ?

par chaine incomplète, j'entend par exemple :

str = "aaa"
regex = "a*b"

j'aimerai un genre de str.prefixmatches(regex) qui renverai vrai - la chaine correspond bien au début de la regex. (pour cet exemple, str.matches(regex) renvoie faux )
En fait, il me faut savoir si une chaine en cours de construction respecte une expression régulière ou pas.

merci bcp !
08/07/2004, 18h16
bulbo

Une expression reguliere ne pouvant etre decoupe facilement en expression regulieres plus petites, ca va pas etre faisable simplement.

Une chose faisable c'est de ne pas specifier une unique expression reguliere mais un tableau pour chaque expression.
Chaque nouvel element du tableau etant une version plus complete de l'expression reguliere.

par exemple a*b donnera:
a, a*, a*b

Si la chaine ne respecte pas la premiere regex on passe a la suivante dans le tableau. Si aucune ne matche cela veut dire que cette regexp n'est pas valide pour la chaine en cours.

L'inconvenient dans cet algo c'est que tu dois decomposer a la main tes regexp et que la presence d'une etoile dans la regexp arrete la validation a ce point.
Si le debut est juste, la phrase ne sera vraiment validee que lorsque complete.

Un editeur comme eclipse par exemple a choisi une autre strategie, la phrase est testee avec la regexp complete, et jusqu'a ce que la phrase soit termine, une erreur est indiquee.

Voila mes idees en vrac.

Bulbo :wink:
09/07/2004, 12h01
EdoBvD

po bête

pas mal ton idée de découper puis mettre dans un tableau des expressions de plus en plus longues, j'n'y avais pas penser :D
mais j'ai l'impression que ton exemple a un couix :

a*b se décomposerai plutot en : a|b, a*b

il faudrait effectivement faire du découpage à la main - çà par contre j'l'ai déjà envisagé mais çà ne me plait pas bcp de réinventer l'expression régulière...

en fait ma question pourrait se formuler d'une manière un peu différente :

est ce qu'il y a moyen de savoir jusqu'où est allé la méthode String.matches() avant de renvoyer une erreur ?

merci :ave:
09/07/2004, 12h05
narmataru

Il suffit d'utiliser le caractère '?' qui implite qu'un pattern intervient 0 ou 1 fois.
Dans ton exemple se serait : "a+(b+)?"
qui devrait marché pour :

a
aaaaaaaaaaa
ab
aaaaaaaaaab
aaaaaaabbbbbbbb

et voilà :)
09/07/2004, 12h09
bulbo

Non il n'y a pas moyen de savoir, ca match ou pas, c'est tout malheureusement...

Effectivement mon exemple etait bancal, mais c'etait pour l'idee, et apparemment tu l'as bien comprise :P

Pour l'instant j'ai pas mieux a te proposer :(

Bulbo :wink:
09/07/2004, 12h11
EdoBvD

euh, pour moi çà ne fonctionne pas comme idée

exemple :

regex = ":\\w+:"
regex_modifiée = ":(\\w+)?:?"

du coup, la regex_modifiée accepte str="::" ce qui n'est pas correct par rapport à la regex d'origine

[edit]oki, merci bulbo[/edit]
09/07/2004, 12h24
narmataru

C'est normal tu fais w+ qui dit qu'il te faut au moins une lettre (+ = {1..n}) or tu l'entour d'une règle qui te dis que tu peux ne pas l'avoir ? = {0..1}

Montre nous des exemple de ce qui est valide et de ce qui ne l'est pas. Je suis certain que ? peut résoudre ton problème. Il faut que tu décompose ta regexp en deux partie: la partie obligatoire et la partie optionnelle (avec ?).

Dns ton cas réel, à quoi correspond le a* et le b de ton exemple ?
09/07/2004, 12h42
EdoBvD

ex - amplifiés

merci de te plonger dans les méandres de mes turpitudes narmataru :D

emphét', je suis en train de faire un parser RST (en javanais) : ReStructuredText :: http://docutils.sf.net
et il faudrait que j'identifie les blocs par rapport à leur 'entete'

aller hop, c'est parti pour plein d'exemples :

bullet list :"[-+*] "
directive : "\\.\\. \\w+::"
enumerated list : "([0-9]+|[a-z]+|[A-Z]+|[ivxdcm]+|[IVXDCM]+)\\. "
fieldlist : ":\\w+: "
hyperlink : "\\.\\. [\\w _]*: "

donc tu m'conseilles de faire :
bulletlist : "[-+*] ?"
directive : "\\.(\\.( (\\w+(::?)?)?)?)"
fieldlist : ":(\\w+:?)?"

le truc c'est que c'est un peu dommage de modifier ces expressions régulières, car çà ne va pas simplifier la compréhension du code si je rajoute des '?' partout, mais çà me parait faisable oui

[edit]
et en plus par la suite, je n'aurais pas moyen de savoir si le matches a accepter une chaine complete ou une chaine incomplete
[/edit]
09/07/2004, 14h41
narmataru
essaye de ne pas donner directement les expressions régulière mais ce que tu cherche à trouver.

Héhé sisi tu pourras savoir si ton expression est entière ou partielle grace au parenthèse :) Il te suffit de coompter le nombre de bloque (....) trouvé.

si tu fait un truc du genre :
Code:

1 2 ^(w+)(:)?$
et que ça te renvoie 1 c'est forcément qu'il n'y a que (w+) qui a été trouvé :) si c'est 2 l'expression est complète.

tousse le xocolat

exemple de texte à parser :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
- Five types of lists:
 
  1. `Bullet lists`_::
 
         - This is a bullet list.
 
         - Bullets can be "-", "*", or "+".
 
  2. `Enumerated lists`_::
 
         1. This is an enumerated list.
 
         2. Enumerators may be arabic numbers, letters, or roman
            numerals.
 
  3. `Definition lists`_::
 
         what
             Definition lists associate a term with a definition.
 
         how
             The term is a one-line phrase, and the definition is one
             or more paragraphs or body elements, indented relative to
             the term.
 
  4. `Field lists`_::
 
         :what: Field lists map field names to field bodies, like
                database records.  They are often part of an extension
                syntax.
 
         :how: The field marker is a colon, the field name, and a
               colon.
 
               The field body may contain one or more body elements,
               indented relative to the field marker.
 
  5. `Option lists`_, for listing command-line options::
 
         -a            command-line option "a"
         -b file       options can have arguments
                       and long descriptions
         --long        options can be long also
         --input=file  long options can also have
                       arguments
         /V            DOS/VMS-style options too

oki, donc j'ai un moyen de savoir si toute l'expression est trouvée, une épine de moins qui donne une nouvelle épine un peu moins grosse, car je ne sais pas comment connaitre le nombre de capturing group trouvés.
Et malheureusement cette solution va compliquer les pauvres expressions régulières qui n'y sont pour rien elles... :zoubi:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Bullet list : [-*+]
 
Enumeated List : ([0-9]|([IVXLC]+)|[a-z])\.
 
Definition list : ([\w ]+)(\n\t[\w \.,?!éèàêï])+
            ex : 
toto titi
<TAB>Termes qui ne veulent
<TAB>rien dire du tout
 
Field List : 	: :([\w ])+:(\n\t[\w \.,?!éèàêï]+)+
		ex :
:toto titi:
<TAB>Termes qui ne veulent
<TAB>rien dire du tout
 
option list :	(((((-[a-zA-Z] )|(--[a-zA-z]+=))([A-Za-z:/."'`]))|\\[A-Z])

Je n'ai pas testé mais ça devrait ce rapprocher de ce que tu cherche...enfin j'espère ;)

09/07/2004, 16h36
EdoBvD

vexé je suis, master

[héhé, toi au moins tu ne fais pas les choses à moitié :D --X-- merci narmataru]

en fait ce qui est au dessus n'est pas tout à fait ce que je cherche. En effet, le but du jeu est de parser, c'est à dire de charger un fichier RST dans un modèle mémoire. Or comme tu peux l'observer dans l'exemple de code RST, il se peut qu'une liste contienne d'autres listes qui condiendront des éléments comme des paragraphes par exemple..

Ceci pour dire que seul l'entête de chaque type de liste m'intéresse (tu le montre sur la 'bullet list', mais pas sur la 'definition list'). Il faut que j'arrive à identifier cet entete parmis la liste de ceux qui sont disponibles, Il faut donc que j'élimine au fur et à mesure les possibilités d'entête qui sont identifiables sous forme de Regex jusqu'à tomber sur le bon.

Question : Comment je peux faire pour savoir le nombre de capturing groups ( les expressions entre parenthèses ) qui ont été trouvées ?

Là où je suis un peu vexé/déçu, c'est dans l'API java qui ne permet pas de savoir si une chaine est le préfixe d'une chaine reconnue par une regex :( . En programmant, j'étais vraiment convaincu que j'allais trouver cette méthode... éh non :-(
09/07/2004, 16h40
bulbo

Ce que je ne comprends pas c'est pourquoi tu veux parser des lignes incompletes alors que tu veux parser un fichier.
Si tout est dans un fichier alors ta ligne est complete pourquoi te pourrir la vie ??

De plus il serait peut-etre plus rapide et plus sur d'ecrire un vrai parser (il y a des outils comme JLex/Cup ou javaCC pour t'aider) pour ce type de format non ??

Bulbo :wink:
09/07/2004, 16h46
narmataru
Alros pour connaitre le nombre de groupe trouvé tu fais appel à groupCount de ton matcher :roll:

pour savoir si une chaine correspond au prefixe d'une chaine correspondant à une regexp :
Code:

1 2 3 4 5 6 7 Pattern p = Pattern.compile(regexp); Matcher m = p.matcher(chaine); if(m.matches()){ if(chaine.startsWith(lePrefixe)){ commenceAvecLeprefixe = true } }
[EDIT]
Je suis assez d'accord avec bulbo. Un vrai parser avec un grammaire et tout et tout serais plus simple (après avoir compris comment ça marche :roll:)
09/07/2004, 17h26
EdoBvD

Géronte is right ?
Citation:

Envoyé par bulbo

Si tout est dans un fichier alors ta ligne est complete pourquoi te pourrir la vie ??

Là, je crois bien que c'est vrai. En fait, je reprend le développement de quelqu'un d'autre. Mais je pensais tellement que c'était possible de savoir si une chaine est le début d'une expression régulière... Il faudrait que je décrive le mécanisme en détail pour que çà soit compréhensible, j'vais essayer grosso modo déjà :D...

En gros, dans le programme principal il y a une boucle qui va lire caractère après caractère dans le fichier :
Code:

1 2 3 4 5 in = new LineNumberReader(new FileReader(filename)); while(c != -1 && ((result = document.parse(c)) == ParseResult.IN_PROGRESS)){ c = in.read(); }
document.parse va transmettre à ses fils le caractère à parser jusqu'à ce qu'il y en ai un qui accepte. Les fils, çà va être par exemple, le titre, un paragraphe, une bullet list, etc.

jusqu'à présent, il y avait des petits automates dans chaque fils qui permettaient à la fois d' 'accepter' et de "digérer" le contenu de chacun. Mais après avoir passer des heures à débugger ces tomates complètement imbriqués/enchevêtrés/spaghettonnés, j'me suis dis, une regex çà sert à çà :D Donc j'ai commencer à implémenter une classe abstraite qui identifie les entêtes des fils par une regex, et c là que çà coince.

Citation:

Envoyé par narmataru

Alros pour connaitre le nombre de groupe trouvé tu fais appel à groupCount de ton matcher

mea culpa, j'aurai pu trouver tout seul comme un grand ... si j'avais ouvert mes yeux .

par contre, pour le code que tu m'indiques pour le coup du préfixe, il y a oune petite détail qui gratte : la chaine qui correspond(matches) à la regex est inconnue, C'est à dire que l'on ne connait que le préfixe et la regex.

Citation:

Envoyé par bunarmatarulbo

Un vrai parser avec un grammaire et tout et tout serais plus simple

je me suis posé la question en commençant ce dév. Mais en regardant le format RST de plus près, je suis rester un peu perplexe sur la façon dont on pourrait le formaliser... j'ai vu un peu (pa assez) lex et yacc en cours et j'ai du mal à voir comment parser par exemple un tableau

[Edit]
bon ben j'va pas tarder à aller en WE, donc merci à vous deux, bon WE aussi et pis à lundi pour la suite des aventures formidablissimes des parsers aux regex :D

et là, je pense à la réplique de Géronte dans les fourberies de Scapin (Molière) : "Mais que diable allait-il faire à cette galère? Ah maudite galère!"
12/07/2004, 16h38
EdoBvD

jack laurent is dead

En utilisant ce package, j'arrive à me débrouiller pour faire ce que je veux !
http://jakarta.apache.org/regexp/

merci encore !
12/07/2004, 16h48
narmataru

hé bien il s'agit d'expressions régulière non ? qu'est-ce qu'il a en plus ce package ?

en plus

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
RE r = new RE("(a*)b");                  // Compile expression
boolean matched = r.match(test);     // Match against "xaaaab"
 
String wholeExpr = r.getParen(0);        // wholeExpr will be 'aaaab'
 
int startWholeExpr = r.getParenStart(0);   // startWholeExpr will be index 1
int endWholeExpr = r.getParenEnd(0);       // endWholeExpr will be index 6
int lenWholeExpr = r.getParenLength(0);    // lenWholeExpr will be 5
 
String insideParens = r.getParen(1);     // insideParens will be 'aaaa'
int startInside = r.getParenStart(1);    // startInside will be index 1
int endInside = r.getParenEnd(1);        // endInside will be index 5
int lenInside = r.getParenLength(1);     // lenInside will be 4

Code:

1
2
3
4
pour aaaaaaab :
true
whole = aaaaaaab
inside = aaaaaaa

Code:

1
2
3
4
pour aaaaacaab :
true
whole = aab
inside = aa

Code:

1
2
3
4
pour aaaaacaa :
false
whole = ""
inside = ""

donc en regardant à quelle position (start) est la chaine whole, on peut savoir si cela commence bien par ce qu'on veux, malgré le fait que çà soit plus ou moins mal placé.

13/07/2004, 16h22
EdoBvD

toujours plus toujours plus

encore mieux :
http://jregex.sourceforge.net

http://jregex.sourceforge.net/api/jregex/Matcher.html#matchesPrefix()
13/07/2004, 17h14
narmataru

C'est vrai qu'elle a l'aire bien puissante cette librairie :P