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:
| | stat: list EOF // try this alternative first |
| | | list '=' list // if 1st alternative ... |
Get Language Implementation Patterns now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
