Skip to content
Tutorials Center
My learning

Topics

Lesson 58 of 61 ยท Practice and Review

Practice Exercises with Solutions

Practice compiler design with exercises on lexing, grammars, FIRST and FOLLOW, parsing, optimization and virtual machines. Every solution runs in your browser.

Reading about compilers is not the same as building them. This lesson gives you twelve exercises, six of them programming tasks with runnable solutions and six short paper exercises with answers. They follow the order of the track: lexing, grammars, FIRST and FOLLOW sets, parsing, optimization and virtual machines.

For the best result, try each exercise first: read the task, think about the approach, and write your own version in a scratch editor before you open the solution. Each solution below is a complete program you can run and modify. If your output differs from the one described, the difference is where the learning is.

flowchart LR
    X1["1. Lexing<br/>maximal munch"] --> X2["2. Grammars<br/>count parse trees"]
    X2 --> X3["3. FIRST, FOLLOW<br/>LL(1) check"]
    X3 --> X4["4. Parsing<br/>recursive descent"]
    X4 --> X5["5. Optimization<br/>constant folding"]
    X5 --> X6["6. Execution<br/>stack VM"]

Each exercise practices one stage of the compiler pipeline.

Exercise 1: maximal munch

Task. Write a function lex_ops(text) that splits a string of operators into tokens. The operators are < <= > >= = == != => -> + ++ +=. Always take the longest operator that matches at the current position. What are the tokens of +++= and of <=>=?

Hint. Sort the operator list by length, longest first, and try each one with startswith at the current position. This is the longest-match rule from Regular Expressions for Lexers.

Python Solution 1: maximal munch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

+++= becomes ++ and +=, not + + += and not +++ =. Greedy matching decides, even when the programmer meant something else. That is why a C programmer must write a + ++b with spaces if they want an addition of a pre-incremented value.

Exercise 2: count the parse trees

Task. A grammar is ambiguous when some sentence has more than one parse tree. Write count_trees(grammar, start, tokens) that returns the number of distinct parse trees. Use it on the grammar E -> E + E | E * E | n for n + n * n and n + n + n + n, and then on a layered grammar for the same language.

Hint. Let count(symbol, i, j) be the number of ways symbol can derive the token slice tokens[i:j]. For a terminal that is 1 or 0. For a nonterminal, add up the counts of its productions; for a production, split the slice between its symbols and multiply. Memoize with lru_cache. (The grammars here have no empty productions, which keeps the recursion simple.)

Python Solution 2: counting parse trees

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ambiguous grammar gives 2 trees for n + n * n (for longer chains the counts 5, 14, 42 and so on are the Catalan numbers), while the layered grammar always gives exactly one, which is the whole point of precedence layering.

Exercise 3: FIRST, FOLLOW and an LL(1) check

Task. For the grammar S -> A B c, A -> a A | ฮต, B -> b B | ฮต, compute which nonterminals are nullable and their FIRST and FOLLOW sets. Then write a test that decides whether a grammar is LL(1): for every nonterminal, the FIRST sets of its alternatives must be pairwise disjoint, and if an alternative can be empty, FIRST of the others must not overlap FOLLOW of the nonterminal. Apply the test to a second grammar, S -> A a, A -> a | ฮต.

Hint. Both sets are computed by repeating the rules until nothing changes (a fixed point). See FIRST and FOLLOW Sets. An empty production is written as an empty list.

Python Solution 3: FIRST, FOLLOW and the LL(1) test

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Grammar 1 is LL(1): A can begin with a or be empty, and what may follow it (b or c) never starts with a. Grammar 2 is not. When the parser sees a while expanding A, it cannot tell whether to use A -> a or the empty production and let the following a belong to S. The test reports that overlap.

Exercise 4: parse and evaluate boolean expressions

Task. Write evaluate(source, env) for the grammar below, where env maps variable names to booleans. Print a truth table for a and not b or c.

TEXT
expr   = term ( "or" term )* ;
term   = factor ( "and" factor )* ;
factor = "not" factor | "(" expr ")" | "true" | "false" | NAME ;

Hint. One function per rule, as in Writing a Recursive Descent Parser. Raise SyntaxError for a missing parenthesis or leftover tokens.

Python Solution 4: a boolean expression evaluator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because and is parsed inside term, which is called by expr, and binds tighter than or. The truth table is true in exactly the rows where c is true or where a is true and b is false.

Exercise 5: a constant folder

Task. Given an expression tree made of ("num", n), ("var", name) and ("bin", op, left, right) nodes, write fold(tree) that returns an equivalent smaller tree: compute operations on two constants, and apply the identities x + 0 = x, x * 1 = x, x * 0 = 0 and x - 0 = x. Take care not to fold a division by a constant zero; that error must still happen when the program runs.

Hint. Work bottom-up: fold the children first, then look at the node. See Local Optimizations.

Python Solution 5: constant folding and identities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The division example folds 3 - 3 to 0 but keeps (2 / 0) as an operation, so the program still fails at run time instead of failing in the compiler or, worse, silently producing a value. Notice also that a * 0 = 0 is only safe here because expressions have no side effects. If a were a function call that prints something, deleting it would change the program.

Exercise 6: run a bytecode program

Task. Write run(program) for a stack machine with the instructions PUSH n, LOAD name, STORE name, ADD, SUB, MUL, LT, JMP target, JZ target (jump if the popped value is zero or false), PRINT and HALT. Use it to sum the numbers 1 to 10 and to print a countdown. Add a step limit so an infinite loop is stopped.

Hint. Keep a program counter, a value stack and a dictionary of variables. See Bytecode and Virtual Machines.

Python Solution 6: a stack VM

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sum program prints 55 after 141 machine steps. The step limit turns the infinite loop JMP 0 into an error message instead of freezing the page. Real VMs rarely have a step counter, but sandboxes, test harnesses and fuzzers always add one.

Paper exercises

These need no code; try to answer before reading the answer.

  1. Tokens. How many tokens does the C-like statement a=b+++c; contain? Answer: seven: a, =, b, ++, +, c, ;. Maximal munch reads ++ first.
  2. Left recursion. Remove the left recursion from E -> E + T | T. Answer: E -> T E' and E' -> + T E' | ฮต. The new grammar derives the same strings, but a recursive descent parser can use it. Associativity must then be restored in the tree-building actions.
  3. Dangling else. Is S -> i E t S | i E t S e S | a ambiguous? Answer: yes. For i E t i E t a e a the e can attach to the inner or the outer i. Languages resolve it by rule ("nearest if") or by mandatory braces, as Tiny does.
  4. LR(0) items. How many LR(0) items does the production A -> X Y Z produce? Answer: four, with the dot in each of the four possible positions.
  5. Three-address code. Translate a = b * -c + b * -c. Answer: a straightforward translation uses five temporaries: t1 = -c; t2 = b * t1; t3 = -c; t4 = b * t3; t5 = t2 + t4; a = t5. Common subexpression elimination removes t3 and t4 and leaves t1 = -c; t2 = b * t1; t5 = t2 + t2.
  6. Register allocation. Three variables are live at the same time and interfere pairwise. How many registers avoid a spill? Answer: three. The interference graph is a triangle, and a triangle needs three colors.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Under maximal munch, how is the input +++= split into operators from the list + ++ +=?

    At each position the lexer takes the longest operator that matches: first ++, then +=.
  2. 2. Why does the exercise 2 grammar E -> E + E | E * E | n give two parse trees for n + n * n?

    One tree groups (n + n) * n and the other n + (n * n). Layering the grammar by precedence allows only one.
  3. 3. In the second grammar of exercise 3, why is there an LL(1) conflict on the token a?

    FIRST of the first alternative is {a} and the empty alternative contributes FOLLOW(A) = {a}. The sets overlap, so one token of lookahead cannot decide.
  4. 4. Why does the folder keep (1 + 1) / (3 - 3) as a division?

    An optimizer must preserve behavior, including errors. The division by zero should happen when the program runs.
  5. 5. What does JZ do in the exercise 6 machine?

    JZ is the conditional jump used to leave a loop: when the loop condition evaluates to false, the machine jumps past the loop body.

Summary

  • Maximal munch is implemented by trying the longest candidates first.
  • Counting parse trees with memoization shows ambiguity as a number, and layering as the cure.
  • FIRST, FOLLOW and nullable sets come from fixed-point loops; an LL(1) check compares FIRST and FOLLOW sets of the alternatives.
  • A recursive descent parser has one function per grammar rule, and the call order encodes precedence.
  • An optimizer works bottom-up and must preserve behavior, including run-time errors and side effects.
  • A stack VM is a loop with a program counter, a stack and a few dozen lines of dispatch.

Next: Testing and Debugging a Compiler