How the HTML Tokenizer and Tree Builder Recover from Malformed Markup

A document containing <table><div>hello</div></table> does not produce a table with a div inside it. The div is moved in front of the table, the table is left empty, and the text survives. No error is reported to the page, no exception is thrown, and the resulting tree is identical in every browser that follows the specification. That determinism is the point: HTML is not parsed by a grammar that rejects invalid input, it is parsed by a state machine whose behaviour on invalid input was written down.

The alternative design, an XML-style parser that aborts on the first well-formedness error, was tried. XHTML shipped that model for documents served as application/xhtml+xml, and a single unescaped ampersand turns the document into a parse error page. HTML chose tolerance plus reproducibility instead, which required specifying what to do with every malformed sequence a parser could encounter. The specification therefore reads as a repair manual, and the repairs are mandatory.

Two machines connected by a token stream

Parsing is split into tokenization and tree construction. The tokenizer consumes a stream of Unicode code points and emits tokens: start tags with a name and an attribute list, end tags, character runs, comments, doctypes, and an end-of-file token. The tree builder consumes those tokens and mutates a document, maintaining a stack of open elements and a current insertion mode. The tokenizer knows nothing about nesting; the tree builder knows nothing about bytes.

The tokenizer is a state machine with dozens of named states. The Data state emits ordinary characters until it sees <, which moves to TagOpen. A following / moves to EndTagOpen, a letter moves to TagName, an exclamation mark moves to MarkupDeclarationOpen, and a question mark produces a comment rather than a processing instruction, because HTML has no processing instructions. Each state names the characters that move it elsewhere and the characters that are emitted or ignored in place. Whitespace inside a tag is handled by states such as BeforeAttributeName and AfterAttributeValueQuoted, which exist so that <div class = "a" > tokenizes the same as <div class="a">.

Three consequences of the tokenizer matter in ordinary code. First, attribute names are lowercased, so CLASS and class are the same attribute. Second, a duplicate attribute is dropped and the first occurrence wins, so <input value="a" value="b"> produces a value of a. Third, character references are resolved by longest match against a table of over two thousand named references; a reference that matches nothing is emitted as literal text. Ambiguity around & is resolved by that table rather than by a general rule, which is why &notit; behaves differently from ¬.

A “parse error” in the specification is a label attached to a tokenizer transition or tree-builder step. It is not an exception, it is not surfaced to script, and the algorithm continues. Some branches exist only to define behaviour for input no author should produce, such as a <! sequence that starts neither a comment nor a doctype.

Insertion modes and the stack of open elements

The tree builder tracks which construct it is inside using an insertion mode, and the HTML Standard defines 23 of them, including initial, before html, in head, after head, in body, text, in table, in table body, in row, in cell, in select, in template, and several terminal modes. A token is reprocessed against a new mode whenever a rule switches it, which is why the algorithm is written as a loop over one token at a time.

Every element that is open sits on a stack. Insertion of a new element normally appends it to the current node, which is the top of the stack. Some constructs override that with foster parenting: while the parser is in in table mode, a token that cannot be placed inside the table is inserted at the “appropriate place for inserting a node”, which for a table means immediately before the table element in its parent. That single rule explains the opening example. A <div> token in in table mode is a parse error and is fostered; the div and its text land before the table.

The stack also carries scope definitions. “Has an element in table scope” and “has an element in button scope” determine whether an end tag is allowed to close something further down the stack. This is what makes </p> well behaved when no paragraph is open: the parser inserts an empty p element and immediately closes it, rather than ignoring the tag or closing an ancestor.

The rules that close elements implicitly are the subject of Optional Tags and the Implied End Tag Rules. What matters here is that the tree builder, not the author, decides where a paragraph ends. A <p> start tag while another p is open closes the first one; a <li> start tag closes an open li at the same level; a block-level start tag closes an open p even when the author wrote no end tag at all.

The adoption agency algorithm

Misnested inline elements are the hardest repair. Consider:

<b>1<p>2</b>3</p>

A naive parser closes the paragraph when it meets </b>, leaving the 3 outside both. The specified result is different: the bold text is reopened inside the paragraph so that the character data keeps the formatting the author intended up to the point of the end tag, and the trailing 3 is plain.

<b>1</b>
<p><b>2</b>3</p>

The mechanism behind this is a list of active formatting elements alongside the stack of open elements. When a start tag for b, i, em, strong, a, nobr, font, or a handful of others is processed, the element is recorded in that list. When a block element interrupts, the list is not cleared. When character data or a phrasing element arrives after the interruption, the parser reconstructs the active formatting elements, creating fresh copies and pushing them onto the stack.

The adoption agency algorithm runs on an end tag that matches a formatting element which is not the current node. In outline, it walks the stack from the top looking for the furthest block, unwinds the intervening elements, clones the formatting element, reparents the children of the furthest block into the clone, and removes the original from the list. It also contains a step that limits runaway duplication: if the list already holds three elements with the same tag name, namespace, and attributes, the earliest is removed before the new one is added. That limit is the “Noah’s Ark clause”, and it is why a document with deeply nested repeated <b> tags does not produce unbounded clones.

The algorithm is defined recursively with a counter, and a small number of pathological inputs cause it to be invoked repeatedly. It is also the section where historical browser behaviour diverged most before the specification settled it.

What the tree builder deliberately does not check

Nothing in the parsing algorithm consults a content model. <span> inside <select> is discarded by the in select rules, but <div> inside <span> is inserted without complaint, even though the span content model is phrasing content only. <img> without alt parses fine. <a> nested inside <a> is repaired by closing the outer anchor, which is a parsing behaviour, not a validity rule. Conformance requirements and parsing behaviour are separate layers of the specification, and the distinction explains why an invalid document can still produce a predictable tree. The categories themselves are covered in HTML Content Model Categories.

Because the tree is repaired, round-tripping markup through the DOM does not preserve the source. Serializing the parsed tree in the first example yields a table with no children and a div before it. A parsed <table><tr><td>x gains an implied tbody element that was never written, which is visible to querySelector and to CSS selectors. An entity written as & is serialized back as &, because the serializer escapes the ampersand rather than reproducing the reference. Any comparison of input markup with serialized output has to account for normalization rather than expect identity.

Fragment parsing and the cost of the guarantee

innerHTML and the other fragment-parsing entry points do not run the full algorithm from the initial mode. They run a fragment parsing algorithm that starts from a context element, seeds the stack with a single html element, chooses the insertion mode and tokenizer state from the context, and parses children rather than a document. DOMParser is not one of them: with text/html it parses a complete document through the ordinary algorithm. The context matters: the same string produces different nodes when parsed inside <table>, inside <select>, and inside <template>. This is the basis of context-aware sanitization and the reason a sanitizer that parses in the wrong context can admit markup it did not intend to.

The cost of specified error recovery is a tokenizer with a large state table and a tree builder with several hundred rules, all of which must be present even for documents that are well formed. Engines mitigate the cost by building the state tables from a compact description and by fast paths that scan for < and & without entering the general state machine. The payoff is that markup written a decade ago by a tool that has since disappeared still renders the same way, and that two engines can be compared by diffing serialized trees rather than by inspecting screenshots.

Divergence still exists at the margins, mostly in the handling of rare constructs such as deeply nested tables and certain combinations of formatting elements with template contents, and newer features occasionally require parser changes that older engines will not have. For ordinary markup and ordinary mistakes, the tree is stable.