I've tried many things, from SQL::Statement to Parse::RecDescent. I looked at Parse::Yapp, and even considered shishi. What did those modules get me? A lot of frustration.
This afternoon, after another losing bout with Parse::RecDescent, I threw up my hands.
At that point, I went back to first principles and wrote a simple tokenizer. In goes the SQL, out comes some standardized tokens. The best part? It was easy. Regexp::Common helped with quoted strings, and I was in the home stretch. A simple state machine later, and I had a working SQL-like search tool.
Lesson: Sometimes a pre-existing modules isn't the way to go. It can overcomplicate things and make you work in the wrong direction. KISS works!