Skip to content

Draft: Use non-backtracking (<!>) over (<|>) where possible

Fredrik Wieczerkowski requested to merge non-backtracking into master

JSON has the advantage of being LL(1), therefore we can pretty much always decide which rule to apply based on the next symbol and thus parse in linear time. In consequence, we can almost everywhere rewrite the alternatives to use the non-backtracking (<!>) combinator, since we will never go deeper than one symbol into a branch that will be rejected. The rules where (<|>) couldn't be replaced with (<!>) could probably be rewritten to use (<!>).

This should improve parsing performance by quite a bit, invalid JSON in particular should be rejected much more quickly (a ~2000 line JSON file with a single misplaced \ was rejected almost instantaneously compared to the current implementation not terminating within > 5 min, with KiCS2).

Still, this branch probably needs some more testing to make sure that it doesn't miss some edge case that currently parses.

Edited by Fredrik Wieczerkowski

Merge request reports