Détecter les balises non fermées

Utiliser les expressions régulières pour détecter les balises non fermées

L’auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour à tous,

J’ai un chaîne de caractères à analyser afin de déterminer les balises non fermées. Je DOIS travailler sur une chaîne, c’est une contrainte à respecter.

Voici quelques exemples des chaînes que je dois analyser :

1
2
3
4
5
6
7
8
- ...<tag_1>.....</tag_1>... [fin de chaîne] : aucun tag n'est pas fermé
- ... <tag_1>.... <tag_2>...</tag_2>...[fin de chaîne] : information à obtenir : le tag_1 n'est 
pas fermé
- ...<tag_1>...<tag_2>...[fin de chaîne] : information à obtenir : le tag_1 n'est pas fermé et
 il contient le tag_2 qui n'est pas fermé
- ... <tag_1>...<tag_2>...<tag_3>..[fin de chaîne] : information à obtenir : le tag_1 n'est pas
 fermé et il contient le tag_2 qui n'est pas fermé et qui contient à son tour tag_3 qui n'est 
pas fermé et ainsi de suite

Je cherche depuis un moment du côté des assertions mais je ne parviens à rien… Au final, je ne sais plus comment m’y prendre pour résoudre ce problème

Tous les indices ou toutes les propositions sont les bienvenus car je n’ai plus d’idées après en avoir testées plus d’une vingtaine.

Merci par avance

Édité par picode

+0 -0

Cette réponse a aidé l’auteur du sujet

Bonjour,

On ne peut malheureusement pas effectuer ce genre de tâches en n’employant que des expressions régulières. Ceci est connu sous le nom: "pumping lemma". Il faut se servir de quelque chose de plus puissant, les langages algébriques (ou "sans contexte") qui correspondent à des automates à (simple) pile.

Comme le problème est peu compliqué, on peut donner une solution rapide au problème sans sortir l’artillerie lourde. Il suffit de chercher toutes les balises du texte dans l’ordre (avec des expressions régulières) et, à chaque fois qu’on trouve une balise ouvrante, on la met sur la pile. Si elle est fermante, on s’assure que la balise ouvrante est au sommet de la pile et on la retire. A la fin, on vérifie que la pile est vide.

Édité par Gawaboumga

+0 -0

Cette réponse a aidé l’auteur du sujet

Salut,

Personnellement, je partirais sur une fonction récursive qui crée un graphe des tags existant (en négligeant le contenu vu que ça ne semble pas importer). Quand elle rencontre une ouverture de tag, elle crée un nouvel élément dans l’élément actuel et quand elle rencontre une fermeture de tag, elle modifie une propriété dans l’élément correspondant. Une fois la chaîne de caractères entièrement parcouru, tu vérifies juste les propriétés de chaque élément (ou plus rapide, tu comptes le nombre d’éléments au fur et à mesure que tu les ajoutes et tu comptes le nombre de fermetures, si c’est égal, c’est bon). C’est probablement plus lourd que la méthode de Gawaboumga mais tu finis avec un graphe des balises, et tu peux savoir lesquels n’ont pas été fermés. Tout dépend de ce que tu souhaites faire.

Cependant, ce n’est qu’une des manières, parmi tant d’autres. La plus simple à mettre en place serait de tenter de parser le machin, et si ça pète, c’est que le XML n’est pas valide.

Cette réponse a aidé l’auteur du sujet

Une fonction récursive me semble overkill.

N’en déplaise à Fumble, dans ce cas précis, je pense que tu peux utiliser une regexp pour itérer sur les tags (tu t’en fous de ce qu’il y a entre les tags et tu t’en fous de leurs attributs, donc la regex est super simple: <[^>]+>). Le but n’est pas de parser réellement le HTML (pour produire un arbre), mais de détecter les incohérences, ce qui est tout à fait faisable de façon séquentielle.

Partant de là, en itérant sur tes tags, tu maintiens une pile :

  • si tu rencontres un tag ouvrant, tu l’empiles.
  • si tu rencontres un tag fermant et qu’il correspond au sommet de la pile, tu dépiles le sommet.
  • si tu rencontres un tag fermant et qu’il n’est pas le sommet de la pile, tu as une erreur. Tu parcours la pile du sommet à sa base pour chercher le tag ouvrant :
    • si le tag ouvrant est dans la pile, tu dépiles tout ce qui est au-dessus, ce sont autant de tags pas fermés.
    • s’il n’y a même pas de tag ouvrant correspondant dans la pile, tu t’arrêtes ici, le document est complètement niqué.

Tu peux ensuite raffiner en traitant les tags standalones du HTML (comme <br>) qui sont censés être neutres et ne causer ni empilement, ni dépilement.

Édité par nohar

I was a llama before it was cool

+0 -0

Cette réponse a aidé l’auteur du sujet

Peu importe l’implémentation de la recherche des tags, c’est pas ce qui pose problème ici. On peut aussi vouloir chercher tous les caractères < et utiliser ces positions pour faire le traitement. Ca reviendrait strictement au même qu’utiliser des expressions régulières. Ce qui va compter, c’est le besoin ou non de gérer les cas pathologiques (<img alt="<img> tag" /> par exemple) et l’utilisation d’une pile pour vérifier la grammaire comme l’a très bien expliqué Gawaboumga.

+0 -0
Auteur du sujet

J’ai pondu la fonction ci-dessous sur vos conseils. Je parcours la chaîne (qui n’est jamais bien longue, c’est l’équivalent d’un paragraphe), je détecte si j’ai une balise ouvrante, dans ce cas, je l’empile. Si c’est une balise fermante, je vérifie qu’elle correspond à la dernière balise empilée. Si c’est le cas, je la dépile. Comme j’ai besoin de connaître la position de la balise dans la chaîne, j’ai ajouté une autre variable qui me permet de stocker la position de la balise et son nom.

Après plusieurs tests, j’ai bien le résultat attendu.

Voici ma solution (n’hésitez pas à la critiquer)

 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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
function searchTagNotClosed(string) {
    var arrTagNotClosed = new Object();
    var pile = [];
    for (var i in string) {
        var c = string[i];
        //Détection d'une balise
        if (c === '<') {

            var isTagStart = false;
            var isTagEnd = false;
            var j; //position à partir de laquelle récupérer le nom de la balise
            //type de la balise (fermante ou ouvrante)
            var p = parseInt(i) + parseInt(1);
            if (string[p] === '/') {
                //balise fermante
                isTagEnd = true;
                j = parseInt(i) + parseInt(2);
            } else {
                //balise ouvrante
                isTagStart = true;
                j = parseInt(i) + parseInt(1);
            }
            //on récupère le nom de la balise et on commence à partir de la
            // position courante (qui est < plus 1)
            if (isTagStart || isTagEnd) {
                //on récupère la chaîne à partir de la position courante J
                var stringWithTagName = string.substring(j);
                //le nom s'arrête à > (ce qui inclus alors les éventuels attributs)
                var pos = stringWithTagName.indexOf('>');
                var stringTagNameWithAttr = stringWithTagName.substr(0, pos);
                pos = stringTagNameWithAttr.indexOf(' ');
                if (pos !== -1) {
                    //il y avait bien des attributs, donc on récupère seulement
                    //le nom du tag
                    var tagName = stringWithTagName.substr(0, pos);
                } else {
                    //il n'y a pas d'attribut
                    tagName = stringTagNameWithAttr;
                }

                //si c'est une balise ouvrante, il faut l'empiler et mettre à jour
                // le tableau qui contient le tag et sa position (i) dans la chaîne
                if (isTagStart) {
                    //on empile (en début de tableau)
                    pile.unshift(tagName);
                    arrTagNotClosed[i] = tagName;
                }
                //si c'est une balise fermante, il faut regarder si le nom est
                // le même que le premier élément du tableau. Si c'est le cas,
                // cela signifie que la balise est fermée, il faut retirer
                // l'élément de la pile
                if (isTagEnd) {
                    if (tagName === pile[0]) {
                        //on dépile en début de tableau
                        pile.shift();
                        //on supprime également l'élément dépilé du tableau
                        // contenant les tags ouverts avec leur position
                        Object.deleteLast(arrTagNotClosed);
                    } else {
                        arrTagNotClosed[i] = tagName;
                    }
                }
            }
        }
    }
    return arrTagNotClosed;
}

Je marque le sujet comme résolu, mais s’il y a moyen d’optimiser, n’hésitez pas à le dire. De plus, pour l’instant, ma fonction ne gère pas la possibilité de rencontrer des balises orphelines.

Merci à tous les participants de ce sujet.

+0 -0

Cette réponse a aidé l’auteur du sujet

Quelques commentaires sur ton code :

1
2
3
4
5
// il faut mieux utiliser la syntaxe
{}
// plutôt que
new Object()
// car c'est plus lisible
1
2
// tu peux déclarer deux variables en une ligne
var arrTagNotClosed = {}, pile = []
1
2
3
4
5
6
7
8
// dans une boucle, tu peux remplacer
if (c === '<') {
    foo()
}
// par
if (c !== '<') continue;
foo()
// ça t'évite d'avoir à indenter la partie `foo()`
1
2
3
4
5
6
7
// si deux variables sont égales
var isTagStart = isTagEnd = false
// attention, si c'est une référence, quand tu en modifieras un, tu modifieras l'autre
// par exemple, si tu fais
var foo = bar = []
foo.push(1)
// bar vaudra [1]
1
2
3
4
5
6
7
// je n'ai pas vraiment compris pourquoi tu faisais ça :
var p = parseInt(i) + parseInt(1)
// tu sais que i est l'indice du caractère, donc c'est un nombre entier de base
// (note qu'il n'y a pas de type `int` en JS, un entier est juste un `number` avec `n % 1 === 0`)
// et 1 est un nombre entier lui aussi
var p = i + 1
// pareil pour j
1
2
3
4
5
6
7
8
isTagStart || isTagEnd
// est toujours vrai car tu as juste au dessus
if (foo()) {
    isTagStart = true
} else {
    isTagEnd = true
}
// dans tout les cas, l'un des deux est vrai
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// tu n'as pas vraiment besoin d'avoir `isTagStart` et `isTagEnd`, vu que l'un est l'opposé de l'autre
// donc au lieu de faire
if (isTagStart) {
    foo()
}
if (isTagEnd) {
    bar()
}
// tu peux faire
if (isTagStart) {
    foo()
} else {
    bar()
}

Pourquoi est-ce que tu travailles au début de la liste ? Il me semble que c’est du O(n) pour ajouter un élément au début, vu qu’il doit tout déplacer dans la liste alors que c’est du ~ O(1) si tu append. Sinon, il y a des types faits exprès pour ce genre d’opération, mais ça ne sert pas vraiment dans ton cas je pense.

Pour moi, le principal point d’amélioration que tu peux avoir est d’éviter au maximum d’indenter. Tu arrives à un endroit dans ton algo à 6 indentations. Quand tu sais que la majorité de ton algo va être dans une condition, traite l’inverse avant comme ça tu n’as pas à indenter le corps de l’algo. Et utilise des fonctions pour auto-documenter ton code et isoler les différentes sections de ton algo. Ça ne le rendra que plus clair.

Auteur du sujet

Merci beaucoup tleb pour ces remarques très pertinentes. J’en prends bonne note et compte bien appliquer cette logique pour la suite.

Pour ta question :

// je n’ai pas vraiment compris pourquoi tu faisais ça : var p = parseInt(i) + parseInt(1)

Et bien si je ne fais pas cela, avec par exemple i = 1, je vais avoir p = 11 (i est concaténé à 1), pareil pour j… (et pourtant je suis bien d’accord avec toi que i est un entier)

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte