When a parser prints 'expected one of X, Y or Z' at a bad token, where does that set come from?

## The set is a property of the parser's state, not of the file When a parser stops, nothing about the message comes from guessing. The parser is in some state that summarises everything consumed so far, and every state carries the answer to one question: *which terminals can legally come next?* That answer is the expected set. In a **table-driven** parser the state is a row of the parse table, and the expected set is exactly the terminals in that row whose entry is a real action rather than the error entry. In a **hand-written recursive-descent** parser there is no table, so the equivalent set is built at the failure point by the failing rule: the union of the tokens each still-possible alternative can start with, plus the tokens that would legitimately finish the construct. | Parser family | Where the set lives | Practical caveat | |---|---|---| | Table-driven, top-down prediction | The current state's row of legal terminals | Reflects a single lookahead position, so it can be narrow | | Table-driven, bottom-up | The legal actions of the state on top of the stack | Some reductions can fire before the bad token is noticed, so the reporting state may be a step removed from the clearest explanation; the bad token itself is never shifted | | Recursive descent, hand-written | Assembled by the failing rule from its live alternatives | Quality depends entirely on the author bothering to build it | ## Why the raw set makes a bad message - **Size.** A state deep inside an expression can permit dozens of terminals. Printing all of them buries the one the reader needs. - **Names.** Grammar terminals are internal names. A reader needs the spelling they would actually type, not the symbol the rule author chose. - **Over-approximation.** A state's legal actions can include tokens that would be rejected a step later, so the raw list sometimes suggests things that do not really work. - **Position.** The place the parser stopped is where the imbalance became undeniable, not always where the mistake was made. ## From a set to a sentence 1. **Map** each terminal to the text a user would write, so the message speaks the surface language. 2. **Collapse** families into a class name — any literal, any name, any binary operator — instead of listing members. 3. **Rank** what remains, usually by how deep in the current construct the option is, so the closest continuation appears first. 4. **Truncate** to a handful and say how many were dropped, rather than printing everything. 5. **Add the construct**: naming what the parser was in the middle of parsing is often more useful than the token list itself. ## Pointing at the right place An unclosed construct is the classic case where the failure position and the fixable position differ. The parser only discovers the imbalance when input runs out, so the naive message lands at the end of the file, far from the opener that was never matched. The fix is bookkeeping, not cleverness: recovery routines carry the position of the construct they are inside, so the diagnostic can name a **primary** location at the opener and a **secondary** one where the parser gave up. The same technique produces the much more useful phrasing that says which construct was left open, rather than which token was unexpected. ## What the expected set can never tell you The set is purely syntactic. It is derived from the rules and the state, and it knows nothing about names, declarations or types — a token can be perfectly legal here and still refer to something that does not exist, and that class of error belongs to a later phase entirely. The set also carries no notion of intent: it says what *could* follow, never what the author *meant*. A ranking heuristic can reorder it plausibly, but any message that claims to know the intended text is claiming more than the mechanism supports. ## Message stability One consequence that surprises people: because the set is a property of parser states, refactoring the grammar without changing the language changes the messages. Splitting a rule, factoring a common prefix or merging states all move which state reports and what it considers legal. Teams that care about message quality pin the important cases explicitly — with rules written for the common mistakes, or with per-state message overrides — rather than letting every grammar edit silently reword the diagnostics their users have learned to recognise.