Re: 32-bit programs on Windows x64
On Mon, 07 Jul 2008 14:46:21 +0100, David Lowndes <DavidL@example.invalid>
wrote:
A DFA lexical analyzer does not compare its input string to
the set of valid strings one-at-a-time, it compares its
input string with the entire set of valid strings
all-at-once, simultaneously, and at the-same-time, thus
concurrently.
Hi Peter,
Are you and Joe perhaps not understanding what each other are saying?
Joe won't accept Peter's notion that a DFA that recognizes multiple strings
demonstrates "concurrency". Joe is correct that running the DFA is a
sequential process; the "move" function is essentially indexing into an
array, which maps the current piece of input to a new state. Like an NFA, a
DFA can match any number of strings, all at the same time, and Peter is
calling this "concurrent matching", although it doesn't involve any sort of
concurrency at the hardware level. If you define "concurrency" as what
happens during multithreading, then there is a point of disagreement. If
you were to run a naive string matching algorithm in N threads to match N
patterns against some string, then you would expect to be able to determine
which patterns matched. In contrast, a DFA that matches those N patterns
can't tell you which one matched, which gives people who write regexp
engines fits, because it complicates the implementation of backreferencing
for things like (a|b|c)d\1. You can't use a pure DFA for this. So that's
another difference.
I'm not familiar with what you're describing, but from what you've
said, it sounds like magic.
Does this DFA analyzer perhaps perform some previous steps to coalesce
same values so that it only has to do a subsequent comparison once?
Yes, the standard algorithm first constructs an NFA, and from the NFA, a
DFA is constructed, with each DFA state taking the place of one or more NFA
states. Basically, the DFA gets rid of the epsilon (empty string)
transitions that cause an NFA to frequently be in multiple states at once.
This makes the DFA's "move" function deterministic, such that it starts in
one state, and processing each input character moves it to one and only one
new state. The Dragon Book has a very good, detailed explanation of this in
its second or third chapter.
--
Doug Harrison
Visual C++ MVP