Invisible wrote:
> Not in any regex product I've ever seen. 

You don't even use text regular expressions, so that's not very 
authoritative. ;-)

Seriously, any DFA is the equivalent of a regex.

> Most people seem to equate "regex" with "shorthand for writing text parsers".

Sure. But exactly the same theory works for any stream of tokens. You can 
use most modern libraries to match, for example, unicode, which includes 
chinese, so right there you're outside the "text" area, let alone if you 
write your own parser.

> So much for theory. Most "regular expressions" out there aren't even 
> regular. 

Sure they are. Unless you use a back-escape (i.e., substitute in something 
that you earlier matched) then it's all regular. Stuff like {} and + are 
just trivial macros to reduce typing.  I think I use a backmatch maybe once 
every two or three years interactively, and I don't think I've ever used one 
programmatically.

>>> I recall reading somewhere that Perl's "regular expressions" aren't
>>> actually regular, and so require exponential time for matching. Truly
>>> regular expressions apparently require only linear time.
>>
>> Correct. And not only exponential time, but memory as well. A regular
>> expression is regular because it requires a fixed amount of memory to
>> match or reject.
> 
> Is that the definition of "regular" then?

Wikipedia is your friend. But yes, that's part of the definition. A language 
is regular if it can be matched by a DFA.

> Regardless, if you're trying to do complicated parsing, you should use 
> real parser tools, not a regex.

Again, it depends what you're trying to parse. Are you trying to parse a 
file full of lines like

structure_size = 37
structure_drift = 92.7E13

etc?  A regexp will do just fine.

-- 
Darren New, San Diego CA, USA (PST)
   Serving Suggestion:
     "Don't serve this any more. It's awful."

Post a reply to this message