cf.completefrontend
STRING ALGORITHMS · CORE

Tokenizing text

Turn a string into a list of meaningful pieces, called tokens, by scanning it once and grouping characters by kind.

Time O(n)Space O(n)11 practice problemsStep-through picture

The idea

A computer can't work with price * (qty + 2) as one long string. It first splits it into tokens: the name price, the symbol *, the symbol (, the name qty, the symbol +, the number 2, and the symbol ). This step is called tokenizing, or lexing, and the code that does it is a tokenizer.

A tokenizer walks the text with an index i. It looks at the current character and decides what kind of token starts here. A digit starts a number, so it keeps moving i while digits continue. A letter starts a name. A symbol like + is a token on its own. Spaces are skipped.

Each token is cut out with source.slice(start, i), where start is where the token began. The result is a list of small objects like { type: "number", value: "2" } that the next step, such as a calculator or a parser, can read easily.

An everyday example

Sorting a sentence into word cards

You copy a sentence onto cards, one card per word or punctuation mark. You put your finger on the first letter, slide it right until the word ends, and write that word on a card. A comma gets its own card. Spaces don't get cards at all. Each card also gets a small label: word, number, or punctuation.

How the example maps to the code
In the exampleIn the code
Your finger on the sentenceThe index i
Where the current word beganstart
Sliding to the end of the wordwhile (... /[0-9.]/.test(source[i])) i++
Writing a cardtokens.push({ type, value: source.slice(start, i) })
Skipping spacesif (char === " ") i++

From the slow way to tokenizing text

  1. A first try is source.split(" "). For rate * (h1 - 0.5) it gives rate, *, (h1, -, and 0.5): the brackets stick to their neighbors. And rate*(h1-0.5), with no spaces, wouldn't split at all. Spaces aren't what separates tokens.
  2. So what decides where a token ends? Its kind. A number continues while digits or . follow; a name continues while letters, digits, or _ follow; a symbol like * is always one character. The first character of a token tells you its kind, and the kind tells you where it stops.
  3. That suggests reading with an index i that only moves forward. Look at source[i], pick the branch for its kind, remember start = i, move i while the token continues, and cut the token out with source.slice(start, i). Spaces get a branch of their own that just moves i by one.
  4. Anything that fits no branch is an error, and reporting the character and its index right away makes it easy to fix. Pick a kind, consume it, push a token, and repeat until i reaches the end: that loop is a tokenizer.

How it works

  1. Make an empty tokens list and set i = 0.
  2. While i is inside the text, read char = source[i].
  3. If char is a space, skip it with i++.
  4. If char is a digit, remember start = i, move i forward while digits or . continue, and push a number token with source.slice(start, i).
  5. If char is a letter or _, do the same for letters, digits, and _, and push a name token.
  6. If char is one of the symbols +-*/(), push it as a symbol token and move i by one.
  7. Anything else is an error: throw with the character and its position so the user can fix it.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function tokenize(source) {
  2. const tokens = [];
  3. let i = 0;
  4. while (i < source.length) {
  5. const char = source[i];
  6. if (char === " ") {
  7. i++;
  8. } else if (/[0-9]/.test(char)) {
  9. const start = i;
  10. while (i < source.length && /[0-9.]/.test(source[i])) i++;
  11. tokens.push({ type: "number", value: source.slice(start, i) });
  12. } else if (/[A-Za-z_]/.test(char)) {
  13. const start = i;
  14. while (i < source.length && /[A-Za-z0-9_]/.test(source[i])) i++;
  15. tokens.push({ type: "name", value: source.slice(start, i) });
  16. } else if ("+-*/()".includes(char)) {
  17. tokens.push({ type: "symbol", value: char });
  18. i++;
  19. } else {
  20. throw new Error(`Unexpected character ${char} at ${i}`);
  21. }
  22. }
  23. return tokens;
  24. }

How fast it is

TimeO(n)
Extra memoryO(n)

i only moves forward and each character is handled once. The token list holds all the characters at most once.

  • Best caseO(n)

    Only spaces, like " ": each character is skipped after one check, and tokens stays empty.

  • Average caseO(n)

    A normal expression: each character is tested a few times by the if chain or once by an inner while.

  • Worst caseO(n)

    Long names or numbers, like a 10,000-digit number: the inner while reads them in one loop, still once per character, and slice copies each token once.

Common mistakes

  • Using source.split(" "). It breaks (qty+2) into one piece and can't tell numbers from names.
  • Forgetting to move i in a branch. If a symbol is pushed without i++, the loop pushes it forever.
  • Reading past the end in the inner while. Check i < source.length before source[i], or the loop tests undefined.
  • Checking one-character symbols before two-character ones, so <= becomes < and =. Try the longest symbols first.

When to use it

Look for these clues in a problem:

  • The input is text with structure: a formula, a query string, a CSS rule, a template, or a command.
  • You need to split text, but a simple split would break things like quoted strings or multi-digit numbers.
  • The next step needs to know what kind each piece is: number, name, operator, or text.
  • The problem mentions parsing, evaluating, or validating an expression.

Check yourself

Answer each one in your head first, then open it.

Why can't source.split(" ") tokenize rate*(h1-0.5)?

There are no spaces, so it returns the whole text as one piece. Tokens are separated by changes of kind, not by spaces.

What happens if the symbol branch forgets i++?

i never moves, so the same symbol is pushed again and again, and the loop never ends.

Why does the name branch accept digits in its while but not in its first test?

So h1 is one name, while 1h starts with a number. If digits could start names, a token like 12 would be ambiguous.

How many tokens does "(a)" produce, and of which kinds?

3: the symbol (, the name a, and the symbol ).

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 11 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule at the top of each loop: tokens holds exactly the tokens of source.slice(0, i), and i sits at the start of a token or at a space. At i = 0 nothing has been read, so the rule holds.

Each branch keeps it. The first character picks one kind, and the inner while moves i to the first character that can't continue that kind, so source.slice(start, i) is the longest token of that kind starting at start. The character at the new i must begin the next token or be a space, so i is at a boundary again. Every branch moves i forward by at least one, so the loop can't get stuck.

The loop ends when i reaches source.length, or throws at the first character no branch accepts. In the first case the rule covers the whole text, so tokens is its complete list of tokens. Since i only moves forward and each character is read by one branch, the work is O(n).

Going deeper

3 more ideas

Why one pass is enough

The first character of a token decides its kind, and the token continues as long as the next characters fit that kind. So the tokenizer never needs to look back. Every character is either skipped, added to a token, or reported as an error, and i only moves forward.

How fast it is

Every character is visited once by the outer loop or an inner while, never both, so the time is O(n). The tokens together hold at most n characters, so the memory is O(n).

Strings, escapes, and longer symbols

Real tokenizers handle more: a " starts a string token that runs to the next unescaped ", and two-character symbols like <= or === are checked before one-character ones, so <= isn't split into < and =. The structure stays the same: look at the first character, then consume while the token continues.

Work it by hand

Every step in a table, with why

Split a small expression into tokens. Some symbols have no spaces around them, a name contains a digit, and a number has a decimal point.

source = "rate*(h1 - 0.5)"

Stepi beforecharBranchi afterToken pushedWhat happensWhy
10rname4name rateread until *r is a letter, so start = 0, and i moves while letters, digits, or _ continue. It stops at *, index 4.
24*symbol5symbol *one characterNo space was needed between rate and *; the kind of character decides.
35(symbol6symbol (one characterSymbols are always a single character in this tokenizer.
46hname8name h1a digit inside a nameInside a name, digits are allowed, so h1 is one token. A digit can't start a name, though.
58spacespace9-skipSpaces only move i; they never become tokens.
69-symbol10symbol -one characterThe tokenizer doesn't know whether this is minus or subtraction; that's the parser's job.
710spacespace11-skipAnother space.
8110number14number 0.5read digits and .The number branch accepts ., so 0.5 is one token, ending at ).
914)symbol15symbol )one characteri is now 15, the length of source, so the loop ends.

It returns 7 tokens: rate, *, (, h1, -, 0.5, and ). The outer loop ran 9 times, and every character was handled by exactly one branch.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Tokenizing textO(n)O(n)You control the grammar and want clear errors with positions.
split with a separatorO(n)O(n)Very simple formats, like words separated by commas, where each piece's kind doesn't matter.
One sticky regular expressionO(n)O(n)Short code for a small grammar, if weaker error messages are acceptable.
A parser generatorO(n)O(n)Big grammars, like a full programming language, where hand-written branches get hard to maintain.

Extra memory: O(n): the tokens together hold at most n characters, plus one small object per token.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Tokenizing text and the other approaches, on a scale where each line up is 10 times more steps.
  • Tokenizing text, split with a separator, One sticky regular expression, A parser generator O(n)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Tokenizing text101,0001 million
split with a separator101,0001 million
One sticky regular expression101,0001 million
A parser generator101,0001 million

Inputs that need care

6 tricky inputs
Empty text: ""
The loop never runs and it returns [].
A character with no branch: "a = 1"
It pushes a, skips the space, and throws Unexpected character = at 2. Callers should catch it and show the message with its position.
Two dots in a number: "1.2.3"
The number branch accepts every ., so it returns one number token, 1.2.3. Check it later with Number(value), or end the number at its second ..
A digit followed by a letter: "2x"
It returns the number 2 and the name x. Whether that's an error or means 2 * x is for the parser to decide.
A minus sign before a number: "-4"
It returns the symbol - and the number 4. Telling a negative number from subtraction needs context, so the parser handles it.
Tabs or new lines: "a\t1"
The space branch only checks " ", so the tab at index 1 throws. Use /\s/.test(char) to skip every kind of whitespace.

Variations and follow-ups

Twists interviewers add

Tracking lines and columns

For good error messages in text with many lines, keep line and column next to i: add one to line and reset column at each new line. Store the position in each token, so later errors can point at it too.

A tokenizer as a generator

Instead of building the whole list, write function* tokenize(source) and yield each token. The parser pulls tokens one at a time, which saves memory on large inputs and lets it stop at the first error.

One sticky regular expression

A regular expression with one alternative per kind, like /\s+|\d+(\.\d+)?|[A-Za-z_]\w*|[-+*\/()]/y, can match at lastIndex again and again. The y flag makes each match start exactly where the last one ended. It's shorter, but harder to give good error messages.

Template and markup tokenizers

Template engines and markdown parsers start the same way: walk the text, notice where a special marker like {{ begins, and switch to another kind of token until its closing marker.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "evaluate this expression", "basic calculator", "parse this string", or "decode this format". Almost every such task starts by splitting the text into tokens with one forward index.
  • Explain the structure before coding: "look at the current character, pick its kind, consume while the kind continues, push a token". Write one branch fully, and the others follow the same shape.
  • Make sure every branch moves i. An endless loop from a branch that forgets i++ is the most common bug, so point at the move in each branch as you write it.
  • Test by hand: no spaces at all, extra spaces, a decimal number, and a character you don't support. The usual follow-up is turning the tokens into a value, with two stacks or a recursive descent parser.

Where frontend code uses it

The same idea in real UI code
  • Every JavaScript engine and bundler starts by tokenizing your code. Babel, TypeScript, and esbuild all have a lexer that turns source text into tokens before parsing.
  • Template engines tokenize text like Hello {{ name }} into text pieces and placeholders. Browsers also tokenize HTML and CSS before building the DOM and style rules.
  • URLSearchParams splits a query string like a=1&b=2 into pairs, and syntax highlighters in code editors tokenize each line to color it.

Related algorithms