Re:Perl Cannot Be Parsed: A Formal Proof
by haberman on Friday August 14, 2009 @01:32PM
(#763449)
In C++ that problem gets worse. To parse:
Template<params>::InnerDef * y;
...you have to know whether InnerDef is a type or a number. If it's a type, this is a declaration of a pointer y. If it's a number, it's a multiplication which is then discarded.
The problem is that to know whether InnerDef is a type or a number you have to instantiate Template<params>. But C++ templates are Turing-complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.3...), so performing this instantiation would be undecidable except that C++ defines a recursion depth limit.
The problem is that to know whether InnerDef is a type or a number you have to instantiate Template<params>. But C++ templates are Turing-complete: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.14.3...), so performing this instantiation would be undecidable except that C++ defines a recursion depth limit.
There's a nice writeup of this problem in the C++ FQA: http://yosefk.com/c++fqa/web-vs-c++.html.