Depending on the exact value of "complex" you might be able to get by with JSON (links to Java implementations at that link, with either JSON::XS or JSON::Syck on the Perl side) or YAML (YAML::Syck on the Perl side, again links to Java implementations at link). SOAP::Lite might be worth investigating as well.