Lexing and Parsing: From Text to a Syntax Tree
A compiler's front end first groups characters into tokens, which a state machine can do, then arranges those tokens into a tree according to a grammar. The tree is where operator precedence stops being a rule to memorise and becomes a shape.
What a learner can do afterwards
- Tokenise a line of source and name the token kind of each piece
- Draw the syntax tree for an arithmetic expression with mixed precedence
- Write a grammar rule that makes an operator left associative
1 · Read
A compiler reads your code in two stages that hand work along. First the lexer groups raw characters into tokens: numbers, names, and operators. A state machine can do that grouping job. Then the parser arranges the tokens into a tree that follows the grammar. Each stage hands a finished product to the next.
Take the line total = price + 2 * count. The lexer reads it left to right and reports: name, equals sign, name, plus sign, number, star, name. Seven pieces, each with its kind named. The parser never sees raw characters again. It only sees that token list.
Precedence stops being a memorised rule and becomes a shape in the tree. In price + 2 * count, the star binds tighter, so 2 * count forms a subtree first and the plus joins price to that result. Subtraction is left associative: a - b - c groups as (a - b) - c. A grammar rule with the recursion on the left, like expr = expr - term | term, builds exactly that shape.
When a parse looks wrong, draw the tree and read its shape. If subtraction grouped to the right, a - b - c would mean a - (b - c), which gives a different answer. The grammar decided the shape, so fix the rule, not your memory of the rule.
The lexer groups characters into tokens, and the parser grows those tokens into a tree shaped by precedence and the grammar.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.