What flavour of regular expression is grep?

Default GNU grep behavior is to use a slightly flavorful variant on POSIX basic regular expressions, with a similarly tweaked species of POSIX extended regular expressions for egrep (usually an alias for grep -E). POSIX ERE is what PHP ereg() uses.

GNU grep also claims to support grep -P for PCRE, by the way. So no terribly special kind of grep required.

POSIX BRE (Basic Regular Expressions)

You can compare the various flavors here.

There's a good write-up here. To quote the page, "grep is supposed to use BREs, except that grep -E uses EREs. (GNU grep fits some extensions in where POSIX leaves the behaviour unspecified)."

In other words, it's a long story. ;)