It may also be worth abandoning pure regular expressions in favor of a grammar-based parser. Parse::RecDescent comes to mind immediately, but there's also Regexp:Grammars if you'd like to stick to (spiced-up) regular expression after all.