arr-ai / wbnf

ωBNF implementation
Apache License 2.0
7 stars 4 forks source link

Solve backtracking #17

Open marcelocantos opened 4 years ago

marcelocantos commented 4 years ago

Given the well-defined grammar a -> b+; b -> "x" ":" "x"+ ";"?, the parser will match valid input x:x;x:x but won't match also-valid input x:xx:x. This is because "x"+ greedily slurps up all the xs and the parser doesn't have any look-ahead to see whether an x has a : after it and should therefore be left to the next b to pick up.

This requires an LL(2) grammar, so we will probably have to bite the LL(k) or LL(*) bullet soon.