How do you decide which Chomsky tier a new input format should be specified at, and what does each rung cost?
answer
- Start from what must be rejected
- Lowest rung that carries the constraints
- Each rung up costs a bound
- Who chooses the validator's memory?
- Name the relational checks separately
basics
~20 sSpecify the format at the lowest tier that carries the constraints you must actually reject on, and push anything above it into a separately named check. Each rung upward costs memory bounds, streamability, and agreement between independent implementations.
solid answer
~40 sStart from the constraints you genuinely need to **reject** on, not from how the format looks, then pick the lowest rung that carries them. Type 3 buys one-pass validation in constant memory, which is what you want at a trust boundary. Type 2 buys nesting and recursive structure, and costs a grammar to maintain plus memory the *sender* controls, so it needs a depth cap. Anything above type 2 — a field that must equal another field, a count that must match what follows — no grammar will carry, so it moves into an explicitly named post-parse check. The two failure directions are symmetric: under-shooting ships a validator that accepts malformed input, while over-shooting means every independent implementation must reproduce more behaviour, and the places they quietly differ become the format's real specification.
go deeper
Recall that a format's tier is a decision someone makes, not a property that arrives with the file. The simplest format that expresses what you need is the one to aim for.
Explain what each rung costs in concrete terms: constant memory and one-pass validation at the bottom, a grammar and sender-controlled depth in the middle, a whole buffered document above that.
Show the operational angle: whether validation memory is bounded by your specification or by whoever sends the document, and whether a check can run on a stream or forces you to hold everything first.
Own the trade as a long-lived interface decision. Expressiveness you do not need becomes divergence between independent implementations, and a format is far harder to narrow later than it was to keep narrow now.
## The triage a team actually runs When a new input format arrives — an interchange file, a query string, a policy document, a wire envelope — somebody has to answer one question before any code is written: is this a pattern, a parser, or something more? The Chomsky hierarchy is the vocabulary that makes the answer sayable and reviewable. The method has three steps: 1. **List what must be rejected.** Not what the format looks like — what an invalid document is. Missing required field, unmatched delimiter, trailer disagreeing with header, count not matching the items that follow. 2. **Place each rejection on the ladder.** Fixed shapes and orderings are type 3. Matched, arbitrarily nested delimiters are type 2. Agreement between two separated, unbounded parts of one document is type 1. 3. **Specify at the lowest rung that carries the structural constraints, and name everything above it as a separate check.** ## What each rung costs | Rung | What it lets you express | What it costs | |---|---|---| | 3 | fixed shapes, orderings, bounded repetition, capped depth | nothing to nest freely; machine size grows with any cap you impose | | 2 | recursive, arbitrarily nested structure | a grammar to maintain; validation memory chosen by the sender; no longer trivially streamable | | 1 | relations between separated parts of one document | no grammar carries it — the check leaves the specification's rule set and becomes a named pass; the whole input must be buffered | | 0 | unrestricted rewriting | you no longer have a validator with a resource bound at all | - **Bounded memory is the prize at the bottom rung.** A constant-memory, one-pass checker can sit at an untrusted boundary with no capacity question: the work is a function of input length and nothing else. - **Streamability dies quietly.** A check that relates two distant parts of a document forces you to hold the document, which changes deployment shape far more than it changes code. - **Interoperability is the cost people forget.** Every rung upward is more behaviour that each independent implementation must reproduce identically. ## The rule: lowest tier that carries the constraint The default is not "the most expressive tier available in case we need it later". Expressiveness is not free optionality; it is a permanent widening of what your format is, and formats are far harder to narrow than to widen once documents exist in the wild. Pick the lowest rung that carries what you must reject, and treat any request to move up as a change with named costs. A useful discipline: when someone proposes a feature that pushes the format up a rung, ask what invalid document it lets you reject that you could not reject before. If the answer is "none, it is just more convenient to write", the feature belongs in a layer above the format, not in the format. ## Over-shooting and under-shooting Both failures are common and they look nothing alike in production. - **Under-shooting** means the specification claims a rung its constraints do not fit. The symptom is a validator that accepts malformed documents — patterns that pass input with unbalanced delimiters, or a shape check that never notices the trailer disagrees with the header. It is found late, by the consumer that crashes. - **Over-shooting** means the format is more expressive than anything ever needed. The symptom is divergence: two implementations accept subtly different sets of documents, and senders unknowingly depend on whichever one they tested against. The format's real definition becomes "whatever the dominant implementation does", which is the point at which the written specification stops being useful. ## Writing the decision down A format specification that has done this well reads in two clearly separated parts: 1. A **structural grammar** stating what shapes are legal, pitched at the lowest rung that expresses them, with every bound — maximum nesting depth, maximum field length, maximum document size — stated as part of the format rather than left to whoever implements it. 2. A list of **named relational checks** for everything the grammar cannot carry, each one a rule of the format with its own identifier, so a conformance test can reference it and an implementation cannot silently omit it. And a third property that is easy to forget: the specification should say that an implementation enforcing **more** than these rules is also wrong. Extra strictness fragments a format exactly as extra leniency does, because senders calibrate against what is accepted in practice. ## The judgment this actually is There is no single correct rung for a format — that is what makes this a lead's decision rather than a lookup. You are trading expressiveness against three things you can measure: whether validation memory is bounded by your specification or by the sender, whether documents can be validated as they arrive, and how likely two independent implementations are to agree. A team that can name which rung it chose, and what it gave up, will still have a coherent format in three years. A team that never asked will discover its rung by accident, one compatibility bug at a time.
- What goes wrong when a format is specified above the rung its constraints need?Every independent implementation must now reproduce more behaviour, and the places where they quietly differ become the format's real definition. You also lose the cheap guarantees that came with the lower rung: bounded validation memory, one-pass checking, and the ability to reject early at a trust boundary rather than after buffering a whole document.
- How do you keep a type 1 constraint from quietly widening the format?Name it in the specification as its own numbered check, with its own rule text, rather than leaving it inside one implementation's code. The structural grammar states which shapes are legal; the named checks state which relations must hold. Anything in neither is not a constraint, and an implementation that enforces extra rules is as wrong as one that skips them.
saying these in an interview costs you the question
- Picks the most expressive tier in case it is needed later
- Judges the rung by the format's syntax style, not its constraints
- Assumes a higher rung costs nothing because tooling handles it
- Ignores that unbounded depth lets the sender pick your memory use
- Treats valid as whatever the current implementation accepts