Lexingtypical

Token Kinds

The kind is the terminal symbol the grammar will match on, so choosing the kinds is designing the interface between the lexer and the parser. Too coarse and the grammar does the lexer's work; too fine and the grammar has a rule per operator.

The question

How do I decide what counts as one token kind, and where does the keyword-versus-identifier decision belong?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

A token list in which each entry has been assigned a *terminal symbol* from the grammar's alphabet. The kind is the only part of a token the grammar looks at, so the set of kinds is exactly the set of terminals — which makes this the interface between two phases rather than an internal detail of one.

What this phase may assume or do

The kind assignment must be a total function of the matched text plus a fixed keyword table, and nothing else. The moment a kind depends on information the parser or the symbol table holds, the two phases are coupled and neither can run alone — which is the definition of the C lexer hack and the reason contextual keywords are handled by the parser rather than here.

Key points

The kind is the terminal symbol the grammar matches on, which makes the set of kinds the lexer/parser interface.
Five families cover almost everything: identifiers, keywords, literals, operators and punctuation, and trivia.
Keywords are implemented as identifiers plus a table lookup, which is why iffy is one identifier and why adding a keyword breaks existing code.
Granularity is decided by what the grammar needs to distinguish, not by taste — coarse kinds move work into the parser.
Whether newlines are trivia is a real language decision: C discards them, Python tokenises them, Go inserts semicolons for them.
Literal tokens usually carry the source text rather than a decoded value, because the value depends on target and type information the lexer does not have.

Five families, and what varies

Almost every language's token kinds fall into five families. Identifiers: names the language does not reserve. Keywords: names it does. Literals: numbers, strings, characters, booleans — text that denotes a value directly. Operators and punctuation: the fixed symbol vocabulary. Trivia: whitespace, comments and, in some languages, line terminators, which are usually discarded but sometimes are not.

What varies between languages is the *granularity*, and it varies more than you would expect. Is every keyword its own kind, or is there one KEYWORD kind with the text attached? Is >= one token or two? Is a newline trivia, or is it a statement terminator the grammar needs to see? Each answer moves work across the lexer/parser boundary, and the right answer depends on what the grammar wants to match on.

The example below is a complete statement in a C-family language. Note that >= is one token, not two — the grammar wants a single terminal for the operator, and splitting it would force the parser to reassemble it and to worry about > = with a space in between, which is not the same operator.

Kinds across four families in one statement

if (x >= 10) { return "ok"; }

Read it asEleven tokens over twenty-nine bytes. Four kinds of thing are represented: keywords, an identifier, two literals, and punctuation. Only the kind column is visible to the grammar — everything else in each record exists for diagnostics, for constant folding, or for tools.

Keywords are identifiers that lost a lookup

The standard implementation of keywords is deliberately indirect. The scanner matches the identifier pattern, producing the text if, and *then* looks that text up in a fixed table. If it is present, the token gets the keyword kind; if not, it stays an identifier. Nobody writes a separate automaton per keyword, and the reason is not laziness.

Doing it by lookup has three consequences worth knowing. First, iffy lexes as one identifier rather than as if followed by fy, because the identifier match runs to completion before the lookup happens. Second, adding a keyword to a language is a one-line table change — which is exactly why it is so tempting and why it breaks every program that used that name as an identifier. Third, the lookup is a hash table on a short string, executed once per identifier in the file; it is one of the few genuinely hot loops in a front end, and real compilers intern identifiers to make it a pointer comparison instead.

Reserving a word is a compatibility decision with a real cost. Every language that has grown has had to add vocabulary without breaking code, and the mechanisms for doing so — contextual keywords, # sigils, @ prefixes — all exist to avoid the table change. That story continues in [[lexer-hazards]].

The scan-then-look-up pattern, which is what almost every lexer actually does

1const KEYWORDS = new Map<string, TokenKind>([
2  ['if', 'KEYWORD_IF'],
3  ['else', 'KEYWORD_ELSE'],
4  ['let', 'LET'],
5  ['return', 'KEYWORD_RETURN'],
6])
7 
8function scanWord(src: string, start: number): Token {
9  let i = start
10  while (i < src.length && isIdentChar(src[i])) i++
11  const text = src.slice(start, i)
12  // The identifier match completes FIRST, then the table decides the kind.
13  return { kind: KEYWORDS.get(text) ?? 'IDENTIFIER', text, start, end: i }
14}

The order is the whole trick. Matching the identifier to its full extent before consulting the table is why iffy is one identifier, and it is also what makes contextual keywords implementable — leave the kind as IDENTIFIER and let the parser decide.

Granularity is an interface decision

typicalThe newline row is where languages genuinely diverge rather than merely differ in style. C, Java and Rust discard newlines and require explicit terminators. Python, Go and JavaScript all give line breaks grammatical meaning — Python with NEWLINE tokens, Go by inserting semicolons in the scanner, JavaScript with automatic semicolon insertion in the parser. Three different phases solving the same problem.

How finely to split kinds is not a matter of taste; it is decided by what the grammar needs to match. A grammar rule that says "an if statement starts with if" needs if to be a distinguishable terminal, so KEYWORD_IF earns its own kind. A grammar rule that says "an additive expression is a term, then any number of additive-operator-term pairs" needs to distinguish additive operators from multiplicative ones but does not need to distinguish + from - — so some lexers emit a single ADDOP kind with the text attached.

Two structural choices come up in every language design and are worth deciding explicitly rather than by accident.

Granularity choices and where the work lands

Choice	Coarse kinds	Fine kinds	Who pays
Keywords	One KEYWORD kind, text attached	One kind per keyword	Coarse: every grammar rule must compare text. Fine: a large terminal set, but a table-driven parser stays fast.
Operators	ADDOP / MULOP groups	PLUS, MINUS, STAR, SLASH	Coarse: the AST builder must re-inspect the text. Fine: more terminals, simpler actions.
Numbers	One NUMBER kind	INT, FLOAT, HEX, BIGINT	Coarse: the parser or a later phase decides the type. Fine: the lexer commits early and must be right.
Newlinestypical	Trivia, discarded	A NEWLINE terminal the grammar sees	Discarding requires the grammar to have explicit terminators; keeping them puts line structure into every rule.
Comments	Discarded	Retained as trivia attached to the next token	Discarding breaks formatters and doc extraction; retaining costs memory and a field on every token.

Literals: what the token carries

A literal token has a second question attached: does it carry the source text, the decoded value, or both? Carrying the text is cheap and lossless — 0x2A, 42 and 0b101010 stay distinguishable, which a formatter and a linter both need. Carrying the value means the lexer performs the conversion, which means the lexer needs to know the target type, the overflow rules and, for floats, the rounding mode.

Most production lexers carry the text and defer the conversion, because the conversion depends on information the lexer does not have. In C, whether 42 is int or long depends on the value and on the target's type sizes; in Rust, 42 has an inference variable for a type until the type checker resolves it. Committing at scan time would mean the lexer is making a target-dependent semantic decision, and that is the wrong phase for it.

String literals are the harder case, because escape processing genuinely has to happen somewhere and the lexer is the only phase that can see the raw bytes. The usual answer is that the lexer both records the raw span and produces the decoded value, keeping the two side by side — which is why a token record in a real compiler is bigger than the four fields this module shows.

How it works

The steps, in the order the compiler takes them.

Enumerate the terminals the grammar needs to distinguish; that list is the set of token kinds, and nothing else belongs in it.
Group the terminals into families and give each family a scanning routine: word, number, string, operator, punctuation.
Scan words with the identifier pattern to full extent, then look the text up in a fixed keyword table to assign the final kind.
Scan multi-character operators longest-first so that >= is preferred over >, and >>= over >>.
Decide per literal family whether the token carries text, value, or both, and record the decision — later phases will depend on it.
Decide whether trivia is discarded or attached, and if attached, to which neighbouring token; formatters need this to be consistent.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A keyword is added to the language and every program using it as a variable name stops compiling — a source-breaking change delivered as a feature.
Operator patterns are tried shortest-first, so >= lexes as > followed by = and every comparison in the codebase becomes a syntax error at the =.
The lexer converts numeric literals eagerly and a value that fits the target type is rejected on a host with different type sizes, so the compiler works on one machine and fails on another with a literal-out-of-range error.
Comments are discarded entirely and the documentation generator, the formatter and the lint suppression comments all need a second scanner that disagrees subtly with the first about where a comment ends.
A coarse KEYWORD kind forces grammar rules to compare token text, and a typo in one comparison makes one statement form silently unreachable — it parses as something else and produces a confusing error much later.

When it helps

Designing a new language or DSL: fixing the terminal set before writing either phase makes both phases fall out and keeps the interface reviewable.
Porting a grammar between parser generators, where the terminal set is the part that must be preserved exactly and the rest is notation.
Adding an operator to an existing language: knowing that the operator table is scanned longest-first tells you immediately which existing operators the new one can collide with.

When it hurts

Over-splitting kinds for a language with a large operator vocabulary produces a terminal set of several hundred symbols, which inflates a generated parser's tables without making any grammar rule clearer.
Under-splitting to keep the enum small pushes text comparisons into semantic actions, where they are unchecked by the generator and silently wrong when misspelled.

What it costs

Every one of these is paid by something.

Fine-grained kinds buy grammar rules that never inspect token text and cost a large terminal set, which enlarges generated parse tables and the switch statements in every consumer.
Coarse kinds buy a small, stable interface and cost type safety: the distinction moved from the enum, which the compiler checks, into string comparisons, which it does not.
Retaining trivia buys formatters, documentation extraction and comment-aware diagnostics, and costs a field on every token plus a policy decision about which token each comment attaches to.
Deferring literal conversion buys target independence and lossless round-tripping, and costs a later phase the work plus the need to keep the original text alive until it happens.

What else you could do

What a different compiler or language does instead, and when that is better.

A single WORD kind with all classification deferred to the parser, which is what some scannerless and PEG designs do. It makes contextual keywords free and makes every grammar rule responsible for text comparison.
Token kinds carrying a payload union rather than raw text — an interned symbol id for identifiers, a parsed value for numbers. This is what most production compilers actually do, and it costs the ability to reproduce the original spelling.
A lexer that emits *layers*: a significant-token stream for the parser and a trivia stream for tools, indexed by position. This is roughly the tree-sitter and Roslyn model, and it buys full-fidelity tooling at the cost of a more complex token representation.

See it for yourself

The flag, dump or tool that shows you this directly.

clang -Xclang -dump-tokens -fsyntax-only x.c prints the kind name Clang assigned to every token; the names come directly from its TokenKinds.def.
python3 -m tokenize file.py labels each token with a type name from the token module — NAME, NUMBER, OP, STRING, plus NEWLINE, INDENT and DEDENT.
The Go standard library's go/token package lists every terminal Go has, including the SEMICOLON tokens the scanner inserts at line ends that had none.
node --experimental-vm-modules is not the tool here; instead use astexplorer.net with the Babel parser and inspect tokens on the returned file to see JavaScript's kinds.

Plausible wrong readings

Stated the way a confident engineer states them.

"Keywords are matched by their own patterns." They are matched as identifiers and reclassified by lookup, which is why iffy is not if plus fy.
"The token kind tells you what the thing means." It tells you what category it is. IDENTIFIER says nothing about whether the name is a variable, a function or a type — that is name resolution.
"More token kinds is always more precise." It is more precise about categories the grammar may not distinguish, at the cost of table size and switch statements everywhere downstream.
"A NUMBER token holds a number." In most compilers it holds the text. The value comes later, because the value depends on the target type, and the lexer does not know it.

Misconceptions

The claim, and what is actually true.

Keywords and identifiers are recognised by different automata.

One automaton recognises both. A table lookup after the match assigns the kind, which is why the longest-match rule applies to keywords too.

The set of token kinds is an internal detail of the lexer.

It is the terminal alphabet of the grammar, so it is a published interface between two phases and changing it is a grammar change.

Discarding comments is free.

It costs every tool that needs them — formatters, doc generators, lint suppressions, coverage annotations — a second scanner, and two scanners disagree eventually.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

A token kind is the category the parser sees: keyword, identifier, number, string, operator, punctuation. Keywords are found by scanning an identifier and looking it up in a fixed table. How finely you split the categories depends on what the grammar needs to tell apart.

practical

When adding an operator to a language, check the operator table's match order first: multi-character operators must be tried before their prefixes, or the new >>= will lex as >> followed by =. When adding a keyword, accept that it is a source-breaking change and consider a contextual keyword instead — leave the kind as IDENTIFIER and let the parser recognise it positionally.

advanced

The newline decision is the one that reveals a language's whole design. C discards line breaks and demands semicolons, which makes the grammar clean and the source noisy. Python emits NEWLINE, INDENT and DEDENT tokens so the grammar sees line structure explicitly, which moves a non-context-free feature into the lexer. Go's scanner inserts a semicolon after any line whose last token could end a statement, so the grammar is C-like while the source is not — and that rule is why func f() { must have the brace on the same line, since a line ending in ) gets a semicolon. JavaScript pushed the same idea into the parser as automatic semicolon insertion, which is the most error-prone of the three because the decision is made after parsing has already failed. One design question, four phases, four sets of consequences.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThe scan-then-look-up implementation of keywords is what mainstream lexers do, including Clang, rustc and CPython. A hand-written scanner for a tiny DSL might branch on the first character instead, which is faster for a handful of keywords and does not scale past about ten.

implementationWhether a token carries text or a decoded value differs by compiler. Clang stores a pointer into the source buffer plus a length and interns identifiers into an IdentifierInfo; CPython's tokenizer yields the raw string and defers conversion to the compiler. A port that assumes one model and lands in the other has to add or remove a conversion phase.

specWhich words are reserved is normative per language and differs sharply: C has around forty keywords, Java around fifty, and Go deliberately has twenty-five and has said it will not add more. That last is a language-design commitment about compatibility, not an implementation limit.

If you were asked this in an interview

How does a lexer distinguish if from an identifier, and what does that imply about iffy?
Should >= be one token or two? Defend the answer with what the grammar needs.
Your language needs a new keyword but cannot break existing code. What are your options?

Connections

DSAhash-table string