Comment by beat | Hacker News Reader

Comment by beat | Hacker News Reader

Parent Full thread

I go a little deeper and more esoteric with my big gripe with C++... why can't it be parsed with a simple LALR(1) parser?

Donald Knuth summed this up much more elegantly than I could ever hope to do so, in his six character critique of C++:

a < b > c;

What the hell does that mean? What it means is that you cannot determine the meaning of those six characters without knowing in advance the types of a, b, and c. Is it an odd-but-valid C comparison? (a is less than b and b is greater than c) Or is it a template declaration? You cannot know these things without context.

Back when I studied compiler theory and was reading the Dragon Book, the simplicity, elegance, and precision of the LALR(1) parser design really touched me. And it was implemented on every Unix box with lex and yacc. This is how you write a compiler! This is how you understand structure precisely! To be syntactically valid, a statement must have one and only one meaning.

C++ cannot be parsed without interpreting variable types at parse time. LALR(1) does not work. It never has worked. C++ has been broken on this front since the 1980s, when it was just a preprocessor that cross-compiled to C. Why? What possible benefit is there to giving up that core bit of parser discipline?

"Because it's powerful!", someone sneers, as if that condescension justified bad design. "Because templates are so hard!" another whispers. But what about this?

a [< b >] c;

If the template declaration tokens were [< >] rather than < >, they wouldn't overload the comparison operators. The meaning of Knuth's example would be unambiguous, and both could be parsed without grief - both by machines, and by human eyeballs. This isn't difficulty. It's just not thinking through the consequences.

But that's okay. Smoke enough of that << and >> crack, and you'll soon forget those tokens are bitwise shift operators, not i/o. Sigh.

Of all the complaints I can think of regarding C++, the one I care least about is the difficulty in disambiguating the grammar... Languages exist to help humans, not compilers. Of course, C++ often fails in that regard as well.

Aside, a pox on the house of bottom up parsers. Anyone trying to produce useful semantic errors out of a bottom up parser understands how god awful they are to work with. There's a reason both GCC and clang use hand rolled recursive descent parsers...

My first professional exposure to C++ was porting code across every Unix platform available in the late 90s, using a bunch of proprietary compilers. It was hell. Nothing was consistent. And of course, there were no unit test suites, and the programmers thought that if it compiled on HP-UX 9, it'd compile anywhere. So I have a real attitude about how the parsers work.

I have yet to see a reasonable explanation why C++ needs a type-aware compiler to accomplish its goals. I can't think of any other languages with this problem.

"I have yet to see a reasonable explanation why C++ needs a type-aware compiler to accomplish its goals."

Are you saying strong typing is a problem with C++ as a language? Or am I misunderstanding?

You can't assign a category to the tokens in something like "T * p" unless you know whether "T" is a type or not. Suppose you have the following line of code:

    T *p;

It means one thing if it were preceded by this, making the line a variable declaration:

    struct T;
    typedef struct T T;

It means quite another if it were preceded by this, making the line an expression:

    int T=5,p=0;

(This particular problem also affects C.)

Why is this a problem? Is your gripe that * is used for declaring pointers as well as for multiplication?

The specific details aren't too important. (Another example: "(T)-1" - very different interpretations depending whether we previously had "typedef int T" or "int T=10"). The problem is that a line of code can't be understood, not even at the most basic level of dividing it up into appropriately-categorized tokens and arranging it an appropriate tree-like structure, without having previously interpreted (to some extent) the code that precedes it.

From a practical perspective, this makes the compiler code more complicated, because now the parsed code has to be analyzed and the results fed back to the loop. As well as the obvious negative effects of code that's more complicated, this also means any code analysis tools that work with source code have to themselves do this same work. (For C, this probably isn't too much of a difficulty, but it's still annoying having to keep track of typedef names and so on just so you can parse it! For C++, it's a very big problem indeed, on account of how much stuff you have to keep on top of - and that's why C++ source analysis tools basically never worked properly once you got past a certain level of complexity until people started just using the compiler to do it.)

I don't have an in-depth background in this stuff, so it's possible there are also more abstract benefits from having a grammar that doesn't suffer from this sort of problem.

You are probably talking about static typing, not strong. Strong typing implies that there are no implicit type conversions which is not true for C++.

Oh god not this again...

> Of all the complaints I can think of regarding C++, the one I care least about is the difficulty in disambiguating the grammar

Compile time speed? Refactoring? Jump-to-definition? Autocomplete? Intellisense? Those are all important for UX, and a tricky-to-parse grammar makes those things mighty challenging.

Visual Studio does an almost-perfect job of this, and what is missing is not because of the parsability of C++. What's your point?

Those are all examples of semantic analysis (which is also a problem with C++, but has little to do with the grammar). A tricky grammar is simply a parsing problem.

C++ compilation times are absolutely ridiculous, esp. when compared to something like D which has greater expressiveness in its compile-time features.

Semantic analysis is a post-parse task. Difficulty of constructing the parse tree has no impact on consumers of the parse tree.

There's a reason both GCC and clang use hand rolled recursive descent parsers...

Another thing about recursive descent, besides the ability to generate very specific error messages, is that it's a naturally intuitive algorithm which is very similar to how humans mentally parse. Perhaps that's also why context-sensitivity is not a problem at all, since natural languages are AFAIK all context-sensitive.

Parser generators are complex, generate huge amounts of virtually undebuggable code, and require learning another language, yet are less flexible than recursive-descent. It's clear why they've fallen out of favour in comparison to simpler and more flexible parsing algorithms.

Natural languages are reasonably close to context-free, actually. There are some freaky constructions in Dutch and (some variants of) German that can't be generated by a CFG. They sometimes get called mildly context-sensitive.

If a computer struggles to parse unambiguously, it doesn't bode well for mortals.

Depends. Have computers do what computers do well, have humans do what humans do well. Humans are intuitive. They can make correct decisions from incomplete, ambiguous, or even incorrect data. What humans suck at is precise, repeatable thinking - like parsing. Meanwhile, computers are great at generating repeatable results from consistent data very quickly, but absolutely cannot make decisions. Even conditional statements aren't actually "decisions".

So a language can be hard to parse unambiguously for machines, but it can be pretty straightforward for humans - like pretty much any natural spoken language.

Try insert "English" between "parse" and "unambiguously" and you can see how patently false your assertion is.

I had English in mind when I wrote that comment.

https://en.wikipedia.org/wiki/List_of_linguistic_example_sen...

It has knock on effects, even now there aren't really any great refactoring tools for C++ like there are for C# or Java.

What does Resharper not do for C++ that you'd like it to do? I know there are some areas that aren't as well-covered as the C# version, I'm just wondering in what real-world those make a difference (my experience is relatively short so I'm probably missing things)

> Languages exist to help humans, not compilers.

Until you realize that there is rarely any proper tooling around the language, which would be really helpful to humans!

I can list clang and cppcheck on Linux, but nothing else so far. Some of the clang related tools still choke on some parts of C++ though, so even that isn't close.

While this is a legitimate complaint, it also applies (though in fewer ways) to C. How do you parse this?

  (x)(y);

Is that a call of function (or function pointer) `x` with argument `y`? Or is it a cast of `y` to type `x`? You need to have kept track of of all the typedefs in the code prior to that point to know.

Another one:

  x * y;

Is that a multiplication, whose result is being thrown away, or a declaration of a variable y of type pointer-to-x?

Good point. But keep in mind that C predates C++ by over 15 years. There were tremendous advances in theory in that time. It's not completely fair to compare a hacker's tool from 1970 with a state of the art academic exercise from 1987.

Early versions of C date to 1972, while early versions of C++ (called C with classes back then) date 1979, only 7 years later, probably a few rooms down the hall from where C was originally developed.

True, templates came much later, but by then C++ was already hopelessly unparsable by LALR(1) parsers. But in truth, it was this way from moment 0, since it was based on C-syntax. Making it parsable by yacc was a lost cause, since yacc followed C and not the other way around.

By itself it's almost certainly a function call with a discarded return. The result is not assigned to anything.

It depends on the context though. Code like

  vector<int> years;
  list<string> names;

is pretty easy to wrap your brain around.

> Is it an odd-but-valid C comparison? (a is less than b and b is greater than c)

That's not the C comparison, that's a Python chained comparison. A C comparison will parse this as `(a < b) > c`, and you'll get false for a=3, b=5 and c=1.

This is pretty much solvable with a preprocessor and some heuristics and you get to keep your LALR parser

Also IMHO a<b>c should not exist as a comparison. Does this mean a<b AND b>c? Then spell it out, it's a rare case and it doesn't contribute to readability (as opposed to a<b<c for example)

> Also IMHO a<b>c should not exist as a comparison. Does this mean a<b AND b>c? Then spell it out, it's a rare case and it doesn't contribute to readability (as opposed to a<b<c for example)

Both are probably broken anyway. The first one will compute as (a < b) > c, and the second one as (a < b) < c. Unless you're using Python which has chained comparison, which has its own pitfalls e.g. `a < b == c > d` may not do what you want (it's equivalent to `a < b and b == c and c > d`, not `(a < b) == (c > d)`)

Reply on news.ycombinator.com