I was reading about parsers and parser generators and found 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 of C++ causes it to be impossible to parse with LR parsers?
Using google, I only found that C can be perfectly parsed with LR(1) but C++ requires LR(∞).
ベストアンサー1
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:
- It can be the declaration of y, as pointer to type x
- 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, and therefore a program can mean different things depending on how this should have been parsed.
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 grammar ambiguous.
Thus pure LR parsing can't handle this. Nor can many other widely available parser generators, such as Antlr, JavaCC, YACC, or traditional Bison, or even PEG-style parsers, used in a "pure" way.
There are lots of more complicated cases (parsing template syntax requires arbitrary lookahead, whereas LALR(k) can look ahead at most k tokens), but only it only takes one counterexample to shoot down pure LR (or the others) parsing.
Most real C/C++ parsers handle this example by using some kind of deterministic parser with an extra hack: they intertwine parsing 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, etc.) are (at best) context free.
One can cheat, and add per-rule reduction-time semantic checks in the to LR parsers to do this disambiguation. (This code often isn't simple). Most of the other parser types have some means to add semantic checks at various points in the parsing, that can be used to do this.
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これらは完全な文脈自由パーサ（実質的に無限の先読みを持つ）である。GLRパーサは単に両方解析して、あいまいな解析を表す「ツリー」（実際にはほとんどがツリーのような有向非巡回グラフ）を生成します。解析後のパスであいまいさを解決できます。
私たちは、DMS ソフトウェア リエンジニアリング ツールキットの C および C++ フロントエンドでこの手法を使用しています (2017 年 6 月現在、これらは MS および GNU 方言で完全な C++17 を処理します)。これらは、大規模な C および C++ システムの何百万行にも及ぶ処理に使用され、完全かつ正確な解析によってソース コードの完全な詳細を含む AST が生成されます。(C++ の最も厄介な解析の AST。）