Algorithme du tokenizer HTML

Question

J'essaie d'écrire un analyseur html de base qui ne tolère pas les erreurs et j'ai lu l'algorithme d'analyse HTML5 mais c'est juste trop d'informations pour un simple analyseur. Je me demandais si quelqu'un avait une idée de la logique d'un tokenizer de base qui transformerait simplement un petit html en une liste de tokens significatifs. Je suis plus intéressé par la logique que par le code

std::string html = "<div id='test'> Hello <span>World</span></div>";

Tokenizer t;
t.tokenize(html);

Donc pour le html ci-dessus, je veux le convertir en une liste de quelque chose comme ceci :

["<","div","id", "=", "test", ">", "Hello", "<", "span", ">", "world", "</", "span", ">", "<", "div", ">"]

Je n'ai rien pour la méthode tokenize mais je me demandais si itérer sur le html caractère par caractère est la meilleure façon de construire la liste

void Tokenizer::tokenize(std::string html){
    std::list<std::string> tokens;

    for(int i = 0; i < html.length();i++){
        char c = html[i];
        if(...){
            ...
        }
    }
}

Answer 1

Je pense que ce que vous cherchez est un analyseur lexical . Son but est d'obtenir tous les tokens qui sont définis dans votre langage, dans ce cas le HTML. Comme l'a dit @IraBaxter, vous pouvez utiliser un outil lexical, tel que Lex qui est fondée en Linux o OSX mais vous devez définir la règle et, pour cela, vous devez utiliser des expressions régulières.

Mais, si vous voulez connaître un algorithme pour cette question, vous pouvez consulter le livre de Keith D. Cooper et Linda Torczon , chapitre 2, Scanners . Ce chapitre traite des Automates et de la façon dont ils peuvent être utilisés pour créer un Scanner où il utilise une Scanner sur table pour obtenir des jetons, comme vous le souhaitez. Laissez-moi vous montrer une image de ce chapitre :

L'idée est que vous définissez un DFAE où vous avez :

• Un ensemble fini d'états dans la machine de reconnaissance, y compris état de départ , États acceptants y état d'erreur .
• Un Alfabet.
• Une fonction qui permet de déterminer si une transition est valide ou non, en utilisant la table des transitions ou, si vous ne voulez pas utiliser une table, en codant les automates.

Prenez le temps d'étudier ce chapitre.

Answer 2

Les autres réponses sont excellentes, et vous devez absolument utiliser un générateur d'analyseurs lexicaux tel que flex pour le travail. L'entrée d'un tel générateur est une liste de règles qui identifient les différents types de jetons. Un fichier d'entrée peut ressembler à ceci :

WHITE_SPACE    \s*
IDENTIFIER     [a-zA-Z0-9_]+
LEFT_ANGLE     <

L'algorithme que flex utilise est essentiellement :

• Trouvez la règle qui correspond au plus grand nombre de textes.
• Si deux règles correspondent à la même longueur de texte, choisissez celle qui apparaît le plus tôt dans la liste des règles fournies.

Vous pourriez écrire vous-même cet algorithme assez facilement en utilisant des expressions régulières. Cependant, n'oubliez pas que cela ne sera pas aussi rapide que flex, puisque flex compile les expressions régulières en un DFA très rapide.