3 ms·
All you need to parse HTML is regular expressions (to recognize tags) and a stack (to match tags). Your programming language has a stack -- a call stack. So i
by chubot 6y ago
All you need to parse HTML is regular expressions (to recognize tags) and a stack (to match tags).
Your programming language has a stack -- a call stack.
So in practice all you really need is regular expressions. (Which I tend to call "regular languages" to make a distinction with Perl-style regexes [1], although they work fine too in practice for this case)
Using the call stack in a more functional style is nicer than using the OOP style that s in the Python standard library, which is probably inherited from Java, etc.
I have done this with a bunch of HTML processors for the Oil blog and doc toolchain:
https://github.com/oilshell/oil/tree/master/doctools https://github.com/oilshell/oil/tree/master/doctools
It works well in practice and is correct and fast.
Big caveat: this style is only for HTML that I generate myself, e.g. the blog and docs. There are a bunch of rules around matching tags in HTML5 that are subtle. Although one of the points here is that you don't have to do a full DOM-style parse and can ignore those rules for many useful cases.
The other caveat is that HTML has a bunch of rules for what happens when you see a stray < or > that isn't part of a tag. This style makes it a hard syntax error, so it's really a subset of HTML (which has no syntax errors). For my purposes that is a feature rather than a bug, basically following Postel's law.
I meant to write a blog post titled "why/when you can parse HTML with regexes" about this but didn't get around to it.
There is also a caveat where parsing arbitrary name=value pairs with regexes isn't ergonomic, because it's hard to capture a variable number of pairs. However the point is that I wrote 5 or 6 useful and compact HTML processors that don't need that. In practice when you parse HTML you often have a "fixed schema".
Concrete examples are generating a TOC from <h1>, <h2>, etc. and syntax highlighting <pre><code> blocks. Those all work great with the regex + call stack style.
[1] http://www.oilshell.org/blog/2020/07/eggex-theory.html http://www.oilshell.org/blog/2020/07/eggex-theory.html
edit: for completeness, another caveat is that the stack-based style is particularly bad for C++/Rust and arbitrary input because you could blow the stack, although we already limited the problem to "HTML generated ourselves"
- c-cube 6y agoWhat you're describing is using regex to _lex_ html, not parse it. The parser is easy to build once you have a lexer (after all most of XML's unpleasantness comes from escaping). It still isn't the same thing as parsing with regular expressions. Similarly you can't parse S-expressions with regular expressions, but if you have the lexer (e.g. with `lex` or other languages' equivalent) then the parser on top of it becomes absolutely trivial.
- chubot 6y agoRight exactly, in fact I call the library "lazylex" because it only does the minimum to find the <> structure. If you want to recognize more, then you invoke a attribute "name=value" lexer on the tag, but usually you don't. This makes it quite fast (and speed is useful because most doc toolchains are slow). The lexing is the "generic" part and parsing is specific to the task at hand. In the case of making an HTML table of contents, you literally just find <h1>, <h2> with regexes, and don't do all this DOM nonsense. It's easier to write than the SAX style with an explicit stack. So yes the point is that parsing HTML is trivial for most purposes: use the call stack. It helps if your language has exceptions to indicate errors.
- aidenn0 6y agoYes, HTML is a deterministic context-free language, so you can parse with a DPDA. In addition, tokens are regular (as it is for many languages), so you can use a regex for tokenization. All you need for writing a recursive descent parser with backtracking is a call-stack, so are all LL(k) and most practical CFGs also parseable with regex?
- chubot 6y agoI am not sure if you can say that precisely -- I added the caveats about the rules for end tags, and the rules for stray < and >. But certainly a useful subset of HTML can be parsed with a DPDA. (I'd be interested in more analysis of that; arbitrary tags are another factor) It's a matter of opinion but I would say recursive descent is "nontrivial", whereas matching tags is "trivial". Recursive descent involves some choice around lookahead or backtracking. It can be slow if you do the wrong thing, hard to debug, etc. It takes a little practice, and correspondence with a grammar is important. Whereas matching HTML tags requires no lookahead, and I would say anyone can figure it out just with a simple code reading. Even the "inverted" OOP style is "simple", but annoying for me to read and correctly modify. The call stack reads much better.