State machines for parsers

Overview

A finite state machine (FSM) is a way of organising code that has to remember "where am I right now?" as it walks through a sequence of inputs. Instead of scattering that memory across a pile of boolean flags and deeply nested conditionals, you keep it in one variable — the state — and you describe, for each input, how the state changes.

Think of reading a sentence out loud. Your brain is in one of a few modes: between words (waiting for the next word to start) or inside a word (reading letters until a space). Every character you see either keeps you in the same mode or flips you into another. That is exactly an FSM: a handful of modes, plus rules for moving between them.

This lesson builds directly on two things you already know. From if / else you know how to make a decision based on the current character. From for / while / do-while you know how to walk through every character of a string. An FSM simply organises those decisions: the loop feeds you one byte at a time, and a switch on the current state decides what that byte means and what to do next. The plain-language idea is "one mode variable that changes as I read"; the formal name for that idea is a finite state machine, and the moves between modes are transitions.

Why it matters

Most real C parsers are finite state machines under the hood — HTTP request parsers, JSON and XML readers, CSV splitters, regular-expression engines, and the tokenizer in every shell and compiler. When you can see the FSM pattern, three things get dramatically easier.

First, correctness: with the whole design expressed as a small table of states and transitions, you can walk every case and convince yourself nothing is missing. Second, readability: a colleague can read the states like a story instead of untangling nested flags. Third, security: text parsers are a favourite target for attackers, and an explicit state variable is far easier to audit, log, and test against hostile input than a maze of conditionals. Sloppy parsers are where bugs and vulnerabilities hide; explicit FSMs are how professionals keep them out.

Core concepts

1. State

Definition: the state is a single value — usually a small integer or an enum — that records what the parser is currently looking for. It is the parser's "mode."

Plain-language explanation: at any moment while scanning text, there are only a few meaningfully different situations you can be in. A word counter is either between words or inside a word — that's it. A shell tokenizer might be outside a token, inside a bare token, or inside a quoted string. Each of those situations is one state.

How it works internally: the state lives in one variable that survives from one loop iteration to the next. On each byte, you read the state, decide what to do, and possibly write a new state back. Nothing else needs to "remember" anything.

When to use it / when not to: use an explicit state when behaviour depends on what came before, not just the current byte. If every character can be handled on its own with no memory (for example, uppercasing a string), you do not need an FSM — a plain loop is simpler.

Common pitfall: spreading the state across several booleans (in_word, in_quote, seen_dot) so that the real state is some combination of them. That quickly becomes impossible to reason about. Prefer one named state variable.

  ONE state variable, walking a string byte by byte:

     input:   H   e   l   l   o   ' '   W   o   r   l   d
              |   |   |   |   |    |    |   |   |   |   |
     state: OUT  IN  IN  IN  IN  OUT  IN  IN  IN  IN  IN
              ^
              start-of-word transitions happen here and at 'W'

Knowledge check: In a word counter with states OUT and IN_WORD, which single event should increase the word count — entering IN_WORD, or leaving it? (Either works if done consistently, but pick one and say why.)

2. Transition

Definition: a transition is the rule that maps (current state, current input byte) -> next state.

Plain-language explanation: for each byte you ask, "given where I am, and given this character, where should I go next?" Often the answer is simply stay put or move to the next state.

How it works internally: you implement transitions with a switch (state) whose cases inspect the byte and assign a new value to the state variable. Because the loop repeats, those assignments carry forward automatically.

When to use it / when not to: every FSM needs transitions; the design work is deciding them. Keep them total — every (state, byte) pair should have a defined result, even if that result is "reject."

Common pitfall: forgetting a transition for some input, so the parser "falls through" and behaves undefinedly on an edge case (an empty string, a trailing space, a stray quote).

Knowledge check (predict the output): Using the table above, how many words does the FSM count in the string " a bb " (two leading spaces, two middle spaces, one trailing space)?

3. Action on transition

Definition: an action is the useful work you do at the moment a transition fires — the side effect, separate from changing state.

Plain-language explanation: moving between modes is often the exact moment something meaningful happens. When you cross from OUT into IN_WORD, a new word has just begun — that is when you increment the counter or record where the word starts.

How it works internally: the action is a statement placed in the same case branch as the state change, for example { words++; state = IN_WORD; }.

When to use it / when not to: attach actions to the edge (the transition) when the event is "something just started/ended," and to the state (every byte while in a state) when you need to accumulate, such as copying characters into a token buffer.

Common pitfall: doing the action on the wrong event, so you count a word once per character instead of once per word, or emit an empty token for a run of spaces.

Knowledge check (explain in your own words): Why does incrementing the counter only on the OUT -> IN_WORD edge avoid over-counting when several spaces separate two words?

4. The default-reject branch (a defensive habit)

Definition: a catch-all branch that treats any input not explicitly allowed as an error and refuses it.

Plain-language explanation: a robust parser knows exactly which inputs are legal. Anything else should stop the machine, not be quietly tolerated. The old slogan "be liberal in what you accept" turns out to be a security anti-pattern: loose parsing is where malformed and malicious input slips through.

How it works internally: in a validator you add an else/default that sets a failure flag or moves to a dedicated REJECT state that ignores the rest of the input and returns "invalid."

When to use it / when not to: essential for validators and for parsing untrusted input (network data, user files). For a purely internal, trusted transformation you may relax it — but defaulting to reject is the safer habit.

Common pitfall: writing an FSM that only lists the "happy path" and lets everything else fall into the last case, so garbage is accepted as if it were valid.

  Validator with an absorbing REJECT state:

     START ──digit──► INT ──digit──► INT ──end──► ACCEPT
       │               │
       └──other──►  REJECT ◄──other──┘
                     (stays REJECT forever)

Knowledge check (find the design flaw): A number validator has states START and INT but no REJECT, and its default case just leaves the state unchanged. What kinds of malformed strings would it wrongly accept?

Syntax notes

The idiomatic C shape is an enum for the states and a switch inside a byte-at-a-time loop:

enum state { OUT, IN_WORD, IN_QUOTE }; /* named states, not magic numbers */
enum state st = OUT;                   /* the single state variable       */

for (const char *p = line; *p; p++) {  /* walk one byte at a time          */
    unsigned char c = (unsigned char)*p; /* cast before <ctype.h> functions */
    switch (st) {
    case OUT:                          /* one case per state               */
        if (!isspace(c)) st = IN_WORD; /* transition + optional action     */
        break;
    case IN_WORD:
        if (isspace(c)) st = OUT;
        break;
    case IN_QUOTE:
        if (c == '"') st = OUT;
        break;
    }
}

Key points: name states with an enum (never bare 0/1/2); keep one state variable; always cast the char to unsigned char before passing it to <ctype.h> functions like isspace, because passing a negative char is undefined behaviour.

Lesson

A finite state machine (FSM) tracks the question "what mode am I in?" as you walk through the input one byte at a time.

A few common examples:

• Word counting — two states: in a word, or not in a word.
• Command-line parser — out of a token, in a token, or inside a quote.
• URL parser — moving through scheme, then authority, then path, then query.

Code examples

#include <stdio.h>
#include <ctype.h>

/* Count whitespace-separated words in `s` using a two-state FSM.
   A word is a maximal run of non-whitespace characters. */
int count_words(const char *s)
{
    enum { OUT, IN_WORD } state = OUT; /* current mode */
    int words = 0;

    for (const char *p = s; *p != '\0'; p++) {
        unsigned char c = (unsigned char)*p; /* safe for isspace */
        switch (state) {
        case OUT:
            if (!isspace(c)) {   /* OUT -> IN_WORD: a new word begins */
                words++;         /* action fires exactly once per word */
                state = IN_WORD;
            }
            break;               /* whitespace while OUT: stay OUT */
        case IN_WORD:
            if (isspace(c)) {    /* IN_WORD -> OUT: the word ended */
                state = OUT;
            }
            break;               /* non-space while IN_WORD: stay IN_WORD */
        }
    }
    return words;
}

int main(void)
{
    const char *tests[] = {
        "hello world",
        "  lots   of   spaces  ",
        "",
        "single",
        "\ttabs\nand newlines\n"
    };
    size_t n = sizeof tests / sizeof tests[0];

    for (size_t i = 0; i < n; i++) {
        printf("%2d  <%s>\n", count_words(tests[i]), tests[i]);
    }
    return 0;
}

What it does: count_words scans a string one byte at a time. It starts in OUT. The first non-whitespace byte after any gap moves it to IN_WORD and counts one word; whitespace moves it back to OUT. Because the counting action fires only on the OUT -> IN_WORD edge, runs of spaces never inflate the count.

Expected output:

 2  <hello world>
 3  <  lots   of   spaces  >
 0  <>
 1  <single>
 3  <	tabs
and newlines
>

(The last line's tab and newlines render as whitespace; the three words are tabs, and, newlines.)

Edge cases handled: the empty string returns 0 (the loop never runs); leading, trailing, and repeated whitespace do not create phantom words; tabs and newlines count as separators because isspace treats them as whitespace.

Line by line

Let us trace count_words(" ab ") — two spaces, a, b, one trailing space.

• enum { OUT, IN_WORD } state = OUT; — the machine begins between words. words = 0.
• The loop reads each character and switch (state) picks the branch for the current mode.

• After step 5 the string's '\0' ends the loop. The function returns words = 1, which is correct: "ab" is one word.

The important insight is that words++ lives on a single edge (OUT -> IN_WORD). The two leading spaces keep the machine in OUT without counting; the letters a and b sit inside IN_WORD without re-counting; only the transition into the word counts. This is why the FSM handles arbitrary runs of whitespace with no special cases.

Common mistakes

Mistake 1 — counting on every non-space byte instead of on the transition.

/* WRONG: counts letters, not words */
for (const char *p = s; *p; p++)
    if (!isspace((unsigned char)*p)) words++;

Why it is wrong: this increments once per non-space character, so "ab" reports 2. The count belongs on the edge into a word, not on every byte. Fix: track state and count only on OUT -> IN_WORD, as in the lesson code. Recognise it when your counts look roughly like the character count rather than the word count.

Mistake 2 — hiding the state in nested ifs and flags.

/* WRONG: the real state is smeared across booleans */
if (in_quote) { if (c == '"') in_quote = 0; }
else if (in_word) { if (isspace(c)) { in_word = 0; emit(); } }
else if (!isspace(c)) { if (c == '"') in_quote = 1; else in_word = 1; }

Why it is wrong: the actual mode is a combination of in_quote and in_word, and impossible combinations (in_quote && in_word) are not prevented. Fix: one enum state variable and a switch. Recognise it when you find yourself adding "just one more flag" to a parser.

Mistake 3 — passing a raw char to isspace.

if (isspace(*p)) ...   /* WRONG on bytes >= 128 with signed char */

Why it is wrong: on platforms where char is signed, a byte like 0xE9 becomes a negative int, which is undefined behaviour for <ctype.h> functions. Fix: isspace((unsigned char)*p). Recognise it via crashes or wrong results on non-ASCII input.

Mistake 4 — no reject path in a validator. Listing only valid transitions and letting everything else fall through means malformed input is silently accepted. Fix: add an explicit default/REJECT that fails the parse (covered in the validator exercise).

Debugging tips

Compiler errors

• "enumeration value not handled in switch" (with -Wall): you added a state to the enum but forgot a case. Add the missing branch — this warning is a gift.
• Implicit declaration of isspace: you forgot #include <ctype.h>.
• Unused variable state: you declared a state but never read it, usually a sign the logic collapsed back into flat ifs.

Runtime / logic errors

• Off-by-one word counts almost always mean the action is on the wrong event (per byte vs per transition) or the loop mishandles the final byte.
• Wrong results only on non-ASCII bytes point straight at a missing (unsigned char) cast.
• An FSM that "never finishes" a token often forgot to handle end-of-input: after the loop, if you are still IN_WORD, you may need to emit or finalise the last token.

Concrete debugging step — log every transition. Temporarily print each move:

printf("state %d -> %d on '%c' (0x%02x)\n", old, state, isprint(c)?c:'?', c);

The resulting trace reads like a story and usually shows exactly where the machine took a wrong turn.

Questions to ask when it misbehaves: Which state am I in for each byte? Is every (state, byte) pair handled? Does an action fire on an edge that repeats? What happens on the empty string, on all-whitespace input, and at end-of-input?

Memory safety

The state logic of an FSM is pure computation — a single int or enum — so the machine itself has no bounds or lifetime hazards. The risks appear at the edges, where the FSM touches memory:

• Output buffers. If transitions emit tokens into an array (char *argv[], or a fixed char buf[N]), you must bound both the number of tokens and the length of each token. Writing the k-th token without checking k < max is a classic buffer overflow. Always compare against capacity before storing.
• <ctype.h> and negative chars. As noted, cast char to unsigned char before isspace/isdigit/etc.; a negative argument (other than EOF) is undefined behaviour.
• Reading past the end. Drive the loop off the NUL terminator (*p != '\0') or an explicit length. Do not assume a fixed size.
• Uninitialised state. Always initialise the state variable (= OUT). An uninitialised state reads garbage and the very first transition is unpredictable.

Security angle (even in this non-security lesson). Parsers sit on the boundary between your program and untrusted input, so they are prime attack surface. Two defensive habits matter most: (1) reject by default — an explicit REJECT state for anything not in the grammar, rather than "accept and hope"; and (2) agree on the grammar — when two parsers (say a proxy and a back-end) disagree about the same bytes, that gap is the root of request-smuggling style bugs. You do not need to exploit anything to benefit here: just test your FSM against pathological inputs (empty, all-separators, unterminated quotes, embedded NULs, over-long tokens) and make sure it fails safely rather than reading or writing out of bounds.

Real-world uses

Concrete uses. Finite state machines drive the request-line parser in web servers (nginx and Node's HTTP parser are explicit FSMs), the tokenizer in every shell (splitting a command line into argv, honouring quotes), JSON/XML/TOML readers, CSV field splitters, URL/URI parsers following RFC 3986, and the lexer stage of essentially every compiler and interpreter. Regular-expression engines compile a pattern into a state machine and run it the same way.

Professional best-practice habits

A beginner should aim for a readable enum + switch that passes obvious cases. An advanced engineer additionally treats the parser as a security boundary: total transition coverage, default-reject, precise error offsets, and fuzz testing against hostile input.

Practice tasks

Beginner 1 — Character-class counter. Objective: scan a string with a two-state FSM and count runs of digits (a maximal run of 0-9 counts as one). Requirements: use an enum { OUT, IN_NUM } and increment only on the entering edge. Example: "a12b345" -> 2. Constraints: single pass, no strtok. Hint: this is the word counter with isdigit instead of !isspace. Concepts: state, transition, action-on-edge.

Beginner 2 — Trim detector. Objective: report whether a string has leading whitespace, trailing whitespace, both, or neither, using states as you scan once. Requirements: do not modify the string; decide from the first and last non-space positions you observe. Example: " hi " -> "both". Hint: track whether you have entered a word yet, and remember the state at end-of-input. Concepts: state, end-of-input handling.

Intermediate 1 — Quote-aware tokenizer. Objective: split a line into tokens, treating a "..." region as a single token even if it contains spaces. Requirements: states OUT, IN_WORD, IN_QUOTE; store a pointer to each token's start; bound the token array. Example: hello "two words" x -> 3 tokens. Constraints: reject a line that ends while still IN_QUOTE. Hint: the closing quote transitions back to OUT and ends the token. Concepts: three-state FSM, actions on edges, buffer bounds.

Intermediate 2 — Signed-integer validator. Objective: return 1 if the whole string is a valid signed integer (optional leading +/-, then one or more digits, nothing else), else 0. Requirements: states START, SIGN, DIGITS, plus a default-reject; the string is valid only if it ends in DIGITS. Example: "-42" -> 1, "+" -> 0, "4 2" -> 0. Hint: the accepting state matters — ending in START or SIGN must fail. Concepts: default-reject, accepting states.

Challenge — Minimal number-literal lexer. Objective: validate a floating-point literal of the form [+/-]? digits ( '.' digits )? ( ('e'|'E') [+/-]? digits )? with a single FSM. Requirements: at least six states (e.g. START, SIGN, INT, DOT, FRAC, EXP, EXP_SIGN, EXP_DIGITS); an absorbing REJECT; accept only on states where a digit has been seen in the required place. Example: "-3.14e-2" valid; "3.", "1e", ".5" (your choice — document it) handled deliberately. Constraints: one pass, no strtod. Hint: draw the transition diagram before coding, and list the accepting states explicitly. Concepts: multi-state FSM, transition table thinking, default-reject, accepting states.

Summary

• A finite state machine organises stateful text processing as one state variable plus explicit transitions — far clearer and safer than nested flags.
• The idiomatic C shape is enum { ... } state; driving a switch inside a byte-at-a-time loop; name states with an enum and keep a single state variable.
• Attach actions to the right event: to the edge (transition) for "something started/ended" like counting a word, and to the state for accumulating like copying into a token buffer.
• Always cast char to unsigned char before <ctype.h> calls, initialise the state, and handle end-of-input (finalise the last token; check the accepting state).
• Add a default-reject branch for untrusted input, keep transition coverage total, and bound any output buffer — that is the recipe for a correct, secure parser.
• Remember: word counters, shell tokenizers, HTTP/JSON parsers, and regex engines are all this same pattern once you learn to see it.

Practice with these exercises

• Count words
• Validate a number string
• Count whitespace-separated words
• Final Project: mini-shell — argv tokenizer
• Caesar cipher (educational toy)
• Final Project: CSV row parser (no quoting)