I am mostly an autodidact and learned bits regex on the fly when I needed it and I was always baffled why people have auch a hard time with it.

The problem IMO is that a lot of the traditional teaching material starts with the complexity (and impressive possibilities) of regex, when the best way to start learning it is probably just thinking about it as an extension to simple text matching.

Getting to know regex fully is in fact complicated, getting know enough regex to filter/search/replace 90% of everything you will always need is not too complicated.

▲ ogogmad 6 hours ago | parent [-]

Autodidact here. Beyond just the five core quantifiers

  .
  |
  ?
  *
  +

regex only has capture groups

()

and lazy variants of the core quantifiers "?", "*" and "+", which are helpfully called:

  ??
  *?
  +?

The rest is just shorthands.

So while I think it's a worthwhile suggestion not to show people the whole thing the first time round, I doubt that the whole thing is really that complicated.

▲ ryangittins an hour ago | parent | next [-]

> The rest is just shorthands.

If you really want to get technical: ., ?, and + are also shorthands. The formal definition of a regular expression is very minimal on purpose.

`.` is just `(a|b|c|...)` - List of all literal characters

`x?` is just `(x|)` - "x or empty string"

`x+` is just `xx*` - "x followed by zero or more x characters"

Whether this is exactly how they are implemented in any particular regex engine is an implementation detail, but formally there are very few operations which aren't just syntactic sugar.

▲ StilesCrisis 5 hours ago | parent | prev [-]

Regex has many more features than this, e.g. backreferences. I agree that it's easy to learn enough regex to be dangerous with that subset, but that's not everything regex offers.

▲ ogogmad 4 hours ago | parent | next [-]

Backreferencing inside of a regex (which is a way to find repeat occurrences of a substring) is a very controversial feature that some regex engines intentionally omit, while most others support it only grudgingly. Supporting backreferences opens up a big can of worms: Most regex engines will fall back to a slow, poorly optimised algorithm if they ever encounter backreferences.

Also, it's important for people not to confuse backreferences with capture groups. They look a bit similar, but capture groups are actually fine.

In fact, backreferencing is such a footgun that I don't see it as a possible regex feature. It's a PCRE feature - perhaps even the core distinguishing feature. While all regexes are PCREs, not all PCREs are regexes. It's simply not possible to create a consistently performant implementation of PCRE.

▲ teiferer 3 hours ago | parent | prev [-]

There are hundred different flavors of what "regex" actually means. The basics are often the same but the extended features differ.

The foundation is in theoretical CS with deterministic and nondeterministic finite automata (DFAs and NFAs), and I found it easiest to teach regexes using DFAs since you can then just draw circles and arrows. Regex notation is just a different notation. It's a bit likeif you know piano and then learn another instrument, your brain can always refer back to the piano and it's all much easier.

Backreferences are not really "controversial" but just an extension which does not map to regular languages (those recognized by finite automata). That is, they make regexes "non-regular", so they are more a hack. Regex engines that want to support them need a fundamentally different approach, that's why some don't support them and in principle will never be able to.

▲ ogogmad 3 hours ago | parent [-]

They are controversial because supporting them raises matching time to O(2^n) in the worst case - which is dangerous - while not supporting them enables matching time to be O(n) in the worst case. And a user might not be aware of that danger.

Also, I think it's misleading to mention NFAs and DFAs alone, like there's no deeper reason. The deeper reason is that:

  Regexes (or NFAs, or DFAs) classify exactly the properties of strings which can be checked in constant space.

It turns out that any such string property can also be checked in O(n) time, and in one single left-to-right pass.

Briefly returning to backreferences, supporting them makes constant space unachievable. They also make linear time unachievable, since matching them becomes NP-COMPLETE.

Also, no regex implementation actually uses DFAs. NFAs yes, but DFAs no. The point of NFAs is that they're easy to execute in constant space and linear time, while also making concatenation and Kleene star easy to implement. It seems much harder to implement concatenation and Kleene star using most other constant-space automata - like DFAs - which is what actually forced people to invent NFAs.

	▲	teiferer 2 hours ago \| parent [-]
		I think we are actually on the same page, but it is funny that we express things in exactly the opposite way as well as reach opposite conclusions. :) It's not about being pedantic, quite the opposite It's intuitive to use circles and arrows as the mental model, instead of the cryptic regex syntax. Both have the same semantics. The quite visual representaton of the finite automata makes the meaning more approachable, not unlike the marble run illustration. In contrast, bringing "constant space" and "O(n) matching" and NP-completeness etc into the discussion is all formally correct (and I'm a big fan of formally correct) but that's where things become pedantic from the common folk's POV and is also where you lose people who just want to understand how something works practically. Therefore I'm saying, start withthe easy circles-and-arrows intuition and only go to the theoretical background (aka be pedantic) once people want to know more. (Backrefs can't be expressed with circles-and-arrows which illustrates why they are something special.)