5,107 reads

Building a Linux Shell [Part III]

by Mohammed IsamJune 29th, 2020

Too Long; Didn't Read

This is part III of a tutorial on how to build a Linux shell. We use input tokens to create an AST, which is a tree-like structure that contains information about the components of a command. In the upcoming parts of this tutorial, we'll add more functions to enable our shell to parse loops and conditional expressions. 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) or we reach the end of our input.

Company Mentioned

featured image - Building 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_H

enum 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) or
```
NODE_VAR
```
(command name and arguments list)
```
val_type
```
=>
```
VAL_STR
```
```
val.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.c

If 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.

Stay tuned!

Previously published at https://medium.com/swlh/lets-build-a-linux-shell-part-iii-a472c0102849