Req: Performance comparison will be good

[ArsenShnurkov]

this implementation claimed to be fastest:
https://github.com/vnmakarov/yaep

it's readme file contain performance comparison with Marpa and yacc

[patrickhuber]

Any insight into algorithm specifics?

[ArsenShnurkov]

may be this?

[patrickhuber]

Ok, that's very interesting. It uses diffs instead of specific origins to determine if it can reuse an earley set. Also looks like it is caching at the set level rather than the item level. It can do that because of the diffs.

…

On Sun, Aug 27, 2017, 12:39 PM ArsenShnurkov ***@***.***> wrote: may be this <https://raw.githubusercontent.com/vnmakarov/yaep/master/Internals.txt>? — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#83 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AALIfus5S52ELDcxG-UHElFVwPogN0vEks5scZuygaJpZM4PDV5z> .

[patrickhuber]

After further digging, looks like a derivative of the DEEP (Directly Executable Earley Parser) with the addition of Frame grouping and origin differentials. I'll have to look into this further.

To speak to the original opened issue:

To get benchmarks, I'd have to pull in an ANSI C Grammar. I have one defined in bnf in the benchmarks project, but haven't used it to parse anything. I was mostly using it to test the bnf parsing.

[ArsenShnurkov]

speedup for special case
2010, Trevor Jim, Yitzhak Mandelbaum, Efficient Earley Parsing with Regular Right-hand Sides