Lexer, parser and syntax tree

In short: A compiler first reads source code as a stream of characters. The lexer splits it into tokens, the parser builds a syntax tree (AST) from them using the grammar.

In more detail: The lexer recognises words, numbers, operators and brackets and ignores whitespace and comments. The parser checks whether the tokens match the language’s grammar and builds the structure, for example 1 + 2 * 3 as a tree in which the multiplication sits deeper.

In Depth

• Token: for example IDENT(x), NUMBER(42), PLUS.
• Grammar: Rules in Backus-Naur form (BNF). Recursion models nested structures.
• Recursive-descent parser: One function per rule; easy to write by hand.
• Operator precedence: Through grammar levels or Pratt parsing.
• AST: Abstract syntax tree, without superfluous details such as brackets.
• Error messages: Good parsers report line and column and recover after errors.
• Tools: ANTLR, tree-sitter, parser combinators.

See also: Intermediate representation and compiler optimisation, Type systems and type inference