|Limits of regular languages email@example.com (e0726905) (2010-02-11)|
|Re: Limits of regular languages firstname.lastname@example.org (Matthias-Christian Ott) (2010-02-13)|
|Re: Limits of regular languages email@example.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 firstname.lastname@example.org (Max Hailperin) (2010-02-13)|
|Re: Limits of regular languages email@example.com (e0726905) (2010-02-27)|
|Date:||Thu, 11 Feb 2010 22:36:06 +0100|
|Posted-Date:||13 Feb 2010 11:33:13 EST|
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
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
Return to the
Search the comp.compilers archives again.