5 ms·

Can regular expressions parse HTML or not?

18 points by duck 14y ago

Qantourisc 14y ago
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 http://bit.ly/XrnV | Home: http://bit.ly/KEo1Gx http://bit.ly/KEo1Gx | FAQ: http://bit.ly/L949Mk http://bit.ly/L949Mk | Quiz: ? quiz | Regex website: http://regex101.com/ 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.
newishuser 14y ago
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.
- cardine 14y ago
  5 cent ideas in $10 sentences is pretty much describing half of HackerNews.
bculkin2442 14y ago
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.
- johndcook 14y ago
  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.
  - fuzzix 14y ago
    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.
    - simonster 14y ago
      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.
      - fuzzix 14y ago
        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.
    - johndcook 14y ago
halis 14y ago
I agree, you can parse HTML with regex but...probably should not. If you must, then at a minimum you should normalize the html first. For example ensure that spaces are stripped out of the front of tags (i.e. < html> becomes <html>) doing things like this, that do not change the actual content of the markup can make parsing much easier. I still prefer using Javascript or jQuery on the client side or HTML Agility pack on the server for manipulating markup.
giardini 14y ago
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-expressions-to-parse-html-why-not http://stackoverflow.com/questions/590747/using-regular-expr... for details. Also http://stackoverflow.com/questions/5175840/is-html-a-context-free-language 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 http://en.wikipedia.org/wiki/Tag_soup
- omaranto 14y ago
  Is your comment aimed at people who didn't read the linked article?
mjn 14y ago
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/Settings.h#L408 http://trac.webkit.org/browser/trunk/Source/WebCore/page/Set...
- bvdbijl 14y ago
  Why does webkit have a limited tag depth?
  - coldtea 14y ago
    Logically to avoid denial of service attacks, with exhaustion of memory etc.
    - T-hawk 14y ago
      And here's the canonical example in XML: http://en.wikipedia.org/wiki/Billion_laughs http://en.wikipedia.org/wiki/Billion_laughs
ufo 14y ago
> 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/ http://www.whatwg.org/specs/web-apps/current-work/multipage/
bunderbunder 14y ago
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.
lutusp 14y ago
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.

18 points by duck 14y ago

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 http://bit.ly/XrnV | Home: http://bit.ly/KEo1Gx http://bit.ly/KEo1Gx | FAQ: http://bit.ly/L949Mk http://bit.ly/L949Mk | Quiz: ? quiz | Regex website: http://regex101.com/ 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.

newishuser 14y ago

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.

cardine 14y ago
5 cent ideas in $10 sentences is pretty much describing half of HackerNews.

bculkin2442 14y ago

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.

johndcook 14y ago
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.
- fuzzix 14y ago
  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.
  - simonster 14y ago
    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.
    - fuzzix 14y ago
      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.
  - johndcook 14y ago

halis 14y ago

I agree, you can parse HTML with regex but...probably should not. If you must, then at a minimum you should normalize the html first. For example ensure that spaces are stripped out of the front of tags (i.e. < html> becomes <html>) doing things like this, that do not change the actual content of the markup can make parsing much easier. I still prefer using Javascript or jQuery on the client side or HTML Agility pack on the server for manipulating markup.

giardini 14y ago

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-expressions-to-parse-html-why-not http://stackoverflow.com/questions/590747/using-regular-expr... for details. Also http://stackoverflow.com/questions/5175840/is-html-a-context-free-language 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 http://en.wikipedia.org/wiki/Tag_soup

omaranto 14y ago
Is your comment aimed at people who didn't read the linked article?

mjn 14y ago

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/Settings.h#L408 http://trac.webkit.org/browser/trunk/Source/WebCore/page/Set...

bvdbijl 14y ago
Why does webkit have a limited tag depth?
- coldtea 14y ago
  Logically to avoid denial of service attacks, with exhaustion of memory etc.
  - T-hawk 14y ago
    And here's the canonical example in XML: http://en.wikipedia.org/wiki/Billion_laughs http://en.wikipedia.org/wiki/Billion_laughs

ufo 14y ago

> 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/ http://www.whatwg.org/specs/web-apps/current-work/multipage/

bunderbunder 14y ago

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.

lutusp 14y ago

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.