Tokenizing Shell Input with a State Machine

Shell tokenization cannot split only on whitespace because quoting changes what whitespace means. A space ends an argument in normal input but becomes ordinary argument data inside single quotes.

echo hello world       -> ["echo", "hello", "world"]
echo 'hello world'     -> ["echo", "hello world"]

The current parser work introduces the essential state distinction:

data QuoteState
  = Normal
  | InSingleQuote

The unfinished parseCommand also establishes recursive character consumption:

parseCommand :: String -> [String]
parseCommand input = go input ""
  where
    go [] current = [current]
    go (c : rest) current = go rest (current ++ [c])

At this point every character is appended to one string, so it does not yet tokenize or use QuoteState. The next step is to make parser state explicit in the recursive function.

The minimum parser state

A tokenizer must remember three things:

mode       whether whitespace and quotes are structural
current    characters accumulated for the active token
tokens     completed tokens

The transition function consumes one input character at a time:

(mode, current, tokens, next character)
  -> (new mode, new current, new tokens)

No mutable cursor is required. The unconsumed suffix of the input list is the cursor, and recursive arguments carry the new state.

Character transitions

In normal mode:

• a single quote enters InSingleQuote and is not copied into the token;
• whitespace completes a non-empty current token;
• any other character is appended to the current token.

Inside single quotes:

• a single quote returns to Normal and is not copied;
• every other character, including whitespace, is appended literally.

The state table is small enough to enumerate:

Mode	Input	Next mode	Token action
Normal	'	InSingleQuote	keep current token
Normal	whitespace	Normal	finish non-empty token
Normal	other	Normal	append character
InSingleQuote	'	Normal	keep current token
InSingleQuote	other	InSingleQuote	append character

This table is the parser’s behaviour independent of Haskell syntax.

A complete single-quote tokenizer

The state table translates directly into guarded recursive equations:

import Data.Char (isSpace)

data QuoteState
  = Normal
  | InSingleQuote
  deriving (Eq, Show)

parseCommand :: String -> Either String [String]
parseCommand input = go Normal False input [] []
  where
    go :: QuoteState -> Bool -> String -> String -> [String]
       -> Either String [String]
    go Normal started [] current tokens =
      Right (reverse (finish started current tokens))

    go InSingleQuote _ [] _ _ =
      Left "unterminated single quote"

    go Normal _ ('\'' : rest) current tokens =
      go InSingleQuote True rest current tokens

    go InSingleQuote started ('\'' : rest) current tokens =
      go Normal started rest current tokens

    go Normal started (c : rest) current tokens
      | isSpace c =
          go Normal False rest [] (finish started current tokens)
      | otherwise =
          go Normal True rest (c : current) tokens

    go InSingleQuote started (c : rest) current tokens =
      go InSingleQuote started rest (c : current) tokens

    finish :: Bool -> String -> [String] -> [String]
    finish False _ tokens = tokens
    finish True current tokens = reverse current : tokens

Characters are prepended with (c : current) instead of appended with current ++ [c]. Prepending to a linked list is constant time; appending must traverse the entire current string each time. The token is reversed once when it is complete.

Completed tokens are also prepended, so reverse restores command order once at end-of-input. The accumulator invariants are explicit: current holds the active token backwards, and tokens holds completed tokens backwards.

Empty quoted arguments require a separate fact

An empty buffer alone cannot distinguish a blank gap from an empty quoted argument:

echo '' x

The correct tokens include an empty string:

["echo", "", "x"]

The started Boolean in go preserves that distinction. Entering a quote sets it to True even when no character is appended. Whitespace finishes a token based on started, not on whether current contains characters.

As the parser grows, the arguments can be named in a record:

data TokenState = TokenState
  { quoteState :: QuoteState
  , tokenStarted :: Bool
  , currentReversed :: String
  , tokensReversed :: [String]
  }

This is a general parser constraint: two histories that require different future behaviour must not collapse into the same state representation.

Parse errors belong in the type

An unmatched quote is not an I/O failure. It is a deterministic result of the input string, so the parser can remain pure and return:

Either String [String]

Right tokens represents success and Left message represents a parse error. Unlike Maybe, Either preserves information about why parsing failed. The REPL decides how to display that error; the tokenizer only detects it.

The state machine grows by adding modes

Double quotes and backslash escapes require different transition rules, not a completely different architecture:

data QuoteState
  = Normal
  | InSingleQuote
  | InDoubleQuote
  | Escaped QuoteState

Single quotes treat almost everything literally. Double quotes permit selected expansions and escapes. Normal mode gives whitespace and shell operators structural meaning. Each new feature should be added as explicit state and transitions, with focused examples for boundaries, rather than as another global string split.

The tokenizer remains a pure function from text to tokens or an error. Filesystem lookup and process execution occur only after that function succeeds, preserving the same pure-core/effectful-edge boundary established by the initial REPL.