Re: Improvement in R/R Conflict resolution

[Akim Demaille]

Hi Jot,

> Le 15 déc. 2020 à 19:00, Jot Dot <jotdot@shaw.ca> a écrit :
> 
> Doing some googling, I have found the solution (or one of many solutions?)
> is to tie into the lexer and have it check the context for IDENTIFIER
> so that the lexer can discern the difference between a simple identifier
> or a typedef'd type; returning one token or another.
> (ie: return IDENTIFIER or say, TYPE_IDENT).
> We then change the parser grammar accordingly.

You don't need Google to find about this, just 'info bison' should do.
Look for lexical-tie in.

https://www.gnu.org/software/bison/manual/html_node/Lexical-Tie_002dins.html


> This is great for a single pass compiler. What if we want to check for
> syntactic correctness only at that point but push context sensitive issues
> into a second pass? Somehow we should be able to discern this ambiguity,
> mark it, and move on.

That's called GLR.  It's also in the documentation.


> THE CURRENT SOLUTION
> 
> As per: 
> https://www.gnu.org/software/bison/manual/html_node/Reduce_002fReduce.html
> Section 5.6 Reduce/Reduce Conflicts, Paragraph 6
> 
> quote: "Bison resolves a reduce/reduce conflict by choosing to use the rule
> that appears first in the grammar, but it is very risky to rely on this."

To be clear: we are not advocating that you accept the "resolution"
(I hate the word here, we are not resolving anything, we are just
shooting alternatives down until only one remains).  You should not
accept RR conflicts at all, period.



> THE PROPOSED SOLUTION:
> 
> Instead of having Bison pick the first one, we should allow the user to
> specify an alternate.
> 
> In the example shown above:
>    | ...
>    | storage_type '(' expr ')'
>    | storage_type '(' declaration ')'
>    | ...
> 
> Would it be possible to flag an alternate rule for the conflict?
> A proposal would be to introduce a directive to choose the reduction for
> a R/R conflict.
> 
> example:
>    | ...
>    | storage_type '(' expr ')'
>    | storage_type '(' declaration ')'
>    | %RR storage_type '(' IDENTIFIER '*' IDENTIFIER ')' // For ambiguous 
> context
>    | ...
> 
> In what I am doing, this is exactly what I want.

There are several problems with your proposal.

First, it is very narrow: it fits your need, but does not scale to
more complex cases of ambiguities.

Second, you are probably underestimating the difficulty of what you
are proposing.  On two accounts.  First, our generated parsers have
a single lookahead; not many, only one.  So the vast majority of these
annotations can simply not be taken care of by the parser.
Second, these resolutions must be processed by the generator to build
the shift-reduce automaton, and if you don't have an idea of how
technical and complex this is, I suggest that you have a look at this
paper, which is the basis for Bison's implementation of the state
machine generation:

https://hassan-ait-kaci.net/pdf/others/p615-deremer.pdf

Last, besides GLR, the true answer to your problem is the fusion
of the scanner within the parser (or pseudo-fusion), so that the
"context-free context" dependency is dealt with by the tool, not
by you.  But that's an extremely difficult task, already dubbed
Bison 4, which is not for the near future.


> If this makes sense, then it would not be as hard to introduce as one
> might think.

No, indeed, it is even more difficult than that :)  I suggest that
you read Joel E. Denny's PhD.


Cheers.