search

ollef / Earley

Parsing all context-free grammars using Earley's algorithm in Haskell.
BSD 3-Clause "New" or "Revised" License
361 stars 24 forks source link

Is Earley’s implementation related to Marpa? #36

Open Profpatsch opened 6 years ago

Profpatsch commented 6 years ago

The author of Marpa claims it to be an improvement over Joop Leo’s ’91 paper.

Has Marpa influenced this library’s implementation?

ollef commented 6 years ago

I'm aware of Marpa but haven't been directly influenced by it.

Profpatsch commented 6 years ago

But buried in their paper is a solution to the zero-length rule bug. And this time the solution requires no additional bookkeeping.

Have zero-length rules been a problem in Earley?

ollef commented 6 years ago

Yeah, that's been very tricky to get right, especially when you want to do semantic actions as well. This library uses the approach from the linked paper. But maybe it can be improved still.