search

softdevteam / lrpar

Rust LR parser
Other
1 stars 0 forks source link

Add tests, and a fix, derived from Cerecke's PhD thesis #60

Closed ltratt closed 6 years ago

ltratt commented 6 years ago

NB: Needs https://github.com/softdevteam/lrtable/pull/88 to be merged first.

Cerecke's thesis is a goldmine of edge case examples. One of them shows up a problem which I sort-of knew we had, but which turned out to be much worse than I thought. Because (like Kim & Yi) we use the stategraph to guide repairs, it's obvious that, for grammars that have shift/reduce or reduce/reduce errors, we would find different repairs than the statetable. I assumed that we would simply find a superset of repairs, but I was wrong: Cerecke has an example that shows we produce repairs which are a) not the lowest possible cost (!) b) can't be parsed by the statetable.

After adding a couple of tests, this PR thus fixes this problem in https://github.com/softdevteam/lrpar/commit/09a567bbd13e729864028ea31ae3205e85ee5953. As a happy bonus this means that (apart from the Dist calculation) we no longer have any reliance on the stategraph. Since Dist can be calculated at compile-time, this means that the MF recoverer does not, ultimately, need to keep the stategraph around at run-time. That will, one day, enable it to take up less memory when it generates static grammar tables (a la Yacc).

ltratt commented 6 years ago

Fix pushed.

ptersilie commented 6 years ago

Looks good.

ltratt commented 6 years ago

OK, I think this is ready for merging then?

ptersilie commented 6 years ago

Yes, I was just waiting for the tests to finish.

ptersilie commented 6 years ago

Merged!