Fast and Compact HTML/XML Scanner/Tokenizer

17:42 11 Sep '08

Here is what can be used for utf8 input stream implementation.

bytes here is simple struct

struct bytes 
{ 
  byte* start;
  uint  length;
}

Function wchar getc_utf8(const bytes& buf, int& pos) does the job of converting input sequence of bytes into single UCS-2 (16bit) codepoint - basic multilingual plane subset of big UNICODE.

inline uint get_next_utf8(unsigned int val)
{
  // Check for the correct bits at the start.
  assert((val & 0xc0) == 0x80);
  //bad continuation of multi-byte UTF-8 sequence
  // Return the significant bits.
  return (val & 0x3f);
}

inline unsigned int getb(const bytes& buf, int& pos) 
{
  if( uint(pos) >= buf.length )
    return 0;
  return buf[pos++];
}

// ATTN: UCS-2 only!
wchar getc_utf8(const bytes& buf, int& pos)
{
    unsigned int b1;
    bool isSurrogate = false;

    b1 = getb(buf,pos);
    if(!b1)
      return 0;
    isSurrogate = false;

    // Determine whether we are dealing
    // with a one-, two-, three-, or four-
    // byte sequence.
    if ((b1 & 0x80) == 0) 
    {
	    // 1-byte sequence: 000000000xxxxxxx = 0xxxxxxx
	    return (wchar)b1;
    } 
    else if ((b1 & 0xe0) == 0xc0) 
    {
	    // 2-byte sequence: 00000yyyyyxxxxxx = 110yyyyy 10xxxxxx
	    uint r = (b1 & 0x1f) << 6;
           r |= get_next_utf8(getb(buf,pos));
      return (wchar)r; 
    } 
    else if ((b1 & 0xf0) == 0xe0) 
    {
	    // 3-byte sequence: zzzzyyyyyyxxxxxx = 1110zzzz 10yyyyyy 10xxxxxx
      uint r = (b1 & 0x0f) << 12;
           r |= get_next_utf8(getb(buf,pos)) << 6;
           r |= get_next_utf8(getb(buf,pos));
      return (wchar)r;
    } 
    else if ((b1 & 0xf8) == 0xf0) 
    {
	    // 4-byte sequence: 11101110wwwwzzzzyy + 110111yyyyxxxxxx
	    //     = 11110uuu 10uuzzzz 10yyyyyy 10xxxxxx
	    // (uuuuu = wwww + 1)
	    isSurrogate = true;
           return L'?';
      /*
	    int b2 = get_next_utf8(pc++);
	    int b3 = get_next_utf8(pc++);
	    int b4 = get_next_utf8(pc++);
	    buf += 
	      (wchar)(0xd800 |
		     ((((b1 & 0x07) << 2) | ((b2 & 0x30) >> 4) - 1) << 6) |
		     ((b2 & 0x0f) << 2) |
		     ((b3 & 0x30) >> 4));
	    buf +=
	      (wchar)(0xdc | ((b3 & 0x0f) << 6) | b4);
				    // TODO: test that surrogate value is legal.
      */
    } 
    else 
    {
      assert(0);
      return L'?';
      //bad start for UTF-8 multi-byte sequence"
    }
}

UCS-2 strings are used by Windows (so called LPCWSTR) prior XP. In Windows XP LPCWSTR is UTF-16 string.
Welcome to UTFs! Smile

Encoding advise

_Stilgar_

7:12 13 Dec '07

Hi,

This is the code I'm using in the sample app:

struct ascii_file_istream : public markup::instream
{
	FILE *f;
	unsigned int pos;
	ascii_file_istream(const char* filename) : pos(0), f(NULL) { f = fopen(filename, "rb"); }
	virtual wchar_t get_char() { wchar_t c; pos++; return fread(&c,sizeof(wchar_t),1,f)? c : 0; }
	~ascii_file_istream() { fclose(f); }
	bool is_file() { return (!(f==NULL)); }
};

int main(int argc, char* argv[])
{
  ascii_file_istream fi("c:\\testfile.htm");

  if (!fi.is_file())
	  return 0;

  markup::scanner sc(fi);
  bool in_text = false;
  while(true)
  {
    int t = sc.get_token();
    switch(t)
    {
      case markup::scanner::TT_EOF:
        printf("EOF\n");
        goto FINISH;
      case markup::scanner::TT_SPACE:
	printf("SPACE\n");
	break;
      case markup::scanner::TT_WORD:
	{
	  const markup::wchar* w = sc.get_value();
	  printf("WORD: {%S}\n", sc.get_value());
	}
        break;
      // The rest of the cases
      // ...
  }
FINISH:
  printf("--------------------------\n");
  return 0;
}

This code works perfectly well when used to scan English documents. It is not working when I'm using it to scan documents with non-english words. The only way I could make it work is by setting the default charset to Unicode in the project properties, re-saving the file as Unicode with Notepad (UTF8 didn't work to, only Unicode), only then would w in the TT_WORD case got the correct value and not a set of squares. Also note I'm reading wchar_t from the file, not char as you suggested in the original code you posted a while ago. I never got printf (nor wprintf) to output the correct chars to the screen, even when the word was read allright.

My question is that: how can I read the non-english file correctly also when it is saved as UTF8 or ANSI? does the scanner itself aware of those characters, or does it just ignore them so once I'm calling sc.get_value() I can convert it to whatever encoding I need and it will display it fine?
Also, can I still read the file with your code:
virtual wchar_t get_char() { char c; pos++; return fread(&c,1,1,f)? c : 0; }
and still read the non-english words correctly?
The best practice would be for the reader to be indepndant of the file encoding. Is that possible?

Please advise.

Stilgar.

Re: Encoding advise

12:56 15 Jan '09

Here is what I use for parsing UTF8 encoded streams:

  class mem_utf8_istream: public markup::instream 
  {
    bytes buf;
    int   pos;
  public:
    mem_istream(bytes text) : buf(text), pos(0) { }
    virtual wchar_t get_char() { return getc_utf8(buf, pos); } 
  };

Where getc_utf8 is this:

inline uint get_next_utf8(unsigned int val)
{
  // Check for the correct bits at the start.
  assert((val & 0xc0) == 0x80);
  //bad continuation of multi-byte UTF-8 sequence
  // Return the significant bits.
  return (val & 0x3f);
}

inline unsigned int getb(const bytes& buf, int& pos)
{
  if( uint(pos) >= buf.length )
    return 0;
  return buf[pos++];
}

// ATTN: UCS-2 only!
wchar getc_utf8(const bytes& buf, int& pos)
{
    unsigned int b1;
    bool is_surrogate = false;

    b1 = getb(buf,pos);
    if(!b1)
      return 0;

    // Determine whether we are dealing
    // with a one-, two-, three-, or four-
    // byte sequence.
    if ((b1 & 0x80) == 0)
    {
      // 1-byte sequence: 000000000xxxxxxx = 0xxxxxxx
      return (wchar)b1;
    }
    else if ((b1 & 0xe0) == 0xc0)
    {
      // 2-byte sequence: 00000yyyyyxxxxxx = 110yyyyy 10xxxxxx
      uint r = (b1 & 0x1f) << 6;
           r |= get_next_utf8(getb(buf,pos));
      return (wchar)r;
    }
    else if ((b1 & 0xf0) == 0xe0)
    {
      // 3-byte sequence: zzzzyyyyyyxxxxxx = 1110zzzz 10yyyyyy 10xxxxxx
      uint r = (b1 & 0x0f) << 12;
           r |= get_next_utf8(getb(buf,pos)) << 6;
           r |= get_next_utf8(getb(buf,pos));
      return (wchar)r;
    }
    else if ((b1 & 0xf8) == 0xf0)
    {
      // 4-byte sequence: 11101110wwwwzzzzyy + 110111yyyyxxxxxx
      //     = 11110uuu 10uuzzzz 10yyyyyy 10xxxxxx
      // (uuuuu = wwww + 1)
      is_surrogate = true;
      return L'?';
      /*
      int b2 = get_next_utf8(pc++);
      int b3 = get_next_utf8(pc++);
      int b4 = get_next_utf8(pc++);
      buf +=
        (wchar)(0xd800 |
         ((((b1 & 0x07) << 2) | ((b2 & 0x30) >> 4) - 1) << 6) |
         ((b2 & 0x0f) << 2) |
         ((b3 & 0x30) >> 4));
      buf +=
        (wchar)(0xdc | ((b3 & 0x0f) << 6) | b4);
            // TODO: test that surrogate value is legal.
      */
    }
    else
    {
      assert(0);
      return L'?';
      //bad start for UTF-8 multi-byte sequence"
    }
}

Thoughts on DOCTYPE ...

7:00 4 Nov '07

This fragment causes problems:

<?xml version="1.0" encoding="utf-8"?>

<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20000303 Stylable//EN"   "http://www.w3.org/TR/2000/03/WD-SVG-20000303/DTD/svg-20000303-stylable.dtd" [
     <!ENTITY st0 "fill:#E61408;">
     <!ENTITY st1 "fill:#1C1585;">
]>

This is parsed as:

TAG START: ?xml
TT_ATTR: version 1.0
TT_ATTR: encoding utf-8
TT_ATTR: ?
TT_DATA: ?   Generator: Adobe Illustrator 9.0, SVG Export Plug-In
TAG START: !DOCTYPE
TT_ATTR: svg
TT_ATTR: PUBLIC
TT_ATTR: "-//W3C//DTD
TT_ATTR: SVG
TT_ATTR: 20000303
TT_ATTR: Stylable//EN"
TT_ATTR: "http://www.w3.org/TR/2000/03/WD-SVG-20000303/DTD/svg-20000303-stylable.dtd"
TT_ATTR: [
TT_ATTR: !ENTITY
TT_ATTR: st0
TT_ATTR: "fill:#E61408;"
TT_ENTITY_START: !ENTITY
TT_DATA: "fill:#E61408;" st1 "fill:#1C1585;"
TT_ENTITY_END: !ENTITY

Any thoughts on the best way to integrate fix? Perhaps by having a dedicated scan_doctype() ?

TIA

Jerry

10:39 4 Nov '07

Thanks for that, I've updated distribution at:
http://www.terrainformatica.com/org/xh_scanner_demo.zip

Scanning loop looks like this now:

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;
      case markup::scanner::TT_PI_START:
        printf("\tPI");
        break;
      case markup::scanner::TT_PI_END:
        printf("\n");
        break;
      case markup::scanner::TT_DOCTYPE_START:
        printf("\tDOCTYPE");
        break;
      case markup::scanner::TT_DOCTYPE_END:
        printf("\n");
        break;
      case markup::scanner::TT_DATA:
        printf("[%S]", sc.get_value());
        break;
    }

14:54 4 Nov '07

Andrew, that is very helpful but there is still a problem recognising the first entity in the DOCTYPE section. The output below is from parsing the original doctype example. TT_DOCTYPE_START TT_DATA: svg PUBLIC "-//W3C//DTD SVG 20000303 Stylable//EN" "http://www.w3.org/TR/2000/03/WD-SVG-20000303/DTD/svg-20000303-stylable.dtd" [ <!ENTITY st0 "fill:#E61408;" (Implied)TT_DOCTYPE_END
Sign In·View Thread·PermaLink

17:32 4 Nov '07

I see. I have updated sources again with the fix. Scanner is not trying to parse content of DOCTYPE - it just passes content "as is" to the caller. Thus scanner is not doing any DTD parsing. That is out of scope of the scanner anyway. If someone will want to implement such parsing/support - let me know.
Sign In·View Thread·PermaLink

2:24 5 Nov '07

Many thanks. For my purposes parsing the DTD is overkill but it is important to be ale to extract entity definitions correctly. This is an excellent tool for the job.
Sign In·View Thread·PermaLink

2:36 5 Nov '07

OK, the current method is fine as the entities in the doctype scope can be parsed separately. one trivial suggestion: For clarity: how about adding add TT_DOCTYPE_DATA enumeration which is returned by scanner::scan_doctype_decl()? this makes client code a tiny bit simpler and intent is clearer. Thanks again.
Sign In·View Thread·PermaLink

17:26 5 Nov '07

It returns now one or more TT_DATAs tokens.

In principle typical text->DOM parser should have something like this:

switch( token_stream.get_token() ) 
{
  case  TT_DOCTYPE_START:
    parse_DOCTYPE(token_stream);
    break;
  case  TT_COMMENT_START:
    ...
}

where parse_DOCTYPE() in its turn shall have inside:

while(1)
  switch( token_stream.get_token() ) 
{
  case  TT_ENTITY_DECL_START:
    parse_ENTITY_decl(token_stream);
    break;
  case  TT_ATTR_DECL_START:
    parse_ATTR_decl(token_stream);
    break;
  ...
}

But again this scanner was designed for cases when "linear" XML/HTML scanning is required. So DOCTYPE and local DTD parsing was out of scope.
Typical use ccase: HTML -> plain text converter.
Another example: we use customized version of the scanner for DOM-less SVG rendering in htmlayout/sciter.
It scans SVG (some subset of) and draws elements as they appear in the source. Without building SVG DOM.

I've commented out TT_ENTITY_DECL_START handling. It shall be enabled if someone will decide to build full parser.
Things like TT_ATTR_DECL_START can be added in the same way as TT_ENTITY_DECL_START.

Extremely useful.

13:21 12 Oct '07

Many thanks Andrew, you have enabled me to cross another task off my todo list. Gets my 5. Can you clarify licensing please? Thx++ Jerry.
Sign In·View Thread·PermaLink

Re: Extremely useful.

URL of latest source code

13:37 12 Oct '07

I am publishing all my stuff with BSD license. So is this one too has BSD license.
Sign In·View Thread·PermaLink

Re: nuther bug [modified]

22:18 7 Oct '07

http://www.terrainformatica.com/org/xh_scanner_demo.zip
Sign In·View Thread·PermaLink

nuther bug [modified]

dr3d

21:10 4 Jul '07

I've spotted what appears to be another problem with your very useful markup scanner.

Sometimes an attribute-value might be a quoted-url that includes a querystring:

<input value="http://mysite?foo&bar" type=hidden name=foobar>

The scanner sees the '&' and calls scan_entity(). That function will read up to 31 chars looking for the terminating ';'. When it doesn't find it, it simply appends those 31 chars to the value of the attribute. In the case above, that means the terminating '"' is passed over...

My solution is good enuf for my purpose but isn't perfect: I pass a delimiter to scan_entity() which it also checks-for when collecting chars into its buf[]. The for() loop winds up looking like:

...
      for(; i < 31 ; ++i )
      {
        t = get_char();
        if(t == 0) return TT_EOF;
        if (delim == ' ' && is_whitespace(t) || t == delim) {
            push_back(t);
            append_value('&');
            for(int n = 0; n < i-1; ++n)
               append_value(buf[n]);
            return buf[i-1];
        }
        buf[i] = char(t); 
        if(t == ';')
          break;
      }

the 4 calls to scan_entity() become

...
  scan_entity(0);
...
  scan_entity('"');
...
  scan_entity('\'');
...
  scan_entity(' ');

-scott

19:19 6 Oct '07

Thanks dr3d.

In fact fragment at xh_scanner.cpp (126),
needs to be fixed as this:

      else  // scan token, allowed in html: e.g. align=center
        do
        {
            if( is_whitespace(c) ) return TT_ATTR;
            /* these two removed in favour of better html support:
            if( c == '/' || c == '>' ) { push_back(c); return TT_ATTR; }
            if( c == '&' ) c = scan_entity();*/
            if( c == '>' ) { push_back(c); return TT_ATTR; }
            append_value(c);
        } while(c = get_char());

I also slightly updated scan_entity().

I've sent updates to codeproject people so these changes will appear soon in source.

Nested tags

Nulleh

19:10 28 Oct '06

Nice lightweight parser, thanks for sharing. I think I may have found a bug: if a nested tag begins and ends, get_tag_name() still returns that nested tag. For example: " Text bold text " For each word, the parser says that its tag is(respectively): "p b b b" This is incorrect, as it should output "p b b p" -Tyson
Sign In·View Thread·PermaLink

Re: Nested tags

Process information token

21:39 28 Oct '06

get_tag_name() returns actual value only for TT_TAG_START and TT_TAG_END tokens. Otherwise tokenizer shall maintain stack of elements. That require memory allocations - thing I was trying to avoid in scanner for many reasons.
Sign In·View Thread·PermaLink

Re: Nested tags

Nulleh

18:10 29 Oct '06

Thanks for the reply! I understand; the stack was easily implemented. I just wanted to bring this to your attention in the case that it was a bug[not really a bug, but a feature left out that you meant to put in]. The small memory footprint is fantastic, especially for the environment I am deploying this for. Thanks. -Tyson
Sign In·View Thread·PermaLink

Jacob Skjoet

7:29 27 Sep '06

Thank you for the contribution. It seems that the tokenizer never returns TT_PI_START/END. This means that eg <?xml version="1.0" encoding="iso-8859-1"?> is matched as a standard tag without a tag end. Is this a bug or just me missing something ? Jacob Skjøt
Sign In·View Thread·PermaLink

Re: Process information token

osocha

0:14 27 Oct '06

Hello!

I made simple work around:

1)

scanner::token_type scanner::scan_head()
    {
      wchar c = skip_whitespace();

      if(c == '>') { c_scan = &scanner::scan_body; return scan_body(); }
      if(c == '?') //***pi
      {
         wchar t = get_char();
         if(t == '>')   { c_scan = &scanner::scan_body; return TT_PI_END; }
         else { push_back(t); return TT_ERROR; } 
      }      
      if(c == '/')
.......

    scanner::token_type scanner::scan_tag() 
    {
.........
        switch(tag_name_length)
        {
        case 4: //***pi
        if(equal(tag_name,"?xml",4))  { 
			  c_scan = &scanner::scan_head; 
			  return TT_PI_START; }
        break;        
        case 3: 
...........

I don't use scan_pi() at all because it returns data as string, while my way uses scan_head() and returns attrib/value pairs.

This code works for me, but it was quit work around w/o in deep analysis!

It is written so simply (e.g. so good) that I converted it to C (not C++) code for my own purposes!

C-smile - it' really great job!!!

Greetings
Przemek

How to deal with this condition? [modified]

digitalpump

22:26 16 Jun '06

Hi. Usual we may come up against some HTML code like this "<a href=/script/profile/whos_who.asp?id=26162>Jack Hui</a> ". At here,The "/" symbol was treat with an end tag symbol in your code. But in fact that was an error judgement. do you think so? thanks. digitalpump. www.51qk.com -- modified at 3:26 Saturday 17th June, 2006
Sign In·View Thread·PermaLink

Re: How to deal with this condition? [modified]