News for hackers. Stuff that matters.

A comment on Is there a regular expression to detect a valid regular expression?. Parent comment

Re:Is there a regular expression to detect a valid regular e... by tobinfricke on Sunday September 08, 2019 @10:27AM (#20910733)
Follow-up question: without the grouping parentheses, is the regex language regular?
[ Parent | on HN ]
Re:Is there a regular expression to detect a valid regular e... by trisiak on Sunday September 08, 2019 @11:13AM (#20911009)
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.

[ Parent | on HN ]
Re:Is there a regular expression to detect a valid regular e... by gbacon on Sunday September 08, 2019 @03:36PM (#20912856)
Regex matching with backreferences is NP-hard.

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

[ Parent | on HN ]
Re:Is there a regular expression to detect a valid regular e... by saltcured on Sunday September 08, 2019 @04:47PM (#20913315)
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.
[ Parent | on HN ]
Re:Is there a regular expression to detect a valid regular e... by lonelappde on Sunday September 08, 2019 @10:32AM (#20910779)
Yes 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.
[ Parent | on HN ]