Processes (proc) Project
COP-3402

start     ::= pipes "\n"
pipes     ::= command pipe*
pipe      ::= "|" command
command   ::= program in? out?
program   :: STRING STRING*
in        ::= "<" STRING
out       ::= ">" STRING

This grammar allows for any number of pipes, but only one pipe (or no pipe) is required to be supported. Supporting unbounded pipes is a bonus feature.

This grammar requires that a redirect in comes before a redirect out, i.e., ls <infile >outfile is allowed, but ls >outfile <infile is not. This makes parsing the command input simpler.

The lexer identifies the individal tokens of the command input and handles whitespace for you. The lexer is given to you (lex.l). The lexer is called with yylex() and returns the type of token, while setting yytext to the actual text (lexem) of the token. Below are the names of the tokens as defined in the token type enum (tokens.h):

typedef enum {
        STRING,
        PIPE,
        REDIRECT_IN,
        REDIRECT_OUT,
        END_OF_LINE,
} token_t;

The token enum names correspond to the actual text of the tokens as given in the below table. Whitespace is ignored

The code template provides a consume() function which will read the next token from the input and save the lexeme (text) of the token into the globla variables lookahead and lexeme respectively. Use consume() and inspect lookahead and lexeme to parse the input into a data structure.

Write a parser that takes tokens from the user input (via consume()) and both checks that the input is valid (according to the grammar) and creates an in-memory data structure to store the commands.

See the lecture notes on parsing for an example to get you started.

You are also free to interpret the commands (run programs, do redirection and piping) during parsing, although this may be more challenging.

The code template provides an empty parse() function for you to implement your parser in.

The result of parsing should be a linked list of command_t structs. Use the provided add_command() function (util.h) to create and add a new, empty command_t struct to the list. add_command() will returns a pointer to the new struct that you can then populate with the program name, args, and redirect file names.

Use the provided print_commands() function (util.h) to help debug your parser.

The code template provides you with a data structure, command_t in util.h, to store the results of parsing the commands from the input.

typedef struct command_s {
        char *argv[MAX_ARGS];  // NULL-terminated list, i.e., the next element after the last should be NULL.
        char *in;  // NULL if there is no redirect
        char *out;  // NULL if there is no redirect
        struct command_s *next;
} command_t;

The data structure has one field for the argv array. This stores both the name of the program and the arguments, i.e., if the command is ls path1 path2, argv will be

[ "ls", "path1", "path2", NULL ]

The last element in the argv list must be succeeded by NULL. This is requirement of the exec series of commands (man 2 execv, "The array of pointers must be terminated by a null pointer.).

There are fields for the name of file to redirect stdin from (in) and the name of the file to redirect standard out to (out). If redirects are not present for the command in the user input, these fields should be NULL.

The next field points to the next element in the linked list or NULL when it is the last element.

add_command() (util.h) allocates a new command_t struct and appends it to the list for you.

The beginning of the list is pointed to by the global variable first_command (util.h) and the end by last_command (util.h), each of which will be NULL if the list is empty.

You can check for list sizes with the following conditions:

You are also free to define your own data structure(s) if you prefer.

fork() creates a new process, dup2() redirects I/O, and pipe() creates a pipe.

For program execution, you can use (execvp instead of execve) which does path lookups for you.

When performing redirection, be sure to close the pipe file descriptors in the parent or the program reading the pipe may hang waiting for the file to close.

You can use the following in the parent to wait until there are no more child processes running:

do {
  while (wait(NULL) > 0);
} while (errno != ECHILD);

syscall errors should always be checked.

Report errors via exit codes passed to the exit library call, i.e., exit(EXIT_FAILURE).exit code 5.

Error messages are optional, but should only be written to stderr, not to stdout, which will be used for program output, i.e., use perror() or fprintf(stderr, ...) instead of printf.

No erroneous commands will be given for testing.

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include <unistd.h>    // fork()
#include <stdlib.h>    // exit()
#include <inttypes.h>  // intmax_t
#include <sys/wait.h>  // wait()
#include <string.h>    // strcspn(), strtok
#include <errno.h>     // ECHILD
#include <fcntl.h>     // O_RDONLY, open

#include "tokens.h"

#include "util.h"

#include "lex.c"

Note that lex.c isn't a header, but the generated code from the lexer.

Be sure to complete the vc exercise before attempting this project.

Create a new local repository, following the directions in the vc exercise (including the git --set-upstream last step) and set the local and remote repository URLs to be the following locations:

See the hello project for instructions on cloning a project from the grading server.