HTML Parsing with JavaScript

• Long ago, browser vendors made the choice that browsers would not display error messages when given malformed HTML, but instead attempt to display the malformed input in some reasonable way. For web compatibility, all browsers today must do that. XHTML was a attempt at imposing a strict syntax on the web, and it failed.
• So for web compatibility, browsers must all parse HTML liberally and accept malformed input. And for web interoperability, browsers must all parse malformed HTML in the same way.
• The HTML parsing specification is long and complicated. This is because in addition to specifying exactly how to parse valid HTML inputs, it also specifies exactly how to parse all possible invalid inputs. A standardized parsing algorithm is, in fact, one of the most important (but least appreciated) features of HTML 5 and represents a huge amount of work by Ian Hickson.
• The HTML spec defines the parser in terms of a tokenizer stage and a tree builder stage. And both stages are defined as state machines (which you may remember from undergrad CS classes). The prose description of a state machine is verbose, but the translation to JavaScript code is fairly mechanical (in fact, I wrote a simple script to help me translate most of the tokenizer state machine from HTML prose to JavaScript code).
• The advantage of a state machine specification is that it can account for every possible input. What happens, for example, when the tokenizer sees <a href=>, for example, or reaches the end-of-file while in the middle of a comment? Since the tokenizer is specified as a state machine unexpected inputs like these are just state transitions and have a well-defined behavior.
• The flip side is that by specifying the HTML parser in terms of state machines, the HTML spec never explicitly says how the parser is supposed to behave when it is given <a href=> or other malformed input. The behavior is implicit in the transitions of the state machine, but to figure out what the parser does for any given input, you have to read through the spec, simulating the state machines in your head. There is not a formal grammar like you'd see when reading a programming language specification, just an algorithmic description of how the parser behaves.
• The HTML specification includes specific instructions on how to handle the </sarcasm> end tag. I think its a joke, though, since the instructions say to treat it like any other end tag. :-)
• The HTML specification integrates the SVG and MathML grammars, and as part of that, HTML adopts all the named character entities (things like &lt; and &quot;) of MathML. There are now 2125 named character references you can use, including &CounterClockwiseContourIntegral; and &InvisibleComma;!
• An HTML parser implementation cannot be separated from the HTML and DOM implementation of which it is a part. I had always assumed that an HTML parser could be written generically to build up a DOM parse tree using public DOM APIs like document.createElement() and Element.appendChild(). It turns out that there are a number of places where the parser must manipulate DOM nodes in ways that are not possible with the public API. These include setting the compatMode property of the Document object and setting the form property of HTML form elements like input fields and buttons.
• There is a really nice HTML parsing test suite (the tokenizer and tree-construction directories are the most important ones) and I gather that the major browser vendors all use it. Strangely, the documentation for using the test data is at a completely different site.

It took me a couple of weeks, but I learned a lot about HTML parsing and ended up with a working parser! The source code weighs in at over a quarter megabyte and 6300 sloc. (Though to be fair, I should note that the object literal that holds those 2125 named character references takes up over 1000 of those lines of code.) It passes the tokenizer and tree construction tests mentioned above, and it can parse the HTML specification (over 6 megabytes of HTML) in under 8 seconds.

If I can brag a bit, this 8 second speed easily beats the two other JavaScript-based HTML parsers that I know of. The Node-based parser at https://github.com/aredridel/html5 displays some kind of quadratic behavior (doubling the size of the HTML to be parsed quadruples the parsing time) and as far as I can tell (I gave up after 5 minutes or so) it is just not capable of parsing the HTML spec, at least not when used with the Node-based DOM library at https://github.com/tmpvar/jsdom.

The other JavaScript HTML parser I know about is the Validator.nu parser by my Mozilla colleague Henri Sivonen. This is a Java-based parser, but it includes a custom Java-to-C++ translator, and when translated to C++, it is used as Firefox's HTML parser. The same codebase can be translated to JavaScript using Google's GWT parser, but the result is not terribly efficient. Parsing the HTML specification takes 18 to 20 seconds with the GWT version of Henri's parser. (I thought seriously about modifying Henri's Java-to-C++ translator to output JavaScript instead of C++, but in the end, I decided that it would take a similar amount of time and would be more fun and educational to just write my parser from scratch.)

If you've read this far, here is where I confess that my parser isn't even done yet. It does not yet execute scripts, which means that it doesn't handle document.write() calls. That's next on my list, but its kind of scary. You'd think that executing a script in a JavaScript-based parser would just amount to an eval() call. But there's a lot more to it than that. Another colleague of mine described these sections of the spec as "brain-meltingly" complex. We'll see. I'm keeping my fingers crossed that none of the strange cases where document.write() inserts new scripts require me to refactor the parsing code in major ways!