When I read your question, one thought hit me, which was

DOM or SAX?

Basically, it appeared as if you asking whether to construct a parse tree and subsequently evaluate it, or whether you should shift/reduce tokens on the fly.

I think the answer is

It depends.

As to the level of complexity, I would agree that frequently in all but the simplest cases, you might want to take a look into CPAN, and see if your parsing job can be made easier by one of the many modules there. However, if it is simple enough, then parsing with regexes might be the appropriate solution to your needs. Sometimes it's just easier to use a regex in a while.

Again, it's a matter of the particular problem, the nature of the data, and your requirements for processing it.