A bird's eye view of a parser
summary
Explains how parsing actually works by building the data structures: uses Thompson's construction to make finite state machines for regular languages, introduces tokenization before parsing, and shows table-driven context-free parsing built from computed FIRST and FOLLOW sets into an LL parse table plus a stack algorithm that unapologetically accepts or errors. Notes tradeoffs: parser generators like flex, bison, antlr precompute tables but cost memory, handwritten recursive descent trades expressiveness for control, and C++ ambiguity surfaces as the most vexing parse.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 3:46What is a parser
- 8:45Formal languages and grammars
- 15:31Tokens and lexical analysis
- 17:15Chomsky hierarchy
- 19:25Regular languages limits
- 22:18Context-free languages
- 24:50Parsing algorithms and ambiguity
- 25:55Parsing with finite state machines
- 29:28Thompson's construction for regex to FSM
- 32:21Parsing tables for CFG
- 34:29First and follow sets
- 41:30LL parsing algorithm
- 46:09Parser generators trade-offs
- 48:58C++ parsing ambiguities
- 50:24Why parsers matter
related talks
31mTime flies like an arrow, fruit flies like a banana
52mA bird's eye view of a compiler
32mTime flies like an arrow; Fruit flies like a banana: Parsers for Great Good
58mParsing in C# from first principles
29mMy Little Parser: Tooling is Magic
26mLiberating Ruby's Parser from Lexer Hacks
52mBuilding a parser in C#, from first principles
37mThe Art of Parsing