Pourquoi il n'est pas possible d'utiliser des regex pour analyser HTML / XML: une explication formelle en termes simples

Il n'y a pas de jour sur SO qui passe sans une question sur l'analyse (X) HTML ou XML avec des expressions régulières posées.

Bien qu'il soit relativement facile de trouver des exemples qui démontrent la non-viabilité des expressions rationnelles pour cette tâche ou avec une collection d'expressions pour représenter le concept, je n'ai toujours pas pu trouver sur SO une explication formelle de la raison pour laquelle cela n'est pas possible en profane. termes.

Les seules explications formelles que j'ai pu trouver jusqu'à présent sur ce site sont probablement extrêmement précises, mais aussi assez cryptiques pour le programmeur autodidacte:

le défaut ici est que HTML est une grammaire Chomsky Type 2 (grammaire sans contexte) et RegEx est une grammaire Chomsky Type 3 (expression régulière)

ou:

Les expressions régulières ne peuvent correspondre qu'à des langues régulières, mais HTML est un langage sans contexte.

ou:

Un automate fini (qui est la structure de données sous-jacente à une expression régulière) n'a pas de mémoire en dehors de l'état dans lequel il se trouve, et si vous avez une imbrication arbitraire profonde, vous avez besoin d'un automate arbitrairement grand, qui entre en conflit avec la notion d'automate fini.

ou:

Le lemme de pompage pour les langues régulières est la raison pour laquelle vous ne pouvez pas faire cela.

[Pour être honnête: la majorité des explications ci-dessus renvoient aux pages wikipedia, mais ce ne sont pas beaucoup plus faciles à comprendre que les réponses elles-mêmes].

Ma question est donc la suivante: quelqu'un pourrait-il s'il vous plaît fournir une traduction en termes simples des explications formelles données ci-dessus sur les raisons pour lesquelles il n'est pas possible d'utiliser des regex pour analyser (X) HTML / XML?

EDIT: Après avoir lu la première réponse, j'ai pensé que je devais clarifier: je cherche une "traduction" qui explique aussi brièvement les concepts qu'elle essaie de traduire: à la fin d'une réponse, le lecteur devrait avoir une idée approximative - par exemple - de ce que signifient "langage régulier" et "grammaire sans contexte" ...

Concentrez-vous sur celui-ci:

Un automate fini (qui est la structure de données sous-jacente à une expression régulière) n'a pas de mémoire en dehors de l'état dans lequel il se trouve, et si vous avez une imbrication arbitraire profonde, vous avez besoin d'un automate arbitrairement grand, qui entre en conflit avec la notion d'automate fini.

La définition des expressions régulières équivaut au fait qu'un test pour savoir si une chaîne correspond au modèle peut être effectué par un automate fini (un automate différent pour chaque modèle). Un automate fini n'a pas de mémoire - pas de pile, pas de tas, pas de bande infinie sur laquelle griffonner. Tout ce qu'il a est un nombre fini d'états internes, dont chacun peut lire une unité d'entrée de la chaîne testée, et l'utiliser pour décider à quel état passer au suivant. En tant que cas spéciaux, il a deux états de terminaison: "oui, cela correspond" et "non, cela ne correspond pas".

HTML, d'autre part, a des structures qui peuvent s'emboîter de manière arbitraire. Pour déterminer si un fichier est du HTML valide ou non, vous devez vérifier que toutes les balises de fermeture correspondent à une balise d'ouverture précédente. Pour le comprendre, vous devez savoir quel élément est fermé. Sans aucun moyen de "se souvenir" des balises d'ouverture que vous avez vues, aucune chance.

Notez cependant que la plupart des bibliothèques "regex" permettent en fait plus que la définition stricte des expressions régulières. S'ils peuvent correspondre à des références arrière, alors ils sont allés au-delà d'un langage normal. Donc, la raison pour laquelle vous ne devriez pas utiliser une bibliothèque regex sur HTML est un peu plus complexe que le simple fait que le HTML n'est pas régulier.

Le fait que le HTML ne représente pas une langue régulière est un hareng rouge. Les expressions régulières et les langages réguliers semblent similaires , mais ne le sont pas - ils partagent la même origine, mais il y a une distance notable entre les «langages réguliers» académiques et la puissance actuelle des moteurs. En fait, presque tous les moteurs d'expressions régulières modernes prennent en charge les fonctionnalités non régulières - un exemple simple est (.*)\1. qui utilise le backreferencing pour faire correspondre une séquence répétée de caractères - par exemple 123123, ou bonbon. L'association de structures récursives / équilibrées les rend encore plus amusantes.

Wikipédia met cela bien, dans une citation de Larry Wall :

Les «expressions régulières» [...] ne sont que marginalement liées aux expressions régulières réelles. Néanmoins, le terme a grandi avec les capacités de nos moteurs de correspondance de motifs, je ne vais donc pas essayer de lutter contre la nécessité linguistique ici. Je les appellerai cependant généralement des "regexes" (ou "regexen", quand je suis d'humeur anglo-saxonne).

«L'expression régulière ne peut correspondre qu'à des langages réguliers», comme vous pouvez le voir, n'est rien d'autre qu'une erreur communément déclarée.

Alors pourquoi pas alors?

Une bonne raison pour ne pas faire correspondre HTML avec une expression régulière est que "ce n'est pas parce que vous pouvez le faire". Bien que cela soit possible, il existe simplement de meilleurs outils pour le travail . Considérant:

• Un HTML valide est plus difficile / plus complexe que vous ne le pensez.
• Il existe de nombreux types de HTML "valide" - ce qui est valide en HTML, par exemple, n'est pas valide en XHTML.
• Une grande partie du code HTML de forme libre trouvé sur Internet n'est de toute façon pas valide . Les bibliothèques HTML font également un bon travail pour les gérer et ont été testées pour bon nombre de ces cas courants.

• Très souvent, il est impossible de faire correspondre une partie des données sans les analyser dans son ensemble. Par exemple, vous pouvez rechercher tous les titres et finir par correspondre à l'intérieur d'un commentaire ou d'une chaîne littérale. <h1>.*?</h1>peut être une tentative audacieuse de trouver le titre principal, mais il pourrait trouver:

  <!-- <h1>not the title!</h1> -->

  Ou même:

  <script>
  var s = "Certainly <h1>not the title!</h1>";
  </script>

Le dernier point est le plus important:

• L'utilisation d'un analyseur HTML dédié est meilleure que n'importe quelle expression régulière que vous pouvez créer. Très souvent, XPath permet une meilleure façon expressive de trouver les données dont vous avez besoin, et l' utilisation d'un analyseur HTML est beaucoup plus facile que la plupart des gens ne le pensent .

Un bon résumé du sujet, et un commentaire important sur le mélange de Regex et de HTML peut être approprié, peuvent être trouvés dans le blog de Jeff Atwood: Parsing Html The Cthulhu Way .

Quand est-il préférable d'utiliser une expression régulière pour analyser le HTML?

Dans la plupart des cas, il est préférable d'utiliser XPath sur la structure DOM qu'une bibliothèque peut vous donner. Pourtant, contre l'opinion populaire, il y a quelques cas où je recommanderais fortement d'utiliser une regex et non une bibliothèque d'analyseurs:

Compte tenu de quelques-unes de ces conditions:

• Lorsque vous avez besoin d'une mise à jour unique de vos fichiers HTML et que vous savez que la structure est cohérente.
• Lorsque vous avez un tout petit extrait de code HTML.
• Lorsque vous n'avez pas affaire à un fichier HTML, mais à un moteur de création de modèles similaire (il peut être très difficile de trouver un analyseur dans ce cas).
• Lorsque vous voulez changer des parties du HTML, mais pas la totalité - un analyseur, à ma connaissance, ne peut pas répondre à cette demande: il analysera tout le document et enregistrera un document entier, en changeant les parties que vous n'avez jamais voulu changer.

Parce que HTML peut avoir une imbrication illimitée <tags><inside><tags and="<things><that><look></like></tags>"></inside></each></other>et que l'expression régulière ne peut pas vraiment faire face à cela, car elle ne peut pas suivre un historique de ce dans quoi il est descendu et d'où il est sorti.

Une construction simple qui illustre la difficulté:

<body><div id="foo">Hi there!  <div id="bar">Bye!</div></div></body>

99,9% des routines d'extraction généralisées basées sur les regex seront incapables de me donner correctement tout ce qui se trouve à l'intérieur du divavec l'ID foo, car ils ne peuvent pas dire la balise de fermeture pour ce div de la balise de fermeture pour le bardiv. C'est parce qu'ils n'ont aucun moyen de dire "d'accord, je suis maintenant descendu dans la deuxième des deux divs, donc la prochaine div close que je vois me ramène à une, et celle qui suit est la balise de fermeture pour la première" . Les programmeurs répondent généralement en concevant des expressions régulières de cas spéciaux pour la situation spécifique, qui se cassent dès que plus de balises sont introduites à l'intérieur fooet doivent être libérées à un coût énorme en temps et en frustration. C'est pourquoi les gens deviennent fous de tout cela.

Un langage normal est un langage auquel une machine à états finis peut correspondre.

(Comprendre les machines à états finis, les machines à pousser vers le bas et les machines de Turing est essentiellement le programme d'un cours de quatrième année universitaire.)

Considérez la machine suivante, qui reconnaît la chaîne "hi".

(Start) --Read h-->(A)--Read i-->(Succeed)
  \                  \
   \                  -- read any other value-->(Fail) 
    -- read any other value-->(Fail)

C'est une machine simple pour reconnaître une langue régulière; Chaque expression entre parenthèses est un état et chaque flèche est une transition. Construire une machine comme celle-ci vous permettra de tester n'importe quelle chaîne d'entrée par rapport à un langage régulier - par conséquent, une expression régulière.

Le HTML exige que vous sachiez plus que simplement dans quel état vous vous trouvez - il nécessite un historique de ce que vous avez vu auparavant, pour correspondre à l'imbrication des balises. Vous pouvez accomplir cela si vous ajoutez une pile à la machine, mais alors elle n'est plus "régulière". Cela s'appelle une machine Push-down et reconnaît une grammaire.

Une expression régulière est une machine avec un nombre fini (et généralement assez petit) d'états discrets.

Pour analyser XML, C ou tout autre langage avec une imbrication arbitraire d'éléments de langage, vous devez vous rappeler à quel point vous êtes. Autrement dit, vous devez être capable de compter les accolades / crochets / balises.

Vous ne pouvez pas compter avec une mémoire finie. Il peut y avoir plus de niveaux d'accolades que d'états! Vous pourrez peut-être analyser un sous-ensemble de votre langage qui limite le nombre de niveaux d'imbrication, mais ce serait très fastidieux.

Une grammaire est une définition formelle de l'endroit où les mots peuvent aller. Par exemple, les adjectifs précèdent les noms in English grammar, mais suivent les noms en la gramática española. Sans contexte signifie que le grammeur est universellement dans tous les contextes. Sensible au contexte signifie qu'il existe des règles supplémentaires dans certains contextes.

En C #, par exemple, usingsignifie quelque chose de différent en using System;haut des fichiers, que using (var sw = new StringWriter (...)). Un exemple plus pertinent est le code suivant dans le code:

void Start ()
{
    string myCode = @"
    void Start()
    {
       Console.WriteLine (""x"");
    }
    ";
}

Il y a une autre raison pratique pour ne pas utiliser d'expressions régulières pour analyser XML et HTML qui n'a rien à voir avec la théorie de l'informatique: votre expression régulière sera soit horriblement compliquée, soit elle sera erronée.

Par exemple, c'est très bien d'écrire une expression régulière pour correspondre

<price>10.65</price>

Mais si votre code doit être correct, alors:

• Il doit autoriser les espaces après le nom de l'élément dans les balises de début et de fin

• Si le document est dans un espace de noms, alors il doit permettre l'utilisation de n'importe quel préfixe d'espace de noms

• Il devrait probablement autoriser et ignorer tous les attributs inconnus apparaissant dans la balise de début (selon la sémantique du vocabulaire particulier)

• Il peut être nécessaire d'autoriser les espaces avant et après la valeur décimale (encore une fois, en fonction des règles détaillées du vocabulaire XML particulier).

• Cela ne devrait pas correspondre à quelque chose qui ressemble à un élément, mais qui se trouve en fait dans un commentaire ou une section CDATA (cela devient particulièrement important s'il y a une possibilité que des données malveillantes tentent de tromper votre analyseur).

• Il peut avoir besoin de fournir des diagnostics si l'entrée n'est pas valide.

Bien sûr, cela dépend en partie des normes de qualité que vous appliquez. Nous voyons beaucoup de problèmes sur StackOverflow avec des personnes devant générer du XML d'une manière particulière (par exemple, sans espace dans les balises) car il est lu par une application qui nécessite qu'il soit écrit d'une manière particulière. Si votre code a une certaine longévité, il est important qu'il puisse traiter le XML entrant écrit de toutes les manières autorisées par la norme XML, et pas seulement le seul exemple de document d'entrée sur lequel vous testez votre code.

Dans un sens purement théorique, il est impossible pour les expressions régulières d'analyser XML. Ils sont définis d'une manière qui ne leur permet aucune mémoire d'un état précédent, empêchant ainsi la correspondance correcte d'une balise arbitraire, et ils ne peuvent pas pénétrer à une profondeur arbitraire d'imbrication, car l'imbrication devrait être intégrée à l'expression régulière.

Les analyseurs de regex modernes, cependant, sont construits pour leur utilité pour le développeur, plutôt que pour leur adhésion à une définition précise. En tant que tel, nous avons des choses comme les références arrière et la récursivité qui utilisent la connaissance des états précédents. En les utilisant, il est remarquablement simple de créer une expression régulière qui peut explorer, valider ou analyser du XML.

Considérez par exemple,

(?:
    <!\-\-[\S\s]*?\-\->
    |
    <([\w\-\.]+)[^>]*?
    (?:
        \/>
        |
        >
        (?:
            [^<]
            |
            (?R)
        )*
        <\/\1>
    )
)

Cela trouvera la prochaine balise ou commentaire XML correctement formé, et il ne le trouvera que si son contenu entier est correctement formé. (Cette expression a été testée en utilisant Notepad ++, qui utilise la bibliothèque regex de Boost C ++, qui se rapproche étroitement de PCRE.)

Voici comment ça fonctionne:

1. Le premier morceau correspond à un commentaire. Il est nécessaire que cela vienne en premier afin qu'il traite tout code commenté qui pourrait autrement provoquer des blocages.
2. Si cela ne correspond pas, il recherchera le début d'une balise. Notez qu'il utilise des parenthèses pour capturer le nom.
3. Cette balise se terminera par un />, complétant ainsi la balise, ou se terminera par un >, auquel cas elle continuera en examinant le contenu de la balise.
4. Il continuera l'analyse jusqu'à ce qu'il atteigne un < , auquel point il reviendra au début de l'expression, lui permettant de traiter un commentaire ou une nouvelle balise.
5. Il continuera à travers la boucle jusqu'à ce qu'il arrive à la fin du texte ou à un <qu'il ne peut pas analyser. Le fait de ne pas correspondre le fera, bien sûr, redémarrer le processus. Sinon, le <est vraisemblablement le début de la balise de fermeture de cette itération. En utilisant la référence arrière à l'intérieur d'une balise de fermeture <\/\1>, elle correspondra à la balise d'ouverture de l'itération actuelle (profondeur). Il n'y a qu'un seul groupe de capture, donc cette correspondance est une question simple. Cela le rend indépendant des noms des balises utilisées, bien que vous puissiez modifier le groupe de capture pour capturer uniquement des balises spécifiques, si nécessaire.
6. À ce stade, il sortira de la récursivité actuelle, jusqu'au niveau suivant ou se terminera par un match.

Cet exemple résout les problèmes de gestion des espaces ou d'identification du contenu pertinent en utilisant des groupes de caractères qui annulent simplement <ou >, ou dans le cas des commentaires, en utilisant [\S\s], qui correspondra à tout, y compris les retours chariot et les nouvelles lignes, même sur une seule ligne mode, en continuant jusqu'à ce qu'il atteigne un -->. Par conséquent, il traite simplement tout comme valide jusqu'à ce qu'il atteigne quelque chose de significatif.

Dans la plupart des cas, une expression régulière comme celle-ci n'est pas particulièrement utile. Cela validera que XML est correctement formé, mais c'est tout ce qu'il fera vraiment, et il ne tient pas compte des propriétés (bien que ce serait un ajout facile). C'est aussi simple que cela car cela laisse de côté les problèmes du monde réel comme celui-ci, ainsi que les définitions des noms de balises. L'adapter pour une utilisation réelle en ferait beaucoup plus une bête. En général, un véritable analyseur XML serait bien supérieur. Celui-ci est probablement le mieux adapté pour enseigner le fonctionnement de la récursivité.

En bref: utilisez un analyseur XML pour un vrai travail, et utilisez-le si vous voulez jouer avec les expressions régulières.

N'analysez pas XML / HTML avec regex, utilisez un analyseur XML / HTML approprié et un puissant xpath requete.

théorie :

Selon la théorie de la compilation, XML / HTML ne peut pas être analysé à l'aide de regex basée sur une machine à états finis . En raison de la construction hiérarchique de XML / HTML, vous devez utiliser un automate pushdown et manipuler la grammaire LALR à l'aide d'un outil tel que YACC .

outil de tous les jours realLife © ® ™ dans un coquille :

Vous pouvez utiliser l'un des éléments suivants:

xmllint est souvent installé par défaut avec libxml2, xpath1 (vérifiez mon wrapper pour avoir une sortie délimitée par les retours à la ligne

xmlstarlet peut éditer, sélectionner, transformer ... Non installé par défaut, xpath1

xpath installé via le module XML :: XPath, xpath1 de perl

xidel xpath3

saxon-lint mon propre projet, wrapper sur la bibliothèque Java Saxon-HE de @Michael Kay, xpath3

ou vous pouvez utiliser des langages de haut niveau et des bibliothèques appropriées, je pense à:

pythonde lxml ( from lxml import etree)

perl« s XML::LibXML, XML::XPath,XML::Twig::XPath ,HTML::TreeBuilder::XPath

rubis nokogiri, vérifiez cet exemple

php DOMXpath, vérifiez cet exemple

Vérifier: Utilisation d'expressions régulières avec des balises HTML