Can regular expressions parse HTML or not? | Hacker News Reader

Can regular expressions parse HTML or not?

johndcook.com

18 pointsduck23 comments

The correct answer doesn't just depend on what you mean by "regular expressions", it also depends on what you mean by "parse". And perhaps also what you mean by "HTML".

Case in point: A while back I ran into a nasty bug in our software which would cause it to crash with a stack overflow exception. It turned out to be that the problem was in how HTML Agility Pack would respond to certain kinds of particularly poorly-formed HTML documents.

Now, we had chosen to use HTML Agility Pack in part because of all the comments to the effect of "NOOOOOO don't use regex, use Agility Pack!" complete with links to a certain famous Stack Overflow answer that are littered around the internet. But in analzying the situation in more detail, we discovered a few things: First, we were just stripping tags, so our parsing needs were very minor compared to what HTML Agility pack does. Second, generating a full-on parse tree for an HTML document was kind of harming us, in that doing so takes both time and RAM, two things we were trying to be light on. Third, we could afford to be fairly tolerant of a missed tag or some lost content, but the parser giving up was a minor tragedy. Noisy results were far better than no results for our purposes.

The upshot of all this being, for our "HTML parsing" needs, regular expressions turned out to be exactly the right tool for the job. Following that realization, it was the work of only one afternoon to fix the bug, and as a side benefit dramatically improve both the engine's performance and the quality of its output.

Long story short, what passes for common wisdom on the Internet is no substitute for knowing what you're doing.

> HTML in the wild can be rather wild.

One easy way to get an idea of how complicated this can be is checking out the parsing algorithm in the HTML5 spec [1] (section 12).

To start the complexity, HTML is not XML and not all tags are created equal. Void elements like <img> and <br> don't have matching close tags and contents for things like <textarea> and <script> are treated as text (you can't nest more tags inside). Then you have the issue of javascript being able to call document.write at HTML-parsing times, something you need to hope doesn't happen or parsing becomes intractable. Finally, There is a vast number of rules and special cases that kick off when you have missing or mis-nested tags or tags being put in the wrong places.

[1] http://www.whatwg.org/specs/web-apps/current-work/multipage/

On the theoretical side, pure regular expressions (w/o PCRE extensions) can actually parse HTML to the extent that most browsers can. The expressions would be gigantic, unmaintainable messes, and probably not even possible to write by hand, but nonetheless it's more of a practical problem than an issue of formal language power.

For example, WebKit sets a maximum DOM nesting limit of 512 [1], and most other browsers have a limit as well. A context-free language restricted to a finite maximum production depth becomes a regular language, so WebKit's parsing could be done by an NFA or DFA, and the parser could be encoded as a regular expression if desired. But the only plausible way to write such an expression correctly would be to mechanically "compile" it from a grammar. So you're going to need the grammar anyway, at which point you might as well use it directly.

[1] http://trac.webkit.org/browser/trunk/Source/WebCore/page/Set...

Why does webkit have a limited tag depth?

Logically to avoid denial of service attacks, with exhaustion of memory etc.

And here's the canonical example in XML: http://en.wikipedia.org/wiki/Billion_laughs

IMO The probablity of a given page being well formed, or being non-well formed in a manner that will not completely screw the parser is probably very low. Therefore, you should use a dedicated html parser for parsing html.

I agree as far as parsing most HTML. I use regular expressions all the time when I'm working with HTML I've written by hand because I know what's there.

I just find it interesting that the efficacy of regular expressions can be framed as a computer science question, a practical question, and a statistical question.

In practical terms, how often are you actually parsing HTML? Building a DOM, rendering...

A knee-jerk reaction to 'HTML' and 'regular expression' being used in the same sentence is like someone seeing 'goto' without understanding the context and shouting "goto considered harmful!"

I recently use some combination of perl's split() and regexes to trivially pull all links from a piece of markup. I had to suppress the "Don't parse HTML with regular expressions!" voices echoing in my head the whole time I was writing it. I'm OK with the code now, of course.

In my experience, an XPath (or CSS selector) to get relevant information is both easier to construct and easier to understand than a regular expression, and the resulting code is more likely to continue to work as the website changes. I don't see why you would subject yourself to using regular expressions unless your environment doesn't have an HTML parser.

In this particular instance, for reasons of a self-imposed contraint to favour ease of deployment and use by the target audience, I have no parser.

Using xpath (or just about anything else) would be smashing.

The likelihood of the markup changing to the point where the code breaks is unlikely, the target pages are open source mirrors exposed over HTTP. It even winds up being nicer code than the FTP handler.

Goto statements are a good example. It's easier to recite "goto is harmful" than to say "In most situations, other control structures are more expressive and easier to maintain than goto statements. However, there may be rare occasions, particularly in low-level system programming, where goto statements could be preferable."

"Don't parse HTML with regex" is good general advice, but no more an absolute than avoiding goto statements.

>rare occasions, particularly in low-level system programming, where goto statements could be preferable

Or something as simple as "break 2;"

Depends entirely on what you are doing. If you need to parse a page and be sure that you have found every single link in that page - even javascript - then a regex is going to fall flat.

If you need to collect a number of links from the web using a spider, and you don't really mind if you get them all or not, then regex is perfectly fine. You could do a regex to match the first href="" following "<a" and stopping when it hits a "/>". This will give you at least 75% of the links on the internet, and it's done it in far less processing power or ram usage as a full html parser.

As always, a chainsaw is not necessarily better than a butter knife for cutting down trees, if the 'tree' in question is just a 5cm shoot. In fact, using a chainsaw for that would be mighty funny.

Would that really count as parsing? Honest question.

I'm using the term 'parsing' because it's the one used by the article. What else would you use regex and html together for? You only have two options: extracting data from html using regex, or modifying html using regex. Modifying using regex is just string replacement. For example, replacing all hrefs in a html document with new links. You'd use the same method as described above, with a similar 75% of all links replaced.

Good question - but it is 90% of what I see people using HTML parsers for grab the content of a single tag from a page.

Which is why I often recommend "parsing" HTML with a regex. Particularly on throwaway projects. The overhead of a real parser is a waste.

And if the complexity grows - the sucker will need a rewrite anyhow.

This can easily be summarized -- if the target HTML meets a modern specification and has no serious syntax errors, or if we're really talking about XHTML, which has a much stricter syntax, then no problem. Otherwise parsing the target will produce endless difficulties.

But then, if the HTML has syntax problems or contains inconsistent syntax, then no approach is entirely reliable, which means it's not about regular expressions any more.

This post reminds me of Clarence Thomas' explanation of his short opinions. This is the perfect example of a "5 cent idea in a $10 sentence."

Post adds nothing of substance to the following:

"Well-formed HTML is context-free. So you can match it using regular expressions."

"But most HTML you see in the wild is not well-formed. And just because you can, doesn’t mean that you should."

which wasn't even written by him.

5 cent ideas in $10 sentences is pretty much describing half of HackerNews.

The topic in #regex on irc.freenode.org:

READ THIS FIRST: Need help? 1) Language/platform. 2) Sample string. 3) Desired result. 4) Your attempt. | Do NOT use RegEx to parse HTML! | Do NOT tell us a RegEx doesn't work if you aren't testing it in the language you asked about! | Intro: http://bit.ly/XrnV | Home: http://bit.ly/KEo1Gx | FAQ: http://bit.ly/L949Mk | Quiz: ? quiz | Regex website: http://regex101.com/

Note the part "Do NOT use RegEx to parse HTML!" ...

You can use regex to to parse HTML, but it's a verry bad idea. Basicly you would nee to reimplement the HTML definition in regex, otherwise your regex will screw up.

In general, no. Regular expressions match regular languages but HTML is a context-free language. Every regular grammar is context-free but not all context-free grammars are regular.

See http://stackoverflow.com/questions/590747/using-regular-expr... for details. Also

http://stackoverflow.com/questions/5175840/is-html-a-context...

And then you have attempts to recover when HTML is ill-formed: http://en.wikipedia.org/wiki/Tag_soup

Is your comment aimed at people who didn't read the linked article?

Reply on news.ycombinator.com