To me, this is the sort of problem that should be described in terms of a grammar, and then handled using Parse::RecDescent. (I have used that module quite extensively and it works very well.)
Let me give you one small tip if you go that way... Part of your code will consist of the grammar and Perl code that will be compiled on-the-fly into it. This is a great place to put a use statement(s) that will link to any subroutines that you find that you need to make use of in the grammar code.
Anyway, the advantage of this approach is that you describe the structure of the language being processed and let the parser do the magic. It takes a bit of practice to get the grammar right, heh, but the parser can handle the mechanics of regex’ing and backtracking so that your code doesn’t have to. You can extend it to do more things without getting buried.