CSC 7000-001 Algorithms & Programming
Thursdays from 6:15pm to 8:45pm in Mendel 115
Dr. David Matuszek, Mendel 162C, (610) 519-5654
The purpose of this (long) page is to show the program development process, from initial concept to final working program. Almost all the mistakes made along the way are included in this development trail.
The program I chose for this purpose is one to translate a file containing English text into "Pig Latin," in which the letters of the English word are rearranged (details presented later on this page). I chose this problem because it involves a fair amount of string manipulation and is complex enough to require a number of support functions.
The necessary first step is to decide the overall logic of the program. Sometimes you can do this entirely in your head; I tried to write out as much of the process as I reasonably could.
Pig Latin 1
read in a line;
if successful {
get word from line;
if successful {
convert word to Pig Latin
}
}
Problem: only reads one line.
Pig Latin 2
do forever {
read in a line;
if successful {
get word from line;
if successful {
convert word to Pig Latin
}
else break;
}
}
Problem: only translates one word per line.
Pig Latin 3
do forever {
read in a line;
if successful {
do forever {
get word from line;
if successful {
convert word to Pig Latin
}
else break;
}
else break;
}
}
Problem: Doesn't handle punctuation.
Pig Latin 4
do forever {
read in a line;
if successful {
do forever {
handle punctuation before word;
get word from line;
if successful {
convert word to Pig Latin
}
else break;
}
else break;
}
}
Problem: Doesn't handle punctuation at end of line.
Pig Latin 5
do forever {
read in a line;
if successful {
do forever {
handle punctuation before word or eol;
get word from line;
if successful {
convert word to Pig Latin
}
else break;
}
else break;
}
}
Problem: where do we put results?
Pig Latin 6
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
get word from line;
if successful {
convert word to Pig Latin;
write out converted word;
}
else break;
}
else break;
}
}
Problem: forgot to write out newlines.
Pig Latin 7
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
if saw eol, write out newline;
get word from line;
if successful {
convert word to Pig Latin;
write out converted word;
}
else break;
}
else break;
}
}
Minor problem: no need to look for word after eol.
Pig Latin 8
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
if saw eol {
write out newline;
break;
}
get word from line;
if successful {
convert word to Pig Latin;
write out converted word;
}
else break;
}
else break;
}
}
Minor problem: no need for second break. In fact, no need to test if we got a word.
Pig Latin 9
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
if saw eol {
write out newline;
break;
}
get word from line;
if successful {
convert word to Pig Latin;
write out converted word;
}
else break;
}
else break;
}
}
Clean up by removing strikeouts.
Pig Latin 10
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
if saw eol {
write out newline;
break;
}
get word from line;
convert word to Pig Latin;
write out converted word;
}
else break;
}
}
Looks OK; add usual initialization & closing.
Pig Latin 11
usual header stuff;
get file name 1;
open file 1 for input;
get file name 2;
open file 2 for output;
do forever {
read in a line;
if successful {
do forever {
get punctuation before word or eol;
write out punctuation;
if saw eol {
write out newline;
break;
}
get word from line;
convert word to Pig Latin;
write out converted word;
}
else break;
}
}
close files;
Looks OK; start turning into C.
Pig Latin 12
/* usual header stuff; */
#include <stdio.h>
int main (int argc, char *argv[]) {
/* Forgot to mention error checking */
if (argc != 2) {
printf ("Must provide two filenames"
" as arguments.\n");
exit (1);
}
/* get file name 1;*/
FILE *in, *out; /* Must move up */
/* file name 1 is argv[1] */
/* open file 1 for input; */
in = fopen (argv[1], "r");
/* get file name 2; */
/* open file 2 for output; */
out = fopen (argv[2], "w");
/* do forever { */
while (1) {
/* read in a line; */
/* if successful { */
char line[500]; /* must move up */
if (fgets (in, 500, line)) {
/* do forever { */
while (1) {
/* get punctuation before word or eol; */
char *punctuation; /* move up */
punctuation = get_punctuation (line);
/* write out punctuation; */
fprintf (out, "%s", punctuation);
/* if saw eol { */
-- Now we have a problem.
How do we know if we saw an eol?
write out newline;
break;
}
get word from line;
convert word to Pig Latin;
write out converted word;
}
else break;
}
}
close files;
We need to define get_punctuation to keep track of position. Let's define it as:
char *get_punctuation(char *line, int *pos);
where "pos" is the position in the line. So it's going to return a string and
update pos.
Now we can do:
while (1) {
/* get punctuation before word or eol; */
char *punctuation; /* move up */
int position; /* move up */
position = 0; /* DON'T move up */
punctuation = get_punctuation (line, &position);
/* write out punctuation; */
fprintf (out, "%s", punctuation);
/* if saw eol { */
if (line[position] == '\0') {
Pig Latin 13
/* usual header stuff; */
#include <stdio.h>
int main (int argc, char *argv[]) {
/* Forgot to mention error checking */
if (argc != 2) {
printf ("Must provide two filenames"
" as arguments.\n");
exit (1);
}
/* get file name 1;*/
FILE *in, *out; /* Must move up */
/* file name 1 is argv[1] */
/* open file 1 for input; */
in = fopen (argv[1], "r");
/* get file name 2; */
/* open file 2 for output; */
out = fopen (argv[2], "w");
/* do forever { */
while (1) {
/* read in a line; */
/* if successful { */
char line[500]; /* must move up */
if (fgets (in, 500, line)) {
/* do forever { */
while (1) {
/* get punctuation before word or eol; */
char *punctuation; /* move up */
int position; /* move up */
position = 0; /* DON'T move up */
punctuation = get_punctuation (line, &position);
/* write out punctuation; */
fprintf (out, "%s", punctuation);
/* if saw eol { */
if (line[position] == '\0') {
/* write out newline; */
fprintf (out, "\n");
break;
}
/* get word from line; note different approach */
char word[100]; /* move up */
get_word (line, &position, word);
/* convert word to Pig Latin; */
char latin[100]; /* move up */
latinize (word, latin);
/* write out converted word; */
fprintf (out, "%s", latin);
}
else break;
}
}
/* close files; */
fclose (in); fclose (out); }
Move declarations up, add prototypes.
Pig Latin 14 /* usual header stuff; */ #include <stdio.h>
char *get_punctuation(char *line, int *pos); void latinize (char *word, char *latin);
int main (int argc, char *argv[]) {
FILE *in, *out;
char line[500];
char *punctuation;
int position;
char word[100];
char latin[100]; /* move up */
/* Forgot to mention error checking */
if (argc != 2) {
printf ("Must provide two filenames"
" as arguments.\n");
exit (1);
}
/* get file name 1;*/
/* file name 1 is argv[1] */
/* open file 1 for input; */
in = fopen (argv[1], "r");
/* get file name 2; */
/* open file 2 for output; */
out = fopen (argv[2], "w");
/* do forever { */
while (1) {
/* read in a line; */
/* if successful { */
if (fgets (in, 500, line)) {
/* do forever { */
while (1) {
/* get punctuation before word or eol; */
position = 0; /* DON'T move up */
punctuation = get_punctuation (line, &position);
/* write out punctuation; */
fprintf (out, "%s", punctuation);
/* if saw eol { */
if (line[position] == '\0') {
/* write out newline; */
fprintf (out, "\n");
break;
}
/* get word from line; note different approach */
get_word (line, &position, word);
/* convert word to Pig Latin; */
latinize (word, latin);
/* write out converted word; */
fprintf (out, "%s", latin);
}
else break;
}
}
/* close files; */
fclose (in); fclose (out); }
Now try it!
renoir% gcc piglatin.c piglatin.c: In function `main': piglatin.c:35: warning: passing arg 1 of `fgets' from incompatible pointer type piglatin.c:35: warning: passing arg 3 of `fgets' from incompatible pointer type piglatin.c:63: parse error before `else'
Here's the first two errors:
if (fgets (in, 500, line)) {
should be:
if (fgets (line, 500, in)) {
Since there is no obvious syntax error before the else, it's probably a
problem with mismatched braces. Let's look at just the relevant lines:
int main (int argc, char *argv[]) {
if (argc != 2) {
}
while (1) {
if (fgets (in, 500, line)) {
while (1) {
if (line[position] == '\0') {
break;
}
}
else break;
}
}
}
Sure enough, the braces are messed up. So was some of the indentation, so I reindented things as appropriate.
Now let's try compiling it to see what happens:
renoir% gcc piglatin.c Undefined first referenced symbol in file latinize /tmp/cce6a4RH1.o get_word /tmp/cce6a4RH1.o get_punctuation /tmp/cce6a4RH1.o ld: fatal: Symbol referencing errors. No output written to a.out
This isn't the compiler complaining, but the linker. It's complaining because I haven't written those functions yet.
Pig Latin 14
/* usual header stuff; */
#include <stdio.h>
char *get_punctuation(char *line, int *pos);
void latinize (char *word, char *latin);
int main (int argc, char *argv[]) {
FILE *in, *out;
char line[500];
char *punctuation;
int position;
char word[100];
char latin[100]; /* move up */
/* Forgot to mention error checking */
if (argc != 2) {
printf ("Must provide two filenames"
" as arguments.\n");
exit (1);
}
/* get file name 1;*/
/* file name 1 is argv[1] */
/* open file 1 for input; */
in = fopen (argv[1], "r");
/* get file name 2; */
/* open file 2 for output; */
out = fopen (argv[2], "w");
/* do forever { */
while (1) {
/* read in a line; */
/* if successful { */
if (fgets (line, 500, in)) {
/* do forever { */
while (1) {
/* get punctuation before word or eol; */
position = 0; /* DON'T move up */
punctuation = get_punctuation (line, &position);
/* write out punctuation; */
fprintf (out, "%s", punctuation);
/* if saw eol { */
if (line[position] == '\0') {
/* write out newline; */
fprintf (out, "\n");
break;
}
/* get word from line; note different approach */
get_word (line, &position, word);
/* convert word to Pig Latin; */
latinize (word, latin);
/* write out converted word; */
fprintf (out, "%s", latin);
} /* while */
} /* if */
else break;
}
/* close files; */
fclose (in);
fclose (out);
}
Now to begin writing the missing functions.
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or end of string) */
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = 0; i < *pos - start; i++)
*(punc + i) = line[start + i];
*(punc + i) = '\0';
}
void get_word (char *line, int *pos, char *word) {
while (is_letter (line[*pos])) {
*word = line[*pos];
word++;
}
*word = '\0';
}
int is_letter (char c) {
if (c >= 'a' && c <= 'z') return 1;
if (c >= 'A' && c <= 'z') return 1;
if (c == '\'' || c == '-') return 1;
return 0;
}
void latinize (char *word, char *latin) {
/* Stub */
latin = word;
}
Prototypes: char *get_punctuation(char line[], int *pos); void get_word (char *line, int *pos, char *word); int is_letter (char c); void latinize (char *word, char *latin);
Here is the program as developed so far:
#include <stdio.h>
char *get_punctuation(char *line, int *pos);
void latinize (char *word, char *latin);
int main (int argc, char *argv[]) {
FILE *in, *out;
char line[500];
char *punctuation;
int position;
char word[100];
char latin[100]; /* move up */
/* Forgot to mention error checking */
if (argc != 2) {
printf ("Must provide two filenames"
" as arguments.\n");
exit (1);
}
In order to fit comfortably on overheads, the
body of the program has been moved to next page.
/* close files; */ fclose (in); fclose (out); }
Body of the program, with comments
improved and condensed to fit on page.
/* open files for input and output */
in = fopen (argv[1], "r");
out = fopen (argv[2], "w");
while (1) {
/* attempt to read in a line */
if (fgets (line, 500, in)) {
while (1) {
/* get punctuation before word or eol; */
position = 0; /* DON'T move up */
punctuation =
get_punctuation (line, &position);
fprintf (out, "%s", punctuation);
/* if saw eol, write newline and break */
if (line[position] == '\0') {
fprintf (out, "\n");
break;
}
/* get word from line; different approach */
get_word (line, &position, word);
/* convert word to Pig Latin; */
latinize (word, latin);
/* write out converted word; */
fprintf (out, "%s", latin);
} /* while */
} /* if */
else break;
}
/* close files; */
fclose (in);
fclose (out);
}
Prototypes: char *get_punctuation(char line[], int *pos); void get_word (char *line, int *pos, char *word); int is_letter (char c); void latinize (char *word, char *latin);
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or eol) */
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = 0; i < *pos - start; i++)
*(punc + i) = line[start + i];
*(punc + i) = '\0';
}
void get_word (char *line, int *pos, char *word) {
while (is_letter (line[*pos])) {
*word = line[*pos];
word++;
}
*word = '\0';
}
int is_letter (char c) {
if (c >= 'a' && c <= 'z') return 1;
if (c >= 'A' && c <= 'z') return 1;
if (c == '\'' || c == '-') return 1;
return 0;
}
void latinize (char *word, char *latin) {
/* Stub */
latin = word;
}
renoir% a.out inp outp Must provide two filenames as arguments.
if (argc != 2) {
Typical dumb error; my program requires three arguments, because argument numbering is as follows:
a.out inp outp 1 2 3
Here's the correction:
if (argc != 3) {
Try, try again.
renoir% a.out inp outp Segmentation Fault (core dumped)
I hate it when that happens, because I get so little helpful information. I don't see anything obvious by just looking at the code, so I put in some print statements. As I was doing it, I realized that I had forgotten to return a value, so I added that also.
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or end of string) */
printf ("In get_punctuation, line=\"%s\"\n",
line);
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
printf ("In get_punctuation 2, line=\"%s\"\n",
line);
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = 0; i < *pos - start; i++)
*(punc + i) = line[start + i];
*(punc + i) = '\0';
printf ("In get_punctuation 2, punc=\"%s\"\n",
punc);
return punc;
}
That didn't help; crashed, no additional output. Maybe because it doesn't work when there is no punctuation before the first word? Reading the program very carefully, I also found another error, this time in the way the for loop was set up.
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
while (line[*pos] != 0 && !is_letter (line[*pos]))
(*pos)++;
if (*pos == start) {
printf ("Returning empty string.\n");
return "";
}
punc = (char *) malloc (*pos - start + 1);
for (i = start; i < *pos; i++) {
*(punc + i) = line[start + i];
}
*(punc + i) = '\0';
return punc;
}
No crash, but program gets into an infinite loop (doesn't finish, but doesn't do anything else, either). Maybe the punctuation is OK but there's something wrong with getting the words? More print statements:
void get_word (char *line, int *pos, char *word) {
while (is_letter (line[*pos])) {
printf ("Copying line[%d]='%c'\n", *pos, line[*pos]);
*word = line[*pos];
word++;
}
*word = '\0';
}
Copying line[0]='O'
Copying line[0]='O'
Copying line[0]='O'
Copying line[0]='O'
Copying line[0]='O'
Copying line[0]='O'
...
Lots of that; I had to abort the program. 'O' is the first letter of the first input word, so my position isn't getting updated properly. Now that I know what's going on, it's easy to find and fix:
void get_word (char *line, int *pos, char *word) {
while (is_letter (line[*pos])) {
*word = line[*pos];
word++;
(*pos)++;
}
*word = '\0';
}
Try, try again.
Copying line[0]='O' Copying line[1]='n' Copying line[2]='e' Copying line[0]='O' Copying line[1]='n' Copying line[2]='e' Copying line[0]='O' Copying line[1]='n' Copying line[2]='e' ...
Relevant portion of code from the calling program:
while (1) {
position = 0; /* DON'T move up */
punctuation = get_punctuation (line, &position);
get_word (line, &position, word);
}
So I'm updating position properly, but then setting it to zero again. Change to:
position = 0; /* DON'T move up */
while (1) {
punctuation = get_punctuation (line, &position);
get_word (line, &position, word);
}
New output:
renoir% a.out inp outp Copying line[0]='O' Copying line[1]='n' Copying line[2]='e' Copying line[4]='f' Copying line[5]='l' Copying line[6]='e' Copying line[7]='w' Copying line[9]='o' Copying line[10]='v' Copying line[11]='e' Copying line[12]='r' Copying line[14]='t' Copying line[15]='h' Copying line[16]='e' Copying line[18]='c' Copying line[19]='u' Copying line[20]='c' Copying line[21]='k' Copying line[22]='o' Copying line[23]='o' Copying line[24]=''' Copying line[25]='s' Copying line[27]='n' Copying line[28]='e' Copying line[29]='s' Copying line[30]='t' Segmentation Fault (core dumped)
Remove some print statements, insert others.
while (1) {
/* get punctuation before word or eol */
punctuation =
get_punctuation (line, &position);
printf ("punctuation = \"%s\"\n", punctuation);
fprintf (out, "%s", punctuation);
/* if saw eol, write newline and break */
if (line[position] == '\0') {
printf ("newline\n");
fprintf (out, "\n");
break;
}
/* get word from line; different approach */
get_word (line, &position, word);
printf ("word = \"%s\"\n", word);
/* convert word to Pig Latin; */
latinize (word, latin);
/* write out converted word; */
fprintf (out, "%s", latin);
} /* while */
renoir% a.out inp outp punctuation = "" word = "One" punctuation = "" word = "flew" punctuation = "" word = "over" punctuation = "" word = "the" punctuation = "" word = "cuckoo's" punctuation = "" word = "nest" Segmentation Fault (core dumped)
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or eol) */
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
if (*pos == start) {
return "";
}
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = start ; i < *pos; i++) {
*(punc + i) = line[start + i];
}
*(punc + i) = '\0';
return punc;
}
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or eol) */
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
if (*pos == start) {
return "";
}
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = 0 ; i < *pos - start + 1; i++) {
*(punc + i) = line[start + i];
}
*(punc + i) = '\0';
return punc;
}
renoir% a.out inp outp punctuation = "" word = "One" punctuation = " f" word = "flew" punctuation = " o" word = "over" punctuation = " t" word = "the" punctuation = " c" word = "cuckoo's" punctuation = " n" word = "nest" punctuation = ". " newline punctuation = " " newline
char *get_punctuation(char line[], int *pos) {
int start = *pos;
char *punc;
int i;
/* Find end of punctuation (letter or eol) */
while (line[*pos] != 0 &&
!is_letter (line[*pos]))
(*pos)++;
if (*pos == start) {
return "";
}
/* Allocate space for punctuation and copy it */
punc = (char *) malloc (*pos - start + 1);
for (i = 0 ; i < *pos - start; i++) {
*(punc + i) = line[start + i];
}
*(punc + i) = '\0';
return punc;
}
This works (finally).
Rules for Pig Latin:
Vowels are a e i o u ; don't worry about y.
Here's our prototype:
void latinize (char *word, char *latin);
Here's our first cut at a function:
void latinize (char *word, char *latin) {
/* Count consonants at beginning */
/* Copy remaining letters (if any) to latin */
/* If consonant count > 0,
copy consonants to latin */
/* else move 'h' to latin */
/* move "ay\0" to latin */
}void latinize (char *word, char *latin) {
int count = 0;
int dest = 0;
int i;
/* Count consonants at beginning */
while (is_consonant (word[count])) count++;
/* Copy subsequent letters (if any) to latin */
for (i = count; word[i] != '\0'; i++)
latin[dest++] = word[i];
/* If # consonants > 0, copy them to latin */
if (count > 0)
for (i = 0; i < count; i++)
latin[dest++] = word[i];
else /* move 'h' to latin */
latin[dest++] = 'h';
/* move "ay\0" to latin */
latin[dest++] = 'a';
latin[dest++] = 'y';
latin[dest] = '\0';
}
int is_consonant (char *c) {
if (!is_letter (c)) return 0;
if (strchr ("aeiouAEIOU", c)) return 0;
return 1;
}
renoir% gcc piglatin.c piglatin.c: In function `latinize': piglatin.c:109: warning: passing arg 1 of `is_consonant' makes pointer from integer without a cast piglatin.c: In function `is_consonant': piglatin.c:129: warning: passing arg 1 of `is_letter' makes integer from pointer without a cast
Change:
int is_consonant (char *c) {
if (!is_letter (c)) return 0;
if (strchr ("aeiouAEIOU", c)) return 0;
return 1;
}
To:
int is_consonant (char c) {
if (!is_letter (c)) return 0;
if (strchr ("aeiouAEIOU", c)) return 0;
return 1;
}
And also make the change in the prototype!
Output:
Onehay ewflay overhay ethay uckoo'scay estnay.
We're done, right? Almost.
One successful run does not mean you have all the bugs out. I tried the program on another file that had multiple lines of text, and discovered that the output was double-spaced. Why? Because fgets returns the newline and the zero terminator byte (I thought it discarded the newline). The solution I chose is to change
/* if saw eol,write newline andbreak */ if (line[position] == '\0') {fprintf (out, "\n");break; }
to
/* if saw eol, break */
if (line[position] == '\0') {
break;
}