CS211 - Fundamentals of Computer Programming II Homework 1

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CS 211 Homework 1

Purpose

The goal of this assignment is to get you programming with strings, iteration, and dynamic memory.  Read through the requirements of the assignment carefully and then make sure to read the “Algorithm   hints” section at the end of the document for additional guidelines on implementing the various requirements.

Preliminaries

Login to the server of your choice and cd to the directory where you   keep your CS 211 work.  Then unarchive the starter code, and change into the project directory:

%  cd  cs211

%  tar  -kxvf  ~cs211/hw/hw1 .tgz

.

. .

%  cd  hw1

If you have correctly downloaded and configured everything then the project should build cleanly (although several of the tests may not pass because of the unimplemented code):

% make

. . .

cc  -fsanitize=address,undefined  -l211  -o  test_translate . . .

%

Background

In this project, you will implement a clone of the standard Unix program tr(1), which is afilter program that performs translitera-  tion.  Given two equal-length sequences of characters,from and to,  it replaces all occurrences of characters appearing infrom with the character in the corresponding position in to.

The tr program takes thefrom and to character sequences as  command-line arguments.  Once the program is run, it takes in a string from user input, replaces the appropriate characters according to the from and to sequences, and prints out the result. In the simplest case, thefrom and to sequences are strings of the same length.  The   following shows an example of your tr program could work.

This homework assignment must be completed on Linux by log- ging intoa Linux workstation. Each time you login to work on CS 211, you should run 211   to ensure your environment is   setup correctly.  (If you get an   error saying that 211.h doesn’t  exist, that probably means you forgot to run 211.)

Contents

Make targets

The project also provides a Makefile with several targets which you can enter after make:

* default         & phony

Specifications

The project comprises two functional components, which are specified in this section.  First, though, we define charseqs (character sequences).

Character sequences

The tr program uses charseqs to specify which characters to replace and what to replace them with.  The C type of a charseq is just char*—that is, a C string—but they can be represented in two forms having different interpretations, each of which is used at different stages of the program:

•  A literal charseq is just a sequence of characters, each standing for itself.  For example, interpreted as a literal charseq, the string    "a-e " contains the three characters  ' a ' ,  ' - ' , and  ' e '  at indices 0, 1, and 2, respectively. In a literal charseq, no character has special  meaning.

•  An unexpanded charseq may contain ranges, written “c-d”, and escape sequences, written “\c”.

Target test is the default, which means you can run it by typ-   ing make alone, with no target name.
In C (but not C++) those lit- erals don’t actually have type char!—they have type int for obscure historical reasons.  That is,  ' A '  is an alternative way of    writing the int value 65.  Try printing sizeof  ' A '  and see. . . .

–  The range “c-d” stands for the interval of characters from  ' c '  to  ' d ' , inclusive.  (This means that if  ' c '  >  ' d '  then the range is empty, and if  ' c '  ==  ' d '  then the range contains only  ' c ' .)

Range bounds, both lower and upper, are always represented by single characters.  They are never the result of another range or  escape expansion.

–  If the escape “\c” is valid C string literal escape sequence, then it has the same meaning for tr as in C; otherwise it just stands for  character  ' c '  itself.

–  Every other character stands for itself. In particular, a “-” char- acter that is not part of a range stands for itself, as does “\”

character that is not followed by another character.

–  In cases of ambiguity, the leftmost possible expansion takes priority, and a range takes priority over a potential escape at the same position.

Here is a table showing several unexpanded charseqs along with their literal expansions, written as C string literals:

The tr program takes charseqs in unexpanded form, and must expand them to literal form before it can do its work.

The translate library

The translate library is responsible for expanding charseqs from un- expanded to literal form, and for using a pair of literal charseqs to translate a string. It provides a function for each of these purposes that will be used in src/tr.c. Additionally, the header file (translate.h)  exposes two helper functions which you will implement in translate.c to facilitate testing.  See section "Algorithm hints" on page 9 for detailed hints on how to implement each of the functions you are required to    write. src/translate.c defines four functions:

We have provided you a function mapping character  ' c '  to the meaning of \c, so you don’t have to figure that part out.

How could we figure out what characters should appear in these ranges?  See the manual page: man  ascii.

Then argc will contain the number of command-line arguments (in- cluding the name of the program itself in argv[0]), and argv will

contain the comnand line arguments themselves.

For example, if a C program is run like

%  my_prog  foo  bar  bazzz

then argc is 4 and argv is the array {

" my _prog " ,

" foo " ,   " bar " ,   " ba zzz "

} .

Reading input a line at a time

The C programming language doesn’t provide an easy way to read a line of input whose length is unknown, so we have provided you a small library, lib211, on the Unix login machines.  The library exports a function read_line () for this purpose.  Here is its signature:

char *   read _ line ( void );

The read_line function returns a character array allocated by

malloc(3), which means that the caller is responsible for deallocating it with free(3) when finished with it.  See the next subsection for more on this topic, and see the read_line(3) manual page on the lab machines  for information on the read   line function.

Working with  C strings

When testing your functions, you might be tempted to write assertions like this:

assert(   expand _ char seq ( " a - e " )  ==   " abcde "   ); But there are three problems with this:

1.  It leaks memory.

2.  It compares the addresses of the strings rather than the characters in them.

3.  In rare cases, it might cause undefined behavior.

C natively provides gets(3),

which is easy to use but inher- ently unsafe, and fgets(3), which can be used safely but requires  you to specify a limit on the length of the line.

The second and third prob- lems here are also solved by CHECK_STRING, which is de- scribed in the next subsection.

It leaks memory because expand_charseq() allocates memory and  the code above doesn’t free it.  To fix that, we need to store the result of expand_charseq() in a variable, which lets us refer to it twice:

char *   actual _ result  =   expand _ char seq ( " a - e " ); assert(  actual _ result   ==   " abcde "   );

free ( actual _ result );

However, this still won’t work, because when you use == to compare    pointers, it compares the addresses, not the pointed-to values. And the address returned by expand_charseq() will never be the same as the  address of a string literal.

Instead, to compare strings, we need to use thestrcmp(3) function (from ), which compares them character by character. You may expect, incorrectly, that strcmp() would return

true for equal strings and false for unequal strings, but actually it does something more useful:  strcmp(s1,  s2) determines the lexico- graphical ordering for s1 and s2. If s1 should come before s2 when sorting then it returns a negative int; if s1 should come after s2 then it returns a positive int. If they are equal, it returns 0.  Thus we should write:

char *   actual _ result  =   expand _ char seq ( " a - e " );

assert(   st rcmp ( actual _ result ,   " abcde " )  ==   0   ); free ( actual _ result );

This almost works! In fact, it usually will work.  But to be completely correct, we need to deal with the possibility that expand_charseq()    fails to allocate memory and returns NULL. In that case, strcmp() will  deference NULL, which is undefined behavior.  Thus, we need to ensure that actual_result is not NULLbefore we try to use the string that it points to:

char *   actual _ result  =   expand _ char seq ( " a - e " ); assert(  actual _ result   );

assert(   st rcmp ( actual _ result ,   " abcde " )  ==   0   ); free ( actual _ result );

Here are some more functions from  that you may find useful:

char*  strchr (const  char*  s,  int  c)

Searches string s for the first occurrence of (char)c, returning a pointer to the occurrence if found or NULL if not.

char*  strcpy (char*  dst,  const  char*  src)

Copies string pointed to by src into string pointed to by dst (which must have sufficient capacity, or you’ll get undefined    behavior).

size_t  strlen (const  char*)

Computes the length of a string (not including the  '\0' ).

Lexicographical order is a gen-   eralization of alphabetical order to sequences of non-letters (or more than just letters). strcmp()

compares the numeric values of chars, which means that

' a '  < ' b ' and ' A ' < ' B ' , but also ' B ' < ' a ' and '$ ' < ' , ' .

Why does strchr() take an int rather than a char?  Many C functions take a character as type int for obscure historical reasons.

Better testing assertions

We have created a number of helpful functions for testing your code, available in the lib211 library.  They have names like CHECK () or CHECK_INT () and function similarly to assertions: either the state-

ment is true or the test fails.  Here’s what writing test assertions with these macros looks like:

static   void   example _ checks ( void )

{

CHECK _ INT(   2   *   3 ,   6   );

CHECK _ SIZE (   size of ( double ) ,  8   );

CHECK _ CHAR (   toupper ( ' a ' ) ,    ' A '    );

CHECK(   is lower ( ' a ' )   );

}

The provided checks are summarized here:

Algorithm hints

In this section, we provide suggestions, such as algorithms, for writing the necessary functions.  These hints are given in what we expect will  be the best order of implementation. It’s a very good idea to test each function as you write it, rather than testing them all at the end, because you will find bugs sooner that way.

The  charseq_length()function

The charseq_length() function scans its argument string (an un- expanded character sequence) while counting how many characters it will take when expanded.  Thus, you need two variables: one to count, and one to keep track of the position while scanning the string. Start the count at 0 and the position at the beginning of the argu- ment string (i.e., at 2).  Then iterate through the sequence string and evaluate the following conditions for each iteration:

To keep track of a position in   a string, you can use a size_t variable to hold the index.

• If the character at the current position is  '\0' , then you’ve reached the end and should return the count.
• If the character at the next position is  ' - ' , and the character at the position after that is not  '\0 ' , then you’ve found a range. If we call the character before the hyphen start and the character after  the hyphen end, then we can determine the length of the range by   comparing the two characters: If start  >  end then the range is empty; otherwise the length of the range is end  -  start  +  1. Add this resulting length to the count, and then advance the current position by 3 to get to the first character past the right side of the range.
• If the character at the current position is  '\\ '  (a single backslash), and the character at the next position is not  '\0 '  then you have found an escape sequence. Its expanded length is 1, so add that much to the count, and advance the current position by 2 to get to the first character after the escape sequence.
• Otherwise, the character at the current position will be copied as is, so increment the count by 1 and advance the current position to the  next position in the string.

The  expand_charseq()function

Like charseq_length(), the expand_charseq() function scans its argument string (an unexpanded character sequence), but instead of    counting, it copies the characters into a fresh string, expanding ranges and escape characters into their literal meanings.

The first thing it must do is allocate memory for its result. We have provided you code that calls charseq_length() to find out how much memory is needed, allocates the memory, and checks that the allocation succeeded.  Then the algorithm works by scanning the argument string while storing characters into the result string.  To do this, you will likely need two variables: one to keep track of your position in the unexpanded character sequence being scanned (the    source); and one to keep track of your position in the result string    being filled in (the destination).

The control logic of the scanning-and-copying loop is the same as in the charseq_length() function (including by iterating through the source sequence), but the actions at each step differ:

The  translate_char()function

The translate_char() function takes a character to translate (c) and two literal charseqs (from and to). The idea is to scan charseq from    searching for c. If we find c at some index i then return to[i].  If we  get to the end of from without finding c then return c unchanged.

The  translate()function

The translate() function takes a string to translate in place (s) and  two literal charseqs (from and to). The idea is to iterate through each character in s, replacing each character with its translation according to translate_char().

Deliverables & evaluation

For this homework you must:

1.  Implement the specification for the translate library from the previous section in src/translate.c.

2.  Implement the specification for the tr program from the previous section in src/tr.c.

3.  Add more test cases to test/test_translate.c in order to test the four functions that you defined in src/translate.c.

To avoid undefined behavior here, you should store start and end as ints, not chars.

To understand why, consider what would happen if end were CHAR_MAX.