This page is still very incomplete!
Regular expressions are a computer science construct, used to determine whether a string matches some sort of pattern. There are countless variations, including both syntactic and semantic changes. Let's start with the theory.
A regular expression consists of three features:
Concatenation. Two regular expressions may be written next to each other. The resulting large expression will match the input string if and only if a part of the input that matches the first small expression is immediately followed by a part that matches the second small expression.
Union. This is basically an "or" operation. The large expression will match the input if either of the small expressions matches the input.
Closure. Also called "Kleene closure" (prounced "KLEE-nee"). The small expression may be "repeated" zero or more times in order to match the input.
(I'm not using precise mathematical language here. If you need formal definitions, please consult a computer science textbook instead.)
The syntax in which these features are expressed varies widely between different implementations of regular expressions. For now, we'll stick with the syntax used by the Unix command egrep, because it's probably the most common. Here are some example of the three required features, using this syntax:
Concatenation. Regular expression ab matches an input string of ab.
Union. Regular expression a|b matches an input string of a or an input string of b. It does not match ab.
Closure. Regular expression a* matches the empty string, or an input string of a, or an input string of aa, etc.
Obviously, in order to have any practical use, these features must be combined together.
Regular expression f(oo|ee)t matches foot or feet.
Regular expression a(0|1|2|3|4|5|6|7|8|9) matches a0 or a1 or ... or a9.
Most regular expression implementations have shortcuts to greatly reduce the length and ugliness of common expressions. For example, in egrep, our previous example could be written:
Regular expression a[0-9] matches a0 or a1 or ... or a9.
The [...] syntax is called a character class, and specifies an implicit union operation. The resulting expression matches any single character that falls within the specified range. However, this relies on the ASCII ordering of characters. In the case of digits, there's not much danger; but in the case of letters of the alphabet, ASCII ordering cannot be safely assumed. Therefore, modern implementations of egrep use class names instead:
Regular expression a[[:digit:]] matches a0 or a1 or ... or a9.
Regular expression [[:alpha:]]0 matches a0 or B0 or ....
The character class [[:space:]] is particularly useful; it matches any character which is displayed as whitespace (including spaces, tabs, carriage returns, etc.).
Now the bad news: there are a plethora of incompatible regular expression syntaxes and feature sets in common use. It's nearly impossible to determine what a given regular expression means without knowing which tool is supposed to use it. Let's take a look at some of the common ones.
Extended Regular Expression (ERE). This is the syntax used by egrep.
ERE a+ matches a or aa or .... It does not match the empty string. In other words, the + means "one or more".
ERE ab? is equivalent to regular expression a(b|). It matches a or ab. In other words, the ? means "optionally once".
ERE a{3} is equivalent to regular expression aaa. It matches aaa only. In other words, "exactly three times".
ERE a{3,} is equivalent to regular expression aaaa*. It matches aaa or aaaa or any longer sequence of as. In other words, "three or more times".
ERE a{,3} is equivalent to regular expression |a|aa|aaa. It matches the empty string or a or aa or aaa. In other words, "up to three times".
ERE a{3,5} is equivalent to regular expression aaa|aaaa|aaaaa. In other words, "between three and five times".
Basic Regular Expression (BRE). This is the syntax used by the Unix commands grep and sed. In BRE syntax, operators like |, +, *, ?, {, and } mean literal characters and if you want them to have meaning as operators they must be prefixed with a backslash, so union becomes foo\|bar, one-or-more becomes a\+, a{3,5} is written a\{3,5\} and so on. Notably however, character classes and start/end anchoring are not backslash escaped, so in BRE [a-c] or ^foo means the same thing as in ERE.
Perl-Compatible Regular Expression (PCRE).
In most implementations, regular expressions are not anchored by default. This means the expression can match any part of the input string, rather than the entire input string. Thus, the BRE abc used in grep (for example) would match the input string abcdefg. If you want grep to act differently, you must specify whether your expressions are anchored at the start of a line, at the end of a line, or both:
grep '^abc' matches an input line of abcde but not 42abc or 42abcde. The ^ at the start of a BRE or ERE causes the expression to be anchored at the start of a line.
grep 'xyz$' matches an input line of tuvwxyz but not xyzzy. The $ at the end of a BRE or ERE anchors the expression at the end of a line.
grep '^abc$' matches an input line of abc only. The expression is anchored at both the start and end of a line.