# Process 7 Activity

## Command line representation

The shell grammar defines the underlying hierarchical structure of command lines. The overall structure of a line, as described by the grammar, is:

• A list is composed of conditionals joined by ; or & (and the last command in the list might or might not end with &).
• A conditional is composed of pipelines joined by && or ||.
• A pipeline is composed of commands joined by |.
• A command is composed of words and redirections.

So lists are comprised of conditionals, which are comprised of pipelines, which are comprised of commands. But must this structure be reflected in your implementation?

There are two common ways to represent our parsed command line in a data structure appropriate for our shell, a tree representation and a list representation. Students often are biased toward the tree representation, which precisely represents the structure of the grammar, but the list representation can be easier to handle! The tradeoff is simplicity vs. execution time: the list representation requires more work to answer some questions about commands, but command lines are small enough in practice that the extra work doesn’t matter.

### Tree representation

The following tree-formatted data structure precisely represents this grammar structure.

• A command contains its executable, arguments, and any redirections.
• A pipeline is a linked list of commands, all of which are joined by |.
• A conditional is a linked list of pipelines. But since adjacent conditionals can be connected by either && or ||, we need to store whether the link is && or ||.
• A list is a linked list of conditionals, each flagged as foreground (i.e., joined by ;) or background (i.e., joined by &). Note that while the conditional link type doesn’t matter for the last pipeline in a conditional, the background flag does matter for the last conditional in a list, since the last conditional in a list might be run in the foreground or background.

For instance, consider this tree structure for a command line (the words and redirections that are there, but not being shown for the sake of simplifying the image somewhat):

Exercise: Assuming that a, b, c, d, e, and f are distinct commands, what could be a command line that would produce this tree structure?

Exercise: Sketch a set of C++ structures corresponding to this design.

Exercise: Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

Exercise: Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

Exercise: Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

Exercise: How should we destroy a conditional, in other words, free all its memory and the memory of related structures? How should the conditional::~conditional() destructor function be implemented?

### Linked list representation

Alternatively, we can create a single linked list of all of the commands. In this case, we also store the connecting operator (one of & ; | && or ||). For our example command line above, the flat linked list structure might look something like:

Again, this is the structure we recommend (we don’t require it). Traversing this structure is slightly more time-consuming than in the tree representation, but the structure is much easier to build, and the additional CPU time spent traversing it is in the noise given how short command lines typically are.

Exercise: Write a set of C++ structures corresponding to this design.

Exercise: Given a C++ structure corresponding to a conditional chain, explain how to tell whether that chain should be executed in the foreground or the background.

Exercise: Given a C++ structure corresponding to a command, how can one determine whether the command is on the left-hand side of a pipe?

Exercise: Given a C++ structure corresponding to a command, how can one determine whether the command is on the right-hand side of a pipe?

Exercise: Sketch out code for parsing a command line into these C++ structures.