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:

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.

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):

Tree structure example

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:

Flat linked list structure example

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.