Parsing Techniques Overview

This is a living document exploring different parsing techniques I’ve been studying during my time at the Recurse Center.

Types of Parsers

Recursive Descent

• Hand-written, top-down approach
• Easy to understand and debug
• Natural mapping to grammar rules
• Used in many production compilers (Rust, Go, etc.)

LR Parsing

• Bottom-up, table-driven
• More powerful than recursive descent
• Can be harder to generate good error messages
• Generated by tools like yacc, bison

Parser Combinators

• Functional approach to parsing
• Compose small parsers into larger ones
• Popular in functional languages (Haskell, F#)
• Can be elegant but sometimes slower

Key Insights

The choice of parsing technique depends on:

• Language complexity
• Error message quality requirements
• Development time vs runtime performance tradeoffs
• Team familiarity

Further Reading

• “Crafting Interpreters” by Bob Nystrom
• Dragon Book (Compilers: Principles, Techniques, and Tools)
• Papers on PEG parsers and error recovery

---

Note: This is a work in progress. I’ll update as I learn more.