What do people mean when they say C++ has "undecidable grammar"?
What do people mean when they say this? What are the implications for programmers and compilers?
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):
What it probably means is that C++ grammar is syntactically ambiguous, that you can write down some code that could mean different things, depending on context. (The grammar is a description of the syntax of a language. It's what determines that a + b is an addition operation, involving variables a and b.)
For example, foo bar(int(x)); , as written, could be a declaration of a variable called bar, of type foo, with int(x) being an initializer. It could also be a declaration of a function called bar, taking an int, and returning a foo. This is defined within the language, but not as a part of the grammar.
The grammar of a programming language is important. First, it's a way to understand the language, and, second, it's part of compiling that can be made fast. Therefore, C++ compilers are harder to write and slower to use than if C++ had an unambiguous grammar. Also, it's easier to make certain classes of bugs, although a good compiler will provide enough clues.
If "some people" includes Yossi Kreinin, then based on what he writes here ...
Consider this example:
x * y(z);
in two different contexts:
int main() {
int x, y(int), z;
x * y(z);
}
and
int main() {
struct x { x(int) {} } *z;
x * y(z);
}
... he means "You cannot decide by looking at x * y(z) whether it is an expression or a declaration." In the first case, it means "call function y with argument z, then invoke operator*(int, int) with x and the return value of the function call, and finally discard the result." In the second case, it means "y is a pointer to a struct x, initialized to point to the same (garbage & time-bomb) address as does z."
Say you had a fit of COBOLmania and added DECLARE to the language. Then the second would become
int main() {
DECLARE struct x { x(int) {} } *z;
DECLARE x * y(z);
}
and the decidability would appear. Note that being decidable does not make the pointer-to-garbage problem go away.
链接地址: http://www.djcxy.com/p/74860.html上一篇: 从c ++代码中获取可读的AST