The Backtracking Problem

• Can yield exponential worst-case parse times

• Typical solution: avoid backtracking by

  • Prediction using one-token lookahead
  • Hacking the grammar
  • Designing the language for easy parsing

• Alternate solution: allow backtracking;

  • memoize all intermediate results.