regexp et équilibrage de parenthèses

Le
mpg
Bonjour,

Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?

Autre question, peut-on faire une regexp qui matche les lignes ayant
exactement une parenthèse fermante de plus que de parenthèses ouvrantes ?
(En supposant, ou sans supposer, que les autres parenthèses sont
équilibrées et que la parenthèse surnuméraire arrive à la fin ?)

Bref, en gros, que peut-on détecter purement en regexp sur les
équilibrages de parenthèses ?

Merci d'avance,
Manuel.
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Matthieu Moy
Le #756920
mpg
Bonjour,

Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?


C'est un problème bien connu comme étant impossible en théorie (pour
vérifier un language bien parenthésé, il faut un automate à pile, et
les expressions régulières sont équivalentes aux automates finis
seulement).

Maintenant, il existe peut-être une syntaxe particulière d'expressions
régulière étendues pour le faire (par exemple, les expressions
régulières de perl sont bien plus puissantes que celles de la théorie
des expressions régulières), mais je pense pas.

--
Matthieu

Stephane Chazelas
Le #756919
2007-07-10, 20:39(+02), mpg:
Bonjour,

Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?
[...]


Avec les regexps de perl, oui, voir perldoc perlre où il y a un
exemple. Sinon non, mais avec des outils comme sed you awk, ca
ne pose pas de probleme:

sed '
h
s/[^()]//g
:1
s/()//g
t1
/./!d
g'

par exemple.

Retourne les lignes où les parentheses ne sont pas matchees.
Enlever le ! pour le contraire.

--
Stéphane

Pascal Bourguignon
Le #756918
mpg
Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?

Autre question, peut-on faire une regexp qui matche les lignes ayant
exactement une parenthèse fermante de plus que de parenthèses ouvrantes ?
(En supposant, ou sans supposer, que les autres parenthèses sont
équilibrées et que la parenthèse surnuméraire arrive à la fin ?)

Bref, en gros, que peut-on détecter purement en regexp sur les
équilibrages de parenthèses ?


En theorie, non.

En pratique, comme tu ne considère surement pas des lignes de longueur
indéfinie, on peut écrire une expression régulière qui détecte ce que
tu veux pour un nombre maximum de parenthèses. Mais ce serait idiot
de le faire, puisque ça resterait plus compliqué que d'écrire un
parseur recursif.


--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.

mpg
Le #756915
Le Tue, 10 Jul 2007 20:00:35 +0000, Stephane Chazelas a écrit:

2007-07-10, 20:39(+02), mpg:
Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?
[...]


Avec les regexps de perl, oui, voir perldoc perlre où il y a un exemple.


Hum... perlre fait un peu trois kilomètres de long :) Tu te souviens d'un
bon mot-clé pour retrouver l'exemple ? Du nom de la feature spécifique
perl qui permet de faire ça ?

Sinon non, mais avec des outils comme sed you awk, ca ne pose pas de
probleme:

En effet. En fait, je m'étais posé la question pour un fichier

d'indentation vim, j'ai donc pu résoudre le truc un peu brutalement en
comparant strlen(substitute(line, '[^{]', '', 'g')) et strlen(substitute
(line, '[^{]', '', 'g')) (il s'agissait de {} à équilibrer en fait).

Mais sur le principe ça m'intéressait pas mal de savoir si c'était
faisable en regex ou pas.

Manuel.


mpg
Le #756631
Le Tue, 10 Jul 2007 22:01:15 +0200, Pascal Bourguignon a écrit:

En theorie, non.

En pratique, comme tu ne considère surement pas des lignes de longueur
indéfinie, on peut écrire une expression régulière qui détecte ce que tu
veux pour un nombre maximum de parenthèses. Mais ce serait idiot de le
faire, puisque ça resterait plus compliqué que d'écrire un parseur
recursif.


Oui, en fait j'avais envisagé de commencer à déterminer combien de
parenthèses je pouvais raisonnablement avoir par ligne, et en déduire une
regex pas très belle qui fasse le boulot. Mais comme ça avait pas l'air
joli j'ai même pas essayé :)

Manuel.

Pascal Bourguignon
Le #756629
mpg
Le Tue, 10 Jul 2007 22:01:15 +0200, Pascal Bourguignon a écrit:

En theorie, non.

En pratique, comme tu ne considère surement pas des lignes de longueur
indéfinie, on peut écrire une expression régulière qui détecte ce que tu
veux pour un nombre maximum de parenthèses. Mais ce serait idiot de le
faire, puisque ça resterait plus compliqué que d'écrire un parseur
recursif.


Oui, en fait j'avais envisagé de commencer à déterminer combien de
parenthèses je pouvais raisonnablement avoir par ligne, et en déduire une
regex pas très belle qui fasse le boulot. Mais comme ça avait pas l'air
joli j'ai même pas essayé :)


C'est pas que ça n'ait pas l'air joli, au contraire:

(defun build-paren-match-regexp (max-parentheses)
"
RETURN: An extended regular expression matching
up to max-parentheses parentheses.
"
(flet ((alt (&rest regexps)
(format nil "~{(~A)~^|~}"
(remove-duplicates regexps :test (function string=))))
(seq (&rest regexps)
(format nil "~{~A~}" regexps)))
(let ((no-paren "[^()]*"))
(if (zerop max-parentheses)
no-paren
(let ((subre (build-paren-match-regexp (1- max-parentheses))))
(alt
subre
(seq subre "\(" no-paren "\)" no-paren)
(seq no-paren "\(" subre "\)" no-paren)
(seq no-paren "\(" no-paren "\)" subre)))))))

(BUILD-PAREN-MATCH-REGEXP 2) --> "(([^()]*)|([^()]*\([^()]*\)[^()]*))|(([^()]*)|([^()]*\([^()]*\)[^()]*)\([^()]*\)[^()]*)|([^()]*\(([^()]*)|([^()]*\([^()]*\)[^()]*)\)[^()]*)|([^()]*\([^()]*\)([^()]*)|([^()]*\([^()]*\)[^()]*))"

Mais la taille de l'expression régulière est exponentielle, alors on a
vite fait de remplir la mémoire.


Donc j'avais tors, en pratique, c'est aussi non...


--
__Pascal Bourguignon__ http://www.informatimago.com/

NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.


Stephane Chazelas
Le #756628
2007-07-11, 00:37(+02), mpg:
Le Tue, 10 Jul 2007 20:00:35 +0000, Stephane Chazelas a écrit:

2007-07-10, 20:39(+02), mpg:
Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?
[...]


Avec les regexps de perl, oui, voir perldoc perlre où il y a un exemple.


Hum... perlre fait un peu trois kilomètres de long :) Tu te souviens d'un
bon mot-clé pour retrouver l'exemple ? Du nom de la feature spécifique
perl qui permet de faire ça ?


Voir "(??{ code })" dans perlre.

Les regexps des ksh93 recents ont un operateur de matching de
paires si je me souviens bien.

--
Stéphane



bruno
Le #756626
mpg wrote:
Bonjour,

Est-il possible avec des expressions régulières de de repérer (soit
positivement, soit négativement) les lignes ayant des parenthèses
déséquilibrées ?




Bon, je suppose que c'est pas du tout ce que tu cherches, mais ca me
fait penser à un petit script perl que j'ai écrit, et étant plutôt fier
;-) je vais le poster:

C'est un script qui entoure les expressions lisp "globales" de deux
bornes <lisp> et </lisp>. Le but étant de les isoler. Il tient compte
des chaînes de caractères et des commentaires.

par exemple:

;; petit code en AutoLisp
(setq hello_world "hello world ! ;-)")
(defun hello ()
(princ hello_world))

devient:

;; petit code AutoLisp
<lisp>(setq hello_world "hello world ! ;-)")</lisp>
<lisp>(defun hello ()
(princ hello_world))</lisp>

Utilise l'entrée standart et renvoie sur la sortie standart:
./parse-lisp.pl
----8<---
cat parse-lisp.pl
#!/usr/bin/perl

sub parse_lisp {

my $arg = shift(@_);
my $result = '';
my $c = getc(STDIN);

SWITCH: {

if ($c eq ';') {
while (($c = getc(STDIN)) ne '' && $c ne "n") {
$result .= $c;
}
$result = ";$resultn";
# $result = "#;$result/#n";
last SWITCH;
}

if ($c eq '"') {
while (($c = getc(STDIN)) ne '' && $c ne '"') {
$result .= $c;
if ($c eq '\') { $result .= getc(STDIN); }
}
$result = ""$result"";
# $result = "["$result"]";
last SWITCH;
}

if ($c eq '(') {
while (($c = &parse_lisp($arg+1)) ne '') {
$result .= $c;
}
$result = "($result)";
if (!$arg) { $result = "<lisp>$result</lisp>"; }
# if (!$arg) { $result = "{$result}"; }
last SWITCH;
}

if ($arg && ($c eq ')')) {
$result = '';
last SWITCH;
}

$result = $c;

}

return $result;

}


while (($c = &parse_lisp) ne '') { print $c; }
----8<---

Publicité
Poster une réponse
Anonyme