The first C++ compiler (Cfront) compiled from C++ to C.
Once you get some C code that does things with structures and function pointers like a C++ compiler would do, I think it's not impossible to turn those back into classes if you can recognise the patterns that a C++ compiler uses to compile C++ constructs like classes, virtual functions, etc.
It's actually a lot harder than C. There is a roughly 1:1 correspondence between C and assembly. There is no such 1:1 correspondence between assembly and C++.
> There is a roughly 1:1 correspondence between C and assembly.
I'm afraid that hasn't been true for a number of years. Turn on the optimizer and the resulting assembly can be totally unrecognizable as a translation of what you actually wrote. The compiler takes all kinds of steps both to eliminate redundant operations (via CSE, loop unrolling, etc.) and to take advantage of the weird quirks of modern CPU architectures, like out-of-order execution.
Just yesterday I was debugging a piece of code I was writing. I started with a printf where I suspected a segfault was occurring.
printf(...);
for (...) {...}
The printf never executed. So I fired up gdb and confirmed the segfault was happening where I thought it was, but the for loop was being initialized before the printf. Even with debugging on and optimization off. Could be a bug in clang (I didn't think to try it with gcc), but even so it shows that the way things should work in theory don't necessarily dictate the way they do work in practice.
There is a roughly 1:1 correspondence between C++ and C, so it's just one more step to go from C to C++. Just off the top of my head...
class data fields -> structure members
non-static methods (ctors/dtors included) -> functions with an extra 'this' pointer parameter
inheritance -> extended structures with matching prefices
virtual functions -> structure with function pointers
operator overloading -> methods with special names
default arguments -> automatically inserted by compiler
function overloading -> types encoded in name of function
templates -> whatever code they generate
exceptions -> special library functions are used, e.g. _CxxThrowException()
Some of those don't decompile so well (e.g. template-generated code, although a refactoring tool might be of help), and things like operators and overloaded functions are probably more of a stylistic choice than a difference in the generated code, but for the most part it doesn't look impossible to get some C++ features to show up in decompiled code. (And given that many of the C++-level optimisations revolve around removing unnecessary code, they could make the C to C++ step even easier.)
Once you get some C code that does things with structures and function pointers like a C++ compiler would do, I think it's not impossible to turn those back into classes if you can recognise the patterns that a C++ compiler uses to compile C++ constructs like classes, virtual functions, etc.