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

More efficient linearization #16

Open
cdfa opened this issue Feb 3, 2022 · 0 comments
Open

More efficient linearization #16

cdfa opened this issue Feb 3, 2022 · 0 comments
Labels
enhancement New feature or request performance Issues that affect performance

Comments

@cdfa
Copy link
Owner

cdfa commented Feb 3, 2022

Currently, the number of linearization variations grows exponentially with the number of construction sites (in the worst case where none are nested).
This could be improved by finding parts of the grammar which naturally isolate syntax errors (and corresponding AST nodes) and only reparsing linearized variations of those parts.

In more detail (probably only comprehensible to me):

  1. Find stoppers by finding loops in the grammar. All parents outside the loop are stoppers.
  2. Partition AST based on isolated loops. This isolates syntax errors and reduces the number of linearizations
  3. Within each partition: decompose nodes on paths to (nested) construction sites instead of linearizing complete partition (combats exponential complexity of variations). Still generate exponential number of variations. This way, we can be conservative with the combination of ambiguity and nested construction sites
  4. Parsing only has to consider partitions
@cdfa cdfa added enhancement New feature or request performance Issues that affect performance labels Feb 3, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request performance Issues that affect performance
Projects
None yet
Development

No branches or pull requests

1 participant