I’ve spent most of the week trying to get rollback working in my parser rules, having thought that the bug I found while implementing look-ahead was the main issue. Unfortunately the problems are rather deeper than that, but this morning I had a good look at my test examples, and realised that all of them work without rollback, with either the use of one token look-ahead or just fixing the order of alternative choices. Basically my rollback examples were either sorted with look-ahead, or dependant on rules that would be valid (though poor) eBNF, but aren’t really valid PEG rules.
The challenge with rollback really comes down to the way by rules build up a data tree as they progress. This makes rolling back a little bit very difficult. If I was just building a list of tokens paired with a matching rule, rollback would be much simpler, as I’d just have to truncate the list to the rolled back starting point.
There is an alternative approach: as my parsers are built up from little PEG parsers that just match a ‘phrase’, I could only permit rollback to the start, and maybe implement Ford style Packrat caching to limit the impact of that. That would be simpler, and is probably what I should have done when I started trying to implement rollback. I’ll leave in the roll-back information data structures for now, so I can reuse them later if I do try that approach.
For now though, I’m leaving rollback out: as all my examples are either so contrived they require poor rule design, or easily fixed with look ahead, I think it’s quite likely I have no need of rollback.
Next week I’ll be doing more reading, and getting back into finishing my two interpreters (with the benefit of look-ahead rules.)