Parsing Pipelines

Tokens in hand, the shell now finds the structure: which tokens form commands, and where | splits them. A pipeline is the shell's marquee feature — and structurally, it's the simplest grammar you'll ever parse: a list of commands separated by pipes. The subtleties are all at the edges.

The grammar

pipeline := command ( '|' command )*
command  := word+

In English: one or more commands, pipe tokens between them, each command being one or more words (the first word is the program, the rest are its arguments). Parsing it is a single pass:

current = []
for each token:
    if token is '|':
        finish current command; start a new one
    else:
        append token to current command
finish the last command

Applied to cat access.log | grep 404 | wc -l:

[[cat, access.log], [grep, 404], [wc, -l]]

That list-of-lists is your parse result — the exact shape the executor (chapter 2) will walk to spawn processes and wire pipes. Notice what the parser does not know: what cat is, whether files exist, what the pipe will carry. Structure now, meaning later — the same discipline as tokenizing.

The edge cases are the exercise

The happy path is ten lines; correctness lives at the boundaries, and each boundary is a real thing users type (usually by accident):

• Leading pipe — | grep x — a pipe with no command before it. Syntax error. Real bash: syntax error near unexpected token '|'.
• Trailing pipe — cat file | — no command after. Interactive bash prompts for continuation; a batch parser reports an error. Your spec picks one; implement exactly that.
• Double pipe with nothing between — a | | b — an empty command in the middle. Error. (Careful: a || b is a different token entirely — the logical-OR from a later lesson. This is why tokenizing || as one operator vs | | as two matters — stage boundaries again.)
• Empty input — zero commands. Not an error; just nothing to do.

The unifying rule: every position between pipes (and the ends) must contain at least one word. Check that invariant explicitly and all four cases fall out of one condition — much cleaner than four special cases.

Why this representation wins

It's tempting to parse a pipeline into something fancier — a tree, say. Resist. The flat list mirrors what execution actually does: N processes, N−1 pipes connecting adjacent pairs, all started together (a fact that surprises people: cat | grep | wc runs all three concurrently, the pipes doing the coordination — you'll build exactly that in Executing a Pipeline). Later grammar — &&, ;, redirects — attaches around pipelines, so the pipeline stays this simple list even in a full shell. Choosing representations that match execution is half of systems design; here's a small, perfect example.

Your exercise: Parse Pipelines

Token streams in, command-lists out, errors on malformed input. Build the happy path first (single command → two-stage → N-stage), then walk the four edges above in order. When the empty-command invariant is one clean check and all your error cases route through it, you've written the parser the way a shell author would — and the next two lessons just add more operators to the same skeleton.