Thu, 11 Feb 2010 22:36:06 +0100

Related articles |
---|

Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-11) |

Re: Limits of regular languages ott@mirix.org (Matthias-Christian Ott) (2010-02-13) |

Re: Limits of regular languages kkylheku@gmail.com (Kaz Kylheku) (2010-02-13) |

Re: Limits of regular languages cfc@shell01.TheWorld.com (Chris F Clark) (2010-02-13) |

Re: Limits of regular languages max@gustavus.edu (Max Hailperin) (2010-02-13) |

Re: Limits of regular languages e0726905@student.tuwien.ac.at (e0726905) (2010-02-27) |

From: | e0726905 <e0726905@student.tuwien.ac.at> |

Newsgroups: | comp.compilers |

Date: | Thu, 11 Feb 2010 22:36:06 +0100 |

Organization: | Compilers Central |

Keywords: | lex, question |

Posted-Date: | 13 Feb 2010 11:33:13 EST |

Hi,

I have been playing around with regular expressions for the last few

weeks, implementing the automaton generation algorithms from the dragon

book and taking at the existing tools.

Now a few questions have sprung, that I haven't been able to answer:

Is there a way implement the usual longest-match behaviour of a scanner

with a DFA without any backtracking mechanisms, meaning is that

behaviour strictly regualr or not?

I know that backreferences make a language non-regular (more about that

later), but what forms of capture are regualr? Are there any tools out

there who always answer membership in O(n) that support some kind of

subexpression capture? (Without having to hack around yourself with

embedded actions.)

I also have two rather unrelated questions that have been bugging me for

quite some time:

Is every regular language LL(1)? I know that every regular language is a

context-free language, and that every LL(1) language is also

context-free. But are all regular languages contained in LL(1)?

What class of language do regexes with backreferences fall into?

Membership is NP-Complete so they are not in CFG (or are they? assuming

P=NP?).

thanks, fabian

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.