Lecture notes for CSC 173, Tues. Sept. 15 -- , 2005 ------------------------------------------------- READING ASSIGNMENT: see web pointers and books on reserve. HOMEWORK ASSIGNMENT is on the web ------------------------------------------------- ======================================================================== C First: Why study C? C is the language of choice for systems programming, including most operating systems and language run-time systems (e.g. Java Virtual Machines). C tends to have fast, simple implementations, and gives the programmer better control over implementation details than do most languages. Any professional programmer needs to know C. Many of the advanced courses in the CS department use it. OK; so what does it have to do with Formal Systems? Well, nothing really. The book happens to use C, but that's an historical accident. It would probably be better from a pedagogical point of view if the book used Java or C++. We cover C in 173 because we have to cover it somewhere, and this seems to be the place where it fits best in prerequisite chain. -------------- I'm going to assume everybody knows Java, and orient my presentation toward learning C given that you know Java. First the good news: Java is derived from C and C++, and C++ is derived from C. Superficially the three languages look very similar. You'll recognize the function call syntax, the basic variable types (char, short, int, long, float, double), the various arithmetic operators, and the control structues (if, while, switch, for, ...). I think the best strategy is for me to focus on the things in C that are most different from Java, or most likely to be confusing. function calls (no methods); parameter modes no implicit this parameter; no object name-dot everything except arrays passed by value arrays passed by reference; interchangable with pointers (more on this later) program starts in main, with argc, argv arguments: int main (int argc, char *argv[]) { ... argc is the number of command-line arguments. argv[0] is the name of the program itself; argv[argc] is the last argument. ---------------- ---------------- storage classes and separate compilation (global) static (local) static extern const #include typedefs and externs in .h file matching globals in *one* .c file each I/O #include printf, scanf, puts, gets, putchar, getchar FILE *fopen (const char* filename, const char *mode) fprintf, fscanf, fputs, fgets, fputc, fputc, fwrite, fread also sprintf, sscanf types structs are like classes without methods, and with all-public fields declaration syntax read right as far as possible, then left, then out one level of parentheses (if any) and repeat parentheses appear mainly in really messy declarations involving function pointers; you probably won't see any in this class struct foo *bar[10]; bar is a 10-element array of pointers to foo structs const char *s; s is a pointer to chars that are constant v. char * const t; t is a constant pointer to chars typedef, struct names pointers v. refs; in-line allocation of structured objects This is one of the potentially most confusing differences between Java and C. In Java everything that isn't of a basic built-in type (i.e. all classes and all arrays) is dynamically allocated. A variable of a non-basic type is a *reference* to the dynamically-allocated space, so it's perfectly natural to have recursive types in Java: class listnode { mytype data; listnode next; } In C all types (including structs and arrays) are allocated in place unless you do something special to force dynamic allocation. This means recursive types don't make sense. You need an explicit POINTER type: struct listnode { mytype data; struct listnode * next; } ---------------- ---------------- example: search for element in list struct node { int datum; struct node *next; } node *find (int d, node *head) { while (head) { if (head->datum == d) /* could also say (*head).datum */ return head; head = nead->next; } return 0; } Note that C has no boolean type. Integers play the role of Booleans. Zero is false. Anything else is true. A nil pointer is coerced to an address, at which point nil is false and anything else is true. The comparison operators (==, !=, <, >, <=, >=) return 0 or 1. Beware the pitfall: if (A = B) { ... This sets A equal to B and then does what's in the braces if the copied value is non-zero. Almost never what you want. memory management (lack of garbage collection) void *malloc void free typical syntax: int *foo = (int *) malloc (10 * sizeof (int)); ... free (foo); NB: declarations must all be at the beginning of their scope; they can't be intermixed with code as in Java (or C++) arrays and pointers variable definitions (global or local) (these allocate space): int foo[100]; /* 100-element array of integers */ int *foo; /* pointer to integer (or to element of integer array) */ code: foo[10] /* works with EITHER variable definition */ /* correct with latter only if foo refers to an array with at least 11 elements (indices start at zero, as in Java) */ parameter declarations (in a function prototype [header]) (these do NOT allocate space): int foo[100] /* parameter is a pointer to a 100-elem int array */ int foo[] /* don't actually have to know the size */ int *foo /* equivalent parameter declaration */ NB: declarations of extern arrays allow missing sizes, as in parameter declarations. ---------------- ---------------- 2D v. row-pointer array layout variable definitions: int foo[10][10]; /* 10x10 array of integers, contiguous layout */ int *foo[10]; /* 10-elem array of pointer to ints. This is a DIFFERENT LAYOUT, and more like Java */ code: foo[3][4] /* works with EITHER definition */ parameter declarations: int foo[10][10] /* 10x10 array of integers, contiguous layout */ int foo[][10] /* don't have to know size of first dimension */ int foo[10][] /* ERROR: must know size of second dimension */ int *foo[10] /* row-pointer layout */ int *foo[] /* don't have to know size */ int **foo /* equivalent parameter declaration */ ------------------------------------------------------------------------ Unix the basics cd ., .. mkdir chmod 777 convention -- see ls -l less file redirection >, < >> >&, >>& >! remote access, X server "." files ls -a .login .cshrc .emacs stuff to put in your .cshrc set noclobber set filec set autoexpand set ignoreeof alias rm 'rm -i' alias mv 'mv -i' alias cp 'cp -i -p' alias ls 'ls -F' alias ll 'ls -l' alias cs 'cd \!* ; ls' alias up 'cd $cwd:h ; echo $cwd' alias ups 'cd $cwd:h ; ls' job control and command-line editing & jobs history ^P, ^N ^B, ^F, ^A, ^E ^H, ^D other useful commands grep rcs Read the man pages for ci, co, rcs, and rlog, in that order. Then see rcsdiff and rcsmerge if necessary. enscript psnup emacs tutorial info mode multiple buffers emacsclient tags etags, ctags M-., M-* stuff to put in your .emacs file (server-start) (resize-minibuffer-mode t) (setq inhibit-startup-message t) (setq require-final-newline t) (setq completion-auto-help nil) (add-hook 'temp-buffer-show-hook 'resize-temp-buffer-window) gdb (read the emacs info page!) list break, watch run, cont, next where print, display whatis ptype makefile subtleties (read the emacs info page!) tabs implicit rules: .c.o, etc. $@ The target of the current rule $* The root of the target of the current rule (e.g. 'foo' if the target is 'foo.o') $^ Names of all dependencies $? Names of all dependencies that are newer than the target. (lots of others; see the info files) variables and environment variables conventions make clean make install make depend gcc -M ---------------- Makefile example # excerpted from the makefile for the CSC 254 PL/0 compiler # see /u/cs254/plzero/src/Makefile .SUFFIXES: .o .cc CC = g++ CFLAGS = -g -Wall # compile for gdb (-g); warn about everything potentially dangerous GOAL = pl0 TOOLS = /u/cs254/plzero/tools ETAGS = etags -C CFILES = scanner.cc inpbuf.cc parser.cc \ attributes.cc semantics.cc symtab.cc codegen.cc \ driver.cc mips.cc optimize.cc OBJECTS = scanner.o inpbuf.o parser.o ... HFILES = scanner.h scantab.h inpbuf.h ... OTHERSOURCES = grammar SOURCES = $(HFILES) $(CFILES) $(OTHERSOURCES) .cc.o: $(CC) -c $(CFLAGS) $*.cc # End of header $(GOAL): $(OBJECTS) $(CC) $(CFLAGS) -o $(GOAL) $(OBJECTS) -liberty # libiberty contains the GNU extended getopt functions. tokens.h: grammar $(TOOLS)/mungegrammar < grammar scantab.cc: tables $(TOOLS)/makescan > scantab.cc ... # the following entries can be used to get lists of files of various classes, # for example, to do grep foo `make sources` sources: @echo $(SOURCES) writable: @ls -lg $(SOURCES) | egrep 'w-' objects: @echo $(OBJECTS) tags: $(CFILES) $(HFILES) $(ETAGS) $(CFILES) $(HFILES) tokens.h actions.cc actions.h clean: -rm -f $(GOAL) $(OBJECTS) depend: echo '# DO NOT EDIT THIS FILE -- it is automatically generated' \ > makefile.dep echo '' >> makefile.dep $(CC) -M $(CFILES) actions.cc >> makefile.dep include makefile.dep