Fast and Compact HTML/XML Scanner/Tokenizer

c-smile

Rate me:

4.90/5 (31 votes)

10 Oct 2007BSD2 min read

552.7K

HTML/XML scanner/tokenizer, also known as a pull parser

Download source files - 7.6 KB

Introduction

The proposed code is an implementation of an HTML and XML scanner (or tokenizer). Imagine that you have some XML or HTML text and you just need to find some word, tag or attribute in it. For such trivial tasks, the use of a full-blown "DOM compiler" or SAX alike parser is too much. It is enough to use the markup::scanner described below. Features of markup::scanner include:

It does not allocate any memory while scanning, at all.
It is written in pure C++ and does not require STL or any other toolkit/library.
It is fast. We managed to reach a speed of scanning nearly 40 MB of XML per second (depends on the hardware you have, of course).
It is simple.

How to Use

I think the best way to explain is to show an example. First, we need to declare the input stream for the scanner. Here is an example of a simple string-based stream:

C++

struct str_istream: public markup::instream
{
    const char* p;
    const char* end; 
    str_istream(const char* src): p(src), end(src + strlen(src)) {}
    virtual wchar_t get_char() { return p < end? *p++: 0; }
};

This is all that we need in order to write the program which will, let's say, print out all of the tokens in the input HTML:

C++

int main(int argc, char* argv[])
{
    str_istream si("<html><body><p align=right" 
        " dir='rtl'> Begin &amp; back </p>" "</body></html>");
    markup::scanner sc(si);
    bool in_text = false;
    while(true)
    {
        int t = sc.get_token();
        switch(t)
        {
            case markup::scanner::TT_ERROR:
                printf("ERROR\n");
                break;
            case markup::scanner::TT_EOF:
                printf("EOF\n");
                goto FINISH;
            case markup::scanner::TT_TAG_START:
                printf("TAG START:%s\n", sc.get_tag_name());
                break;
            case markup::scanner::TT_TAG_END:
                printf("TAG END:%s\n", sc.get_tag_name());
                break;
            case markup::scanner::TT_ATTR:
                printf("\tATTR:%s=%S\n", sc.get_attr_name(), sc.get_value());
                break;
            case markup::scanner::TT_WORD: 
                case markup::scanner::TT_SPACE:
                    printf("{%S}\n", sc.get_value());
                    break;
        }
    }
    FINISH:
        printf("--------------------------\n");
        return 0;
}

As you may see, the main method doing the job here is markup::scanner::get_token(). It scans the input stream and returns the value of markup::scanner::token_type.

C++

enum token_type 
{
    TT_ERROR = -1,
    TT_EOF = 0,

    TT_TAG_START,   // <tag ...
                    //     ^-- happens here
    TT_TAG_END,     // </tag>
                    //       ^-- happens here 
                    // <tag ... />
                    //            ^-- or here 
    TT_ATTR,        // <tag attr="value" >      
                    //                  ^-- happens here   
    TT_WORD,
    TT_SPACE,

    TT_DATA,        // content of following:

    TT_COMMENT_START, TT_COMMENT_END, // after "<!--" and "-->"
    TT_CDATA_START, TT_CDATA_END,     // after "<![CDATA[" and "]]>"
    TT_PI_START, TT_PI_END,           // after "<?" and "?>"
    TT_ENTITY_START, TT_ENTITY_END,   // after "<!ENTITY" and ">"
  
};

According to the value of the token, you can use get_tag_name(), get_value() or get_attr_name() to retrieve the needed information. This is pretty much all you need in order to be able to scan HTML/XML..

In Closing

The given scanner does not address any input stream encoding problems. XML and HTML are dealt with differently with this. A general idea for the cases where you don't know the input encoding up front: your input stream should be smart enough to be able to switch the encoding of the input on the fly. The given scanner was initially created as part of the HTMLayout SDK: a lightweight embeddable HTML rendering component.

History

11 May 2006 - Initial version
12 May 2006 - Article moved
09 June 2006 - Bug fixes and a new VS 2005 project
10 October 2007 - Download updated (bug fixes)

License

This article, along with any associated source code and files, is licensed under The BSD License

Written By

c-smile

Founder Terra Informatica Software

Canada

Andrew Fedoniouk.

MS in Physics and Applied Mathematics.
Designing software applications and systems since 1991.

W3C HTML5 Working Group, Invited Expert.

Terra Informatica Software, Inc.
http://terrainformatica.com

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.