4 ms·
Follow-up question: without the grouping parentheses, is the regex language regular?
by tobinfricke 7y ago
Follow-up question: without the grouping parentheses, is the regex language regular?
- lonelappde 7y agoYes but it's mostly useless, since it can't match (variable-count) repeated strings of length greater than 1. Goruping isn't only about extraction.
- trisiak 7y agoYes, but you're taking too much. Without grouping, regex is weaker than regular languages. Grouping & capturing parentheses can stay. It's only the back-referrences that you need to remove.
- gbacon 7y agoRegex matching with backreferences is NP-hard. https://perl.plover.com/NPC/ https://perl.plover.com/NPC/
- saltcured 7y agoGrouping is very useful, but I think you can get pretty far in practical patterns with a limit of k-nesting for k=0..3 or so. That pattern language would still be regular.