1. Goals for this week

2. Starting Point Code

Start by creating a week10 directory in your inlab subdirectory and copying over some files:

$ cd ~/cs31/inlab
$ mkdir week10
$ cd week10
$ pwd
/home/you/cs31/inlab/week10
$ cp ~richardw/public/cs31/week10/* ./
$ ls
Makefile  str.c  twoD_method2.c

3. Starting to build a parser

Let’s look at the file str.c. You saw the majority of this code in In-Lab Assignment 09. At the end of the file is a TODO item commented out.

3.1. Reminders

  • In C, a string is an array of char with a terminating null character '\0' that signifies the end of the string.

  • When allocating space for the array of chars, (statically, or dynamically using malloc) remember to allocate enough space for the terminating null character.

3.2. Try it out

  • Compile and run this program to remind yourself what it’s doing. Try running with some different input strings, for example:

hello 1 2 3
    hello   1   2   3
!@  hello  x%

3.3. Extracting the first token

  • Follow the instructions in the TODO section of the str.c file. Try implementing code to create a substring for the first token in the str string:

    1. Search for the start of the first token (the first non-space char). Save the index of this character in the string (in a variable called start_index, for example).

    2. Continue through the string until you find the end of first token (the first whitespace character after the start of this token). Save the index of this character in the string (in a variable called stop_index, for example).

    3. malloc space to hold all of the characters from start_index up to stop_index, saving a space for the '\0' character.

    4. Copy all of the characters from the original string from start_index to stop_index into the new string, and be sure to add a '\0' at the end.

    The result should be that the substr pointer points to a string equal to the first token of str. After you’ve extracted this token, print it out.

    Compile and try running with different input strings and see if it works.

4. Dynamically allocated 2-D arrays (an array of arrays)

We are going to look at an example of the "Method 2" way of dynamically allocating a 2D array. This way supports [i][j] indexing, but it is less memory efficient than the single malloc ("Method 1") way of allocating 2D arrays.

This method allocates a 2D array as an array of arrays. In the outer array (of row dimension) each element stores the base address of an inner array ( of column dimension) of values in each row of the 2D array. Section 2.5 of the textbook describes this, and includes an figure of what this version of a 2D array looks like in memory.

This type of 2D array is used for the argv 2D array of char that contains the command line argument values passed as a parameter to main (and as we’ll see in class, the parameter passed to execvp).

In this method, the programmer makes num_rows + 1 calls to malloc:

  1. one malloc to dynamically allocate an array of type * that will store the base address of an array to store each row’s values.

  2. num_rows mallocs to dynamically allocate arrays of type to store the values in each row of the 2D array. The base address of each is stored in the ith bucket of the outer array.

The variable storing the base address of the outer array is a type **: a pointer to a storage location that stores a type * (which stores the base address of an array of type). For example:

int **2d_array;
char **2d_chararr;
  • Let’s look at the example in twoD_method2.c.

  • Next, try implement the two functions that it calls.

  • Next, try adding code to free its dynamically allocated space.

  • Next, run in valgrind and see if you have any memory access errors:

    valgrind ./twoD_method2

5. Parsing the entire command line

Proceed to Lab 8. This is a two-week lab. In this part of the lab, you will be writing a library that parses the command-line arguments into a dynamically allocated two dimensional array.

6. Handy References