Let’s Build a Linux Shell — Part III
This is part III of a tutorial on how to build a Linux shell. You can read the first two parts of this tutorial from these links: part I, part II.
NOTE: You can download the complete source code for Part II & III from this GitHub repository.
Parsing Simple Commands
In the previous part of this tutorial, we implemented our lexical scanner. Now let’s turn our eyes to the parser.
Just to recap, the parser is the part of our Command Line Interpreter that calls the lexical scanner to retrieve tokens, then constructs an Abstract Syntax Tree, or AST, out of these tokens. This AST is what we’ll pass to the executor to be, well, executed.
Our parser will contain only one function, parse_simple_command(). In the upcoming parts of this tutorial, we'll add more functions to enable our shell to parse loops and conditional expressions.
So let’s start coding our parser. You can begin by creating a file named parser.h in the source directory, to which you'll add the following code:
#ifndef PARSER_H
#define PARSER_H#include "scanner.h" /* struct token_s */
#include "source.h" /* struct source_s */struct node_s *parse_simple_command(struct token_s *tok);#endif
Nothing fancy, just declaring our sole parser function.
Next, create parser.c and add the following code to it:
#include <unistd.h>
#include "shell.h"
#include "parser.h"
#include "scanner.h"
#include "node.h"
#include "source.h"
struct node_s *parse_simple_command(struct token_s *tok)
{
if(!tok)
{
return NULL;
}
struct node_s *cmd = new_node(NODE_COMMAND);
if(!cmd)
{
free_token(tok);
return NULL;
}
struct source_s *src = tok->src;
do
{
if(tok->text[0] == '\n')
{
free_token(tok);
break;
} struct node_s *word = new_node(NODE_VAR);
if(!word)
{
free_node_tree(cmd);
free_token(tok);
return NULL;
}
set_node_val_str(word, tok->text);
add_child_node(cmd, word); free_token(tok); } while((tok = tokenize(src)) != &eof_token); return cmd;
}
Pretty simple, right? To parse a simple command, we only need to call tokenize() to retrieve input tokens, one by one, until we get a newline token (which we test for in the line that reads: if(tok->text[0] == '\n')), or we reach the end of our input (we know this happened when we get an eof_token token. See the loop conditional expression near the bottom of the previous listing). We use input tokens to create an AST, which is a tree-like structure that contains information about the components of a command. The details should be enough to enable the executor to properly execute the command. For example, the figure below shows how the AST of a simple command looks like.
Each node in the command’s AST must contain information about the input token it represents (such as the original token’s text). The node must also contain pointers to its child nodes (if the node is a root node), as well as its sibling nodes (if the node is a child node). Therefore, we’ll need to define yet another structure, struct node_s, which we'll use to represent nodes in our AST.
Go ahead and create a new file, node.h, and add the following code to it:
#ifndef NODE_H
#define NODE_Henum node_type_e
{
NODE_COMMAND, /* simple command */
NODE_VAR, /* variable name (or simply, a word) */
};enum val_type_e
{
VAL_SINT = 1, /* signed int */
VAL_UINT, /* unsigned int */
VAL_SLLONG, /* signed long long */
VAL_ULLONG, /* unsigned long long */
VAL_FLOAT, /* floating point */
VAL_LDOUBLE, /* long double */
VAL_CHR, /* char */
VAL_STR, /* str (char pointer) */
};union symval_u
{
long sint;
unsigned long uint;
long long sllong;
unsigned long long ullong;
double sfloat;
long double ldouble;
char chr;
char *str;
};struct node_s
{
enum node_type_e type; /* type of this node */
enum val_type_e val_type; /* type of this node's val field */
union symval_u val; /* value of this node */
int children; /* number of child nodes */
struct node_s *first_child; /* first child node */
struct node_s *next_sibling, *prev_sibling;
/*
* if this is a child node, keep
* pointers to prev/next siblings
*/
};struct node_s *new_node(enum node_type_e type);
void add_child_node(struct node_s *parent, struct node_s *child);
void free_node_tree(struct node_s *node);
void set_node_val_str(struct node_s *node, char *val);#endif
The node_type_e enumeration defines the types of our AST nodes. For now, we only need two types. The first type represents the root node of a simple command's AST, while the second type represents the simple command's child nodes (which contain the command name and arguments). In the next parts of this tutorial, we'll add more node types to this enumeration.
The val_type_e enumeration represents the types of values we can store in a given node structure. For simple commands, we'll only use strings (VAL_STR enumeration type). Later on in this series, we'll use the other types when we handle other types of complex commands.
The symval_u union represents the value we can store in a given node structure. Each node can have only one type of value, such as a character string or a numeric value. We access the node's value by referencing the appropriate union member (sint for signed long integers, str for strings, etc).
The struct node_s structure represents an AST node. It contains fields that tell us about the node's type, the type of the node's value, as well as the value itself. If this is a root node, the children field contains the number of child nodes, and first_child points to the first child node (otherwise it will be NULL). If this is a child node, we can traverse the AST nodes by following the next_sibling and prev_sibling pointers.
If we want to retrieve a node’s value, we need to check the val_type field and, according to what we find there, access the appropriate member of the val field. For simple commands, all nodes will have the following attributes:
type=>NODE_COMMAND(root node) orNODE_VAR(command name and arguments list)val_type=>VAL_STRval.str=> pointer to the string value
Now let’s write some functions to help us work with node structures.
Create a file named node.c and add the following code:
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <errno.h>
#include "shell.h"
#include "node.h"
#include "parser.h"
struct node_s *new_node(enum node_type_e type)
{
struct node_s *node = malloc(sizeof(struct node_s)); if(!node)
{
return NULL;
}
memset(node, 0, sizeof(struct node_s));
node->type = type;
return node;
}
void add_child_node(struct node_s *parent, struct node_s *child)
{
if(!parent || !child)
{
return;
} if(!parent->first_child)
{
parent->first_child = child;
}
else
{
struct node_s *sibling = parent->first_child;
while(sibling->next_sibling)
{
sibling = sibling->next_sibling;
}
sibling->next_sibling = child;
child->prev_sibling = sibling;
}
parent->children++;
}
void set_node_val_str(struct node_s *node, char *val)
{
node->val_type = VAL_STR; if(!val)
{
node->val.str = NULL;
}
else
{
char *val2 = malloc(strlen(val)+1);
if(!val2)
{
node->val.str = NULL;
}
else
{
strcpy(val2, val);
node->val.str = val2;
}
}
}
void free_node_tree(struct node_s *node)
{
if(!node)
{
return;
} struct node_s *child = node->first_child;
while(child)
{
struct node_s *next = child->next_sibling;
free_node_tree(child);
child = next;
}
if(node->val_type == VAL_STR)
{
if(node->val.str)
{
free(node->val.str);
}
}
free(node);
}
The new_node() function creates a new node and sets it's type field.
The add_child_node() function expands the AST of a simple command by adding a new child node and incrementing the root node's children field. If the root node has no children, the new child is assigned to the first_child field of the root node. Otherwise, the child is appended to the end of the children's list.
The set_node_val_str() function sets a node's value to the given string. It copies the string to a newly allocated memory space, then sets the val_type and val.str fields accordingly. In the future, we'll define similar functions to let us set node values to different data types, such as integers and floating points.
The free_node_tree() function frees the memory used by a node structure. If the node has children, the function is called recursively to free each of them.
That’s all for the parser. Now let’s write our command executor.
Executing Simple Commands
Similar to our parser, the executor will contain only one function, do_simple_command(). In the upcoming parts of this tutorial, we'll add more functions to enable us to execute all sorts of commands, such as loops and conditional expressions.
Create a file named executor.h, and add the following code:
#ifndef BACKEND_H
#define BACKEND_H#include "node.h"char *search_path(char *file);
int do_exec_cmd(int argc, char **argv);
int do_simple_command(struct node_s *node);#endif
Just some function prototypes. Now create executor.c and define the following functions:
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <errno.h>
#include <sys/stat.h>
#include <sys/wait.h>
#include "shell.h"
#include "node.h"
#include "executor.h"
char *search_path(char *file)
{
char *PATH = getenv("PATH");
char *p = PATH;
char *p2;
while(p && *p)
{
p2 = p; while(*p2 && *p2 != ':')
{
p2++;
}
int plen = p2-p;
if(!plen)
{
plen = 1;
}
int alen = strlen(file);
char path[plen+1+alen+1];
strncpy(path, p, p2-p);
path[p2-p] = '\0';
if(p2[-1] != '/')
{
strcat(path, "/");
} strcat(path, file);
struct stat st;
if(stat(path, &st) == 0)
{
if(!S_ISREG(st.st_mode))
{
errno = ENOENT;
p = p2;
if(*p2 == ':')
{
p++;
}
continue;
} p = malloc(strlen(path)+1);
if(!p)
{
return NULL;
}
strcpy(p, path);
return p;
}
else /* file not found */
{
p = p2;
if(*p2 == ':')
{
p++;
}
}
} errno = ENOENT;
return NULL;
}
int do_exec_cmd(int argc, char **argv)
{
if(strchr(argv[0], '/'))
{
execv(argv[0], argv);
}
else
{
char *path = search_path(argv[0]);
if(!path)
{
return 0;
}
execv(path, argv);
free(path);
}
return 0;
}
static inline void free_argv(int argc, char **argv)
{
if(!argc)
{
return;
} while(argc--)
{
free(argv[argc]);
}
}
int do_simple_command(struct node_s *node)
{
if(!node)
{
return 0;
} struct node_s *child = node->first_child;
if(!child)
{
return 0;
}
int argc = 0;
long max_args = 255;
char *argv[max_args+1];/* keep 1 for the terminating NULL arg */
char *str;
while(child)
{
str = child->val.str;
argv[argc] = malloc(strlen(str)+1);
if(!argv[argc])
{
free_argv(argc, argv);
return 0;
}
strcpy(argv[argc], str);
if(++argc >= max_args)
{
break;
}
child = child->next_sibling;
}
argv[argc] = NULL; pid_t child_pid = 0;
if((child_pid = fork()) == 0)
{
do_exec_cmd(argc, argv);
fprintf(stderr, "error: failed to execute command: %s\n",
strerror(errno));
if(errno == ENOEXEC)
{
exit(126);
}
else if(errno == ENOENT)
{
exit(127);
}
else
{
exit(EXIT_FAILURE);
}
}
else if(child_pid < 0)
{
fprintf(stderr, "error: failed to fork command: %s\n",
strerror(errno));
return 0;
} int status = 0;
waitpid(child_pid, &status, 0);
free_argv(argc, argv);
return 1;
}
The search_path() function takes the name of a command, then searches the directories listed in the $PATH variable to try and find the command's executable file. The $PATH variable contains a comma-separated list of directories, such as /bin:/usr/bin. For each directory, we create a pathname by appending the command name to the directory name, then we call stat() to see if a file that exists with the given pathname (for simplicity, we don't check whether the file is actually executable, or whether we have enough permissions to execute it). If the file exists, we assume it contains the command we want to execute, and we return the full pathname of that command. If we don't find the file in the first $PATH directory, we search the second, third, and the rest of the $PATH directories, until we find our executable file. If we fail in finding the command by searching all the directories in the $PATH, we return NULL (this usually means the user typed an invalid command name).
The do_exec_cmd() function executes a command by calling execv() to replace the current process image with the new command executable. If the command name contains any slash characters, we treat it as a pathname and we directly call execv(). Otherwise, we try to locate the command by calling search_path(), which should return the full pathname that we will pass on to execv().
The free_argv() function frees the memory we used to store the arguments list of the last command executed.
The do_simple_command() function is the main function in our executor. It takes the command's AST and converts it to an arguments list (Remember that the zeroth argument, or argv[0], contains the name of the command we want to execute).
The function then forks a new child process. In the child process, we execute the command by calling do_exec_cmd(). If the command is executed successfully, this call shouldn't return. If it does return, it means an error happened (e.g., the command wasn't found, the file wasn't executable, insufficient memory, ...). In this case, we print a suitable error message and exit with a non-zero exit status.
In the parent process, we call waitpid() to wait for our child process to finish execution. We then free the memory we used to store the arguments list and return.
Now in order to incorporate the new code into our existing shell, you need to first update the main() function by removing the line that reads printf("%s\n", cmd); and replace it with the following lines:
struct source_s src;
src.buffer = cmd;
src.bufsize = strlen(cmd);
src.curpos = INIT_SRC_POS;
parse_and_execute(&src);Now before you close the main.c file, go to the beginning of the file and add the following lines after the last #include directive:
#include "source.h"
#include "parser.h"
#include "backend.h"Then go to the end of the file (after the read_cmd()'s function definition), and add the following function:
int parse_and_execute(struct source_s *src)
{
skip_white_spaces(src); struct token_s *tok = tokenize(src); if(tok == &eof_token)
{
return 0;
} while(tok && tok != &eof_token)
{
struct node_s *cmd = parse_simple_command(tok); if(!cmd)
{
break;
} do_simple_command(cmd);
free_node_tree(cmd);
tok = tokenize(src);
} return 1;
}
This function takes the Eval-Print part of our Read-Eval-Print-Loop (REPL) away from the main() function. It starts by skipping any leading whitespace characters, then it parses and executes simple commands, one command at a time, until the input is consumed, before it returns control to the REPL loop in the main() function.
Finally, don’t forget to add the following include and function prototype to your shell.h file, right before the closing #endif directive:
#include "source.h"
int parse_and_execute(struct source_s *src);And that should be it! Now let’s compile our shell.
Compiling the Shell
Let’s compile our shell. Open your favorite terminal emulator, navigate to your source directory and make sure you have 13 files in there:
Now compile the shell using the following command:
gcc -o shell main.c source.c scanner.c parser.c node.c executor.c prompt.cIf everything goes well, gcc should not output anything, and there should be an executable file named shell in the current directory:
Now invoke the shell by running ./shell, and try entering a few commands, such as ls, ls -l, and echo Hello World!:
As you can see, our shell can now parse and execute simple commands, regardless of the number of arguments we pass in the command line. Yay!
However, if you try to execute a command such as echo $PATH, you will find that the result is not what you expected! This is because our shell doesn't know how to access its environment, how to store shell variables, and how to perform word expansion. This is what we'll fix in the next part of this tutorial.
What’s Next
In order to be able to perform word expansion, we’ll first need to access the shell’s environment and to find a dynamic way to store shell variables. We’ll do this in the next part.
You can read part IV from here.
Stay tuned!
