You should listen to the other monks who directed you to modules. But I wanted to take a stab at doing it in a regex. This code seems to work:

#!perl  -w
use strict;

for my $y ( 1753 .. 9999 )
{
for my $m ( 1 .. 12 )
{
for my $d ( 1 .. 31 )
{
my $date = sprintf "%04d/%02d/%02d", $y, $m, $d;

if ( $date !~ 
m/^
########################
# Year 
([2-9]\d{3}|1[89]\d\d|17[6-9]\d|175[3-9])
\/ #####################
# Month
(0[1-9]|1[0-2])
\/ #####################
# Day
(
0[1-9]|1\d|2[0-8]|  # 01 - 28
(?<=(?:0[13578]|10|12)\/)(?:29|3[01])| #  to 31
(?<=(?:0[469]|11)\/)(?:29|30)| #  to 30
(?<=(?:
    (?:2[048]|3[26]|4[048]|5[26]|6[048]|7[26]|8[048]|9[26])00|
    \d\d(?:0[48]|1[26]|2[048]|3[26]|4[048]|5[26]|6[048]|7[26]|8[048]|9
+[26])\/02\/)
    )(?:29) # Leap year
)
########################
$/x 
)
{
print "$date is invalid\n";
}
# Else $1 == year, $2 == month, $3 == day
}}}
[download]

Of course, different countries switched to the Gregorian calendar at different dates, so you really need a module to get it right. My favorite tome on the topic is "Calendrical Calculations" by Edward M Reingold and Nachum Dershowitz.

Update: I realized that I made a mistake listing leap-years. I've now fixed that, but it further demonstrates why a module is better.