Language Implementation Patterns

Parsing like a Pack Rat

Until a backtracking parser finds a winning alternative, it might speculatively parse the same input with the same rule multiple times. Almost by definition, we use backtracking parsers only when we need to distinguish between similar language constructs. If the constructs are similar, the associated grammar likely contains repeated references to the same rule.

In the implementation section of Pattern 5, ​Backtracking Parser​, we’ll augment the list-of-names language to allow parallel assignments like Python does: [a,b]=[c,d]. The stat rule needs to backtrack because it cannot distinguish the two alternatives with finite lookahead: