[antlr-interest] Regular Expression vs CFG

[Randall R Schulz]

On Monday 05 March 2007 18:38, Terence Parr wrote:
> On Mar 5, 2007, at 6:34 PM, Randall R Schulz wrote:
> > Dennis,
> >
> > 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.
>
> Oohhhh...was that gleaned from my "The nature of computer languages"
> chapter or your automata theory class? ;)

I thought it was common knowledge...

I could be that once upon a time I wrote a fairly comprehensive, 
generic, extensible regular expression library (it even had a generator 
for finite REs that would implement the shell's "curly-brace" synthesis 
mechanism.) (And yes, I know, everyone has written one of these in 
their day...)

But in point of fact, I haven't read your book and I never actually took 
the automata theory or lexer / parser / compiler class. But osmosis 
does appear to have done its thing, somehow.


> Ter


RRS