Why can’t C++ be parsed with a LR(1) parser?

by

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, 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.
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 our
DMS Software Reengineering Tookit (as of June 2017
these handle full C++17 in MS and GNU dialects).
They have been used to process millions of lines
of large C and C++ systems, with complete, precise parses producing ASTs with complete details of the source code. (See the AST for C++’s most vexing parse.)

More Related Contents:

  1. C++ if statement/xcode [closed]
  2. program to delete certain text which is predefined in another file from a file in c++
  3. C++ What’s the standard way to define a recursive constructor?
  4. How can I read and parse CSV files in C++?
  5. How to parse a string to an int in C++?
  6. Why does reading a record struct fields from std::istream fail, and how can I fix it?
  7. Parsing a comma-delimited std::string [duplicate]
  8. Regular expression to detect semi-colon terminated C++ for & while loops
  9. Boolean expression (grammar) parser in c++
  10. Parse (split) a string in C++ using string delimiter (standard C++)
  11. Is C++ context-free or context-sensitive?
  12. int a[] = {1,2,}; Why is a trailing comma in an initializer-list allowed?
  13. Convert string to int with bool/fail in C++
  14. Assigning parsers to auto variables
  15. Cross-platform way to get line number of an INI file where given option was found
  16. parsing math expression in c++
  17. How do you convert a C++ string to an int? [duplicate]
  18. How to parse ini file with Boost
  19. Good tools for creating a C/C++ parser/analyzer [closed]
  20. Parsing strings of user input using the cparse library from git
  21. Parse quoted strings with boost::spirit
  22. C++ Remove punctuation from String
  23. Spirit-Qi: How can I write a nonterminal parser?
  24. C++ Templates Angle Brackets Pitfall – What is the C++11 fix?
  25. Writing a simple equation parser
  26. std::lexical_cast – is there such a thing?
  27. Safer but easy-to-use and flexible C++ alternative to sscanf()
  28. Constraining the existing Boost.Spirit real_parser (with a policy)
  29. C/C++ JSON parser [closed]
  30. Parse string containing numbers into integer array

Leave a Comment