[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: multistart: free choice of the start symbol

From: Akim Demaille
Subject: Re: multistart: free choice of the start symbol
Date: Sun, 4 Oct 2020 16:19:53 +0200

Hi Rici,

> Le 29 sept. 2020 à 19:20, Akim Demaille <> 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

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]