search

patrickhuber / Pliant

MIT License
26 stars 4 forks source link

Req: Performance comparison will be good #83

Open ArsenShnurkov opened 7 years ago

ArsenShnurkov commented 7 years ago

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

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

patrickhuber commented 7 years ago

Any insight into algorithm specifics?

ArsenShnurkov commented 7 years ago

may be this?

patrickhuber commented 7 years ago

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 notifications@github.com 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 https://github.com/patrickhuber/Pliant/issues/83#issuecomment-325209563, or mute the thread https://github.com/notifications/unsubscribe-auth/AALIfus5S52ELDcxG-UHElFVwPogN0vEks5scZuygaJpZM4PDV5z .

patrickhuber commented 7 years ago

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 commented 6 years ago

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