Why compilers can't parse nested parentheses with regex | Ep. 7

Episode 7 of Compute Illustrated – Season 1: From Text to Tokens ◀ Previous: Lex and flex: generate a lexer from regular expressions | Ep. 6    • Lex and flex: generate a lexer from regula...   Next ▶: Context-free grammars: derivations, parse trees, ambiguity | Ep. 8    • Context-free grammars: derivations, parse ...   Full season playlist:    • Compilers, Part 1: From Text to Tokens   Can a regular expression check that parentheses are balanced? Our calculator accepts x = ((((10)))) and rejects the same line with one parenthesis missing, but it's the parser that notices, not the scanner. In this video, you'll see why no regular expression and no finite automaton can ever do this job. We first build an automaton that counts parentheses and watch it run out of states, then try a loop and watch it accept nonsense. Then comes the real argument: with the pigeonhole principle, every automaton with n states is fooled by a line with n opening parentheses. That's the idea behind the pumping lemma, and it shows why aⁿbⁿ is not a regular language. Finally, we look at what the parser has that the automaton lacks: a stack, and a grammar rule that refers back to itself. Nothing in the animations is drawn by hand: the automata run in a small Python program, a brute-force check tries every automaton with up to four states, and the parser's stack comes from a real calculator built with flex and bison. In the next episode: grammars and syntax trees. Code for this episode: https://github.com/computeillustrated... Chapters: 0:00 Recap 0:14 Can the scanner check parentheses? 0:49 An automaton that counts 1:44 A loop instead of a counter 2:17 No automaton can do it 3:38 The pumping lemma 4:28 Limited memory and the parser's stack 5:49 Summary More from this series: Mentioned in this video: How does a compiler work? The six phases, step by step | Ep. 1    • How does a compiler work? The six phases, ...   Mentioned in this video: How does a lexer work? Tokens, regex and finite automata | Ep. 3    • How does a lexer work? Tokens, regex and f...