Limits of regular languages

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

Return to the comp.compilers page.
Search the comp.compilers archives again.