From: ahoward <ahoward@...>
Date: 2003-02-22T07:04:22+09:00
Subject: Re: Regexp help: Parsing a CSV file

On Sat, 22 Feb 2003, Brian Candler wrote:

> > But this is to my knowledge also not possible in regular expressions
> > implementations. If you match a finite number of parentheses you can both
> > formally and in real-world regular expressions. Otherwise you enter the
> > world of LL-1 grammars etc. and you need to write a stack supported
> > recursive descent parser or a bottom-up parser (LR, or LALR) parser.
> >
> > To be more precise regular expressions are supported by finite state
> > machines (finite as in no stack), whereas a bottom-up parser like Yacc is
> > also a state machine, but not a finite one - it uses an infinite stack and
> > thus support infinite nesting levels.
>
> Agreed. I was wondering why implementors have gone for non-deterministic
> implementations, and I suspect that some features require it (e.g.
> look-ahead and look-behind assertions, greedy and non-greedy matching). If
> so, then perhaps they're not true regular expressions?

every NFA can be reduced to a DFA, and so either a NFA or DFA is 'regular' by
definition.

whether or not ruby regexps are limited by this i do not know.

-a

-- 
 ====================================
 | Ara Howard
 | NOAA Forecast Systems Laboratory
 | Information and Technology Services
 | Data Systems Group
 | R/FST 325 Broadway
 | Boulder, CO 80305-3328
 | Email: ahoward@fsl.noaa.gov
 | Phone:  303-497-7238
 | Fax:    303-497-7259
 ====================================