3 ms·
Is that somehow special? CFG parsing is O(n^3) worst case using Earley's algorithm, regexp is faster. Back-references is a matter of inserting extra non-termina
by tgv 3y ago
Is that somehow special? CFG parsing is O(n^3) worst case using Earley's algorithm, regexp is faster. Back-references is a matter of inserting extra non-terminals. I once wrote a regexp to DFA with backreferences. I never checked the correctness, though.
- davidgay 3y agoThe perl version of regexps is np-hard... https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- teraflop 3y agoIt is easy to write a regexp with backreferences that cannot be represented by any DFA. So I'd say the correctness of your implementation is doubtful. For example, the language defined by the regexp /([ab]*)\1/ is neither regular nor context-free.
- tgv 3y agoMy bad. I had missed the fact that it was in the pattern.