In addition regexps using up stack space diotalevi mentioned, there's also the problem of regexps that never return because they take too long to execute. It was last discussed in Timeout alarm for regex, with slow regular expressions as followup.