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
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.
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
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).
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
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.
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
Let's use a 3 x 1 matrix_t representation from week 1
for the coordinates of a vertex.
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.
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:
Don't forget, at least to hand submit if not to develop, your code directory
needs a makefile.
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
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.
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.
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
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.
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.
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.
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:
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":
More than one production with a non-ε RHS actually do need
the 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.
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).
Our recommended grammar has rules like:
Now in the intuitive version of this grammar we had rules like
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).
Then to assign to such an identifier (e.g., to evaluate a parse-tree
node whose operator is = and whose left-hand side is $45 and whose
right hand side is some expression, you evaluate the RHS as usual,
looking up an identifier named Y by reading
This approach means you don't use the original identifier scanning
code as I did, you get to write a simple little ID-scanning sub-FA.
Last update: 7/1/11
or
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%
Preview
struct p_edge *p_edge_array[50]
Simple Graphics Data Structures
CB's code (and why not)
Assignment
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?
Struct to File
int F_to_array(face_t aface).
File to Struct
Help from GCC?
Extra Credit Ideas
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.
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
./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??
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() (!).
default:
break;
FIRST and FOLLOW -- yes
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.
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);
}
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
(1) E → T Etail
(2) Etail → T Etail
...
E → E + T,
in where the operator (+) is working on the left and right
operands in that very production.
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.
symbol_table(Y).
If there's nothing in symbol_table(Y),
that's an
"unbound identifier" error.
gt;,
you evaluate the RHS recursively as usual, and set
symbol_table(32)
to the result. If the name of the identifier is >99, that's
a syntax error the scanner could catch, or you could let the parser
catch it.
5 + sqrt(15)/cos(.677);
