Hacker News Reader

Comment by stevefan1999 | Hacker News Reader

stevefan1999

I used to learn the source code of TCC 4 years ago and the experience is...pretty awful. Until then, I never know that compilers aren't reentrant and is supposed to follow the Unix philosophy -- use global state but do your thing as minimalistic as you can then let people spawn your program as a process to turn a blind eye to lack of reentrancy. This means you can't embed TCC to your program without TLS or global lock to each compilation however, and I think I already lost my reentrancy patch cause the maintainers said they won't accept it :(

Now I carry on and would like to make a TCC rival. I also wondered if I can make a TCCPP until Iearnt not only C++ syntax is ambiguous (and so we need some form of context sensitivity, and GLR is one good technique to handle C++ type of thing) C++ templates are Turing-complete effectively meaning it will be hellish hard. I abandoned this idea thereafter.

View on HN

"I also wondered if I can make a TCCPP until Iearnt not only C++ syntax is ambiguous (and so we need some form of context sensitivity)"

I believe a C parser would also need some form of context sensitivity. "T * x;" can be a declaration or a statement. However, C++'s syntax is larger than C's and I believe that there may be more cases where context sensitivity is needed to resolve ambiguities.

https://eli.thegreenplace.net/2007/11/24/the-context-sensiti...

Another great piece by Eli on how Clang solves this problem and the nested functions inside C++ classes is https://eli.thegreenplace.net/2012/07/05/how-clang-handles-t....

Clang basicaly moves the semantic processing to another pass, and tokenizes both types and variables as ‘identifiers’.

I’d agree that C/C++ have some sort context sensitivity. However I think this is not an ambiguity. You can deduce a single logical solution when you see T *x; . If the T in scope is a variable you do multiplication, if the T in scope is a type definition you make a variable declaration.

Real ambiguity happens when there are two logical solutions to the same statement and the language specification has to prefer one to remove ambiguity and undefined behaviour.

For example a C# code example from spec that is ambigious and therefore doesn’t compile:

“ static void F(bool a, bool b) { Console.Writeline($”{a} and {b}”); }

static void Main(string[] args) { int G = 2; int A = 1; int B = 2; F(True, False); F(G<A, B>(7)); ”

The compiler prefers to interpret the last line as a function call with one argument, which is a call to a generic method G (that doesn’t exist in the code above) with two type arguments a one regular argument. Instead of one function call with two boolean arguments.

I vaguely remember C++ template crocodiles being white space sensitive some time ago when templates were nested at variable declaration.

Yes, the lexer considered >> as a single token, so you had to you write > >. The standard was changed in c++11 to allow the syntax; that definitely complicated parsing, but at least now heavily templated code looks a 100% less ugly.

It can be complicated even when it's not ambiguous. Consider:

   template<size_t N = sizeof(void*)> struct a;

   template<> struct a<4> {
       enum { b };
   };

   template<> struct a<8> {
       template<int> struct b {};
   };

   enum { c, d };

   int main() {
       a<>::b<c>d;
   }

This is not ambiguous, but the meaning of the line inside main() depends on the compiler and the target - it can be either a declaration:

   a<>::b<c> d;

or an expression:

   a<>::b < c > d;

depending on which b gets selected. This in turn affects future references to d etc.

Note that this is only an issue in non-generic context. For dependent names you have to disambiguate with "typename" and "template".

But yeah, it looks like a C++ compiler has to instantiate templates in lock-step with parsing to make this work, but possibly there are some tricks that are applicable here. In any case, this looks like a hard problem.

I am not familiar with C++ templates, but isn’t this a similar ambigious pattern? If the compiler doesn’t evaluate the sizeof’s before parsing, there are still more than one equally logical ways to parse it.

Nevertheless I think the C# way of choosing generics over comparison without semantic processing is strange. The example above should run as intended (as a simple function call with two arguments) and not fail because of some spec rule.

No, that typedef problem is what C++ inherited from C, which is easily handled if you have a Linear-bounded TM (actually, a long time ago I think if our parser is able to interpret different state by different extra memory (like symbol table and AST), it is actually mimicking a restricted TM...until I learnt about some details of Chomsky Hierarchy)

What I mean is something like "Foo<Bar<Baz>>", the ">>" part can be a little bit challenging because we don't know if this is a right shift or not without context

C++ is also Turing Complete that its template system can implement boundless recursion and infinitely expand on its own without termination...essentially it means it may not even halt. That's why template metaprogramming is a (hard and horrible) thing...it's a sublanguage that uses C++ syntax and generates C++ code making the parsing even more non-deterministic.

Reply on news.ycombinator.com