I'm very glad to hear this.

My poor head couldn't think of a reason for your problem, but fortunately the problem got exposed when the same happened with gcc 4.3.

Regex should be a part of glibc.
To actually answer the question: regex is an abbreviation for
regular expression, which is something like "a[Mm]ule" (matches "aMule" and "amule") or "c*ilation", which would match every word starting with 'c' and ending with "ilation", for instance "compilation".