Templates are already being parsed into an AST and caching of that complete AST is already a solved problem.
Your task amounts to two things: get those expressions parsed and then get them evaluated prior to the method call.
To start, i would look into how Velocity is using JavaCC (see the org.apache.velocity.runtime.parser package and the Parser.jjt file).
Also familiarize yourself with how method calls are resolved and executed.
Last, be aware that
VELOCITY-819 will be updating the parser generation process shortly. You might consider applying that patch locally. I expect to find time to push it into the trunk this weekend or early next week, though i hope someone else beats me to it. I'm too damn busy these days...