Skip to content

Writing drills

A drill generates unlimited randomized practice problems for one technique. It grades the learner's answer with an oracle, giving partial credit and precise feedback, and it can print a step-by-step worked solution. Drills are Python plugins in tools/course/drills/. They use only the standard library and PyYAML.

./course drill list
./course drill dominators                          # random seed, medium; type the answer
./course drill dominators --seed 7 --difficulty hard --solution   # problem + full worked trace
./course drill rpo --seed 3 --answer-file my.txt   # grade a file (exit 0 iff perfect)
./course drill first-follow --seed 1 --mermaid     # also print the instance as Mermaid / --dot

The three reference drills

Read these first. They're deliberately complete.

Drill File Chapters Shows
rpo drills/rpo.py ch08, ch15 sequence answers, first-difference feedback, event trace table
dominators drills/dominators.py ch15 (ch16 for DF) mapping and set answers, feedback that explains why (a witness path), multi-algorithm worked solution (iterative sets, CHK intersect walks, DF runners)
first-follow drills/first_follow.py ch02 (ch03) sectioned answers, per-pass fixed-point tables, LL(1) table with conflict classification

Module API

A drill is one module, tools/course/drills/<name_with_underscores>.py. Files starting with _ are helpers and aren't registered.

NAME = "first-follow"                 # CLI name, kebab-case, unique
TITLE = "nullable / FIRST / FOLLOW and LL(1) conflicts"
SUMMARY = "one line for `./course drill list`"
ALIASES = ("ff",)                     # optional short names
DIFFICULTIES = ("easy", "medium", "hard")   # optional; this is the default

def generate(rng: random.Random, difficulty: str) -> Problem: ...
def solve(problem: Problem) -> object: ...                  # oracle answer (any structure)
def format_answer(problem: Problem, solution) -> str: ...   # that answer, in the learner's answer format
def check(problem: Problem, answer_text: str) -> Result: ... # grade; never raises
def worked_solution(problem: Problem) -> str: ...           # Markdown trace of every step

Problem, Result and the registry are in tools/course/drills/__init__.py:

@dataclass
class Problem:
    prompt: str            # full statement shown to the learner (include the instance + conventions)
    answer_format: str     # fill-in skeleton, e.g. "[idom]\nB: ?\nC: ?"
    data: dict             # plain data only (lists/dicts/str/int): everything solve/check need
    dot: str | None        # optional Graphviz
    mermaid: str | None    # optional Mermaid (authors paste it into lessons)
    drill, seed, difficulty   # filled in by the framework

r = Result()
r.add("idom(C)", False, "A strictly dominates C but is not the closest strict dominator")
r.add("DF(B)", 0.5, "E should not be there (B strictly dominates E); 1 element missing")
r.parse_error = "line 3: cannot read 'B = = A'"      # when the answer cannot be parsed
r.score, r.perfect, r.feedback()

The contract

./course validate and tools/course/tests/test_drills.py enforce it through drills.self_test:

  1. Deterministic. generate depends only on rng and difficulty: same seed, same problem. Never use random.* module functions, time or hash ordering of sets, and sort anything you iterate out of a set. The CLI prints the seed so any problem can be reproduced and discussed.
  2. Round trip. check(p, format_answer(p, solve(p))) scores exactly 1.0 for every seed and difficulty.
  3. Robust. check never raises, even on "", garbage or partial answers. Parse errors go in Result.parse_error with a message that says what format is expected. Junk answers must not score 1.0.
  4. Worked solution is non-empty and ends with the answer in the answer format.
  5. Plain data in Problem.data. Rebuild graphs and grammars from it in each function: _cfg(p), _grammar(p).

Answer formats

Use the shared parser lib.answers.parse_sections so that every drill feels the same:

nullable: A B           # top-level `key: value` lines
[first]                 # a section: `[name]` or `name:` alone on a line
S: a b ε
A: {a, ε}
follow:
S: $
  • Values are parsed by parse_set, parse_sequence and parse_mapping, or by the CFG helpers parse_node_sequence and parse_node_set. The normalization rules are in QUIZ_FORMAT.md, and quizzes and drills share them.
  • Matching is case-insensitive, but feedback uses the real spelling. Map tokens back with lib.cfg.canon_node.
  • Accept any reasonable spelling (A -> B, A: B, {}, ∅, eps), and say in answer_format exactly what you expect.
  • An omitted line for a set-valued item counts as {} when that's the natural reading (for example, empty dominance frontiers). Say so in the prompt.

Grading: partial credit and feedback

  • Grade item by item: one Result.add per node, nonterminal or edge class. The score is earned / possible.
  • Sets use _common.set_credit(expected, given), which gives (|E∩G| − |G∖E|) / |E| clamped to [0, 1] and returns the extras and the number missing. Guessing everything doesn't pay.
  • Sequences get prefix credit, with _common.first_difference.
  • Feedback must be precise and must teach. Explain why a wrong element is wrong, using facts from the oracle:
  • "E does not dominate D: the path A → B → C → D avoids E" (a witness).
  • "ε is in FIRST(S) only if S is nullable" (the rule that was broken).
  • "that is the preorder; RPO is the reverse of the postorder" (a recognized misconception).
  • Name extra elements. For missing ones, give only the count, so the learner can retry without being handed the answer.

Worked solutions

A worked solution is Markdown in the formats from STYLE.md §4, and it's the same trace a lesson would show: - State the algorithm and its conventions in 2–3 lines. - Give one table row per iteration or step, including the initial state and the final no-change pass. - Name every rule applied ("(4) A → C B B: {c} into FOLLOW(B) from FIRST of what follows"). - When several algorithms solve the problem (iterative vs CHK), show each. That's the width rule applied to practice. - Finish with Answer: and a fenced block from format_answer.

Build the trace from instrumented oracle functions, not a separate re-implementation. The library functions take an optional trace list, and the drill only renders it. See dominators_iterative(g, trace), idom_chk(g, trace) and first_sets(g, nullable, trace).

Difficulty

Level Instance size Asks for
easy the smallest that exercises the algorithm (CFG ≈ 6 nodes, 3 nonterminals) the core result only
medium textbook-sized (8 nodes, 4 nonterminals) core plus the second concept (DF, FOLLOW, back edges)
hard 10–12 nodes; names shuffled so alphabetical order ≠ RPO; irreducible CFGs or left recursion allowed everything, including classification (edge kinds, conflict cells)

Shared libraries (reuse, don't duplicate)

  • tools/course/lib/cfg.py:
  • CFG (parse, to_text/to_table/to_dot/to_mermaid, preds, reverse)
  • random_cfg(rng, n, reducible=True|False|None, loops=, extra_edges=, shuffle_names=, single_exit=): every node is reachable, and the entry has no predecessors
  • dfs (pre/post/RPO, edge kinds, events)
  • dominators_iterative, dominators_by_removal, dominators_by_paths, idom_chk, idom_from_dom_sets, dom_sets_from_idom, render_dom_tree
  • dominance_frontiers (CHK runners), dominance_frontiers_by_definition
  • back_edges, natural_loop, is_reducible
  • tools/course/lib/grammar.py:
  • Grammar.parse("S -> a A | ε"), random_grammar
  • nullable_set, first_sets, follow_sets, first_of, ll1_table, ll1_conflicts
  • the cross-check oracles first_follow_by_relations and first_by_derivation
  • tools/course/lib/answers.py: normalization and parsing.
  • tools/course/drills/_common.py: set_credit, describe_set_error, first_difference, permutation_problems, parse_edge, fmt_edges, compact, CFG_CONVENTIONS.

When your chapter needs a new domain (regexes and NFAs, lattices, interference graphs, IR snippets…), add tools/course/lib/<domain>.py with the same style: plain functions, an optional trace parameter, and docstrings stating the conventions.

Testing oracles (required)

Every drill has unit tests in tools/course/tests/test_<topic>.py. They use unittest (no pytest) and run with python3 -m unittest discover tools/course/tests. Start each file with the _bootstrap import used by the existing tests. The tests must include:

  1. Goldens from a textbook or paper example (the Dragon-book expression grammar, the CHK paper's figures).
  2. Cross-checks on many random instances against an independent formulation. For example, test_cfg.py checks dominators four ways on 400 random reducible and irreducible CFGs: path enumeration, the removal definition, iterative dataflow, and CHK. test_grammar.py checks FIRST/FOLLOW by fixed point, by relation closure, and against brute-force derivations.
  3. Feedback tests asserting the exact wording for the most common mistakes.
  4. The framework self-test (drills.self_test(m, seeds=range(1, 31))). test_drills.py already runs it for every registered drill.

Where LLVM implements the concept, the C++ tests in tests/chNN/ compare against LLVM. The Python oracle is then the second opinion, and the two must agree on the shared corpus.

Registering

  1. Add the module. NAME must be unique.
  2. List it under the chapter's drills: in tools/course/chapters.yaml. A drill may serve several chapters.
  3. Run ./course validate to import it and self-test it on seeds 1–10, and python3 -m unittest discover tools/course/tests.
  4. Point to it from the lesson's section 9 (Assessment), and add a "Try it" callout with a seed in the worked-example section.

Skeleton for a new drill

"""Drill: <what>.  Easy: … Medium: … Hard: …  Used by Ch NN."""
from __future__ import annotations

import random

from ..lib.answers import AnswerFormatError
from . import Problem, Result
from ._common import parse_sections, set_credit, describe_set_error

NAME = "my-drill"
TITLE = "…"
SUMMARY = "…"


def generate(rng: random.Random, difficulty: str) -> Problem:
    inst = ...  # build from rng only
    return Problem(prompt="…", answer_format="…", data={"inst": ...})


def solve(p: Problem):
    ...


def format_answer(p: Problem, sol) -> str:
    ...


def check(p: Problem, answer_text: str) -> Result:
    r = Result()
    try:
        sec = parse_sections(answer_text or "", ["section"])
    except AnswerFormatError as e:
        r.parse_error = str(e)
        return r
    sol = solve(p)
    ...  # r.add(item, ok_or_fraction, precise_message)
    return r


def worked_solution(p: Problem) -> str:
    ...  # trace tables, then "Answer:" + format_answer