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

    "Jonathan Barker" <ucapjab@ucl.ac.uk> wrote:


[snip of good analysis]


> The key point here is that a set of DFAs is the same as one big
> DFA. If I'm wrong, I expect that you'll find that a DPDFA is
> equivalent to one of the other well-known models of computation.
> It's just a matter of finding out which.


You have hit on some key points. One /can/ theoretically combine the
set of DFA's over M to generate D.


But stepping back from a practical standpoint for a second: Assume I'm
a developer writer trying to write a grammar for my new language. I'm
struggling to write the lexer because I've overloaded the syntax to
the point that I can't seem to achieve what I want because many of the
tokens have overlapping definitions (they cause conflicts in the
DFA). So the (natural?) thing is to try to partition those token
definitions into several distinct layers and switch between them when
appropriate.


The point I'm trying to make is that notion of "mode" arises from the
difficulty of trying to generate D from the set M.


This is not to say that one cannot find an alternative grammar that
/would/ be conflict-free. In many cases, people use this approach
because it is mentally less challenging to make several modes (states,
layers, contexts, whatever...) and switch between them rather than to
try to find a conflict-free grammar. But in other cases, I think that
no amount of wrangling can generate a deterministic automaton capable
of recognizing the prescribed tokens. They just conflict, and there's
no getting around it (I conjecture).


So what model of computation is this? I'm not too sure (the reason
for my original post). Given the additional thought, I think the
point of using stack instructions for switching between the elements
in M (DPDFA) versus explicit goto instructions (like flex) is not too
relevant. The important thing is that you have multiple "exclusive"
DFA's (using the word "exclusive" to mean that merging them would
cause conflicts) and that you are switching between them.


Taken to an extreme, it seems to "degenerate" into Turing behavior
(according to my gut). Each DFA looks like a procedure which contains
statements that call other procedures. In this case however there is no
concept of a return statement since a DFA never really ever "completes"
(it just keeps running until another procedure call is found).


Any thoughts? Mine are increasingly less productive as it is nearly
5am now.


Paul

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