Re: multistart: free choice of the start symbol

[Akim Demaille]

Hi Rici,

> Le 29 sept. 2020 à 19:20, Akim Demaille <akim.demaille@gmail.com> a écrit :
> 
> This feature, "start *", would generate quite larger automata.
> 
> In the case of Bison's own grammar, I get 450 states (that only x3,
> I was expecting more) *and* additional conflicts (because Bison is
> still using LALR for its grammar, so you can still have "subautomata"
> that share states).

Actually, there are no additional conflicts.  The conflicts I saw,
but had not looked at yet, are created because of symbols who don't
have ID, and they collided.  Indeed, in Bison's grammar we have
symbols such as 'string.opt', 'symbols.1' that are not identifiers,
and my WIP did not reject them as valid possible start symbols.

In other words, once you eliminate these symbols from %start, you
get a conflict-free parser.

Which is just luck.  One could easily build an example where
you'd get good ol' Yacc-style "mysterious conflicts".  For instance

> %start proc macro
> %%
> proc:   argument '.'  | parameter ';'
> macro:  argument ';'  | parameter '.'
> 
> argument: "id"
> parameter: "id"

Both proc and macro, individually, as conflict-free, but put together,
have states with common LR(0) cores, giving a LALR(1) conflict when
merged.

Fortunately that's exactly the kind of issue IELR fixes.

> What I did not anticipate though, is that it crashes when generating
> canonical LR on that grammar.  However, I not not yet investigated
> the impact of my changes in IELR and canonical LR, so that a TODO.

It's much harder to adjust IELR to take into account the changes
in the start state than I anticipate.  I'm making slow progress.

Cheers!