Hacker News new | ask | show | jobs
by trisiak 2482 days ago
Yes, 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.

2 comments

Regex matching with backreferences is NP-hard.

https://perl.plover.com/NPC/

Grouping 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.