HTML tokenizer algorithm

Question

I'm trying to write a basic html parser which doesn't tolerate errors and was reading HTML5 parsing algorithm but it's just too much information for a simple parser. I was wondering if someone had an idea on the logic for a basic tokenizer which would simply turn a small html into a list of significant tokens. I'm more of interested in the logic than the code..

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

Tokenizer t;
t.tokenize(html);

So for the above html, I want to convert it to a list of something like this:

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

I don't have anything for the tokenize method but was wondering if iterating over the html character by character is the best way to build the list..

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

I think what you are looking for is a lexical analyzer. Its goal is getting all the tokens that are defined in your language, in this case is HTML. As @IraBaxter said, you can use a Lexical tool, like Lex, that is founded in Linux or OSX; but you must define the rule and, for this, you need use Regular Expressions.

But, if you wan to know about an algorithm for this issue you can check the book of Keith D. Cooper & Linda Torczon, chapter 2, Scanners. This chapter talks about Automatas and who they can be used to create a Scanner where it use a Table-Driven Scanner to get tokens, like you want. Let me share you an image of this chapter:

The idea is that you define a DFA where you have:

• A finite set of states in the recognizer, including start state, accepting states and error state.
• An Alfabet.
• A function which helps to determine if a transition is valid or not, using the table of transitions or, if you don't want use a table, coding the automata.

Take a time to study this chapter.