It's probably too late now, but for the record I'd like to note that instead of using closures I'd prefer to build a "real" hash (or array) based abstract syntax tree (AST).

The reasons are:

• More flexible: when you expand your grammar you might run into things that are really hard and nasty to implement with closures, and much easier with an AST
• More options: with an AST you can not only evaluate it, but also print it out nicely, or optimize it, or store it easily with Storable, serialize it with yaml, json or XML and hand it to another tool.
• Easier debugging: It's much easier to dump the AST with Data::Dumper and the like
• It's easier to add meta information later on that is ignored by most parts of the implementation, but may produce better error messages (think of line number in the parsed source)

There are a few points in favor of closures, though: reading HOP, and perhaps speed (but I haven't seen benchmarks so far)