Trying to solve the conflict in the grammar found out about %glr-parser which branches on all ambiguities creating copies of the parser and solves the problem that is created because of the inability of the parser to read more than one token. Looking for examples of using glr I didn’t find any serious questions that arose from this:

  1. Why is it so rarely used? Does he have any problems?
  2. How much worse is the parsing speed when using it?
  • Suppose speed is a problem. - VladD
  • It is usually easy to turn a grammar into an unambiguous one by a small change. For example, instead of ambiguous Expr ::= Expr + Expr | Expr - Expr | Term Expr ::= Expr + Expr | Expr - Expr | Term Expr ::= Expr + Expr | Expr - Expr | Term use the left-recursive grammar Expr ::= Term + Expr | Term - Expr | Term Expr ::= Term + Expr | Term - Expr | Term Expr ::= Term + Expr | Term - Expr | Term or right-recursive grammar Expr ::= Expr + Term | Expr - Term | Term Expr ::= Expr + Term | Expr - Term | Term Expr ::= Expr + Term | Expr - Term | Term (respectively for LR or LL parser). - VladD
  • (That is, on the contrary, LL- and LR-.) - VladD
  • @VladD you have an example in which to do it easily. and I will give an example in which it is difficult. for example, C ++. It is impossible without a symbol table or glr parser to parse the construction scopeid :: id because of the grammar C ++. Or everyone's favorite uncertainty x * y . But the glr parser will allow this. - Ilya Chizhanov
  • And is x * y ambiguity disposable without the help of lexer hack? Or are there several parse trees? - VladD

1 answer 1

The GRL parser adds a lot of minuses to its great advantage (the ability to parse almost any grammar and solve any ambiguity).

Here are the minuses that I found:

  1. In the answer, I gave a restriction of the type of semantic value. Not deadly but unpleasant.

  2. Delayed action. This is well written to the docks (see 1.5.3.1).

  3. Because in case of conflicts the parser starts branching then it is impossible to use the return value in the lexer. Well, the delayed action here also affects. This can not cope.

  4. Some grammars can cause unexpected problems when parsing conflicts with which the LALR parser does well. Here we need an analysis of the grammar, which means that not any LALR grammar will suit the GLR parser.

  5. If after parsing different parts of the conflict both parsers are alive, then it is necessary either to set priorities or to make merge. And merzh it always hurts.

And in terms of speed it is difficult to say something. The work of the GRL parser is not linear and very dependent on grammar. But the approximate (very approximate) complexity will be O (2 ^ n) where n is the number of conflicts since on each conflict, the parser branches into two other parsers which, in turn, can also branch.

Write in the comments if you know some more minutes and I will add them to the answer.