3 ms·

Backreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out

Backreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.

Drup 7y ago
Actually, it's been proved for ... longer than PERL exists ? The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens. Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions. Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
- setr 7y ago
  >Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete. Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA. I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
abecedarius 7y ago
Backrefs are nonregular. I believe lookaround by itself is not a problem -- it's essentially intersection, which is regular (though often omitted from regex engines). Yeah, here's a reference: https://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto https://cs.stackexchange.com/questions/2557/how-to-simulate-...
umanwizard 7y ago
The proof that finite automata can’t implement backreferences is actually extremely simple: you need to remember all the text matches as part of any given capture group, in order to match it again as a backreference. This requires unbounded memory.
blaisio 7y ago
Replying to my own comment to clarify: it is true that you can't express a non-regular language with regular expressions. What I meant is, it is likely we can combine automata and backtracking based techniques to get the best of both worlds. In other words, an automata based engine doesn't necessarily mean you can't also have backreferences and still have efficiency gains.

Backreferences and look around. I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.

Drup 7y ago

Actually, it's been proved for ... longer than PERL exists ? The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens. Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions. Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.

setr 7y ago
>Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete. Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA. I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)

abecedarius 7y ago

Backrefs are nonregular. I believe lookaround by itself is not a problem -- it's essentially intersection, which is regular (though often omitted from regex engines). Yeah, here's a reference: https://cs.stackexchange.com/questions/2557/how-to-simulate-backreferences-lookaheads-and-lookbehinds-in-finite-state-auto https://cs.stackexchange.com/questions/2557/how-to-simulate-...

umanwizard 7y ago

The proof that finite automata can’t implement backreferences is actually extremely simple: you need to remember all the text matches as part of any given capture group, in order to match it again as a backreference. This requires unbounded memory.

blaisio 7y ago

Replying to my own comment to clarify: it is true that you can't express a non-regular language with regular expressions. What I meant is, it is likely we can combine automata and backtracking based techniques to get the best of both worlds. In other words, an automata based engine doesn't necessarily mean you can't also have backreferences and still have efficiency gains.