Re: The rewrite rules matter

Bethan Tovey-Walsh <accounts@bethan.wales> writes:
> A further thought - I think some of the speed gains in Norm’s Earley
> parser may be coming from the reduction in epsilon transitions (if
> I’ve understood him correctly). If so, the rewriting to
>
> f, f-star | ()
>
> has the same problem as Norm’s original rewriting, in that it requires
> the parser to recognize the empty string as the final token of any
> starred sequence. Rewriting f* to
>
> f-plus | ()
>
> avoids that.

That’s consistent with my current understanding. I believe Bethan’s
formulation is faster because it generates fewer Earley items.

  f-star = (f, f-star) | ()

always requires a terminal transition through f-star => ().

> So I’m guessing your rewrite will work well for Norm’s GLL parser, but
> may wipe out some of the speed gains he’s reported for the Earley
> parser. I’ll try to persuade him to experiment and report back!

Perhaps. I have no intuition about the GLL parser yet.

I might give this a try. I’ll definitely start working on the “ways to
convert EBNF to BNF” note for the website.

                                        Be seeing you,
                                          norm

--
Norm Tovey-Walsh
Saxonica