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

96

Je vois des questions tous les jours 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, de peur de ressentir la colère!" (cette dernière partie est parfois omise).

C'est assez déroutant pour moi, j'ai toujours pensé qu'en général, la meilleure façon d'analyser une chaîne compliquée est 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 pour l'utilisation d'une expression régulière est qu'il n'y a pas toujours d'alternative à l'analyse (comme JavaScript, où DOMDocument n'est pas une option disponible universellement). jQuery, par exemple, semble bien gérer l'utilisation d'une expression régulière pour convertir une chaîne HTML en nœuds DOM.

Je ne sais pas si oui ou non CW ceci, c'est une vraie question à laquelle je veux une réponse et pas vraiment destinée à être un fil de discussion.

Andy E
la source
Redéfini pour ajouter l'analyse et l'analyse html - @Andy E, j'espère que vous êtes d'accord - j'ai pensé que ce serait utile.
JXG
@JXG: Ça me va, merci :-)
Andy E

Réponses:

65

Généralement en utilisant un tokeniser. Le projet de spécification HTML5 a un algorithme complet pour gérer le "HTML du monde réel".

Quentin
la source
1
Bonne trouvaille ... pour citer "Pour gérer ces cas, les analyseurs ont un niveau d'imbrication de script, qui doit être initialement défini sur zéro, et un indicateur de pause de l'analyseur, qui doit être initialement défini sur false." - En d'autres termes, vous devez l'itérer vous-même et avoir beaucoup de logique personnalisée: P
Timothy Khouri
1
Vote positif. Il vaut mieux mettre l'accent sur la complexité algorithmique plutôt que sur certaines technologies.
Arnis Lapsa
1
Itérer vous-même avec beaucoup de logique personnalisée n'est pas une si bonne idée. Utilisez une bibliothèque prenant en charge l'algorithme standard si vous le pouvez. par exemple, search.cpan.org/~tobyink/HTML-HTML5-Parser-0.03/lib/HTML/HTML5/… / code.google.com/p/html5lib
Quentin
8
Le principal problème avec les analyseurs HTML est que lorsque vous rencontrez une erreur, vous ne pouvez pas cracher "Parse error" et en rester là. Vous entrez en mode bizarreries et essayez de distinguer au mieux le désordre que vous avez rencontré, y compris les balises incompatibles, les entrelacs de style [{]} et toutes sortes de bizarreries, en essayant de rendre le résultat aussi beau que possible et l'inévitable l'échec le moins douloureux ... ce n'est pas quelque chose que vous pouvez faire avec les regex.
SF.
7
@Timothy K: 'Remarque: en raison de la façon dont cet algorithme fait changer les parents des éléments, il a été surnommé "algorithme d'agence d'adoption" (contrairement à d'autres algorithmes possibles pour traiter le contenu mal imbriqué, qui incluait "l'algorithme d'inceste", «l'algorithme de l'affaire secrète» et «l'algorithme de Heisenberg»).
JXG
133

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

Et bien non.

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

Le type le plus simple de langage et de calcul (à 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 les chaînes "d'analyse" dans ces langages utilisent l'état, mais pas la mémoire auxiliaire. Le HTML n'est certainement pas un langage courant. Si vous y réfléchissez, la liste des balises peut être imbriquée de manière arbitraire profondément. Par exemple, les tables peuvent contenir des tables et chaque table peut contenir de nombreuses balises imbriquées. Avec les expressions régulières, vous pourrez peut-être choisir une paire de balises, mais certainement rien imbriqué de manière arbitraire.

Un langage simple classique qui n'est pas régulier est correctement mis en correspondance entre parenthèses. Essayez comme vous le pouvez, vous ne pourrez jamais construire une expression régulière (ou un automate fini) qui fonctionnera toujours. Vous avez besoin de mémoire pour suivre la profondeur d'imbrication.

Une machine à états avec une pile pour la mémoire est la prochaine force du modèle de calcul. C'est ce qu'on appelle un automate push-down, 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 effet, une pile est le modèle de mémoire parfait pour cela.

Eh bien, est-ce suffisant pour HTML? Malheureusement non. Peut-être pour le super-duper soigneusement validé XML, en fait, dans lequel toutes les balises s'alignent toujours parfaitement. Dans le HTML réel, vous pouvez facilement trouver des extraits comme <b><i>wow!</b></i>. Cela ne s'imbrique évidemment pas, donc pour l'analyser correctement, une pile n'est tout simplement pas assez puissante.

Le prochain niveau de calcul est constitué des langages générés par des grammaires générales et reconnus par les machines de Turing. Il est généralement admis que c'est effectivement le modèle de calcul le plus puissant qui soit - une machine à états, avec mémoire auxiliaire, dont la mémoire peut être modifiée n'importe où. C'est ce que peuvent faire les langages de programmation. C'est le niveau de complexité où vit le HTML.

Pour résumer tout ici en une phrase: pour analyser le HTML général, vous avez besoin d'un vrai langage de programmation, pas d'une expression régulière.

Le HTML est analysé de la même manière que les autres langages: le lexing et l'analyse. L'étape de lexing décompose le flux de personnages individuels en jetons significatifs. L'étape d'analyse assemble les jetons, à l'aide d'états et de mémoire, dans un document logiquement cohérent sur lequel il est possible d'agir.

JXG
la source
22

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

L'interdiction d'utiliser des expressions régulières pour l'analyse HTML devrait probablement être écrite plus correctement comme: "N'utilisez pas d' expressions régulières naïves pour analyser le HTML ..." (de peur que vous ne ressentiez la colère) "... et traitez les résultats avec prudence." Pour certains objectifs spécifiques, une expression régulière peut très bien être parfaitement adéquate, mais vous devez être très prudent pour être conscient des limites de votre expression régulière et aussi prudent que cela est approprié à la source du texte que vous analysez (par exemple, si c'est entrée utilisateur, soyez très prudent en effet).

TJ Crowder
la source
+1, une bonne réponse. Je dois admettre que j'ai déjà utilisé des expressions rationnelles même lorsque je ne contrôlais pas le HTML, mais pas dans aucune sorte d'application publiée publiquement. J'ai aussi «ressenti la colère», parce que c'était naïf. Mais c'était il y a longtemps :-)
Andy E
6

L'analyse 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 prochain jeton change tout le temps. Vous pouvez utiliser des expressions régulières dans un analyseur, mais vous aurez besoin de tout un tableau d'expressions régulières pour chaque état d'analyse possible.

Svante
la source
2

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

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

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

Mais tel est le cas:

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

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

Timothy Khouri
la source
4
Un analyseur XML ressemble plus à une solution à 1%. Le nombre de documents HTML qui sont bien formés XML est minime.
Quentin
4
Oui, ils le font ... ne prenez pas «caractère par caractère» à la lettre, car vous pouvez essayer de diffuser des choses. Mais ce que je veux dire, c'est que vous devez écrire votre propre analyseur. Les programmeurs novices ne sont pas habitués à écrire ce genre de code ... nous sommes habitués à "HtmlDocumentUtility.Load" et des trucs comme ça :)
Timothy Khouri
4
@Andy E: Les expressions régulières ne sont pas magiques, elles fonctionnent également caractère par caractère, comme tout autre type d'analyse, ou diable, toute autre fonction de chaîne.
Bart van Heukelom
1
BTW: Votre premier exemple n'est pas simplement "HTML semi-valide". C'est en fait valide HTML 4.01 Strict. Vous pouvez utiliser par exemple le validateur W3C pour vérifier cela. La balise de fermeture est officiellement facultative pour <li> (voir la spécification HTML 4).
sleske
2
@Bart: bon point, parfois mon cerveau oublie toute logique et pense que les choses fonctionnent par magie.
Andy E