CSC448: Overview: Lexing and Parsing Overview [18/133]

For the compiler writer:

• Lexing: from a stream of characters to a stream of tokens.
• Parsing: from a stream of tokens to an abstract syntax tree.

Lexer and parser generators exist and are normally used.

Based on formalisms including:

• regular expressions
• finite-state automata
• context-free grammars and BNF / EBNF
• pushdown-stack automata