Conclusion

• Packrat parsing:

  • Uses memoization to provide backtracking and unlimited lookahead in a linear-time parser
  • Is easily expressed as a lazy data structure
  • Provides more flexibility than LL or LR parsing
  • Enables practical scannerless parsing
  • Has substantial storage cost, but often reasonable