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

Needed mechanism for incremental generation of parsing trees #2

Open
lagodiuk opened this issue Dec 6, 2015 · 1 comment
Open

Needed mechanism for incremental generation of parsing trees #2

lagodiuk opened this issue Dec 6, 2015 · 1 comment

Comments

@lagodiuk
Copy link
Owner

lagodiuk commented Dec 6, 2015

Description of existing functionality:
Currently, parsing trees from the parsing forest - are being generated all at once. In the worst case - such behaviour might lead to exponential runtime complexity and exponential consumption of memory (in case of ambiguous grammar).

TODO:
It is possible to avoid exponential consumption of memory - by developing logic for incremental generation of parsing trees (e.g. using event-handler based approach). This change - requires slight reworking of parsing forest generation logic.

@lagodiuk
Copy link
Owner Author

lagodiuk commented Sep 4, 2016

I have started to work in the scope of branch: treverse_parse_forest_using_generators
I try to make use of ES6 mechanism of generators, in order to make the logic of the traversal of parse forest lazy (instead of eager), which should help to avoid the exponential consumption of memory.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant