Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize Right Recursion in Earley Parser #20

Open
srhickma opened this issue Aug 28, 2018 · 1 comment
Open

Optimize Right Recursion in Earley Parser #20

srhickma opened this issue Aug 28, 2018 · 1 comment
Labels
difficulty/hard This is a difficult or large issue enhancement New feature or request

Comments

@srhickma
Copy link
Owner

srhickma commented Aug 28, 2018

Right recursion runs in quadratic time with the Earley parser on grammars that can be parsed in linear time by LR(k) parsers. Ideally we should optimize the parser, but for the time being, grammars should be rewritten to use left-recursion instead.

Take a look at:
http://loup-vaillant.fr/tutorials/earley-parsing/right-recursion
https://github.com/jeffreykegler/kollos/blob/master/notes/misc/leo2.md

@srhickma srhickma added bug Something isn't working help wanted Extra attention is needed labels Aug 28, 2018
@srhickma srhickma self-assigned this Aug 28, 2018
@srhickma srhickma mentioned this issue Sep 3, 2018
@srhickma
Copy link
Owner Author

srhickma commented Dec 3, 2018

The urgency of this has been dwarfed by other improvements in #12, and this should be moved to the backlog.

@srhickma srhickma added enhancement New feature or request and removed bug Something isn't working help wanted Extra attention is needed labels Dec 3, 2018
@srhickma srhickma removed their assignment Dec 3, 2018
@srhickma srhickma added the difficulty/hard This is a difficult or large issue label Jun 23, 2019
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
difficulty/hard This is a difficult or large issue enhancement New feature or request
Projects
None yet
Development

No branches or pull requests

1 participant