10 Aug 2005 11:51:30 -0400

Related articles |
---|

Regular expressions speedup cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-08-05) |

Re: Regular expressions speedup haberg@math.su.se (2005-08-07) |

Re: Regular expressions speedup cleos@nb.sympatico.ca (Cleo Saulnier) (2005-08-07) |

Re: Regular expressions speedup haberg@math.su.se (2005-08-10) |

Re: Regular expressions speedup bonzini@gnu.org (Paolo Bonzini) (2005-08-10) |

Re: Regular expressions speedup dot@dotat.at (Tony Finch) (2005-08-10) |

Re: Regular expressions speedup kszabo@bcml120x.ca.nortel.com (2005-08-10) |

Re: Regular expressions speedup jburgy@gmail.com (2005-08-10) |

Re: Regular expressions speedup torbenm@diku.dk (2005-08-13) |

Re: Regular expressions speedup cleos@nb.sympatico-dot-ca.remove (Cleo Saulnier) (2005-08-13) |

From: | haberg@math.su.se (Hans Aberg) |

Newsgroups: | comp.compilers |

Date: | 10 Aug 2005 11:51:30 -0400 |

Organization: | Mathematics |

References: | 05-08-023 05-08-028 |

Keywords: | lex, practice |

Posted-Date: | 10 Aug 2005 11:51:30 EDT |

John Levine <johnl@iecc.com> wrote:

*> > The book by Aho, Sethi & Ullman, "Compilers...", end of sec. 3.7, says*

*> > that best for both space and time is a "lazy transition evaluation"*

*> > technique.*

*> [I wonder if they feel differently about space tradeoffs now than they*

*> did 30 years ago. At that point, programs had to fit into 16 bit address*

*> spaces. -John]*

A NFA to DFA translation may, in bad cases, result in an exponential

expansion, in which case no computer will suffice, no matter how much

memory it has. So in order to avoid that, one might use the suggestion

above. That is, translating the NFA to DFA transitions at need, caching

the partial DFA. The quote above also says that this lazy technique may be

faster than a full runtime NFA to DFA translation, in view of that unused

DFA transitions need not be computed.

--

Hans Aberg

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.