| |||||||||||||
Full regular expressions?Full regular expressions?Posted Mar 14, 2010 10:50 UTC (Sun) by ballombe (subscriber, #9523)In reply to: Full regular expressions? by Pc5Y9sbv Parent article: Google's RE2 regular expression library
> Don't some of the back-referencing extensions actually take it from regular deep into LR(1) languages?
This is much much worse. Languages defined with general back-references are undecidable, and even the simplest kind of back reference can cause languages not to be algebraic, for example ([ab]*)\1 and (a*)(b*)\1\2 are not.
Now, all true regular expressions can be matched in linear time and bounded memory. However both the memory bound and the setup time (before starting the match) are in the worse case exponential in the size of the expression.
(Log in to post comments)
|
|||||||||||||