Lexing and Parsing: From Text to a Syntax Tree · seed 1 · A4, ink-friendly. The answer key prints on its own page for grown-ups.

From letters to trees

Computing · Computer Systems · ages 21-22
Name ______________________   Date ____________

  1. In score = base + 6 * rate, what token kind does 6 have?

    • A number token
    • A name token
    • A times token

  2. In this front end, what is the lexer's job?

    • Execute machine instructions and record their results
    • Group characters into tokens with kinds and text
    • Connect tokens into a tree under the grammar rules

  3. Here * binds more tightly than +. The expression a + b * c groups as a + (b * c).

    Circle one:   True   False

  4. Use a binary-operator tree, where * binds more tightly than +. Which tree represents fee + hours * rate?

    • Root * has left child + with children fee and hours, and right child rate
    • Root + has left child fee and right child * with children hours and rate
    • Root + has three direct leaf children fee, hours and rate, with no * node

  5. Ignore spaces and keep names whole. How does the lexer split score = base + 6 * rate?

    • score = base, +, 6 * rate: three tokens containing whole expression pieces
    • s, c, o, r, e, =, b, a, s, e, +, 6, *, r, a, t, e: seventeen character tokens
    • score, =, base, +, 6, *, rate: seven tokens with names kept whole

  6. Subtraction is left associative. How does unparenthesised a - b - c group?

    • It groups as a - (b - c)
    • It has no grouping until runtime
    • It groups as (a - b) - c

  7. Here term has no unparenthesised subtraction and | separates alternatives. Which rule makes subtraction left associative?

    • expr = expr - term | term
    • expr = term - expr | term
    • expr = term - term | term

  8. Subtraction is left associative. A parser groups 9 - 4 - 1 as 9 - (4 - 1), giving 6. Which diagnosis fits?

    • The parser used right grouping; the required left grouping gives 4
    • The lexer must delete the final minus; deletion preserves the required grouping
    • Subtraction is commutative here; changing operand order always preserves its value
LightMySky · lightmysky.comW1-mt_-ZlCxZ3SOh-s1

Answer key

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

From letters to trees W1-mt_-ZlCxZ3SOh-s1

  1. A number token · 6 is a numeric literal, not a name or the multiplication symbol.
  2. Group characters into tokens with kinds and text · The lexer identifies tokens. The parser determines their grammatical arrangement.
  3. True · Multiplication binds more tightly. The multiplication subtree is the right child of root +.
  4. Root + has left child fee and right child * with children hours and rate · The outer addition joins fee to the hours * rate subtree.
  5. score, =, base, +, 6, *, rate: seven tokens with names kept whole · Three names, one number and three symbols make seven tokens.
  6. It groups as (a - b) - c · Subtraction is left associative in this language.
  7. expr = expr - term | term · The recursive expr can hold the earlier subtraction as the left operand. The term alternative terminates the recursion.
  8. The parser used right grouping; the required left grouping gives 4 · 9 - (4 - 1) is 6, but (9 - 4) - 1 is 4. The grouping differs even with the same tokens.
Worksheet · LightMySky