Why C++ cannot be parsed with a LR(1) parser?

Question

I were reading about parsers and parser generators when I hit upon this statement in wikipedia's LR parsing -page:

"Many programming languages can be parsed using some variation of an LR parser. One notable exception is C++."

Why is it so? What particular property in C++ causes it to be impossible to parse with LR parsers?

I first tried google and only found out that C can be perfectly parsed with LR(1) but C++ requires LR(∞). But then I think this is a good question. I understand that it must be very interesting reason why this is so.

(PS. wikipedia's parser articles make much more sense if you have already written couple of parsers yourself with parser generators or perhaps by hand, before that you do not really understand much about them. It's interesting how you need to use the tool to learn about how to build good one, but then.. so obvious)

Answer 1

There is an interesting thread on Lambda the Ultimate that discusses the LALR grammar for C++.

It includes a link to a PhD thesis that includes a discussion of C++ parsing, which states that:

"C++ grammar is ambiguous, context-dependent and potentially requires infinite lookahead to resolve some ambiguities".

It goes on to give a number of examples (see page 147 of the pdf).

Answer 2

I think you are pretty close to the answer.

LR(1) means:

Parsing from left to right needs only one token to look-ahead for the context,

whereas LR(infinity) means an infinite look-ahead. That is, the parser would have to know everything that was coming in order to figure out where it is now.

Answer 3

LR parsers can't handle ambiguous grammar rules, by design. (Made the theory easier back in the 1970s when the ideas were being worked out).

C and C++ both allow the following statement:

x * y ;

It has two different parses:

1. It can be the declaration of y, as pointer to type x
2. It can be a multiply of x and y, throwing away the answer.

Now, you might think the latter is stupid and should be ignored. Most would agree with you; however, there are cases where it might have a side effect (e.g., if multiply is overloaded). but that isn't the point. The point is there are two different parses.

The compiler must accept the appropriate one under the appropriate circumstances, and in the absence of any other information (e.g., knowledge of the type of x) must collect both in order to decide later what to do. Thus a grammar must allow this. And that makes the grammer ambiguous.

Thus LR can't handle this.

There are lots of more complicated cases, but only takes one to shoot down pure LR parsing.

Most real C/C++ parsers handle this by using some kind of deterministic parser intertwined with symbol table collection... so that by the time "x" is encountered, the parser knows if x is a type or not, and can thus choose between the two potential parses. But a parser that does this isn't context free, and LR parsers (the pure ones) are context free.

One can cheat, and add checks in the reduction proposal to LR parsers to do this disambiguation.

And if you cheat enough, you can make LR parsers work for C and C++. The GCC guys did for awhile, but gave it up for hand-coded parsing, I think because they wanted better error diagnostics.

There's another approach, though, which is nice and clean and parses C and C++ just fine without any symbol table hackery: GLR parsers. These are full context free parsers (having effectively infinite lookahead). GLR parsers simply accept both parses, producing a "tree" (actually a directed acyclic graph that is mostly tree like) that represents the ambiguous parse. A post-parsing pass can resolve the ambiguities.

We use this technique in the C and C++ front ends for the DMS Software Reengineering Tookit. They have been used to process millions of lines of large C and C++ systems, as well as dozens of other languages.

Answer 4

As you can see in my answer here, C++ contains syntax that cannot be deterministically parsed by an LL or LR parser due to the type resolution stage (typically post-parsing) changing the order of operations, and therefore the fundamental shape of the AST (typically expected to be provided by a first-stage parse).