Lexing & Parsing

Characters → Tokens → Tree

1:00

How a compiler turns raw source characters into a structured tree — the lexer-to-parser pipeline, token types, context-free grammars, AST construction, and top-down vs bottom-up parsing strategies.

By the end, you can

Describe the compiler front-end pipeline (lex → parse → semantic) and identify which phases belong to it.
Explain what the lexer does, why it discards whitespace, and what the longest-match rule means.
Identify the formal tools behind each stage: regular expressions and finite automata for lexing; context-free grammars for parsing.
Explain how a parser uses a context-free grammar to build a parse tree, and how precedence is encoded in tree structure.
Distinguish a parse tree from an AST and explain what information the distillation step removes.
Contrast top-down (LL / recursive descent) and bottom-up (LR) parsing strategies, including which handles left recursion.
Identify a syntax error, explain when it is caught, and distinguish it from a lexical error or a semantic error.

Up next in Theory of Computation & Compilers