Stories
Slash Boxes
Comments

Dev.SN ♥ developers

Log In

Log In

Create Account  |  Retrieve Password


Site News

Join our Folding@Home team:
Main F@H site
Our team page


Funding Goal
For 6-month period:
2020-01-01 to 2020-06-30
(All amounts are estimated)
Base Goal:
$3500.00

Currently:
$3500.00
100.0%
Stretch Goal:
$2000.00

Currently:
$1254.52
62.7%

Covers transactions:
2020-01-01 00:00:00 ..
2020-06-30 21:00:33 UTC
(SPIDs: [1207..1407])
Last Update:
2020-07-01 02:02:58 UTC
--martyb


Support us: Subscribe Here
and buy SoylentNews Swag


We always have a place for talented people, visit the Get Involved section on the wiki to see how you can make SoylentNews better.

Poll

How often do you click through and read the fine article?

  • Almost all the time
  • More often than not
  • Less often than do
  • When the topic interests me
  • Very rarely
  • Never - it would go against long-standing traditions!
  • Click what?

[ Results | Polls ]
Comments:0 | Votes:2

Site Funding Progress

Funding Goal
For 6-month period:
2020-01-01 to 2020-06-30
(All amounts are estimated)
Base Goal:
$2000.00

Currently:
$126.74
6.4%

Covers transactions:
2020-01-01 00:00:00 ..
2020-01-31 06:46:05 UTC
(SPIDs: [1207..1216])
Last Update:
2020-01-31 12:48:47 UTC
--martyb

posted by martyb on Saturday February 13 2021, @05:54PM   Printer-friendly

Title: Parsing C++ Is Literally Undecidable (2013)

--- --- --- --- Entire Story Below - Must Be Edited --- --- --- --- --- --- ---

Arthur T Knackerbracket has found the following story:

Many programmers are aware that C++ templates are Turing-complete, and this was proved in the 2003 paper C++ Templates are Turing Complete.

However, there is an even stronger result that many people are not aware of. The C++ FQA has a section showing that parsing C++ is undecidable, but many people have misinterpreted the full implications of this (understandable, since the FQA is discussing several issues over the course of its questions and does not make explicit the undecidability proof).

Some people misinterpret this statement to simply mean that fully compiling a C++ program is undecidable, or that showing the program valid is undecidable. This line of thinking presumes that constructing a parse tree is decidable, but only further stages of the compiler such as template instantiation are undecidable.

For example, see this (incorrect, but top-voted) Stack Overflow answer to the question What do people mean when they say C++ has “undecidable grammar”? This answer errs when it says: “Note this has nothing to do with the ambiguity of the C++ grammar.”

In fact, simply producing a parse tree for a C++ program is undecidable, because producing a parse tree can require arbitrary template instantiation. I will demonstrate this with a short program, which is a simplification/adaptation of what is in the FQA link above.

The parse tree for this program depends on whether TuringMachine::output is SomeType or not. If it is SomeType then ::name is an integer and the parse tree for the program is multiplying two integers and throwing away the result. If it is not SomeType, then ::name is a typedef for int and the parse tree is declaring a pointer-to-int named x. These two are completely different parse trees, and the difference between them cannot be delayed to further stages of the compiler.

The parse tree itself depends on arbitrary template instantiation, and is therefore the parsing step is undecidable.

In practice, compilers limit template instantiation depth, so this is more of a theoretical problem than a practical one. But it is still a deep and significant result if you are ever planning on writing a C++ parser.

Parsing, performance, and low-level programming.


Original Submission