From: Brian Candler <B.Candler@...>
Date: 2003-02-22T02:24:50+09:00
Subject: Re: Regexp help: Parsing a CSV file

On Sat, Feb 22, 2003 at 12:44:55AM +0900, Michael Campbell wrote:
> Aren't regex's state machines anyway?

They can be parsed by state machines. In fact, a true regexp can be
mechanically converted into a 'deterministic finite state automaton' - that
is, one which only has to read each input symbol once and never has to
backtrack.

However the regexp libraries I'm aware of are implemented as
nondeterministic FSA's, i.e. when presented with a choice, they take one
option and backtrack later if they reach a blind alley.

I think some things which programmers consider part of "regular expressions"
are not formally part of regexps anyway. In particular, a true regular
expression cannot parse a grammar like matching open and close brackets
(e.g. "match a number of A's followed by an equal number of B's")

Regards,

Brian.