I would like to comment on the claim that "all popular languages have context-free grammars, while C++ has undecidable grammar". Although I understand what is meant here, the terminology is just plain wrong. There are no such things as undecidable grammars. There are only undecidable problems. The C++ grammar is context-free, period. What gets people confused about it is that it is ambiguous, and that there are in fact two parsing problems you can associate to an ambiguous context-free grammar. One of them is decidable, the other is not in the case of C++.
The first parsing problem is what I would call textbook parsing, as this is what is usually presented in books on the topic. It is a decision problem: the answer is either "yes" or "no". For context-free grammars, including C++, it is always decidable. So what about the ambiguous `AA BB(CC);` given in example here? Is it an object definition or a function declaration? The (decidable) textbook answer is simply "yes". The key thing to understand here is that textbook parsing does not require resolving any ambiguities. The "context-free" in "context-free grammar" only refers to this decision problem, which is why C++ has a context-free grammar, because textbook parsing does not require looking at any surrounding context.
Of course, if you are writing a compiler, "yes" is not a very useful answer. You want either "yes, it is an object definition" or "yes, it is a function declaration", which turns the parsing problem into a completely different one, which I will call compiler parsing. Compiler parsing is not a decision problem, and in the case of C++, it is undecidable.
What is meant by "all popular languages have context-free grammars" is simply that most languages have an unambiguous context-free grammar. To add to the confusion, textbook parsing and compiler parsing are essentially the same problem for unambiguous grammars.
The first parsing problem is what I would call textbook parsing, as this is what is usually presented in books on the topic. It is a decision problem: the answer is either "yes" or "no". For context-free grammars, including C++, it is always decidable. So what about the ambiguous `AA BB(CC);` given in example here? Is it an object definition or a function declaration? The (decidable) textbook answer is simply "yes". The key thing to understand here is that textbook parsing does not require resolving any ambiguities. The "context-free" in "context-free grammar" only refers to this decision problem, which is why C++ has a context-free grammar, because textbook parsing does not require looking at any surrounding context.
Of course, if you are writing a compiler, "yes" is not a very useful answer. You want either "yes, it is an object definition" or "yes, it is a function declaration", which turns the parsing problem into a completely different one, which I will call compiler parsing. Compiler parsing is not a decision problem, and in the case of C++, it is undecidable.
What is meant by "all popular languages have context-free grammars" is simply that most languages have an unambiguous context-free grammar. To add to the confusion, textbook parsing and compiler parsing are essentially the same problem for unambiguous grammars.