I cannot comment on parser choices, however it is possible to approach this in such a way that this would become irrelevant.

If execution speed is a requirement, I would suggest not recompiling the QL strings every time. Instead I would suggest pre-compilation of the QL into some kind of AST (abstract syntax tree), and then stashing the tree (keyed by the original QL text) in a DBM::Deep file. A simple example might be:

# original QL code:
my $ql_code = 'select object() from Foo::Bar';

# parsed into something like this 
my $ast = [ select => [ 'object' ], [ from => 'Foo::Bar' ]]

# create the query db
my $query_db = DBM::Deep->new;

$query->{$ql_code} = $ast;
[download]

Then in your CGI scripts, they would just need to load the query database (DBM::Deep is very memory efficient so works quite well under CGI), and access the ASTs when it needs to run the QL. This basically elimnates the parse time from the equation entirely.

If you didn't want to have a seperate QL compilation step, you could lazily compile the QL. The first time you encounter a new QL statement, you could parse it and store the AST and then next time it is called it won't need to reparse.

This approach is similar to Python and the py/pyc files it makes. Of course you would still have the overhead of interpreting the AST, but I would guess that is not that bad compared to the parsing overhead.

If you wanted to take it one step further, you could compile the AST into a function which is tailored to the specific needs of the AST (probably using some heuristics here). The pre-compiled function would be generated as a string, so is easily persisted, and you just need to eval it each time you need to load it (which might eat up all the possible performance advantages). It might look something like this:

# assuming the query above
# the compiled sub might look
# something like this
sub {
    my $query_engine = shift;
    return $query_engine->select(
        'object', 
        $query_engine->from('Foo::Bar')
    );
}
[download]

This idea might be a little on the excessive side, so take it with a grain of salt.