Lexing and Parsing: From Text to a Syntax Tree
In a common compiler front end, a lexer groups characters into tokens and a parser uses grammar rules to build a syntax tree. Finite-state methods recognise many token patterns. The tree records operator grouping under precedence and associativity rules.
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
The finite-state recognisers you studied can recognise many token patterns. Here we use a compiler front end with two stages. The lexer groups characters into tokens, recording their kinds and text. The parser uses grammar rules to connect those tokens into a syntax tree. Other compiler designs can combine these jobs or use additional lexical state.
For total = price + 2 * count, ignore spaces and keep names and numbers whole. The seven tokens are total, =, price, +, 2, *, count. Their kinds are name, assignment, name, plus, number, times, name. Each operator or assignment symbol is separate in this example. The parser receives tokens, not a separate token for every letter.
In an abstract syntax tree, operators are internal nodes and names or numbers are leaves. Multiplication binds more tightly than addition here. For price + 2 * count, draw + at the root. Its left child is price; its right child is *. The * node has children 2 and count. This specifies grouping, not when the parser creates nodes or when the language evaluates operands.
Our arithmetic language makes subtraction left associative: a - b - c means (a - b) - c. The grammar rule expr = expr - term | term describes this. Here = introduces a rule and | separates alternatives. A term is a name, number or parenthesised expression, with no unparenthesised subtraction. The recursive expr before - lets an earlier subtraction become the next subtraction's left operand. The term alternative ends the recursion.
Check grouping with values that expose a difference. For 12 - 5 - 2, left grouping gives (12 - 5) - 2 = 5. Right grouping gives 12 - (5 - 2) = 9. The tokens stay the same; the trees differ. If the language requires left grouping, inspect both the grammar and parser implementation. Explicit parentheses can request different grouping.
The lexer groups characters into tokens, and the parser grows those tokens into a tree shaped by precedence and the grammar.
Lesson, questions and flashcards on compiler tokenisation and parsing written for this dataset.
Additional expression-tree readings and flashcards written for this dataset.
More to read
Drawing an operator tree
For these arithmetic trees, put operators at internal nodes and names or numbers at leaves. A binary operator has one child for each operand.
For cost + units * tax, draw + at the root. Connect cost as its left child and a * node as its right child. Give * the children units and tax.
For (cost + units) * tax, draw * at the root instead. Its left child is a + node with children cost and units. Its right child is tax.
Check the links by writing the fully parenthesised expression they represent. The tree specifies grouping. Operand evaluation order depends on the language's rules.
Reading a recursive grammar rule
Read expr = expr - term | term as two alternatives for expr. A term may be a name, number or parenthesised expression, but contains no unparenthesised subtraction.
The subtraction alternative lets its left expr contain an earlier subtraction. For p - q - r, the outer subtraction can therefore have p - q on the left and r on the right. This groups as (p - q) - r.
Moving the recursive expr to the right gives a different grouping. The tokens can remain identical while the tree changes.
This is a grammar description, not executable parser code. A direct recursive-descent parser needs a strategy for handling left recursion.
2 · Watch
Take it off screen
Where it sits
Optional connections
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.