Re:Proving that C++'s grammar is undecidable
by Kranar on Wednesday April 29, 2020 @11:33AM
(#23020422)
Template expansion is not separate from parsing in C++. That's the very thing this article explicitly demonstrates. A program will end up being parsed in two different ways depending on the solution to an instance of Post's Correspondence Problem. In one solution a declaration of x parses into a variable, in another solution a declaration of x parses into a function. Which of those two parse trees is actually correct? That question is not decidable and hence C++'s grammar is undecidable.
[ Parent
| on HN ]