1. Goals for this week

2. Starting Point Code

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

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

3. Starting to build a parser

Let’s start by looking at a slightly different version of the str.c file we saw last week in Lab Meeting 09. There are a few differences:

  • This version uses fgets instead of readline to read a line from the user.

  • The string read from the user is stored on the stack instead of the heap.

  • At the end of the file is a TODO item commented out. We will work on that now.

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 string you typed in str.c:

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

    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 the variable called tok_end.

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

    4. Copy all of the characters from the original string from tok_start to tok_end 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 that we used in the Game of Life lab.

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;
  • The example in twoD_method2.c shows how to allocate space for a two-dimensional array using this method.

  • You may want to try implmenting the code in this function (or think about how you would do it) as practice for this week’s lab:

    • try to implement the two functions with TODO comments in them

    • try adding code to free the dynamically allocated space

    • run your solution in valgrind to make sure you have no memory access errors: valgrind ./twoD_method2

5. Parsing the entire command line

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

6. Handy References