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

pcj1@my-deja.com asked:
> Since I'm obviously in the belief that "DPDFA" is a unique animal, I'm
> looking for more information about it such that I don't have to spin
> and or re-invent wheels (general laziness).


By restricting the states which can be pushed on the stack to start
states, you definitely restrict the grammar class. However, the
following argument shows that the restriction is not as significant as
one would think.


In a normal lexer and parser, the lexer uses DFA's to recognize tokens
but does not use a stack to switch states. The parser uses a stack,
but can only switch DFA states at token boundaries. Thus, a normal
lexer and parser pairing consist of an automata with a stack (the
parser) that can switch between several sets of lexer start states.
That combination looks essentially identical to the system you are
proposing.


The LR-regular model of parsing (Kulic) was one attempt at formalizing
the interactions between a DFA lexer (with unlimited lookahead) with
an LR parser (with limited lookahead).


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
3 Proctor Street voice : (508) 435-5016
Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

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