[antlr-interest] Regular Expression vs CFG

Oliver Wong owong at benchmarkconsulting.com
Tue Mar 6 08:47:34 PST 2007

> On Monday 05 March 2007 18:29, Dennis Katumalla wrote:
> > Can someone give me a simple example where a regular expression
> > alone (using java.util.regex) is not sufficient to parse a SQL
> > statement and requires specification of a full grammar?
> The mere fact that there are balanced and nested constructs
> (e.g., parenthesized sub-expressions) is enough to tell you that
> no finite automaton alone can recognize the language. Such
> constructs demand a push-down automaton of some sort.

For more information on this, google for "Pumping Lemma". In particular:

	- Oliver

More information about the antlr-interest mailing list