StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Regular expressions in their original form describe regular languages/grammars. Those cannot contain nested structures as those languages can be described by a simple finite state machine. Simplified you can picture that as if each word of the language grows strictly from left to right (or right to left), where repeating structures have to be explicitly defined and are static.</p> <p>What this means is, that no information whatsoever from previous states can be carried over to later states (a few characters further in the input). So if you have your symbol <em>w</em> you can't specify that the input <em>must</em> have exactly the same string <em>w</em> later in the sequence. Similarly you can't ensure that each opening paranthesis needs a closin paren as well (so regular expressions themselves are not even a regular language and thus cannot be described by regular expressions :-)).</p> <p>In theoretical computer science we worked with a very restricted set of regex operators, basically only consisting of sequence, alternative (|) and repetition (*), everything else can be described with those operations.</p> <p>However, usually regex engines allow grouping of certain sub-patterns into matches which can then be referenced or extracted later. Some engines even allow to use such a backreference in the search expression string itself, thereby allowing the expression to describe more than just a regular language. If I remember correctly such use of backreferences can even yield languages that are not context-free.</p> <p>Additional pointers:</p> <ul> <li><a href="https://stackoverflow.com/questions/612654/is-regex-in-modern-programming-langauges-really-context-sensitive-grammar">This</a> StackOverflow question</li> <li><a href="http://en.wikipedia.org/wiki/Regular_expression#Patterns_for_non-regular_languages" rel="nofollow noreferrer">Wikipedia</a></li> </ul>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload