The number of DFA states can explode exponentially. It's a real problem, especially if you're compiling untrusted expressions off the internet.

Evaluation is linear, but you're just evaluating your own password. In this scenario, it may make sense to just use a simple backtracking implementation, though as you alluded to early there aren't many simple ones around.