From: Todd Benson Date: 2008-03-01T02:35:52+09:00 Subject: Re: Need a regex searching html code On Fri, Feb 29, 2008 at 10:52 AM, Florian Gilcher wrote: > > > On Feb 29, 2008, at 2:54 PM, Mark Thomas wrote: > > > All the regex solutions provided will break with the following > > perfectly valid HTML: > > > >
> >
Tagline:
> > Yippee Ki Yay Mo - John 6:27 > >
> > > > This is one of many reasons it is a BAD idea to use regexes to parse > > HTML. Regular expressions are simply not the right tool for the job. > > > > Whats quite interesting is that I am not able to find a nice article > on _why_ > this doesn't work. So, in short: > > Regexp can only parse languages that are regular (hence the name) or - > in other words - a Type 3-language in the Chomsky hierarchy [1]. This > is a > rule of thumb because many Regexp-libraries nowadays implement > features that enable you to do more than formal regular expressions. > But for the typical use, it is true. > > Regular languages do not have any possibility to "look behind". They > do only > look forward. This is the reason why you cannot define a regular > language to > describe an parse arbitrarily deep nested structure (an thus, no regular > expression): > You have no possibility to determine which closing tag matches a given > opening tag. > > A more abstract example: > There is no (formal) regular expression that matches a word that > consists > of n times "a" and then n times "b": > > ab > aabb > aaabbb > aaaabbbb > etc. > > What you can do is extract a tag, push it on a stack, extract the > next one, etc. and pop them when encountering matching closing tags. > Tags > by itself can be described with regexps (afaik, this is how Textmate > does its > markup). > > Greetings > Skade > > [1] http://en.wikipedia.org/wiki/Chomsky_hierarchy Thank you for that great explanation! I was waiting for someone to bring up formal grammar, but I was afraid to, because I wasn't sure it applied (not that familiar with how regexps actually work). Todd