9 Nov 2000 16:52:42 -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) |

[3 later articles] |

From: | chrisd@reservoir.com (Chris Dodd) |

Newsgroups: | comp.compilers |

Date: | 9 Nov 2000 16:52:42 -0500 |

Organization: | Reservoir Labs |

References: | 00-11-073 |

Keywords: | lex, parse, comment |

Posted-Date: | 09 Nov 2000 16:52:42 EST |

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]

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.