I think I saw an article about something along those lines recently. But it was a 2-step process. First the Arduino detects something, and then using the existing Ethernet shields, and the ability to make a simple web client, sends a request to another web server running on a PC (or Mac, Linux, whatever).
So the Arduino might send a simple message like:
http://10.0.0.100/myscript.php?msg=cat_has_escaped
Then the PC-based device uses its gigabytes of memory and processing power to contact your cellphone.
Let's put it another way. On the PHP site I see that PHP 5.2.17 (tar.gz) is 11.5 Mb in size. And that's compressed. So there is no way you are going to fit PHP into 32 Kb of program memory.