Fun With Parsing

on YouTube ↗58m

" summary

Claims that derivative parsing lifts Brzozowski-style derivatives to context‑free grammars, uses laziness and memoization to avoid infinite recursion, and yields a working Scala implementation with tests. It handles ambiguity rather than forcing grammar contortions, admits embedded regexes, and runs with asymptotic cost O(n^3) while keeping constant factors competitive with LR. Earlier exponential fear is now corrected by recent papers, and the prototype proves the idea practical rather than merely theoretical.

AI-written summary · about

" chapters (14)

1. 0:00Introduction to parsing
2. 1:46Formalizing grammars
3. 4:56Recursive descent parsing
4. 6:42Grammar constraints
5. 8:54Building a recognizer
6. 12:27Left recursion issues
7. 15:49LR parsing techniques
8. 18:54Parsing with states
9. 22:14Shift-reduce conflicts
10. 25:17Algorithms and ambiguity
11. 28:09Graph structured stacks
12. 31:50Derivative parsing
13. 35:12Functional implementation
14. 37:14Parser performance

" related talks

• 58mGoodbye Regex. Hello Parsers!Hackle Wayne · NDC Sydney 2020
• 17mWhen Chomsky Met JavaScript: Exploring the Linguistics(...)Alaina Kafkes · JSConf EU 2018
• 27mParsing, Compiling, and Static MetaprogrammingPatrick Dubroy · JSConf EU 2013
• 24mSolving String Constraints with Regex-Dependent Functions through Transducers wiZhilei Han, Anthony W. Lin, Matthew Hague, Taolue Chen, Zhilin Wu, Alejandro Flores-Lamas, Denghang Hu, Shuanglong Kan, Philipp Römmer · POPL 2022
• 41mA language in 20 minutesJames Coglan · FutureJS 2014
• 22mOptimizing Your Code with BabelPranay Prakash, Thomas Fischer · ZEIT Day 2018
• 56mFunctional Programming with JavaScriptSimon Painter · foss-north 2020
• 29mReimplement RegExp in JavaScriptJulian Viereck · JSConf EU 2013