search

softdevteam / lrpar

Rust LR parser
Other
1 stars 0 forks source link

Shift directly rather than using LR cactus #44

Closed ltratt closed 6 years ago

ltratt commented 6 years ago

After a couple of refactoring commits, this PR makes a major -- though not hugely intensive in terms of lines of codes -- change to the MF recoverer in https://github.com/softdevteam/lrpar/commit/982ea65f0a9d9c12e0f971e6e38ca755dd4f8ad0. This change then allows us to optimise the A* function significantly (https://github.com/softdevteam/lrpar/commit/cb9221c59e184dade7cfaab44b9814ad0c22d5b1, https://github.com/softdevteam/lrpar/commit/b4d4de27819bcc8ad6577aede0ee3ba6f6d9dbc4, and https://github.com/softdevteam/lrpar/commit/c615841e41193042ab4c2949f2e74351e64f2e51), with a final minor change (https://github.com/softdevteam/lrpar/commit/c615841e41193042ab4c2949f2e74351e64f2e51). The individual commits are extensively documented (I hope).

One thing that this PR ignores are grammars with shift/reduce reduce/reduce errors. At the moment those break the implicit guarantee that we can't ever search duplicates. That requires a fair few changes and I'd like to wait to a future PR.

In terms of performance, this makes my biggest standard example just over 3x faster, so it's a big difference.

ptersilie commented 6 years ago

Ready to be squashed!

ltratt commented 6 years ago

Squashed.

ptersilie commented 6 years ago

And merged.