softdevteam / lrpar

Rust LR parser
Other
1 stars 0 forks source link

Reimplement Corchuelo in the style of MF, and also fix the shift() function #54

Closed ltratt closed 6 years ago

ltratt commented 6 years ago

Reimplement Corchuelo in the style of MF, and also fix the shift() function.

Our implementation of the Corchuelo recoverer was in a much different (and worse) style to the MF recoverer. This commit homogenises the styles, generally by copying code from MF with the minimal necessary changes.

This also seems the right time to finally bite the bullet and fix one of Corchuelo's most glaring errors: the forward move (what we call the "insert") rule is broken. Because it always tries to generate the maximum possible number of shifts, it misses out some minimal repairs (as KimYi state, but don't explain). This commit thus changes the shift rule to only find one shift at a time. This means that the Corchuelo recoverer can now find all of the same repairs as the MF recoverer.

Because the Corchuelo recoverer creates duplicate nodes in its search, the astar_all function isn't quite what we want. For what of a better term, I've implemented a Dijkstra function. This weeds out duplicates in the todo list. This is clearly less powerful than remembering all previously seen nodes, but implementing that was about 10% slower (possibly just because of the extra memory needed).

ptersilie commented 6 years ago

Looks good. You rebase then I merge?

ltratt commented 6 years ago

Squashed!