Parsing a search string

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


"John Machin" <sjmachin at lexicon.net> wrote in message
news:1104526960.929218.119480 at c13g2000cwb.googlegroups.com...
> 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.

Exactly.

> 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

and:

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