Parsing and tokenizing

coreCommon atStripeAnthropicGoogleDatadogRead firstStrings Recursion Stacks Practise in the Sandbox →

Parse in two passes. A tokenizer (lexer) walks the characters once with a cursor and groups them into tokens such as number, name, >=, each tagged with its position. A parser then reads the tokens with one function per grammar rule (recursive descent). Both passes are O(n) for the grammars you meet in interviews, and every error should say what was expected and where.

The idea in plain words

Reading a sentence happens in two steps. First your eye groups letters into words. Then your brain checks the words against grammar. Nobody checks grammar one letter at a time.

Parsers work the same way:

The tokenizer answers “what are the words?”. count >= 10 becomes three tokens: the name count, the operator >=, the number 10. Spaces vanish here.
The parser answers “how do the words fit together?”. It knows that a list is [, then values separated by ,, then ], and it builds a tree or a value from that.

Splitting the job keeps each half small. The parser never worries about whitespace or how many digits a number has. The tokenizer never worries about nesting.

Two terms you’ll hear:

Maximal munch: at each position the tokenizer takes the longest token that fits. >= is one operator, not > then =. count2 is one name, not count then 2.
Grammar: the rules of the input, written like list := '[' (value (',' value)*)? ']'. * means “zero or more”, ? means “optional”. Writing it down first is half the work.

See it

Type any small program, or pick a preset, and step through. The cursor i only moves forward, and every token remembers its span and line:column. Try the unterminated and bad char presets to see what a useful error looks like.

Tokenizer: characters in, tokens out

type, then step

source (≤ 60 chars, newlines OK)try

␣

(

␣

)

␣

{

↵

␣

;

↵

}

#	kind	text	span [start,end)	line:col
no tokens yet

tokens0

token just readname / number / stringkeywordoperator / punctuationskipped whitespaceerror

The lexer keeps one cursor, i. At each position it looks at the current character and decides what kind of token starts here.

1 / 22speed

When to reach for it

The problem says…	Why a tokenizer + parser fits
“parse this log line / config / query / command”	Text with structure. A cursor-based scanner beats a pile of `split` calls once quoting or nesting appears.
quoted values, escapes, “a comma inside quotes is data”	`split` can’t know it is inside quotes. A scanner with a tiny bit of state can.
nesting: brackets, parentheses, `{...}` blocks	Nesting is recursion. One function per rule mirrors the grammar exactly.
“return an error for invalid input”	A hand-written parser knows the position and what it expected, so errors are precise.
operator precedence (`*` before `+`)	Same toolkit, plus a precedence rule. See expression evaluation.

How it works

Pass 1: the tokenizer

Skip whitespace (unless it is meaningful in your format, like newlines in a line-based format).
Single-character tokens such as [, ], , are emitted directly.
Multi-character tokens (numbers, names, two-character operators) use maximal munch: keep reading while the next character still fits.
Strings scan to the closing quote. A backslash means “the next character is literal”, so \" does not end the string.
Anything else is an error. Report the character and its offset (or line and column).

from dataclasses import dataclass


@dataclass(frozen=True)
class Token:
    kind: str  # "num" | "str" | "punct"
    text: str
    pos: int   # offset of the token's first character


class LexError(Exception):
    pass


def is_digit(c: str) -> bool:
    return "0" <= c <= "9"  # str.isdigit() also accepts "²" and other Unicode digits


def tokenize(src: str) -> list[Token]:
    out: list[Token] = []
    i = 0
    while i < len(src):
        c = src[i]
        if c in " \t\r\n":                       # 1. whitespace separates tokens; drop it
            i += 1
        elif c in "[],":                         # 2. one-character punctuation
            out.append(Token("punct", c, i))
            i += 1
        elif is_digit(c) or (c == "-" and i + 1 < len(src) and is_digit(src[i + 1])):
            start = i                            # 3. maximal munch: take digits while they last
            i += 1
            while i < len(src) and is_digit(src[i]):
                i += 1
            out.append(Token("num", src[start:i], start))
        elif c == '"':                           # 4. string: scan to the closing quote, decode \x
            start, i, buf = i, i + 1, []
            while i < len(src) and src[i] != '"':
                if src[i] == "\\" and i + 1 < len(src):
                    i += 1
                buf.append(src[i])
                i += 1
            if i >= len(src):
                raise LexError(f"unterminated string starting at offset {start}")
            i += 1
            out.append(Token("str", "".join(buf), start))
        else:                                    # 5. say *where*, not just "bad input"
            raise LexError(f"unexpected {c!r} at offset {i}")
    return out


if __name__ == "__main__":
    toks = tokenize('[12, "a\\"b", -3]')
    assert [(t.kind, t.text, t.pos) for t in toks] == [
        ("punct", "[", 0), ("num", "12", 1), ("punct", ",", 3),
        ("str", 'a"b', 5), ("punct", ",", 11), ("num", "-3", 13), ("punct", "]", 15)]
    for bad, msg in [('["oops', "offset 1"), ("[1; 2]", "offset 2")]:
        try:
            tokenize(bad)
            raise AssertionError("expected LexError")
        except LexError as e:
            assert msg in str(e), e
    print("ok")

import assert from "node:assert/strict";

type Kind = "num" | "str" | "punct";
interface Token { kind: Kind; text: string; pos: number } // pos = offset of first char

class LexError extends Error {}

const isDigit = (c: string): boolean => c >= "0" && c <= "9";

export function tokenize(src: string): Token[] {
  const out: Token[] = [];
  let i = 0;
  while (i < src.length) {
    const c = src[i];
    if (" \t\r\n".includes(c)) {
      i++; // 1. whitespace separates tokens; drop it
    } else if ("[],".includes(c)) {
      out.push({ kind: "punct", text: c, pos: i }); // 2. one-character punctuation
      i++;
    } else if (isDigit(c) || (c === "-" && i + 1 < src.length && isDigit(src[i + 1]))) {
      const start = i++; // 3. maximal munch: take digits while they last
      while (i < src.length && isDigit(src[i])) i++;
      out.push({ kind: "num", text: src.slice(start, i), pos: start });
    } else if (c === '"') {
      const start = i++; // 4. string: scan to the closing quote, decode \x
      let buf = "";
      while (i < src.length && src[i] !== '"') {
        if (src[i] === "\\" && i + 1 < src.length) i++;
        buf += src[i++];
      }
      if (i >= src.length) throw new LexError(`unterminated string starting at offset ${start}`);
      i++;
      out.push({ kind: "str", text: buf, pos: start });
    } else {
      throw new LexError(`unexpected ${JSON.stringify(c)} at offset ${i}`); // 5. say where
    }
  }
  return out;
}

assert.deepEqual(tokenize('[12, "a\\"b", -3]').map((t) => [t.kind, t.text, t.pos]), [
  ["punct", "[", 0], ["num", "12", 1], ["punct", ",", 3],
  ["str", 'a"b', 5], ["punct", ",", 11], ["num", "-3", 13], ["punct", "]", 15]]);
assert.throws(() => tokenize('["oops'), /offset 1/);
assert.throws(() => tokenize("[1; 2]"), /offset 2/);
console.log("ok");

var toks = Lexer.Tokenize("[12, \"a\\\"b\", -3]");
var shown = string.Join(" ", toks.Select(t => $"{t.Kind}:{t.Text}@{t.Pos}"));
if (shown != "punct:[@0 num:12@1 punct:,@3 str:a\"b@5 punct:,@11 num:-3@13 punct:]@15")
    throw new Exception(shown);
foreach (var (bad, msg) in new[] { ("[\"oops", "offset 1"), ("[1; 2]", "offset 2") })
{
    try { Lexer.Tokenize(bad); throw new Exception("expected LexException"); }
    catch (LexException e) when (e.Message.Contains(msg)) { }
}
Console.WriteLine("ok");

record Token(string Kind, string Text, int Pos); // Pos = offset of first char

class LexException(string message) : Exception(message);

static class Lexer
{
    static bool IsDigit(char c) => c is >= '0' and <= '9'; // char.IsDigit accepts other scripts too

    public static List<Token> Tokenize(string src)
    {
        var output = new List<Token>();
        int i = 0;
        while (i < src.Length)
        {
            char c = src[i];
            if (c is ' ' or '\t' or '\r' or '\n') i++;                 // 1. drop whitespace
            else if (c is '[' or ']' or ',') output.Add(new("punct", c.ToString(), i++)); // 2. punctuation
            else if (IsDigit(c) || (c == '-' && i + 1 < src.Length && IsDigit(src[i + 1])))
            {
                int start = i++;                                          // 3. maximal munch
                while (i < src.Length && IsDigit(src[i])) i++;
                output.Add(new("num", src[start..i], start));
            }
            else if (c == '"')
            {
                int start = i++;                                          // 4. string, decode \x
                var buf = new System.Text.StringBuilder();
                while (i < src.Length && src[i] != '"')
                {
                    if (src[i] == '\\' && i + 1 < src.Length) i++;
                    buf.Append(src[i++]);
                }
                if (i >= src.Length) throw new LexException($"unterminated string starting at offset {start}");
                i++;
                output.Add(new("str", buf.ToString(), start));
            }
            else throw new LexException($"unexpected '{c}' at offset {i}"); // 5. say where
        }
        return output;
    }
}

Pass 2: recursive descent

Write the grammar first. For nested lists of numbers and strings:

value := number | string | list
list  := '[' ( value ( ',' value )* )? ']'

Each rule becomes a function. A function looks at the next character or token (one token of lookahead), picks a branch, and calls the functions for the pieces. Nesting falls out for free: list calls value, which may call list again.

Top level: parse exactly one value, then require end of input. Otherwise [1] junk is silently accepted.
One method per rule. The next character decides the branch: [ means list, " means string, a digit or - means number.
Rules call each other. That recursion is the nesting.
When the next thing isn’t what the rule needs, throw an error naming what was expected and the offset.

Value = int | str | list["Value"]


class ParseError(Exception):
    def __init__(self, msg: str, pos: int) -> None:
        super().__init__(f"{msg} at offset {pos}")
        self.pos = pos


class Parser:
    """value := number | string | list ;  list := '[' (value (',' value)*)? ']'"""

    def __init__(self, src: str) -> None:
        self.src, self.i = src, 0

    def peek(self) -> str:  # next significant char, "" at the end
        while self.i < len(self.src) and self.src[self.i] == " ":
            self.i += 1
        return self.src[self.i] if self.i < len(self.src) else ""

    def expect(self, ch: str) -> None:
        if self.peek() != ch:
            raise ParseError(f"expected {ch!r}, found {self.peek() or 'end of input'!r}", self.i)
        self.i += 1

    def parse(self) -> Value:  # 1. exactly one value, then nothing else
        v = self.value()
        if self.peek():
            raise ParseError("unexpected trailing input", self.i)
        return v

    def value(self) -> Value:  # 2. one method per rule; one char of lookahead picks the branch
        c = self.peek()
        if c == "[":
            return self.list_()
        if c == '"':
            end = self.src.find('"', self.i + 1)
            if end < 0:
                raise ParseError("unterminated string", self.i)
            s, self.i = self.src[self.i + 1:end], end + 1
            return s
        start = self.i
        if c == "-":
            self.i += 1
        while self.i < len(self.src) and "0" <= self.src[self.i] <= "9":
            self.i += 1
        if self.i == start or self.src[start:self.i] == "-":
            raise ParseError("expected a value", start)
        return int(self.src[start:self.i])

    def list_(self) -> list[Value]:  # 3. the rule recurses through value() for nesting
        self.expect("[")
        items: list[Value] = []
        if self.peek() == "]":
            self.i += 1
            return items
        while True:
            items.append(self.value())
            if self.peek() != ",":
                self.expect("]")  # 4. error names what was expected and where
                return items
            self.i += 1


if __name__ == "__main__":
    assert Parser('[1, [2, "a"], [], -7]').parse() == [1, [2, "a"], [], -7]
    for bad, pos in [("[1 2]", 3), ("[1,]", 3), ("[1] x", 4), ("[[1]", 4)]:
        try:
            Parser(bad).parse()
            raise AssertionError("expected ParseError")
        except ParseError as e:
            assert e.pos == pos, (bad, e)
    print("ok")

import assert from "node:assert/strict";

type Value = number | string | Value[];

class ParseError extends Error {
  constructor(msg: string, readonly pos: number) { super(`${msg} at offset ${pos}`); }
}

/** value := number | string | list ;  list := '[' (value (',' value)*)? ']' */
class Parser {
  private i = 0;
  constructor(private readonly src: string) {}

  private peek(): string { // next significant char, "" at the end
    while (this.src[this.i] === " ") this.i++;
    return this.src[this.i] ?? "";
  }

  private expect(ch: string): void {
    if (this.peek() !== ch) throw new ParseError(`expected '${ch}', found '${this.peek() || "end of input"}'`, this.i);
    this.i++;
  }

  parse(): Value { // 1. exactly one value, then nothing else
    const v = this.value();
    if (this.peek()) throw new ParseError("unexpected trailing input", this.i);
    return v;
  }

  private value(): Value { // 2. one method per rule; one char of lookahead picks the branch
    const c = this.peek();
    if (c === "[") return this.list();
    if (c === '"') {
      const end = this.src.indexOf('"', this.i + 1);
      if (end < 0) throw new ParseError("unterminated string", this.i);
      const s = this.src.slice(this.i + 1, end);
      this.i = end + 1;
      return s;
    }
    const start = this.i;
    if (c === "-") this.i++;
    while (this.src[this.i] >= "0" && this.src[this.i] <= "9") this.i++;
    const text = this.src.slice(start, this.i);
    if (text === "" || text === "-") throw new ParseError("expected a value", start);
    return Number(text);
  }

  private list(): Value[] { // 3. the rule recurses through value() for nesting
    this.expect("[");
    const items: Value[] = [];
    if (this.peek() === "]") { this.i++; return items; }
    for (;;) {
      items.push(this.value());
      if (this.peek() !== ",") { this.expect("]"); return items; } // 4. name what was expected
      this.i++;
    }
  }
}

assert.deepEqual(new Parser('[1, [2, "a"], [], -7]').parse(), [1, [2, "a"], [], -7]);
for (const [bad, pos] of [["[1 2]", 3], ["[1,]", 3], ["[1] x", 4], ["[[1]", 4]] as const) {
  assert.throws(() => new Parser(bad).parse(), (e: unknown) => e instanceof ParseError && e.pos === pos);
}
console.log("ok");

// A Value is a long, a string, or a List<object> of values.
if (Show(new Parser("[1, [2, \"a\"], [], -7]").Parse()) != "[1,[2,\"a\"],[],-7]") throw new Exception("parse");
foreach (var (bad, pos) in new[] { ("[1 2]", 3), ("[1,]", 3), ("[1] x", 4), ("[[1]", 4) })
{
    try { new Parser(bad).Parse(); throw new Exception($"expected ParseException for {bad}"); }
    catch (ParseException e) when (e.Pos == pos) { }
}
Console.WriteLine("ok");

static string Show(object v) => v switch
{
    List<object> xs => "[" + string.Join(",", xs.Select(Show)) + "]",
    string s => $"\"{s}\"",
    _ => v.ToString()!,
};

class ParseException(string msg, int pos) : Exception($"{msg} at offset {pos}") { public int Pos { get; } = pos; }

/// value := number | string | list ;  list := '[' (value (',' value)*)? ']'
class Parser(string src)
{
    int i;

    char Peek() // next significant char, '\0' at the end
    {
        while (i < src.Length && src[i] == ' ') i++;
        return i < src.Length ? src[i] : '\0';
    }

    void Expect(char ch)
    {
        if (Peek() != ch) throw new ParseException($"expected '{ch}'", i);
        i++;
    }

    public object Parse() // 1. exactly one value, then nothing else
    {
        var v = Value();
        if (Peek() != '\0') throw new ParseException("unexpected trailing input", i);
        return v;
    }

    object Value() // 2. one method per rule; one char of lookahead picks the branch
    {
        char c = Peek();
        if (c == '[') return List();
        if (c == '"')
        {
            int end = src.IndexOf('"', i + 1);
            if (end < 0) throw new ParseException("unterminated string", i);
            var s = src[(i + 1)..end];
            i = end + 1;
            return s;
        }
        int start = i;
        if (c == '-') i++;
        while (i < src.Length && src[i] is >= '0' and <= '9') i++;
        var text = src[start..i];
        if (text is "" or "-") throw new ParseException("expected a value", start);
        return long.Parse(text);
    }

    List<object> List() // 3. the rule recurses through Value() for nesting
    {
        Expect('[');
        var items = new List<object>();
        if (Peek() == ']') { i++; return items; }
        while (true)
        {
            items.Add(Value());
            if (Peek() != ',') { Expect(']'); return items; } // 4. name what was expected
            i++;
        }
    }
}

This version is scannerless: it reads characters directly, which keeps a small grammar to one file. For anything with keywords or multi-character operators, run the tokenizer first and let the parser peek() and expect() on tokens instead. The structure of the parser stays identical.

Errors people can act on

A good error answers three questions: what went wrong, where, and what was expected.

error: expected ']', found '2'
  1 | [1 2]
    |    ^

Track the offset of every token. Convert to line and column only when printing (count \n before the offset).
For an unterminated string or bracket, point at where it opened. The end of input is not where the user needs to look.
Decide early: stop at the first error (simplest, normal for parsers) or recover and collect several. See input validation for the collect-all style.

What it costs

	Time	Extra space
Tokenizer (cursor, one pass)	O(n): each character is read once	O(tokens)
Recursive descent, one-token lookahead	O(n): each token is consumed once, no backtracking	O(depth) call stack
Naive backtracking parser	can be exponential	O(depth)
Regex with nested quantifiers (`(a+)+$`)	can be exponential on a crafted input (ReDoS)	small

Two things drive the cost in practice:

Never re-scan. A loop that calls src.find or slices the rest of the string at every position turns O(n) into O(n²). Keep one cursor and move it forward.
Depth is stack. Recursive descent uses one stack frame per nesting level. [[[[…]]]] 100,000 levels deep will overflow: Python’s default recursion limit is 1,000, and .NET and Node crash on deep enough input. Either cap the depth with a clear error, or switch that rule to an explicit stack.

Variations you’ll meet

Tokens with a kind enum. In C# and TS, give tokens a kind from a closed set (an enum or a string-literal union). The parser’s switch then gets exhaustiveness checks for free.
Keywords are identifiers first. Read a whole name, then look it up in a keyword table. Don’t try to match if as a prefix: iffy is a name.
Line-based formats (logs, INI files, HTTP headers): split into lines only if a value can never contain a line break. Then tokenize each line.
Operator precedence. Either one grammar rule per precedence level (expr := term ('+' term)*, term := factor ('*' factor)*) or a Pratt parser. Covered in expression evaluation.
Streaming input. When the data arrives in chunks, a token may be split across two chunks. Keep the unfinished tail and prepend it to the next chunk, or write the lexer as a state machine (see state machines).

CSV is a parsing problem, not a split problem

CSV looks like “split on commas”, and that is the classic trap. RFC 4180 says a field may be wrapped in double quotes, and then it may contain commas, line breaks, and "" for a literal quote. Pick a case below and compare.

split(',') vs a real CSV reader

pick a case

raw text

"Lovelace, Ada",36,London

text.split('\n') then line.split(',')

"Lovelace Ada"36London 4 fields

RFC 4180 reader

Lovelace, Ada36London 3 fields

Different. The comma inside the quotes is data, not a separator. Splitting on every comma gives 4 fields instead of 3, and the quote characters leak into the values.

The lesson generalizes. A reader needs to know what state it is in (inside quotes or not), so it must be a scanner that walks characters with a flag, not a chain of split calls. Also decide, and say out loud, the edge cases the spec leaves open: spaces around quotes, a stray " in the middle of an unquoted field, a trailing line break, an empty line.

Pitfalls

Accepting trailing garbage. Parse the value, then require end of input.
Unicode “digits”. Python’s str.isdigit() and C#’s char.IsDigit accept digits from other scripts (and Python also accepts ²). Compare against '0'..'9' when the format is ASCII.
Built-in number parsers are lenient in surprising ways. Python’s int(" 42 ") and int("1_000") both succeed. JavaScript’s Number("") is 0 and parseInt("12abc") is 12. .NET’s double.Parse("1,5") depends on the current culture: pass CultureInfo.InvariantCulture. Know what you accept.
Not consuming on every path. If some branch neither advances the cursor nor throws, the loop spins forever. Each iteration must move i or fail.
Off-by-one at the end. Every src[i + 1] look-ahead needs an i + 1 < len check (or a language that returns undefined/"" safely).
Position of the error. Report where the problem started (the opening quote), and use the same base everywhere (0-based offsets, 1-based line:column is the usual convention).

In the interview

Ask about the input: Is it always well formed? Can values contain the separator? Quotes? Escapes? Newlines? Is it ASCII? How deep can nesting go? How large is it?
Ask about errors: return a sentinel, throw, or a result type? First error or all of them? What should the message contain?
Say the plan: “I’ll write the grammar in two lines, tokenize with one cursor, then one function per rule.” Interviewers like hearing grammar first.
Test the edges before you’re asked: empty input, only whitespace, a single token, the deepest nesting allowed, an unterminated quote, trailing garbage.
Likely follow-ups: add a new token kind, add escapes, report line:column, stream the input in chunks, recover from errors and keep going.

Check yourself

pick one

A file is read with text.split('\n'), then each line is parsed as CSV with a correct quote-aware field splitter. What can still go wrong?

Check yourself

pick one

Your recursive-descent parser handles nested lists. A user sends a list nested 200,000 levels deep. What happens, and what is the usual fix?

Check yourself

pick one

Using maximal munch with the operators =, ==, <, <=, how is the text a<==b tokenized?

Practice on your own

Classic exercises, not gym questions:

A JSON subset: objects, arrays, strings with \" and \\ escapes, integers, true/false/null, with line:column errors.
An INI file reader: [section] headers, key = value lines, ; comments, and a clear error for a key before any section.
A URL query-string parser: split on & and =, decode %2F and +, and keep repeated keys as lists.
A semantic-version parser and comparator following semver.org (pre-release identifiers make it interesting).
Parse the Apache “common log format” line into fields, where the request is quoted and the timestamp is in brackets.

Go deeper

Robert Nystrom, Crafting Interpreters, ch. 4 “Scanning” and ch. 6 “Parsing Expressions”: the clearest walk-through of a hand-written lexer and recursive descent.
RFC 4180, the closest thing CSV has to a spec, and Python’s csv module docs for the dialect options real files need.
Aho, Lam, Sethi, Ullman, Compilers: Principles, Techniques, and Tools (“the Dragon Book”), ch. 3 (lexical analysis) and ch. 4.4 (top-down parsing).
OWASP, Regular expression Denial of Service (ReDoS), for why a hand-written scanner is often the safer choice.

Expression evaluationPrecedence, shunting-yard and evaluating a syntax tree.

Input validationValidate at the boundary; fail fast or collect every error.

State machinesA lexer is a small state machine over characters.

StacksThe explicit-stack alternative to deep recursion.

Parsing and tokenizing

The idea in plain words

See it

When to reach for it

How it works

Pass 1: the tokenizer

Pass 2: recursive descent

Errors people can act on

What it costs

Variations you’ll meet

CSV is a parsing problem, not a split problem

Pitfalls

In the interview

Check yourself

Practice on your own

Go deeper

Related