Parsing Pipelines

After this lesson your shell takes the token stream from the tokenizer and finds its first piece of structure: which tokens belong to which command in a pipeline. It refuses a pipeline with a missing command, and it never mistakes a quoted | or the || operator for a pipe.

What a pipeline is

In ps aux | grep nginx | wc -l three programs run at the same time. The standard output of each is connected to the standard input of the next by a kernel pipe, a small in-memory buffer with a read end and a write end. The shell's job at parse time is only to recover the three commands; creating the pipes and forking comes in the execution lessons.

The grammar in POSIX (Shell Command Language, section 2.9.2) is short:

pipeline : command
         | pipeline '|' command

A pipeline is one command, or a pipeline followed by | and another command. Two things follow from that definition. First, | is an operator token, so it only counts when the tokenizer produced it. Second, there must be a command on both sides of every |; the grammar has no rule for an empty one.

From tokens to commands

Walk the token list once, start a new command at each pipe operator, and put every other token, including redirection operators and IO numbers, into the current command. A trace on sort < in.txt | uniq > out.txt:

The redirections stay attached to the command they were typed against. Pulling them out is the next lesson's work.

Why the tokenizer comes first

Compare three lines that all contain the character |:

echo "a|b" | wc -c      two commands; the first pipe is inside quotes
grep -E 'x|y' f | sort  two commands; the pattern keeps its bar
a || b                  one command list with the OR operator, no pipe at all

A parser that searches the raw text for the character gets all three wrong. Because the tokenizer already decided what is quoted and what is an operator, the parser only compares token kinds. This is the main reason the stages are separate.

Syntax errors

ls | and | sort and a | | b each have an empty command, so the pipeline is invalid and nothing may run. Real shells print a message and wait for the next line; yours prints one error line for that input and moves on.

Common mistakes

• Splitting the original line on the character |. It breaks quoted bars and cuts || in half.
• Accepting an empty command at either end. ls | is incomplete, not a one-command pipeline.
• Dropping tokens such as < or > while splitting, so later stages cannot see them.
• Counting a pipeline of one command as "not a pipeline" and printing nothing for it.

Your exercise

The starter already tokenizes each line and prints the result in the required format. You write the function that turns a token list into commands, or reports that one is empty. The most likely mistake is checking for emptiness only at the ends and missing a | | b.