Re: Clarification on "Infinite parsing loops in IELR + LAC"

[Joel Denny]

Hi Adrian, Akim,

On 09/11/2018 12:47 AM, akim wrote:
> Hi Adrian,
>
> That would be a question for Joel, I don't know the details.

Thanks for alerting me to this.

> Le 2018-09-11 00:03, Adrian Vogelsgesang a écrit :
> > Hi everyone,
> >
> > From what I understand reading the bison documentation and some of the
> > linked publications,
> > I should probably be using IELR in combination with Lookahead-Correction

Do you have a specific use case in mind that requires these features, or 
have you chosen them because of their superiority in theory?

> > However, I stumbled across a warning in section 5.8.3 (“LAC”) in the
> > bison documentation
> > (https://www.gnu.org/software/bison/manual/bison.html#LAC):
> > > IELR plus LAC does have one shortcoming relative to canonical LR. 
> > > Some parsers generated by Bison
> > > can loop infinitely. LAC does not fix infinite parsing loops that 
> > > occur between encountering a syntax
> > > error and detecting it, but enabling canonical LR or disabling 
> > > default reductions sometimes does.
> >
> > This sounds quite frightening to me and I am not sure if LAC is
> > actually something I should be using.
> > Could someone clarify that part of the documentation for me?

The goal of IELR + LAC is to achieve canonical LR behavior with nearly 
LALR-sized parser tables.  The point of the statement you quoted is to 
clarify that IELR + LAC does not achieve canonical LR behavior for some 
grammars in the case of some syntax errors.  That statement does not 
describe some major flaw that is introduced by switching to IELR or LAC 
from a traditional Yacc/Bison-generated parser, which uses LALR without 
LAC, and which is less powerful.

> > In particular, I would be interested in the following points:
> > * The documentation only mentions IELR + LAC, but what about LALR + LAC?

Switching from IELR to LALR reduces the set of grammars that can be 
recognized.  In other words, it takes you even farther from canonical 
LR.  However, if you have a grammar that LALR is powerful enough to 
parse, IELR produces exactly LALR parser tables.  In that case, until 
your grammar evolves, IELR + LAC = LALR + LAC.

> > * "LAC *does not fix* infinite parsing loops" -> this sounds as if
> > these infinite parsing loops would also exist without LAC?

Exactly.

I suppose it's possible that one could write a semantic action to 
terminate the parse during one of these infinite parsing loops on a 
syntax error.  In that case, because LAC suppresses semantics actions 
while detecting the syntax error, LAC would prevent the semantic action 
from terminating the parse.  However, I don't recall ever encountering 
an actual semantic action written for such a purpose.

> > * When exactly do those infinite loops occur? How can I avoid them?

Infinite parsing loops are a known issue in the LR family, including 
canonical LR.  In my experience, they rarely occur in practical 
grammars, even when using LALR.  I see them mostly as a theoretical 
possibility that occurs in contrived grammars.  If you find that they 
occur for a practical grammar, please post it here.  Perhaps we should 
say something like this in the manual after the text you quoted?

In summary: Traditional Yacc/Bison (that is, LALR without LAC) < IELR + 
LAC < canonical LR.  However, the difference between IELR + LAC and 
canonical LR concerns an issue (infinite parsing loops on syntax errors) 
that appears to be rare for practical grammars.

Hope that helps.

Joel

> > Best,
> > Adrian
> >
> > _______________________________________________
> > address@hidden https://lists.gnu.org/mailman/listinfo/help-bison