Re: StringBuilder Extension: IsQuotedBy

Peter Obiefuna <[email protected]> wrote:

> Barry wrote:
> > Also, I don't see how this is relevant to why one wouldn't "still"
> > hand-write a DFA.
> 
> The point is that a finite state machine is a DFA and is generated by every
> Regex engine implementation from the first input tape (ie: the regex) and
> then moves over the second tape (input string to evaluate it. The input
> string passes if the machine gets to a finish state and there will be many
> of them in most real cases).

Just looking at the pragmatics here: it's simpler to have a transition
to a finish state than it is to annotate every state with an extra flag,
indicating whether it's a finishing state, when the problem you're
trying to solve is matching a single regex against a given string.

> I don't agree that whipping up a new custom
> parser is guaranteed to do the job faster until we see some real theoretical
> analysis or empirical data.

Third-party regexes typically *aren't* DFAs - they usually use NFAs,
that is, with back-tracking, because they use constructs that aren't
possible to match with a simple regex - consider back-references, for
example, where we simply can't match in linear time.

On the other side of the fence, tokenizers usually don't require things
like back-references, so they can indeed be DFAs, which will usually be
faster than NFAs (but never slower).

> I also don't buy the claim that it's as trivial
> a task as to require 1 hour of a developer's time (not to mention testing
> time).

That flatly contradicts my experience. I make my living writing
compilers. Simple lexers - i.e. ones that don't try to do clever tricks
like include files, macros, dual token streams for documentation
comments, etc. - for modern programming languages - i.e. one's that
don't have piles of context-sensitive tokens, like Fortran's famous
problems - are indeed trivial to write. For super-simple languages like
expression evaluation including operators, identifiers and constants, it
shouldn't take more than 5-10 minutes.

> Of course, the dragon book has a 100-line lexer (I hope we all
> remember that enticing chapter).
> I hope you now see the relevance Barry. I probably didn't make the
> connection clear the first time.

What you said is that a regex matcher implements a finite automaton,
which I agree with - I did say 'Yes' back then - but that fact doesn't
really help you with typical tokenizing, because it's normally (1)
hidden behind a simple matching API, so you don't get to differentiate
states that normally wouldn't be differentiated just for matching, and
(2) regex implementations usually have things like backreferences which
preclude using high-performance DFA implementations in general (but they
could of course be used for specific cases).

For a fairly decent discussion, see:

http://swtch.com/~rsc/regexp/regexp1.html

-- Barry

-- 
http://barrkel.blogspot.com/

===================================
This list is hosted by DevelopMentor®  http://www.develop.com

View archives and manage your subscription(s) at http://discuss.develop.com