Comment les analyses HTML fonctionnent-elles si elles n'utilisent pas de regexp ?

Question

Je vois tous les jours des questions demandant comment analyser ou extraire quelque chose d'une chaîne HTML et la première réponse/commentaire est toujours "N'utilisez pas RegEx pour analyser le HTML, sinon vous ressentirez la colère ! (cette dernière partie est parfois omise).

J'ai toujours pensé qu'en général, la meilleure façon d'analyser une chaîne complexe était d'utiliser une expression régulière. Alors comment fonctionne un analyseur HTML ? N'utilise-t-il pas des expressions régulières pour analyser ?

Un argument particulier en faveur de l'utilisation d'une expression régulière est qu'il n'y a pas toujours une alternative d'analyse (comme en JavaScript, où DOMDocument n'est pas une option universellement disponible). jQuery, par exemple, semble se débrouiller très bien en utilisant une expression régulière pour convertir une chaîne HTML en nœuds DOM.

Je ne sais pas s'il faut ou non faire un CW, c'est une question sincère à laquelle je veux une réponse et qui n'est pas vraiment destinée à être un fil de discussion.

Answer 1

Comment fonctionne un analyseur HTML ? N'utilise-t-il pas des expressions régulières pour analyser ?

Eh bien, non.

Si vous vous remémorez un cours de théorie du calcul, si vous en avez suivi un, ou un cours sur les compilateurs, ou quelque chose de similaire, vous vous souviendrez peut-être qu'il existe différents types de langages et de modèles informatiques. Je ne suis pas qualifié pour entrer dans tous les détails, mais je peux passer en revue avec vous quelques-uns des principaux points.

Le type de langage et de calcul le plus simple (à ces fins) est un langage régulier. Ceux-ci peuvent être générés avec des expressions régulières, et reconnus avec des automates finis. Fondamentalement, cela signifie que l'"analyse" des chaînes de caractères dans ces langages utilise un état, mais pas de mémoire auxiliaire. Le HTML n'est certainement pas un langage régulier. Si vous y réfléchissez, la liste des balises peut être imbriquée de manière arbitraire et profonde. Par exemple, les tableaux peuvent contenir des tableaux, et chaque tableau peut contenir de nombreuses balises imbriquées. Avec les expressions régulières, vous pouvez être en mesure de repérer une paire de balises, mais certainement pas quelque chose d'arbitrairement imbriqué.

Un langage simple classique qui n'est pas régulier est celui des parenthèses correctement appariées. Vous aurez beau essayer, vous ne serez jamais en mesure de construire une expression régulière (ou un automate fini) qui fonctionnera toujours. Vous avez besoin de mémoire pour garder la trace de la profondeur d'imbrication.

Une machine à états avec une pile pour la mémoire est la force suivante du modèle de calcul. On l'appelle un automate poussé vers le bas, et il reconnaît les langages générés par des grammaires sans contexte. Ici, nous pouvons reconnaître les parenthèses correctement appariées - en fait, une pile est le modèle de mémoire parfait pour cela.

C'est assez bon pour le HTML ? Malheureusement, non. Peut-être pour le XML validé avec un soin extrême, dans lequel toutes les balises sont toujours parfaitement alignées. Dans le monde réel du HTML, vous pouvez facilement trouver des extraits tels que <b><i>wow!</b></i> . Il est évident que cela ne s'emboîte pas, donc pour l'analyser correctement, une pile n'est pas assez puissante.

Le niveau de calcul suivant est celui des langages générés par des grammaires générales, et reconnus par des machines de Turing. Il est généralement admis qu'il s'agit du modèle de calcul le plus puissant qui soit - une machine à états, avec une mémoire auxiliaire, dont la mémoire peut être modifiée partout. C'est ce que peuvent faire les langages de programmation. C'est le niveau de complexité où se situe le HTML.

Pour résumer tout cela en une phrase : pour analyser le HTML général, il faut un vrai langage de programmation, pas une expression régulière.

Le HTML est analysé de la même manière que les autres langues : par lexie et analyse syntaxique. L'étape de lexie décompose le flux de caractères individuels en jetons significatifs. L'étape d'analyse syntaxique assemble les tokens, en utilisant des états et de la mémoire, en un document logiquement cohérent sur lequel on peut agir.

Answer 2

Généralement en utilisant un tokeniser. Le projet La spécification HTML5 comporte un algorithme étendu pour traiter le "vrai monde HTML".

Answer 3

Les expressions régulières ne sont qu'une forme d'analyseur syntaxique. Un analyseur HTML honnête sera beaucoup plus compliqué que ce qui peut être exprimé par des expressions régulières, en utilisant les éléments suivants descente récursive , la prédiction, et plusieurs autres techniques pour interpréter correctement le texte. Si vous voulez vraiment vous plonger dans le sujet, vous pouvez consulter les sites suivants lex & yacc et d'autres outils similaires.

L'interdiction d'utiliser des regex pour l'analyse HTML devrait probablement être écrite plus correctement comme : "N'utilisez pas naïf expressions régulières pour analyser le HTML..." (de peur que vous ne ressentiez la colère) "...et traiter les résultats avec prudence." Pour certains objectifs spécifiques, une regex peut parfaitement convenir, mais vous devez faire très attention aux limites de votre regex et être aussi prudent que possible en fonction de la source du texte que vous analysez (par exemple, s'il s'agit d'une entrée utilisateur, soyez très prudent).

Answer 4

L'analyse syntaxique du HTML est la transformation d'un texte linéaire en une structure arborescente. Les expressions régulières ne peuvent généralement pas gérer les structures arborescentes. L'expression régulière dont vous avez besoin à chaque point pour obtenir le jeton suivant change tout le temps. Vous pouvez utiliser des expressions régulières dans un analyseur syntaxique, mais vous aurez besoin d'un tableau complet d'expressions régulières pour chaque état possible de l'analyse syntaxique.

Answer 5

Si vous voulez avoir une solution à 100% : Vous devez écrire votre propre code personnalisé qui itère à travers le HTML caractère par caractère et vous devez avoir une quantité énorme de logique pour déterminer si vous devez arrêter le nœud actuel et commencer le suivant.

La raison en est que c'est du HTML valide :

<ul>
<li>One
<li>Two
<li>Three
</ul>

Mais ça aussi :

<ul>
<li>One</li>
<li>Two</li>
<li>Three</li>
</ul>

Si vous êtes d'accord avec la "solution à 90%" : Alors utiliser un parseur XML pour charger un document est bien. Ou utiliser Regex (bien que le xml soit plus facile si vous êtes alors maître du contenu).