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

Question

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

Alors qu'il est relativement facile de trouver des exemples démontrant la non-viabilité des regexes pour cette tâche ou une collection d'expressions pour représenter le concept, je n'ai toujours pas trouvé sur SO une explication formelle de pourquoi cela n'est pas possible expliqué de façon simple.

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

l'erreur ici est que HTML est une grammaire de type 2 de Chomsky (grammaire contextuelle) et RegEx est une grammaire de type 3 de Chomsky (expression régulière)

ou :

Les expressions régulières ne peuvent correspondre qu'à des langages réguliers mais HTML est un langage de type libre.

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 un nidification arbitrairement profonde, vous avez besoin d'un automate arbitrairement grand, ce qui entre en collision avec la notion d'un automate fini.

ou :

La "pumping lemma" pour les langages réguliers est la raison pour laquelle vous ne pouvez pas faire cela.

[La plupart des explications ci-dessus renvoient à des pages de wikipedia, mais celles-ci ne sont pas beaucoup plus faciles à comprendre que les réponses elles-mêmes].

Quelle est une traduction en termes simples des explications formelles données ci-dessus sur pourquoi il n'est pas possible d'utiliser des regex pour l'analyse (X)HTML/XML ?

Je recherche une traduction qui explique également brièvement les concepts qu'elle tente 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 contextuelle".

Answer 1

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 un enchevêtrement arbitrairement profond, vous avez besoin d'un automate arbitrairement grand, ce qui entre en collision avec la notion d'un automate fini.

La définition des expressions régulières est équivalente au fait qu'un test de correspondance d'une chaîne avec le motif peut être effectué par un automate fini (un automate différent pour chaque motif). 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, c'est un nombre fini d'états internes, chacun pouvant lire une unité d'entrée à partir de la chaîne testée, et utiliser cela pour décider du prochain état vers lequel se déplacer. En tant que cas spéciaux, il a deux états de terminaison : "oui, cela correspondait", et "non, cela ne correspondait pas".

D'autre part, le HTML 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 quelle élément est en train d'être fermé. Sans aucun moyen de "se souvenir" des balises ouvertes que vous avez vues, pas de chance.

Cependant, notez que la plupart des bibliothèques "regex" permettent en réalité plus que la stricte définition des expressions régulières. S'ils peuvent faire correspondre des rétro-références, alors ils ont dépassé un langage régulier. Donc, la raison pour laquelle vous ne devriez pas utiliser une bibliothèque regex sur du HTML est un peu plus complexe que le simple fait que le HTML n'est pas régulier.

Answer 2

Le fait que HTML ne représente pas un langage régulier est une fausse piste. Les expressions régulières et les langages réguliers semblent un peu 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 le pouvoir actuel de correspondance des moteurs. En fait, presque tous les moteurs d'expressions régulières modernes supportent des fonctionnalités non régulières - un exemple simple est (.*)\1, qui utilise des références arrière pour correspondre à une séquence répétée de caractères - par exemple 123123, ou bonbon. La correspondance de structures récursives/équilibrées les rend encore plus amusantes.

Wikipédia le dit joliment, dans une citation de Larry Wall:

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

"Les expressions régulières ne peuvent correspondre qu'aux langages réguliers", comme vous pouvez le voir, ce n'est rien de plus qu'une fausse idée communément prononcée.

Alors, pourquoi pas?

Une bonne raison de ne pas utiliser d'expressions régulières pour correspondre à HTML est que "juste parce que vous le pouvez ne signifie pas que vous devriez le faire". Même si cela est possible - il existe simplement de meilleurs outils pour le travail. En considérant:

• Le HTML valide est plus difficile/plus complexe que vous ne le pensez.

• Il existe de nombreux types de HTML "valides" - ce qui est valide en HTML, par exemple, n'est pas valide en XHTML.

• Une grande partie du HTML en libre forme que l'on trouve sur internet n'est de toute façon pas valide. Les bibliothèques HTML font un bon travail pour traiter ces cas également, et ont été testées pour de nombreux de ces cas courants.

• Très souvent, il est impossible de correspondre à une partie des données sans les analyser dans leur globalité. Par exemple, vous pourriez chercher tous les titres, et finir par correspondre à l'intérieur d'un commentaire ou d'une chaîne littérale.

  .*?

  pourrait être une tentative audacieuse pour trouver le titre principal, mais il pourrait trouver:

  Ou même:

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

Le dernier point est le plus important:

• Utiliser un analyseur HTML dédié est préférable à n'importe quelle regex que vous pouvez imaginer. Très souvent, XPath permet une meilleure façon expressive de trouver les données dont vous avez besoin, et utiliser un analyseur HTML est beaucoup plus facile que la plupart des gens ne le réalise.

Un bon résumé du sujet, et un commentaire important sur quand mélanger les Regex et HTML peut être approprié, se trouve 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 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. Néanmoins, contrairement à l'opinion populaire, il y a quelques cas où je recommanderais fortement d'utiliser une regex et non une bibliothèque d'analyse :

Étant donné quelques-unes de ces conditions:

• Lorsque vous avez besoin d'une mise à jour ponctuelle de vos fichiers HTML, et que vous connaissez la structure est cohérente.
• Lorsque vous avez un tout petit extrait de HTML.
• Lorsque vous ne traitez pas un fichier HTML, mais un moteur de template similaire (il peut être très difficile de trouver un analyseur dans ce cas).
• Lorsque vous voulez modifier des parties du HTML, mais pas tout - un analyseur, à ma connaissance, ne peut répondre à cette demande : il analysera le document entier, et sauvegardera un document complet, modifiant des parties que vous n'avez jamais voulu changer.

Answer 3

Parce que HTML peut avoir un nesting illimité de et regex ne peut pas vraiment gérer ça parce qu'il ne peut pas suivre l'historique de ce qu'il a descendu et est sorti.

Une simple construction qui illustre la difficulté :

Salut! Au revoir!

99,9% des routines d'extraction basées sur des regex généralisées ne pourront pas me donner correctement tout ce qui est à l'intérieur du div avec l'ID foo, car elles ne peuvent pas distinguer la balise de fermeture pour ce div de la balise de fermeture pour le bar div. C'est parce qu'elles n'ont aucun moyen de dire "ok, je suis maintenant descendu dans le deuxième des deux divs, donc la prochaine balise de fermeture div que je vois me fait remonter d'un, et celle d'après est la balise de fermeture pour le premier". Les programmeurs répondent généralement en concevant des regex spécifiques pour la situation spécifique, qui se cassent alors dès que plus de balises sont introduites à l'intérieur de foo et doivent être démêlées à un coût énorme en temps et en frustration. C'est pourquoi les gens se mettent en colère à propos de tout cela.

Answer 4

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

Pour analyser XML, C, ou tout autre langage avec un nidification arbitraire des éléments du langage, vous devez vous rappeler à quelle profondeur vous vous trouvez. 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 vous avez d'états! Vous pourriez être en mesure d'analyser un sous-ensemble de votre langage qui restreint le nombre de niveaux de nidification, mais cela serait très fastidieux.

Answer 5

Une grammaire est une définition formelle de l'endroit où les mots peuvent aller. Par exemple, les adjectifs précèdent les noms dans la grammaire anglaise, mais suivent les noms dans la grammaire espagnole. Context-free signifie que la grammaire fonctionne universellement dans tous les contextes. Context-sensitive signifie qu'il y a des règles supplémentaires dans certains contextes.

En C#, par exemple, using signifie quelque chose de différent dans using System; en haut des fichiers, que dans 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"");
    }
    ";
}