AtlasLangimplementation

AtlasLang: The Lexer

Characters to tokens by maximal munch, with a half-open byte range on every token — and one hazard, `123abc`, that our lexer reports instead of silently splitting into two tokens and producing a parse error three lines away.

The question

How does AtlasLang decide where one token ends and the next begins?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A flat list of tokens, each carrying a kind, the exact matched text, a half-open byte range [start, end) into the source, and a 1-based line and column. Flat is the point: the lexer imposes no structure, only classification. The spans are the load-bearing part, because every diagnostic, every cross-panel highlight and anything a language server would ever want to say about a position derives from a range recorded here.

What this phase may assume or do

The lexer is entitled to assume nothing from earlier phases — it is the first phase — and it owes two guarantees to every later one. Every token's range must satisfy source.slice(start, end) === text, so that a span is a fact about the input rather than an approximation; and the scanner must consume at least one character per iteration even on input it cannot classify, so that a malformed file produces a finite list of diagnostics rather than an infinite loop. Both are enforced: the second by advancing past any unrecognised character before reporting it, the first by the token-span check in scripts/check-compilers.ts, which slices the source and compares.

Key points

  • Every token carries a kind, the matched text, a half-open byte range and a 1-based line and column; the range is the part everything downstream depends on.
  • Keywords are scanned as identifiers and then looked up in a table, so adding a keyword is a table entry rather than a new scanner rule.
  • Maximal munch appears in the code as one ordering decision: the two-character operator table is consulted before the one-character one.
  • Numbers and identifiers are both greedy, which creates the 123abc hazard: two well-formed tokens nobody wrote.
  • Our lexer detects that case with one character of lookahead and reports it where the mistake is, rather than letting the parser complain about a symptom further away.
  • The scanner always consumes at least one character, so a file full of unrecognised characters produces a finite list of diagnostics rather than a hang.
  • The [start, end) half-open convention is what makes lengths, empty tokens and adjacency all work without off-by-one corrections.

The token set

AtlasLang has thirty-eight token kinds and no surprises among them. Literals and names — NUMBER, STRING, TRUE, FALSE, IDENTIFIER. Keywords — LET, FN, RETURN, IF, ELSE, WHILE, PRINT, and the three type names INT, BOOL, STR. Operators — PLUS, MINUS, STAR, SLASH, PERCENT, EQUALS, EQEQ, BANGEQ, LT, LTE, GT, GTE, AND, OR, BANG. Punctuation — LPAREN, RPAREN, LBRACE, RBRACE, COMMA, SEMICOLON, COLON. And EOF.

Keywords are not scanned specially. An identifier is scanned first, and then looked up in a keyword table — so let and letter take the same path through the scanner and diverge on one hash lookup. That is not a shortcut; it is the correct design, because it makes "is this a keyword" one decision in one place rather than a set of prefix tests that can accidentally shadow the identifier rule. Adding a keyword to AtlasLang is a table entry.

Whitespace and comments produce no tokens at all. Line comments run to the newline; block comments run to the first */ and are deliberately not nested, which means a block comment cannot be used to comment out code that already contains one. That is a real language design decision with a real consequence, and it is written down in the lexer next to the code that implements it.

  • A newline advances the line counter and resets the column origin. Miss that and every span after the first line reports the wrong line, which is the single most common lexer bug.
  • An unterminated block comment is reported at the point it started, not at the end of the file, because that is where the fix goes.
  • A string runs to a closing quote or to a newline, whichever comes first; an unterminated one is reported and a STRING token is still emitted, so the parser has something to work with.
  • An unrecognised character is reported and skipped one character at a time, so a file full of them produces a list of diagnostics rather than one message and a hang.

Maximal munch, and why the two-character table is tested first

At each position the scanner takes the longest lexeme that forms a valid token. This is the *maximal munch* rule, and in AtlasLang it shows up in exactly one place in the code: the two-character operator table is consulted before the one-character table.

That ordering is the whole rule made concrete. Test = first and x == y lexes as EQUALS EQUALS — two assignments in a row, which is not a program, and the resulting parse error names the second =. Test == first and it lexes as EQEQ, which is what was written. The same ordering makes <=, >=, !=, && and || single tokens.

Maximal munch is also what makes numbers greedy: the scanner takes every consecutive digit. Combined with the identifier rule taking every consecutive alphanumeric, that produces the one genuinely awkward case in the language, which is the subject of the next section.

Every token of let n = 12 >= 3;, with real byte ranges
let n = 12 >= 3;

Read it asThe gaps between ranges are the whitespace, and no token covers them — 3 to 4, 5 to 6, 7 to 8, 10 to 11, 13 to 14. The lexer has decided which characters group together and has decided nothing else: it does not know that n is being declared, that >= produces a bool, or that any of this is a valid statement. Those are the parser's and the checker's questions.

The `123abc` hazard

simplifiedReal lexers face a much larger version of this. 1.2.3, 0x1p3, 1e, 1_000, 123L, and in C++ 0x1e+2 (which is one token in some contexts and three in others) are all decisions a production number scanner has to make, and several languages get them subtly wrong in ways that are now permanent. AtlasLang has integers and nothing else, so it has exactly one hazard, and it handles it.

Maximal munch scans 123 as a number and stops at a, because a is not a digit. The next iteration scans abc as an identifier. Two perfectly well-formed tokens, and a token sequence nobody wrote.

A lexer that stops there has done nothing wrong by its own rules and has produced a genuinely confusing outcome. The parser sees NUMBER IDENTIFIER, which is not a valid expression, and reports something like "expected ; after a let binding, found an identifier" — pointing at abc, several characters after the actual mistake, and describing a symptom rather than a cause. In a longer expression the reported position can be on a different line entirely.

So our lexer looks ahead. After scanning digits, if the very next character is a letter or an underscore, it consumes the whole alphanumeric run and reports the combined text as an invalid number literal, with a help line naming the offending suffix. It then emits a NUMBER token for the digits only and continues — because reporting an error is not a reason to stop producing tokens, and a parser given a plausible token stream can go on to find the next real problem.

This is the general shape of a good diagnostic and it is worth extracting: the error is reported where the mistake is, its message names what was found rather than what was expected downstream, and the help line says what to do. Load the errors example on the playground to see it alongside a parse error and a type error in the same file.

What let n = 123abc; produces — note the gap
let n = 123abc;

Read it asThe diagnostic covers [8, 14) — the whole of 123abc — and reads: "Invalid number literal 123abc." with the help "A number cannot be followed directly by abc. Separate them with an operator or a space." Compare that with what the parser would have said about a stray IDENTIFIER at offset 11, and the value of one character of lookahead in the lexer becomes obvious.

Spans are the product

It is tempting to think the lexer produces tokens and the ranges are bookkeeping. It is closer to the truth the other way round. The kinds are easy; the ranges are what everything downstream depends on and what cannot be recovered if they are dropped.

Every AtlasLang diagnostic points at a range. Every AST node carries the span of the tokens it was built from — Binary takes left.start and right.end, so an expression's span is exactly the text of the expression. The pipeline explorer can highlight the source when you click an IR instruction only because the range survived from the lexer through the parser into the tree and out the other side. A language server's go-to-definition, a debugger's line table and a source map are all the same fact recorded at the same place.

The half-open convention [start, end) is worth stating explicitly because it is the one that composes: end - start is the length, an empty token is start === end (which is exactly what EOF is), and adjacent tokens share a boundary value without overlapping. Getting this convention wrong by one produces diagnostics that underline one character too few, forever.

How it works

The steps, in the order the compiler takes them.

  • Scan left to right from position i, recording start = i at the top of each iteration.
  • Newlines advance the line counter and reset the column origin; other whitespace and both comment forms are consumed and produce no token.
  • A digit begins a number: consume all consecutive digits, then check whether the next character is alphabetic — if so, consume the whole run, report an invalid literal, and emit a NUMBER for the digits only.
  • A letter or underscore begins an identifier: consume all alphanumerics, then look the text up in the keyword table, defaulting to IDENTIFIER.
  • A quote begins a string: consume to a closing quote or a newline, handling two-character escapes, and report if it was not terminated.
  • Otherwise, test the two-character operator table, then the one-character table — that ordering is maximal munch.
  • An unrecognised character is consumed and reported, so the loop always advances.
  • A zero-width EOF token is appended at the end of the input, so the parser always has a token to point an error at.

How it breaks

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

  • A missing newline case in the scanner makes every diagnostic after line one report the wrong line, and the mistake is invisible on single-line test inputs.
  • Testing = before == splits every equality comparison into two assignments, and the parse error names a position two characters after the real one.
  • Without the number-suffix check, 123abc reaches the parser as two tokens and the error is reported against abc with a message about a missing semicolon.
  • A scanner that does not advance on an unrecognised character loops forever, and the symptom is a hung build rather than an error message.
  • Spans computed as character counts rather than byte offsets produce underlines that drift on any input where the two differ.
  • Discarding comment text entirely means a formatter or documentation tool built on this lexer cannot be written without changing the lexer — trivia has to be kept deliberately, and this one does not keep it.

When it helps

  • Reading any real lexer: the structure — a dispatch on the first character, greedy sub-scanners, a keyword table, an ordered operator test — is close to universal.
  • Debugging a compiler whose errors point at the wrong place, where the cause is almost always a span computed in the lexer or lost in the parser.
  • Designing a new language's token set, where the questions this lexer answers explicitly — nested comments, number suffixes, keyword handling — are exactly the ones that become permanent.
  • Building any tool that needs source positions: a linter, a formatter, a syntax highlighter or a language server all start from these ranges.

When it hurts

  • As a model for languages whose lexing is context-dependent: C++ template angle brackets, Python's indentation-driven INDENT/DEDENT, JavaScript's regex-versus-division ambiguity. None of those are lexable by a context-free scanner like this one.
  • For numeric literals of any richness. AtlasLang has one integer form, and the hard cases in real languages are all in the forms it does not have.
  • When trivia matters. This lexer discards whitespace and comments, so it cannot support a formatter that preserves them — see [[concrete-syntax-tree]].

What it costs

Every one of these is paid by something.

  • Reporting the 123abc hazard buys a diagnostic at the mistake and pays with one character of lookahead and a special case in the number scanner — a small but real complication of the simplest loop in the compiler.
  • Discarding whitespace and comments buys a small, fast token stream and pays by making formatters and refactoring tools impossible to build on this lexer without changing it.
  • Non-nesting block comments buy a trivial scanner and pay with the inability to comment out code containing a comment, which is a papercut every user of the language eventually hits.
  • Emitting a token after reporting an error buys continued parsing and pays with the possibility of cascading diagnostics that are artefacts of the recovery rather than real problems.
  • Storing four fields per token — kind, text, range, position — buys everything downstream and pays memory proportional to the input, which is why some production lexers store only offsets and recompute lines on demand.

What else you could do

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

  • A generated lexer from a regular-expression specification — lex, flex, re2c — which produces a table-driven DFA and is faster to change than hand-written code, at the cost of worse error messages and a build-time dependency. See [[nfa-vs-dfa]].
  • A lexer that keeps trivia attached to tokens, as Roslyn and rust-analyzer do, which makes formatting and lossless round-tripping possible at the cost of a larger representation — [[concrete-syntax-tree]].
  • No separate lexer at all: a scannerless or PEG parser matches characters directly, which removes the phase and its hazards and makes precedence and error reporting harder.
  • A lexer driven by the parser, which is how languages with context-dependent tokenisation cope; it works, and it destroys the clean phase separation that makes this one testable in isolation.

See it for yourself

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

  • /compilers/pipeline — the Tokens panel is this lexer's output for whatever you type, with each token highlighting its source range.
  • The lexer stepper walks the scanner one decision at a time, which is the fastest way to see maximal munch actually happening.
  • Type let n = 123abc; on the playground, or load the errors example, to see the hazard diagnostic with its help line.
  • Type x == y and then x = = y and compare the token streams — that is the two-character table doing its job.
  • src/compilers/sim/lexer.ts is under 250 lines including comments, and the comments explain the decisions rather than the code.
  • For comparison: clang -Xclang -dump-tokens file.c prints the same kind of stream for C, with locations in the same half-open style.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "The lexer understands the program." It classifies characters into groups. It does not know that a name refers to anything, that an operator has a precedence, or that a sequence of tokens is a valid statement.
  • "Maximal munch is a heuristic." It is a rule, and it is implemented as an ordering: longer alternatives are tested first. There is no ambiguity in the implementation.
  • "123abc is a lexer error in every language." In many it is two tokens and a parser error, which is exactly the confusing outcome our lexer exists to avoid. The detection is a design choice, not a requirement.
  • "Spans are for error messages." They are for error messages, cross-panel highlighting, debug line tables, source maps, go-to-definition and every refactoring tool. They are the most reused output of the phase.

Misconceptions

The claim, and what is actually true.

Keywords need special handling in the scanner.
They are identifiers the language reserved. Scan the identifier, then look it up — one place, one decision, and adding a keyword does not risk breaking the identifier rule.
A lexer error should stop compilation.
It should be reported and scanning should continue. A file with four typos should produce four messages, not four compilations.
Line and column are what a compiler stores.
Byte offsets are, because they are cheap to compute, exact, and composable. Lines and columns are derived for display; storing them as the primary representation makes every span operation more expensive.

Go deeper

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

overview

The lexer walks the source one character at a time and groups characters into tokens: names, numbers, operators, punctuation. At each position it takes the longest thing that forms a valid token, which is why >= is one token and not two. Each token remembers exactly which characters it came from, and that record is what lets every later error message point at the right place.

practical

When a compiler's error points at the wrong position, suspect the spans first — usually a newline case in the scanner or a span dropped in the parser. When adding an operator to a language, remember that the longer form must be tested first. And if you are ever tempted to have a lexer stop at the first bad character, do not: reporting every one and continuing costs a few lines and saves your users a compile per typo.

advanced

The 123abc case is a small instance of a general principle worth naming: a phase should report the errors it is uniquely positioned to explain, even when it could technically hand them on. The lexer is the only component that knows a number and a name were adjacent in the source with no separator; by the time the parser sees NUMBER IDENTIFIER that fact is gone and only a symptom remains. The same reasoning is why type checkers report "cannot find x" rather than letting the lowering fail, and why a linker cannot produce a good message about a missing function. Diagnostic quality is largely a question of which phase still holds the information needed to explain what went wrong — which makes it an architectural property, not a matter of writing nicer strings.

How much this depends on

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

implementationThe token kinds, the keyword table and the 123abc detection are AtlasLang's, in src/compilers/sim/lexer.ts at this revision. Other lexers make different calls on all three: many treat 123abc as two tokens, many support nested block comments, and several keep whitespace and comments as trivia rather than discarding them. What transfers is the shape, not the specifics.
simplifiedAtlasLang has one numeric form — a run of decimal digits — so it has one lexical hazard. Real languages carry floats, exponents, hex and binary forms, digit separators, type suffixes and raw strings, and the interactions between them are where production lexers are genuinely difficult. Nothing here should be read as evidence that number scanning is easy.
specMaximal munch is not a universal law but a rule each language chooses and writes down. C and C++ specify it as the "longest sequence of characters that could constitute a preprocessing token", which is why x+++y parses as x++ + y and why a<b<c>> was a C++ problem until the standard added a special case. A language that wants a different rule must say so.

If you were asked this in an interview

  • Where does maximal munch appear in this lexer's code, and what breaks if that ordering is reversed?
  • Why does our lexer report 123abc rather than emitting two valid tokens?
  • What does a later phase lose if the lexer does not record spans, and can it be recovered?

Connections

DSAhash-tablestack
Domains that do not exist yet
  • Testing & Reliability Engineering — Property-based testing over generated inputs
    The lexer has two properties worth checking on every input rather than on examples: every token's range slices back to its text, and the scanner always advances. Both are invariants a generator can attack, and the general technique for doing so is owned there.