From Letters to Trees

Computing · Computer Systems · ages 21-22

Name ______________________ Date ____________

In total = price + 2 * count, what kind of token is 2?
- A number
- A name
- An operator
What is the lexer's job?
- To run the finished program
- To group characters into named tokens
- To arrange tokens into a tree
In a + b * c, the parser groups b * c before applying the plus.
Circle one: True False
In the tree for price + 2 * count, what sits directly under the plus?
- price, 2, and count as three equal children
- price on one side and the 2 * count subtree on the other
- The 2 * count subtree alone
How does the lexer split total = price + 2 * count?
- Into one token per character
- Into two tokens: left side and right side
- Into seven tokens: name, equals, name, plus, number, star, name
How does a - b - c group?
- As a - (b - c)
- It cannot be grouped at all
- As (a - b) - c
Which grammar rule makes minus left associative?
- expr = expr - term | term
- expr = term - expr | term
- expr = term + term | term
A student evaluates a - b - c as a - (b - c) and gets a wrong answer. What is the real mistake?
- The tree used right grouping, but minus needs left grouping
- Arithmetic works differently inside compilers
- Token lists cannot hold minus signs

Answer key

For grown-ups. Fold this page away before handing over the rest.

A number · Digits form numbers, letters form names, and symbols like plus form operators.
To group characters into named tokens · Grouping characters is the lexer's whole task. The tree belongs to the parser.
True · The star binds tighter, so its subtree forms first.
price on one side and the 2 * count subtree on the other · Plus joins two parts: price and the already-built 2 * count subtree.
Into seven tokens: name, equals, name, plus, number, star, name · The lexer reports every piece with its kind. Count them: seven.
As (a - b) - c · Minus is left associative, so grouping starts from the left.
expr = expr - term | term · Recursion on the left grows the tree to the left. That shape is left associativity.
The tree used right grouping, but minus needs left grouping · The tokens were fine and arithmetic is normal. The tree shape was wrong, so the rule needs fixing.