One approach is write a formal parser. The other extreme is to hack out some regexes.

How about both?

From the docs:

This technique makes it possible to use regexes to recognize complex, hierarchical--and even recursive--textual structures. The problem is that Perl 5.10 doesn't provide any support for extracting that hierarchical data into nested data structures. In other words, using Perl 5.10 you can match complex data, but not parse it into an internally useful form. An additional problem when using Perl 5.10 regexes to match complex data formats is that you have to make sure you remember to insert whitespace-matching constructs (such as \s*) at every possible position where the data might contain ignorable whitespace. This reduces the readability of such patterns, and increases the chance of errors (typically caused by overlooking a location where whitespace might appear). The Regexp::Grammars module solves both those problems.

See Re: Store data into array by looping? for an example case similar to yours.