You might want to look at Parse::RecDescent or at the various other Parse Modules, amongst which Parse::Yapp might be quite familiar to you if you are used to YACC.

An alternate way is to use regexps but it becomes really complex if you want to have tests and complex expressions.

One way, usually not bullet proof by a long shot, is to allow a subset (or a modified subset) of the Perl syntax so all you have to do is to check the syntax, maybe change a couple of items in the query and then eval it. If you sort of trust your users not to do anything too stupid and not to try to abuse the system then it might work.

If you want to play it safe (and spend some more energy) you will have to write an interpreter though. Parse::RecDescent comes with a _huge_ doc though, so you might be able to find something close to what you want in there.