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 : You can download the complete source code for Part II & III from . NOTE 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 , or out of these tokens. This AST is what we'll pass to the executor to be, well, executed. Abstract Syntax Tree AST, Our parser will contain only one function, . In the upcoming parts of this tutorial, we'll add more functions to enable our shell to parse loops and conditional expressions. parse_simple_command() So let's start coding our parser. You can begin by creating a file named in the source directory, to which you'll add the following code: parser.h ; # PARSER_H ifndef # PARSER_H define # 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 and add the following code to it: parser.c { (!tok) { ; } (!cmd) { free_token(tok); ; } { (tok->text[ ] == ) { free_token(tok); ; } (!word) { free_node_tree(cmd); free_token(tok); ; } set_node_val_str(word, tok->text); add_child_node(cmd, word); free_token(tok); } ((tok = tokenize(src)) != &eof_token); cmd; } # include # 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 return NULL * = ( ); struct node_s cmd new_node NODE_COMMAND if return NULL * = -> ; struct source_s src tok src do if 0 '\n' break * = ( ); struct node_s word new_node NODE_VAR if return NULL while return Pretty simple, right? To parse a simple command, we only need to call to retrieve input tokens, one by one, until we get a newline token (which we test for in the line that reads: ), or we reach the end of our input (we know this happened when we get an token. See the loop conditional expression near the bottom of the previous listing). We use input tokens to create an AST, which is a 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. tokenize() if(tok->text[0] == '\n') eof_token tree-like structure 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, , which we'll use to represent nodes in our AST. struct node_s Go ahead and create a new file, , and add the following code to it: node.h node_type_e { NODE_COMMAND, NODE_VAR, }; val_type_e { VAL_SINT = , VAL_UINT, VAL_SLLONG, VAL_ULLONG, VAL_FLOAT, VAL_LDOUBLE, VAL_CHR, VAL_STR, }; symval_u { sint; uint; sllong; ullong; sfloat; ldouble; chr; *str; }; node_type_e type; val_type_e val_type; symval_u val; children; }; ; ; ; ; # NODE_H ifndef # NODE_H define enum /* simple command */ /* variable name (or simply, a word) */ enum 1 /* signed int */ /* unsigned int */ /* signed long long */ /* unsigned long long */ /* floating point */ /* long double */ /* char */ /* str (char pointer) */ union long unsigned long long long unsigned long long double long double char char { struct node_s enum /* type of this node */ enum /* type of this node's val field */ union /* value of this node */ int /* 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 ( node_type_e type) enum 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, *val) char # endif The 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 and ). In the next parts of this tutorial, we'll add more node types to this enumeration. node_type_e command name arguments The enumeration represents the types of values we can store in a given node structure. For simple commands, we'll only use strings ( enumeration type). Later on in this series, we'll use the other types when we handle other types of complex commands. val_type_e VAL_STR The 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 ( for signed long integers, for strings, etc). symval_u sint str The 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 field contains the number of child nodes, and points to the first child node (otherwise it will be ). If this is a child node, we can traverse the AST nodes by following the and pointers. struct node_s children first_child NULL next_sibling prev_sibling If we want to retrieve a node's value, we need to check the field and, according to what we find there, access the appropriate member of the field. For simple commands, all nodes will have the following attributes: val_type val => (root node) or (command name and arguments list) type NODE_COMMAND NODE_VAR => val_type VAL_STR => pointer to the string value val.str Now let's write some functions to help us work with node structures. Create a file named and add the following code: node.c { (!node) { ; } (node, , (struct node_s)); node->type = type; node; } { (!parent || !child) { ; } (!parent->first_child) { parent->first_child = child; } { struct node_s *sibling = parent->first_child; (sibling->next_sibling) { sibling = sibling->next_sibling; } sibling->next_sibling = child; child->prev_sibling = sibling; } parent->children++; } { node->val_type = VAL_STR; (!val) { node->val.str = ; } { *val2 = ( (val)+ ); (!val2) { node->val.str = ; } { (val2, val); node->val.str = val2; } } } { (!node) { ; } (child) { free_node_tree(child); child = next; } (node->val_type == VAL_STR) { (node->val.str) { (node->val.str); } } (node); } # include # include # include # include # include "shell.h" # include "node.h" # include "parser.h" struct node_s * new_node ( node_type_e type) enum * = ( ( )); struct node_s node malloc sizeof struct node_s if return NULL memset 0 sizeof return void add_child_node (struct node_s *parent, struct node_s *child) if return if else while void set_node_val_str (struct node_s *node, *val) char if NULL else char malloc strlen 1 if NULL else strcpy void free_node_tree (struct node_s *node) if return * = -> ; struct node_s child node first_child while * = -> ; struct node_s next child next_sibling if if free free The function creates a new node and sets it's field. new_node() type The function expands the AST of a simple command by adding a new child node and incrementing the root node's field. If the root node has no children, the new child is assigned to the field of the root node. Otherwise, the child is appended to the end of the children's list. add_child_node() children first_child The function sets a node's value to the given string. It copies the string to a newly allocated memory space, then sets the and 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. set_node_val_str() val_type val.str The function frees the memory used by a node structure. If the node has children, the function is called recursively to free each of them. free_node_tree() 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, . 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. do_simple_command() Create a file named , and add the following code: executor.h ; ; ; # BACKEND_H ifndef # BACKEND_H define # include "node.h" * char search_path ( *file) char int do_exec_cmd ( argc, **argv) int char int do_simple_command (struct node_s *node) # endif Just some function prototypes. Now create and define the following functions: executor.c { *PATH = getenv( ); *p = PATH; *p2; (p && *p) { p2 = p; (*p2 && *p2 != ) { p2++; } plen = p2-p; (!plen) { plen = ; } alen = (file); path[plen+ +alen+ ]; (path, p, p2-p); path[p2-p] = ; (p2[ ] != ) { (path, ); } (path, file); (stat(path, &st) == ) { (!S_ISREG(st.st_mode)) { errno = ENOENT; p = p2; (*p2 == ) { p++; } ; } p = ( (path)+ ); (!p) { ; } (p, path); p; } { p = p2; (*p2 == ) { p++; } } } errno = ENOENT; ; } { ( (argv[ ], )) { execv(argv[ ], argv); } { *path = search_path(argv[ ]); (!path) { ; } execv(path, argv); (path); } ; } { (!argc) { ; } (argc--) { (argv[argc]); } } { (!node) { ; } (!child) { ; } argc = ; max_args = ; *argv[max_args+ ]; *str; (child) { str = child->val.str; argv[argc] = ( (str)+ ); (!argv[argc]) { free_argv(argc, argv); ; } (argv[argc], str); (++argc >= max_args) { ; } child = child->next_sibling; } argv[argc] = ; child_pid = ; ((child_pid = fork()) == ) { do_exec_cmd(argc, argv); ( , , strerror(errno)); (errno == ENOEXEC) { ( ); } (errno == ENOENT) { ( ); } { (EXIT_FAILURE); } } (child_pid # include # include # include # include # include # include # include "shell.h" # include "node.h" # include "executor.h" * char search_path ( *file) char char "PATH" char char while while ':' int if 1 int strlen char 1 1 strncpy '\0' if -1 '/' strcat "/" strcat ; struct stat st if 0 if if ':' continue malloc strlen 1 if return NULL strcpy return else /* file not found */ if ':' return NULL int do_exec_cmd ( argc, **argv) int char if strchr 0 '/' 0 else char 0 if return 0 free return 0 static inline void free_argv ( argc, **argv) int char if return while free int do_simple_command (struct node_s *node) if return 0 * = -> ; struct node_s child node first_child if return 0 int 0 long 255 char 1 /* keep 1 for the terminating NULL arg */ char while malloc strlen 1 if return 0 strcpy if break NULL pid_t 0 if 0 fprintf stderr "error: failed to execute command: %s\n" if exit 126 else if exit 127 else exit else if 0 fprintf stderr "error: failed to fork command: %s\n" return 0 int 0 0 return 1 The function takes the name of a command, then searches the directories listed in the variable to try and find the command's executable file. The variable contains a comma-separated list of directories, such as . For each directory, we create a pathname by appending the command name to the directory name, then we call 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 directory, we search the second, third, and the rest of the directories, until we find our executable file. If we fail in finding the command by searching all the directories in the , we return (this usually means the user typed an invalid command name). search_path() $PATH $PATH /bin:/usr/bin stat() $PATH $PATH $PATH NULL The function executes a command by calling 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 . Otherwise, we try to locate the command by calling , which should return the full pathname that we will pass on to . do_exec_cmd() execv() execv() search_path() execv() The function frees the memory we used to store the arguments list of the last command executed. free_argv() The 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 , contains the name of the command we want to execute). do_simple_command() argv[0] The function then forks a new child process. In the child process, we execute the command by calling . 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 . do_exec_cmd() non-zero exit status In the parent process, we call to wait for our child process to finish execution. We then free the memory we used to store the arguments list and return. waitpid() Now in order to incorporate the new code into our existing shell, you need to first update the function by removing the line that reads and replace it with the following lines: main() printf("%s\n", cmd); src.buffer = cmd; src.bufsize = (cmd); src.curpos = INIT_SRC_POS; parse_and_execute(&src); ; struct source_s src strlen Now before you close the file, go to the beginning of the file and add the following lines after the last directive: main.c #include # include "source.h" # include "parser.h" # include "backend.h" Then go to the end of the file (after the 's function definition), and add the following function: read_cmd() { skip_white_spaces(src); (tok == &eof_token) { ; } (tok && tok != &eof_token) { (!cmd) { ; } do_simple_command(cmd); free_node_tree(cmd); tok = tokenize(src); } ; } int parse_and_execute (struct source_s *src) * = ( ); struct token_s tok tokenize src if return 0 while * = ( ); struct node_s cmd parse_simple_command tok if break return 1 This function takes the part of our ( ) away from the 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 function. Eval-Print Read-Eval-Print-Loop REPL main() main() Finally, don't forget to add the following include and function prototype to your file, right before the closing directive: shell.h #endif ; # 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, should not output anything, and there should be an executable file named in the current directory: gcc shell Now invoke the shell by running , and try entering a few commands, such as , , and : ./shell ls ls -l 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 , 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. echo $PATH 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