14 Nov 2000 13:06:01 -0500

Related articles |
---|

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

Re: Theory about DFA's and f?lex start states broeker@physik.rwth-aachen.de (Hans-Bernhard Broeker) (2000-11-09) |

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) |

[1 later articles] |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 14 Nov 2000 13:06:01 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

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

Keywords: | lex |

Posted-Date: | 14 Nov 2000 13:06:01 EST |

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)

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.