banner

C Programming

Do NOT submit materials that need proprietary products. In other words, nothing from Microsoft. No .doc, NO .docx, no .rar, etc (zip and tar are OK). Make sure your code works under linux, make sure your prose submissions are .pdf. If you have trouble finding the necessary utilities, consult Google(TM), a classmate, or a TA.

I'm told you can convert from .doc to .pdf at DocToPdfSite .

Remember, ideally your submission should be so convincing there is no need for a TA to run your code (though we might). If you perform and report your work correctly the results will speak for themselves. Transcripts of sessions are effective.

Turn in (to Blackboard) your Code, Readme, and writeup.

If you don't have a favorite programming environment, you can use the gdb debugger; in fact you can use it from emacs the editor...much better than nothing. The file GDB Example might help get you started.

MAKEFILE s: Those of you with cool programming environments like Eclipse don't need makefiles, but

Thus, please learn, use, and include makefiles with your code.

You'll find some example (but not exemplary) matrix and FEV code including versions of some of the routines required and simple use of our data structures in this Source Code . Read on.

Week 1: Simple Matrix Operations. Code + Readme 100% Writeup 0%

This is a one-person exercise (no teams).

I recommend doing Week 1 in a day or two -- Try to give yourself extra time for Week Two! All the C projects and exercises are based on existing code in Source Code directory.

Formatted I/O: the formatIO subdirectory has (f)scanf and (f)printf examples. For reference or copying...

Matrix Utilities and Demo: For week 1, you can start with the code in sub-directory matrix. The job is simply to write some simple matrix-operation routines in the style of (thus extending) matrix.c , and to extend mat_test.c to test and demonstrate your matrix utilities.

As you can see in matrix.h and matrix_types.h,
a variable of type matrix_t stores a pointer to a matrix struct containing four fields: int fev-type identifier (used only in week 2), int number of rows, int number of columns, pointer to matrix data (real number matrix elements). Matrix data is a pointer to a rows-long array of pointers to cols-long vectors of doubles (this is the usual way to do it).

You could start by just copying the matrix subdirectory into your space. Run make and then execute (run) runmattest to be sure things are OK to start. (It all works on the CSDepartment's linux, btw.)

Look at the Readme. Technical details of the assignment, comments and directions, are in the .c and .h files.

Make sure you understand how mat_new and mat_free work! How many free commands does it take to return an NxN matrix to storage?

Make sure you understand the makefile if you're not using Eclipse or some other programming environment.

In a simple unix-style command interface, to run an executable (say run_test) in a directory, depending on your system, one of
run_test
or
./run_test
should work. Of course if you're using a slick programming environment there may be no such prompted command interface.

Week 2: Printing, Archiving and Recreating Pointer Structures. Code+Readme 80% Writeup 20%

This is a brand-new project description! Please do NOT hesitate to send me questions or tell me of confusions (yours or mine) errors (mine), etc... thanks, CB

This is a one-person exercise (no teams).

Preview

How do we archive a data structure or display it (for debugging, say)? How convert the archive back into a data structure with pointers? Pictures (like the one below) are fine for display but hard to turn back into the original data structure.

Our job here is to take a pointer into an arbitrarily complex data structure of structs and pointers, and create a human-readable form: For every struct we would like to see what type it is, what its unique ID is within its type, what its non-pointer fields contain, and what other structs it points to.

"Printing out" a struct is one idea -- we'd like a human- and machine-readable result; numbers and strings, basically. If the fields are printable things like numbers, matrices, strings..., it's easy. But at best a pointer looks like a big random integer (a memory address), and isn't really informative about what it points to.

My trick is to put all the structs of each type into an array of pointers, and replace every pointer in every struct in the data structure by an array index. Printing out the structs in these arrays gives our archival, readable, reconstructable representation. It replaces big random pointer values with small integers that act as array indices, and thus "pointers" become printable, and human- and machine-readable too.

That's the assignment. I used an array of pointers for every type of struct -- also an array of pointers to a new version of each struct, called here a "p-struct", which is printable, in that every pointer is replaced by an index integer. We don't need to remember explicitly which array it's an index of, since the type of each pointer in a struct is known to us, the programmers: e.g. a_p_face -> next_edge would be an integer in a face p-struct indexing into some array of printable edge structs, maybe declared
struct p_edge *p_edge_array[50]

I can't see a nice way to avoid the complete customization of all the code to the particular structs involved. Something ugly that avoids typed pointers (declare them all void?) might work, but could be hard to debug. Good news is that several of the routines are similar in structure. In the following, "we" actually means "I". I'm fairly sure my approach is not the only way to go, but 'it works for me'. Maybe you have a nother, better way to go about the job -- go for it!

For convenience and debugging ease, we'll allow each struct to have two extra ID fields: a type code and a serial number. Each struct type gets a unique type code, and serial numbers run from 0 upwards (just like array indices...heh heh).

Here are some pictures of a data structure of two record types (A, B) representing its original form with pointers and its printable form with indices:

Printing the fields of the p_struct arrays (to disk or paper) saves all the needed information.

Not only that, we can invert the process! Given the arrays, we can go through and reconstruct the (non-printable) data structure by creating (original, non-printable, pointer-ful) structs and filling in each field with its contents (for numbers, strings, matrices...) or with a pointer to the struct at the location given by the field's "printable pointer", or array index. Then we can free the arrays, and we're back where we started.

Simple Graphics Data Structures

In a toy 3-D graphics system we represent polyhedra with three types of primitive elements: faces, edges, and vertex points (FEV). Type numbers are #defined in FEV.h

  1. a POLYHEDRON is simply a circular list of FACEs. That is, it's a pointer to the "first" FACE on such a circular list.
  2. A FACE has:
  3. An EDGE has:
  4. a VERTEX has:

Let's use a 3 x 1 matrix_t representation from week 1 for the coordinates of a vertex.

CB's code (and why not)

The algorithms and representations I describe for struct_to_file, file_to_struct are just the first that occurred to me. There are doubtless other and maybe better ways. Also I'm not anyone's model programmer -- au contraire!

Maybe for the worse, the directory below makes. That preserves all the routines hacked up and pasted together during development, which stopped as soon as it ran once. So you may well see structure that I'm sure can be cleaned up, tossed out, rethought, etc. Don't slavishly follow what I did, be critical. If you re-invent or approve of my methods, I'll take it as a compliment. Meliora!

So with sincere warnings and disclaimers, un-guaranteed (and necessarily partial, un-indented, un-commented, but seemingly working in their original) C structure definitions, code, and makefile related to this problem are in the Source Code Directory: the README explains things pretty well.

struct_file_format describes my archival, printable, human-readable representation of an FEV polyhedron structure: what's the "head" face pointed to by the "polyhedron" pointer (which is of type face_t), then for each of the FEV types, the type code followed by how many are in the upcoming list, followed by the contents of each struct, with array indices instead of pointers. Order of these lists is irrelevant. ps_file.data is an example.

Assignment

As a top-level demonstration, you should write a driver program like (or just tweak and use) put_get_put.c. It creates a tetrahedron (you could do something else of course), writes it out, reads it and reconstructs it, and then writes it out again. That pretty much guarantees things are working.

I'm passing on my directory of a seeming-working solution, minus all the guts of the two interesting bits, called struct_to_file and file_to_struct.

You may assume an upper limit on the number of instances of the structs, (say 50) so you can pre-allocate your arrays of pointers. This makes the job a bit easier.

Part credit for doing either half (struct_to_file or file_to_struct).

Tactics:
First and always, I'd recommend that you make some simple test cases rather than do all your debugging with your final structure. Can you save and restore some 'structure' that is only one record (like a single vertex)? How about a simple linked list, or maybe two vertices with two oppositely- directed edges connecting them?

Don't forget, at least to hand submit if not to develop, your code directory needs a makefile.

Struct to File

NOTA BENE: I'm telling you what I did, but you're not advised or expected to do things my way. I'm hoping what's left of the code in the hollowed-out .c files will help.

I'm leaving a gutted version of my struct_to_file.c. My idea here is: for each type of struct, write a possibly recursive routine (call it XXX for now) that creates and fills in a p_struct for that type, puts a pointer to it into the array of pointers for that type of p_struct at the [serial number] location in the array, and returns the serial number.

For this assignment, we need three arrays: for p_faces, p_edges, and p_vertices. My main program takes a pointer to a face, fills up all three arrays via one statement (calling the XXX routine for a face) which creates the p_struct for that face (and all the others by the depth-first search process), and works through the arrays printing everything to a file according to the archival file format. It returns nothing.

So generally, in struct_to_file my XXXs have declarations like
int F_to_array(face_t aface).

For each pointer in the input struct, the routine calls the proper YYY: the p_struct-making routine for that struct. This depth-first pointer-following from a face will find all the structs in a well-formed polyhedron. (It would just find the edges and vertices around a face if given an edge --- see why?). The serial number returned is of course the index of the newly_constructed p_struct in its array, which is what XXX needs for the int printable-pointer field that caused it to call YYY in the first place. Along the way I count how many of each type I find.

Assume that FEV structs don't share matrix data, so there's no need to give arrays individual names. Just treat them as atomic parts of the F,E,V structs to be printed out like any other field.

File to Struct

I'm leaving a gutted version of my file_to_struct.c Our goal is to read the description off disk and recreate the data structure with pointers.

I used a two-pass non-recursive approach, first creating an array of empty structs from the file of pstructs, then re-reading the file to fill in the fields (values and pointers).

First pass: read in the representation and construct the structs and their non-pointer fields (strings, numbers, matrices,...). Pass two: rewind the file and create the pointers in the new structs by producing actual &-type pointers to the proper members of the newly-created struct arrays.

Help from GCC?

I've found the gdb debugger very helpful for tracking down the cause of segmentation faults. The mudflap pointer-debugging option for the gcc C compiler could be of some help: Mudflap Wiki

Extra Credit Ideas

I don't think we need either the type nor the serial numbers to be explicit in the structs. Doing the job without them would be rather cool.

Make up a more complicated data structure than the toy FEV graphics application and substitute that for this assignment.

As usual, explain any extra or innovative things you do in your writeup.

Week 3-4: Scan, Parse, Evaluate. Code+Readme 80%, Writeup 20%

This project may be done singly or as a two-person team. There are ad- and disad- vantages both ways. In one good team approach, for example, the team members would have complementary talents. In one bad approach, one member skives off while the other gets stuck with all the work.

Background

In 2006, this assignment looked like this (a scanner) and this (a parser) , and in 2007 we just did the parser half. This year is related but simpler.

The concepts you need to know are in the readings (the Scott chapter especially -- see below) and in the lectures, but I know it's not easy to know what to pay attention to, how to get started, etc. So I really appreciate this Project Guide , by Karl Stratos, a 173 alum from 2009. You should check it out and see if it helps you.

You may find it helpful too to look over the above old versions of the assignments, get the gist of how the project is organized, helpful hints here and there, etc. But don't spend too much time: our domain is totally different, so (thank goodness) the old details are 97% irrelevant (but useful to see what you get into with a real language like Java !).

The code provided in 2006 will still form the basis of your work. Download it into a directory of your choice from Here: (scanner and parser code) .

If you get errors, make sure you have all the files in one directory and before you type make at top level, type make depend. The depend target creates a file that could have been out of date, and is used in some arcane way by the make utility. Now it's not necessary that this old code to do a different scan-parse job actually "makes" successfully but it does, which at least tells you you're starting with working code.

Scott's chapter pp 43-49, 54-57, 61-69 (on e-Reserves) is recommended reading.

Of course you should check out the "sample projects" for this module, which you'll find back at The Main Projects Page.

Minimal Assignment: Scan, Parse, Evaluate Arithmetic Expressions

Write a finite-state machine scanner, recursive descent parser, and evaluator for a list of arithmetic expressions separated by the semicolon(;). Its output (with input from a file) and output (==) could look something like this when it runs:
((4+ 7) -3.00)/4;
==2.000

5;
==5.000

4 +
(25/5)
;
==9.000

The scanner and parser in the 2006 code do more than you need, but in the right manner and in exemplary style. I recommend:

Here's my parse tree for an expression with an identifier (ID). For this example I just used the original ID scanning code, and my parse tree node had a string field to hold ID names. Practically, we can super-simplify things: details in "Extras" below. The indentation shows the depth of nodes.

./cbparse < data
 starting parse...
5555.5+(4444.444*(2/My_Identifier))/3.33333;
 name, type, id, val, op: expr 0  0.000000, 4
  name, type, id, val, op: term 1  0.000000, 4
   name, type, id, val, op: a NUM 6  5555.500000, 4
  name, type, id, val, op: termtail 2  0.000000, 2
   name, type, id, val, op: term 1  0.000000, 4
    name, type, id, val, op: expr 0  0.000000, 4
     name, type, id, val, op: term 1  0.000000, 4
      name, type, id, val, op: a NUM 6  4444.444000, 4
      name, type, id, val, op: factortail 4  0.000000, 0
       name, type, id, val, op: expr 0  0.000000, 4
        name, type, id, val, op: term 1  0.000000, 4
         name, type, id, val, op: a NUM 6  2.000000, 4
         name, type, id, val, op: factortail 4  0.000000, 1
          name, type, id, val, op: an ID 5 My_Identifier 0.000000, 4
    name, type, id, val, op: factortail 4  0.000000, 1
     name, type, id, val, op: a NUM 6  3.333330, 4;
 name, type, id, val, op: expr 0  0.000000, 4
  name, type, id, val, op: term 1  0.000000, 4
   name, type, id, val, op: factor 3  0.000000, 4
 parse successful

FIRST and FOLLOW -- not??

It is sometimes possible to avoid using FIRST and FOLLOW in parsing code.

Consider the program for non-terminal A() If there is only one non-epsilon production in the grammar with A as a left-hand side, say:
A → B C D
One could figure out the FIRST and FOLLOW for B, C and D and explicitly build in all the cases in A's program. But why bother? Why not do this?:
A() B(); C(); D(); end Not using FIRST: If B(),C(), or D() doesn't like what it sees, let it complain. Sure, A() could have looked and predicted B() would object, but not checking just costs some more recursion.
Not using FOLLOW: Now consider adding the production A → ε to the grammar, so there are now two productions with A as LHS, one being the ε production. Nothing has to change in A() (!).

If BCD is matched, A() is happy, and if not A may have produced ε -- that's enough excuse for A() to declare success and return upward. What's coming up is either grammatical or not. If it's not, sometime later the parser will fail to match a token: that's where it finds the error.

Sure, FOLLOW(A) would tell us that A "really" has produced ε, but this version of A() just assumes it has and kicks any possible problems upstairs.

If a production really needs a switch statement, we need a case for the ε production, but it can always be "accept and don't match anything": default: break;

FIRST and FOLLOW -- yes

More than one production with a non-ε RHS actually do need the FIRST sets: A → B A → D We need to know whether to call B or D, so we need their FIRST sets. Also, if we have something like B → aC D → aD We would not be LL(1): two productions for A have the same FIRST sets.

Last: Our expression grammar is so simple the FIRST sets can be figured out easily "by inspection": + and - are the cases in ETAIL, * and / are the cases in TTAIL, and ( and <number> are the cases in FACTOR.

Making a parse tree:

Using the facts above, here a couple of CB's functions used by the parser: first, a program for a nonterminal with a single production. It must produce a parse-tree node, of course. static ptnode_t parse_expr() { ptnode_t res; % making this node ptnode_t ter; % which points to these ptnode_t tertail; % two nodes /* printf("\n parse_expr\n"); */ ter =parse_term(); % each program returns a parse-tree node tertail = parse_term_tail(); res = make_ptnode("expr", EXPR,"", 0.0,NONE,ter, tertail, NULL); return(res); }

Next, a version of the FACTOR() program; Two cases are tokens that aren't terminal characters, one is an identifier (its value is a string of chars in the input line) and and one a number (string of digit chars in input line). These non-terminals are dealt with in the original scanner code (e.g. with got_dot(), got_dig(), got_ft_dot()), which CB did not change from the original. Again, this code makes a parse-tree node (with lots of debugging info along the way). It also shows one way to evaluate a number in the input and put the resulting float in the parse tree, and how to copy a string (here, an identifier name). static ptnode_t parse_factor() { ptnode_t res; char * idcopy; char * idloc; location_t loc; double anum; printf("\n parse_factor\n"); switch (tok.tc) { case T_LPAREN: match(T_LPAREN); res = parse_expr(); match(T_RPAREN); break; case T_IDENTIFIER: /* printf("\n ID found\n"); */ loc = tok.location; /* cbprint_location(&tok); print_token(&tok); */ idloc = (char *) &(loc.line->data[loc.column]); idcopy = strndup(idloc,tok.length); /*printf("\n ID copied to: %s\n", idcopy);*/ match(T_IDENTIFIER); res = make_ptnode("an ID", IDENTIFIER, idcopy, 0.0, NONE, NULL, NULL, N ULL); break; /* accept */ case T_NUM: /* printf("\n NUM found\n"); */ loc = tok.location; /* cbprint_location(&tok); print_token(&tok); */ idloc = (char *) &(loc.line->data[loc.column]); idcopy = strndup(idloc,tok.length); sscanf(idcopy, "%lf", &anum); /*printf("\n NUM scanned as: %f\n", anum);*/ res = make_ptnode("a NUM", NUM, "", anum, NONE, NULL, NULL, NULL); match(T_NUM); break; } return(res); }

Evaluation

Our recommended grammar has rules like: (1) E → T Etail (2) Etail → T Etail ...

Now in the intuitive version of this grammar we had rules like E → E + T, in where the operator (+) is working on the left and right operands in that very production.

We rendered the original grammar less intuitive by turning it into LL. Now in the LL grammar, say we are evaluating the parse tree node resulting from production (1). The left argument comes from the value field of T, but both the right argument AND the operation that needs to be done come from the right argument Etail. So the operation does not live in the node that receives the value of performing the operation, it lives one level down. Simply one more field to access (and then switch or if on!) when evaluating the node for (1).

Test Data

Mr. Sean Tang in 2009 proposed this test input , which you may want to use to test your program on the minimal requirement for this assignment (no guarantee that this is all the cases you should cover...in the real world your job is to anticipate the crazy things users (naive, sophisticated, malign) come up with.

Extras

Given you've done the minimal, these additions should go quickly, especially if you do a little forward planning and anticipate them.
---
This page is maintained by Deer Boy

Last update: 7/1/11