From: Clifford Heath <cjh-nospam@...>
Date: 2004-02-13T13:36:17+09:00
Subject: Re: Simple parsing of sloppy HTML - LittleLexersame

Regular expressions can't parse reentrant definitions, for example
stmt ::= while expr stmt | if expr stmt | ...

Sure you can wrap them up in loops and other things, and that's
what parsers do when they wrap themselves around a lexer, but
you must have a layer that is not a regular expression, or it
doesn't work. This has been mathematically proven from the
definition of RE, so if you find a way around it, you don't
have an RE.

> So we could have a regex that recognized "atomic" if/else statements...

Yes, but if the if/else statement contains another, and that contains
another, to arbitrary depth, then no RE can parse it, with any amount
of look-ahead.