compiler construction - What do people mean when they say C++ has "undecidable grammar"?

Question

What do people mean when they say this? What are the implications for programmers and compilers?

Answer 1

This is related to the fact that C++'s template system is Turing complete. This means (theoretically) that you can compute anything at compile time with templates that you could using any other Turing complete language or system.

This has the side effect that some apparently valid C++ programs cannot be compiled; the compiler will never be able to decide whether the program is valid or not. If the compiler could decide the validity of all programs, it would be able to solve the Halting problem.

Note this has nothing to do with the ambiguity of the C++ grammar.

---

Edit: Josh Haberman pointed out in the comments below and in a blog post with an excellent example that constructing a parse tree for C++ actually is undecideable. Due to the ambiguity of the grammar, it's impossible to separate syntax analysis from semantic analysis, and since semantic analysis is undecideable, so is syntax analysis.

See also (links from Josh's post):

• C++ grammar: the type name vs object name issue
• C++ grammar: type vs object and template specializations