Proper Reject Handling in Scannerless Generalised LR Parsing

Proper Reject Handling in Scannerless Generalised LR Parsing
Master Project

Project description

Scannerless Generalised LR (SGLR) parsers can parse context-free grammars extended with conjunction-with-negation, represented by reject rules. This gives us the expressive power of Boolean Grammars. To handle reject rules correctly, we need to handle rejects in a specific order. The first attempt was to order states that can be reduced during parsing: first reduce non-rejectable states, then rejectable states. However, in specific situations an ordering between rejectable states is required for correct parsing results, for example when encoding intersections with reject rules. The question of how to order rejectable states was left open. Recently I had an idea for how to do the ordering, so it should be possible to finally complete the algorithm, without any post-parsing fixes.

Now the task remains to see if this idea actually works, how we can best implement it, implement one of the post-parse fixes from other work, compare performance improvement, and maybe prove the correctness of the idea.