Skip to content
Tutorials Center
My learning

Topics

Lesson 57 of 61 ยท Projects

Project: A Mini Linux Shell

Build a small Linux-style shell in Python: tokenize quotes and operators, parse pipelines and lists, expand variables, and execute commands, pipes and redirections.

A shell is a compiler-shaped program in disguise. It reads a line of text, tokenizes it, parses it into a tree, and then executes the tree. The language is small, but it has the problems every language front end has: quoting rules that a plain regular expression cannot capture, operators with different strengths, and a semantics (pipes, exit codes, redirection) you have to get exactly right. That makes it a perfect last project for this track.

In this project you build a mini shell that understands quoting, variables, pipelines (|), redirections (>, >>, <), and the list operators ;, && and ||. Real shells ask the operating system to start programs. Our runtime cannot do that, so the shell runs a handful of built-in commands (echo, cat, grep, wc, sort, uniq, head, ls, rm) against an in-memory file system. The front end is the same you would use for a real one; only the last step differs, and the end of the lesson shows what that step looks like on Linux.

The plan

flowchart LR
    T["Text line"] --> L["Tokenizer<br/>words, quotes, operators"]
    L --> P["Parser<br/>list of pipelines of commands"]
    P --> E["Executor<br/>expand, redirect, run"]
    E --> O["Output and exit status"]

The same pipeline as a compiler's front end: text to tokens to tree, and then the tree is "run" instead of translated.

The grammar is small. Each rule is one level of the tree, and the operators bind from loosest to tightest:

TEXT
list      โ†’ pipeline ( (";" | "&&" | "||") pipeline )*
pipeline  โ†’ command ( "|" command )*
command   โ†’ ( WORD | redirect )+
redirect  โ†’ (">" | ">>" | "<") WORD

So a | b && c means (a | b) && c: the pipe binds tighter than &&. The rule above is also how you would write the parser with recursive descent: one function per rule.

Step 1: tokenizing is not just splitting on spaces

If a shell only split on spaces, echo "two words" would give three arguments. The tokenizer must follow quoting rules:

Quote Effect
'single' everything inside is literal, no variable expansion
"double" spaces are kept as part of one word, but $NAME is still expanded
none the word ends at white space or an operator

Quotes can also be glued to other text: pre"fix ed"post is one word. The tokenizer therefore represents a word as a list of parts, each remembering whether it may be expanded. That is the same trick you used for string literals in a lexer, but here a single token can mix several kinds of text. The parser then builds a tree of three node types: Command (words and redirections), Pipeline (commands joined by |) and a list of pipelines joined by connectors.

Python Tokenizer and parser

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the printed trees, each line starts with the connector that links a pipeline to the previous one, and | separates the commands inside it. A leading ' in the output marks text that came from single quotes and will never be expanded. Notice who finds which error: the first three syntax errors come from the parser, because every token was valid but the sequence was not, while the unclosed quote is caught earlier by the tokenizer. This is the same split between lexical and syntax errors you know from the parsing chapter.

Step 2: executing the tree

Execution has four jobs for every command:

  1. Expand each word: replace $NAME, ${NAME} and $? (the exit status of the last pipeline) with their values, except inside single quotes.
  2. Set up the redirections: < file replaces the command's standard input, > file and >> file send its standard output to a file instead of the next command.
  3. Run the command with its arguments and input text and collect its output text, error text and exit status (0 means success).
  4. Combine the results: a pipeline passes each command's output to the next as input and takes the status of the last command. A list uses the statuses: ; always continues, && continues only after status 0, and || only after a non-zero status.

A real shell runs the commands of a pipeline at the same time, connected by operating system pipes. The mini shell runs them one after another and passes the text along, which gives the same answer for these simple, finite commands. Unknown commands print command not found and give status 127, like a real shell.

Python The complete mini shell

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the transcript from the top. The three echo lines build fruits.txt with > (truncate and write) and >> (append). sort | uniq -c counts duplicates, and shows why uniq needs sorted input: the two banana lines become neighbors only after the sort. The two grep -c lines show && and || working together: the first search succeeds (status 0), so found is printed and the || branch is skipped; the second finds nothing (status 1), so && skips and || runs. The line with NAME=world shows quoting rules at work, since $NAME expands in double quotes and stays literal in single quotes. cat nothing.txt; echo "status was $?" shows that $? holds the status of the previous pipeline, and that ; runs the next command no matter what.

What a real shell does differently

Our shell stops at "run a built-in". A Linux shell would replace that single step with process creation: for each command in a pipeline it creates a pipe, forks a child, rewires the child's standard input and output to the pipe ends with dup2, and calls exec to replace the child with the program. The front end (tokenizer, parser, expansion) is the same. The snippet below, which needs Linux or macOS and so is read-only here, shows the shape of that step for a list of argument lists:

Python
import os

def run_pipeline(commands):                   # commands: [["ls", "-l"], ["wc", "-l"]]
    pids, previous_read = [], None
    for i, argv in enumerate(commands):
        last = i == len(commands) - 1
        read_end, write_end = (None, None) if last else os.pipe()
        pid = os.fork()
        if pid == 0:                          # child process
            if previous_read is not None:
                os.dup2(previous_read, 0)     # stdin  <- previous command
            if write_end is not None:
                os.dup2(write_end, 1)         # stdout -> next command
            for fd in (previous_read, read_end, write_end):
                if fd is not None:
                    os.close(fd)
            os.execvp(argv[0], argv)          # become the program
        if previous_read is not None:
            os.close(previous_read)           # parent closes what it no longer needs
        if write_end is not None:
            os.close(write_end)
        previous_read = read_end
        pids.append(pid)
    status = 0
    for pid in pids:
        _, raw = os.waitpid(pid, 0)
        status = os.waitstatus_to_exitcode(raw)   # a pipeline's status is its last command's
    return status

Two more differences are worth knowing. A real shell expands in a fixed order: braces, then variables, then word splitting on spaces, then file name patterns (globs such as *.txt). The mini shell only does variables and never splits an expanded value into several words, which is why echo $x with spaces in x behaves more safely here than in a real shell. And real shells have jobs (&, Ctrl+Z), subshells ( ... ), here-documents and functions. All of those are more grammar rules and more executor cases, not new ideas.

Exercises

  1. Add a tr built-in that maps characters (tr a-z A-Z). Handle ranges with a helper.
  2. Support 2> so error text can be redirected into a file. You will need a separate redirect target for standard error.
  3. Add $(command) substitution: run the inner command and put its output (without the trailing newline) into the word. Where in the tokenizer does a nested expression make a new problem?
  4. Add if ...; then ...; fi. Which new tokens and which grammar rules do you need, and what makes fi different from an ordinary word?
  5. Add * globbing against the in-memory file names using Python's fnmatch module.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why can a shell not tokenize a line by simply splitting on spaces?

    In echo "two words" the quoted spaces belong to one argument, and a|b contains an operator with no spaces at all. A real tokenizer must follow the quoting and operator rules.
  2. 2. In 'grep x file && echo yes || echo no', when is 'echo no' executed?

    || runs its right side only after a failure. If grep fails, && skips echo yes (the status is still non-zero), so echo no runs.
  3. 3. What is the exit status of a pipeline such as 'a | b | c' in this project (and in a typical shell)?

    The pipeline's status is taken from its last command, which is what && and || then examine.
  4. 4. What does the tokenizer do with the text $NAME inside single quotes?

    Each word part records whether it may be expanded. Single-quoted text is stored with expandable set to False.
  5. 5. Which system call pair does a real shell use to connect two commands in a pipeline?

    The shell creates a pipe, forks, and uses dup2 in each child to wire the pipe ends to descriptors 0 and 1 before calling exec.

Summary

  • A shell has the same shape as a compiler front end: a tokenizer that understands quoting and operators, a small recursive grammar (list, pipeline, command), and an executor that interprets the tree.
  • Words are lists of parts, because quoting decides per piece whether $NAME may be expanded.
  • | binds tighter than &&, || and ;. A pipeline's status is its last command's, and the connectors decide by that status whether the next pipeline runs.
  • Redirections change where a command's input comes from and where its output goes; $? exposes the previous status.
  • A real shell differs mostly in the last step: it creates processes with fork, pipe, dup2 and exec instead of calling built-in functions.

Next: Compiler Practice Exercises