One of the best and academically proficient answers I've seen on SO. And if I understand correctly turns on its head the old refrain "You can't use regexes to parse HTML", of which I've always been a staunch proponent.
Now I understood the reason _why_ you can't use regular expressions to parse HTML is that HTML is usually not regular. Is this true? Does this solution in perl work because of the extended capabilities of perl regexes?
> Now I understood the reason _why_ you can't use regular expressions to parse HTML is that HTML is usually not regular. Is this true?
From the comments:
Q. "The answer is you can't. HTML is not regular so be definition it can't be described by a regular expression."
A. "Your use of REGULAR in regular expressions has been irrelevant and wrong since Ken Thompson first put backrefs into regexes around 40 years ago. /(.)\1/ parses non-REGULAR languages perfectly well. Please stop repeating this nonsense. – tchrist"
Backreferences in some sense don't work because real HTML contains misnesteded tags and other bugs, so many of them, even HTML5 spec explictely mentions correction algo.
Why is the language matched by /(.)\1/ non-regular? Isn't it finite (aa, bb, cc, dd, ..., zz if your alphabet is the lowercase letters a-z)? And all finite languages are trivially regular.
Maybe he meant /(.*)\1/?
Note: I know that backreferences make Perl regexes capable of matching non-regular languages, but this doesn't seem like an example of that.
> Does this solution in perl work because of the extended capabilities of perl regexes?
Yes. It works because perl's "regexes" are not regular expressions (nb: almost no "regex engine" these days is limited to regular expressions). Actual regular expressions can express type-3 chomsky grammars, whereas HTML's grammar (and most programming languages's) is of type 2.
HTML isn't even actually context-free, though you can possibly parse it as context-free (type-2) with some kludges. The kludges are the same as the kludges for parsing it in a regular language, though! (I.e. "all" you need to do is add backreferences.)
Recognizing paired start/end tags is equivalent to recognizing palindromes, and the palindrome language is only context-free if there's a finite, fixed alphabet. But the set of HTML tags a parser needs to match isn't finite. While there are a finite number of defined tags in any particular version of the HTML specification, a parser is still supposed to be able to match start/end tags it doesn't recognize, to distinguish the case of malformed syntax from the case of correctly formed syntax that uses unrecognized tags.
An easy way to see it is to try to write out CFG productions for HTML. The intuitive way requires something like backreferences, which would make the language no longer context-free:
html = '<' + tag + '>' + html + '</' + $0 + '>'
But in a context-free language you don't have that, so you instead have to do something like:
html = '<head>' + html + '</head>'
| '<body>' + html + '</body>'
| '<b>' = html + '</b>'
| ...
which of course only works if the number of tags is finite so that you can exhaustively enumerate them.
While there are a finite number of defined tags in any particular version of the HTML specification, a parser is still supposed to be able to match start/end tags it doesn't recognize, to distinguish the case of malformed syntax from the case of correctly formed syntax that uses unrecognized tags.
I don't think this is necessary in HTML, which expects every unknown tag to be ignored regardless of nesting, unless you are planning to render the content using CSS or support scripting, which may expect the unknown element to be in the DOM or to be styleable, but even there historically different browsers tended to do different things to unknown tags.
I don't wish to be rude, but how can you call yourself a staunch proponent of something you admit two sentences later not to really understand? That seems like an odd position to me.
More on topic, XML is not even a type 2 language since you have to check for matching of tags, and the tags can come from an arbitrary set, so you can't write a context-free grammar that recognises well-formed XML.
You'd want rules like:
XML -> TAG
TAG -> "<" ([a-z]+) ">" (TAG|Text)* "<" "/" \1 ">"
but backreferences are not possible. However, sane parsers allow a lexing phase and semantic rules or post-processing, which is why I think any academic assertions about which level of grammar you need for a certain file format are essentially a waste of time.
Yes, HTML is not a regular language, and so cannot be matched with true regular expressions. As mentioned elsewhere, most "regex" libraries in existence today are not limited to simple regular expressions -- they simply wouldn't be powerful enough for many common tasks otherwise.
HTML is more accurately a context-free language (CFL). A regular expression does not allow you to do any sort of counting or stack-based matching in a match, which is required to do things like "I just saw <div>...<a>...<img> so I better see "</img>...</a>...</div>" later on.
The reason the linked solution works is because of the extended capabilities of PCREs, such as backtracking and things like that.
>Now I understood the reason _why_ you can't use regular expressions to parse HTML is that HTML is usually not regular. Is this true?
I believe the reason is that HTML is a Type 2 grammar by Chomsky hierarchy (that is, a push-down automaton), whereas regexp is a Type 3 grammar (that is, a finite state automaton). To put it simply, HTML has a frame/state stack, and regexp isn't advanced enough for that (instead it reads "left-to-right" - no subroutines or recursion).
I suspect you might be right about him "cheating" using perl, but not knowing a lick of perl, I can't say for sure one way or the other.
Edit: Apparently, back-references mean regexp isn't regular - that actually makes more sense now; they've never quite meshed with my understanding of regular languages.
As the comment by tchrist to this [0] downvoted answer says, as soon as back references were used (40 years ago apparently) regexes were not regular anymore.
Some discussion, plus links, from an earlier HN posting about a related SO post (which argued, roughly, that parsing HTML with regexes opened the door to Hell): http://news.ycombinator.com/item?id=1487975
Now I understood the reason _why_ you can't use regular expressions to parse HTML is that HTML is usually not regular. Is this true? Does this solution in perl work because of the extended capabilities of perl regexes?