Re: Theory about DFA's and f?lex start states

pcj1@my-deja.com wrote:
>However, the implementation I've been working on uses stack
>instructions to maintain the current start_state. Thus, rather than
>lex rules which explicitly say "BEGIN(COMMENT)", it might say
>"PUSH(COMMENT)" and "POP()". I've been describing the automata that
>can be used to recognize such grammars as "Deterministic Pushdown
>Finite Automata" (DPDFA's).
>
>My reason for posting however is to ask if people know of any research
>or investigation into the types of languages that are described by
>flex-like regular grammars (ie the combination of DFA's and STATES). Is
>there theory for this stuff or are multistate lexers just a pragmatic
>incremental improvement on DFA research?


[Its not Arpil 1st is it?]


Yes there's lots of research on these things, though they're usually
referred to as D-PDAs (Deterministic Push Down Automata). They're the
technique used by yacc and similar tools to parse CFGs.


The standard intro textbook on this topic is the Hopcroft & Ullman
automata book (which I don't have right in front of me, or I'd give
you the actual title and ISBN).


Chris Dodd
chrisd@reservoir.com
[Oh, right, it's true, a state machine plus a state stack basically gives
you yacc. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.