Because that's what I took away from reading about C++ templates - the turing-completeness happens at the parsing/preprocessing stage, before the compiler's code generator even starts translating. Was I wrong? Wouldn't a smart IDE that resolves types (for example for tab completion or type hints), looking at the Factorial<N> thing, have to solve for the value for Factorial<4>?
No. (You need parse all includes to know typedefs, but that's it.)
C++ is awkward for a different reason, but there's nothing unparseable about it. Resolving types for tab completion/hinting is getting closer to static analysis (at least, with C++ it is), but parsing is well and truly done by that stage.
There's nothing about template<4> that can't be parsed, and nothing about the templates or instantiations thereof causes the syntax to be interpreted differently; this is probably the requirement for a parser to be Turing complete.
Perl is actually unparseable without execution: you can modify the allowed syntax mid-parse, based on some condition known only at runtime. Nothing about a template argument (for example) in some call causes a later template definition to be interpreted according to different syntax rules.
You can't parse lisp without running reader macros.
You can't parse TeX without running parts of it.
You can't parse C without parsing header files. (Ok, that one is as bit different, because header files are just C code as well).