so-regex-html-legendary

Answer

The fix is a complete HTML parser with three layers, demonstrating precisely why regex fails for HTML per the Chomsky hierarchy:

1. Tokenizer (Lexical Analysis — regex is fine here)

Uses regex to split HTML into tokens: tag_open, tag_close, self_closing, text, comment, cdata. This is the only place regex belongs — breaking input into atomic tokens is a regular language task.

TOKEN_RE = re.compile(r"""
    <!--.*?-->                                          |  # comment
    <!\[CDATA\[.*?\]\]>                                 |  # CDATA
    <(?P<close>\/)\s*([a-zA-Z][a-zA-Z0-9:_-]*)\s*>     |  # close tag
    <([a-zA-Z][a-zA-Z0-9:_-]*)((?:\s+[^>]*?)?)\s*/?>    |  # open/self-closing
    [^<]+                                                  # text
""", re.VERBOSE | re.DOTALL)

2. Recursive Descent Parser (Pushdown Automaton)

Uses a stack — the defining characteristic of a context-free (Type-2) parser. Each tag_open pushes onto the stack; each tag_close pops and verifies the tag name matches. This correctly tracks arbitrary nesting depth, which regex cannot do.

def parse_html(html: str) -> Element:
    tokens = tokenize(html)
    root = Element("root")
    stack = [root]
    for tok in tokens:
        if tok.type == "tag_open":
            el = Element(tok.value, dict(tok.attrs or {}))
            stack[-1].children.append(el)
            stack.append(el)
        elif tok.type == "tag_close":
            top = stack[-1]
            if top.tag != tok.value:
                raise ParseError(f"Tag mismatch: </{tok.value}> vs <{top.tag}>")
            stack.pop()
        # ... text, comment, cdata, self_closing

3. Why Regex Alone Cannot Parse HTML

The pumping lemma proves regular languages can't count arbitrary nesting. HTML needs { aⁿ bⁿ | n ≥ 0 } matching — a context-free language. Python's re on <div><div>deep</div></div> greedily matches from the first <div> to the last </div>, producing an incorrect parse:

Regex  <div>(.*)</div>  matches '<div><div>deep</div></div>'
       → captures "<div>deep</div>" as content (WRONG)

A proper parser uses a stack and gets:

<div>
  <div>
    'deep'
  </div>
</div>