19 Nov 2000 20:28:28 -0500

Related articles |
---|

[2 earlier articles] |

Re: Theory about DFA's and f?lex start states chrisd@reservoir.com (2000-11-09) |

Re: Theory about DFA's and f?lex start states pcj1@my-deja.com (2000-11-11) |

Re: Theory about DFA's and f?lex start states cfc@world.std.com (Chris F Clark) (2000-11-14) |

Re: Theory about DFA's and f?lex start states joachim_d@gmx.de (Joachim Durchholz) (2000-11-14) |

Re: Theory about DFA's and f?lex start states ucapjab@ucl.ac.uk (Jonathan Barker) (2000-11-14) |

Re: Theory about DFA's and f?lex start states frank@gnu.de (2000-11-14) |

Re: Theory about DFA's and f?lex start states pcj1@my-deja.com (2000-11-19) |

Re: Theory about DFA's and f?lex start states cfc@world.std.com (Chris F Clark) (2000-11-21) |

Re: Theory about DFA's and f?lex start states joachim_d@gmx.de (Joachim Durchholz) (2000-11-21) |

Re: Theory about DFA's and f?lex start states vbdis@aol.com (2000-11-22) |

From: | pcj1@my-deja.com |

Newsgroups: | comp.compilers |

Date: | 19 Nov 2000 20:28:28 -0500 |

Organization: | Deja.com - Before you buy. |

References: | 00-11-073 00-11-080 00-11-083 00-11-100 |

Keywords: | lex, theory |

Posted-Date: | 19 Nov 2000 20:28:28 EST |

"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

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.