Parsing a search string

It's me itsme at
Fri Dec 31 22:52:59 CET 2004

"John Machin" <sjmachin at> wrote in message
news:1104526960.929218.119480 at
> Andrew Dalke wrote:
> > "It's me" wrote:
> > > Here's a NDFA for your text:
> > >
> > >        b  0 1-9 a-Z ,  . +  -   '   " \n
> > > S0: S0 E   E  S1  E E E S3 E S2  E
> > > S1: T1 E   E  S1  E E E  E  E  E T1
> > > S2: S2 E   E  S2  E E E  E  E T2  E
> > > S3: T3 E   E  S3  E E E  E  E  E T3
> >
> > Now if I only had an NDFA for parsing that syntax...
> Parsing your sentence as written ("if I only had"): If you were the
> sole keeper of the secret??
> Parsing it as intended ("if only I had"), and ignoring the smiley:
> Looks like a fairly straight-forward state-transition table to me.


> The
> column headings are not aligned properly in the message, b means blank,
> a-Z is bletchworthy, but the da Vinci code it ain't.
> If only we had an NDFA (whatever that is) for guessing what acronyms
> mean ...

I believe  (I am not a computer science major):

NDFA = non-deterministic finite automata


S: state
T: terminal
E: error

So, S1 means State #1..T1 means Terminal #1, so forth....

You are correct that parsing that table is not hard.

a) Set up a stack and place the buffer onto the stack, start with S0
b) For each character that comes from the stack, looking up the next state
for that token
c) If it's not a T or E state, jump to that state
d) If it's a T or E state, finish

More information about the Python-list mailing list