#include <stdio.h>
#include <string.h> //for strcmp(), strlen(), strcpy()
#include <stdlib.h> //for malloc(), free()
#include <ctype.h> //for isalpha(), isalnum(), isdigit()
//compile with: gcc -Wall -Wextra cc-c.c -o cc-c
//run with: ./cc-c < some-file.c (or type input, end with Ctrl-D)
//
//try: ./cc-c <<'EOF'
// #define MAXLINE 1000
// #define IN 1 // inside a word
// #define MSG "hello, world\n"
// char line[MAXLINE];
// int INDEX = 0x1IN;
// if (state == IN) printf(MSG);
// printf("IN stays IN in a string\n"); // and IN here too
// EOF
//K&R2 exercise 6-6: implement a simple version of the #define processor
//(i.e., no arguments) suitable for use with C programs, based on the
//routines of this section. You may also find getch and ungetch helpful.
//
//The table half is already done: install() and lookup() from 6.6 ARE a
//#define table -- name in, replacement text out. What's new is the
//scanner around it, which reads C source on stdin and writes it to
//stdout with two changes:
//
// 1. a line #define NAME text is swallowed and (NAME, text) installed
// 2. every identifier that matches an installed NAME is replaced
//
//The hard part is knowing what NOT to touch. Replacing every "IN" in
//the input would be a text editor's search-and-replace; a preprocessor
//works on TOKENS, so it must step over things that only look like names:
//
// "IN a string" string literal -> copied verbatim
// 'I' char constant -> copied verbatim
// // IN, and the block-comment kind -> copied verbatim
// INDEX a longer identifier -> not IN, read it whole
// 0x1IN a number -> digits+letters read whole
//
//That's why main is a dispatcher on the FIRST character of each token:
//letter/_ starts an identifier, digit starts a number, quote starts a
//literal, '/' MIGHT start a comment. Each branch reads its whole token
//before the loop looks at another character.
//
//Where getch/ungetch earn their place: a scanner often only knows a
//token has ended after reading one character too many. "IN;" -- the
//';' is what says IN is over, but ';' belongs to the next token. So
//getident reads it and ungetch()s it back. Same with '/': it takes the
//NEXT character to decide between "/*", "//" and plain division, and if
//it was just division, that next character goes back.
//
//Simplifications vs. the real cpp: no rescanning of replacement text
//(#define A B, #define B 2 turns A into B, not 2), no line continuation
//with backslash, no #undef, and other directives (#include, #if...) are
//just passed through.
#define HASHSIZE 101
#define MAXWORD 100 //longest identifier
#define MAXDEFN 1000 //longest replacement text
#define BUFSIZE 100 //ungetch buffer
struct nlist { //table entry:
struct nlist *next; //next entry in chain
char *name; //defined name
char *defn; //replacement text
};
static struct nlist *hashtab[HASHSIZE]; //pointer table, all NULL
unsigned hash(char *);
struct nlist *lookup(char *);
struct nlist *install(char *, char *);
char *mystrdup(char *);
int getident(char *, int);
void directive(void);
void copyquoted(int);
void copyslash(void);
int getch(void);
void ungetch(int);
int main(void)
{
int c, d;
int bol = 1; //at beginning of line (only blanks so far)?
char word[MAXWORD];
struct nlist *np;
while ((c = getch()) != EOF) {
if (c == '#' && bol)
directive(); //# only counts at start of line
else if (isalpha(c) || c == '_') {
ungetch(c);
getident(word, MAXWORD);
if ((np = lookup(word)) != NULL)
fputs(np->defn, stdout); //the substitution itself
else
fputs(word, stdout);
} else if (isdigit(c)) { //0x1F, 10L, 1e5: one token
putchar(c);
while (isalnum(d = getch()) || d == '_' || d == '.')
putchar(d);
ungetch(d);
} else if (c == '"' || c == '\'')
copyquoted(c);
else if (c == '/')
copyslash();
else
putchar(c);
if (c == '\n')
bol = 1;
else if (c != ' ' && c != '\t')
bol = 0;
}
return 0;
}
//directive: called just after a '#' at start of line; if it's
// #define NAME text, install it, else pass the '#' line on
void directive(void)
{
int c, i;
char word[MAXWORD], name[MAXWORD], defn[MAXDEFN];
while ((c = getch()) == ' ' || c == '\t') //"# define" is legal
;
ungetch(c);
getident(word, MAXWORD);
if (strcmp(word, "define") != 0) { //#include etc.: echo it,
printf("#%s", word); //main copies the rest
return;
}
while ((c = getch()) == ' ' || c == '\t')
;
ungetch(c);
if (getident(name, MAXWORD) == 0) {
fprintf(stderr, "error: #define without a name\n");
return;
}
while ((c = getch()) == ' ' || c == '\t')
;
//replacement text = rest of the line, but stop before a comment so
//"#define IN 1 // inside" defines IN as "1", not "1 // inside"
for (i = 0; c != '\n' && c != EOF && i < MAXDEFN - 1; c = getch()) {
if (c == '/') {
int next = getch();
//IDIOM: two-character lookahead -- ungetch is a stack, so
//push back in REVERSE order: next now, '/' after the loop,
//and getch hands back '/' first, then next
ungetch(next);
if (next == '/' || next == '*')
break;
}
defn[i++] = c;
}
ungetch(c); //the '\n' or '/' is main's to copy, so the line
//count of the output matches the input
while (i > 0 && (defn[i-1] == ' ' || defn[i-1] == '\t'))
i--; //trim trailing blanks
defn[i] = '\0';
install(name, defn);
}
//getident: read an identifier (letters, digits, _) into w; return
// its length, 0 if the next char can't start one
int getident(char *w, int lim)
{
int c;
char *p = w;
c = getch();
if (isalpha(c) || c == '_')
for ( ; --lim > 0 && (isalnum(c) || c == '_'); c = getch())
*p++ = c;
ungetch(c); //read one too many: give it back
*p = '\0';
return p - w;
}
//copyquoted: copy a string or char literal opened by quote q;
// a backslash protects the next char, so "a\"b" is one string
void copyquoted(int q)
{
int c;
putchar(q);
while ((c = getch()) != EOF) {
if (c == '\n') { //unterminated: stop at end of line
ungetch(c);
return;
}
putchar(c);
if (c == '\\') {
if ((c = getch()) != EOF)
putchar(c);
} else if (c == q)
return;
}
}
//copyslash: called after a '/'; copy a comment through untouched, or
// if it was just a division sign, give the lookahead back
void copyslash(void)
{
int c, prev;
c = getch();
if (c == '/') { //line comment: up to the '\n'
putchar('/');
putchar('/');
while ((c = getch()) != '\n' && c != EOF)
putchar(c);
ungetch(c);
} else if (c == '*') { //block comment: up to star-slash
putchar('/');
putchar('*');
for (prev = 0; (c = getch()) != EOF; prev = c) {
putchar(c);
if (prev == '*' && c == '/')
return;
}
} else { //plain division
putchar('/');
ungetch(c);
}
}
//hash: form hash value for string s
unsigned hash(char *s)
{
unsigned hashval;
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
}
//lookup: look for s in hashtab
struct nlist *lookup(char *s)
{
struct nlist *np;
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np; //found
return NULL; //not found
}
//install: put (name, defn) in hashtab
struct nlist *install(char *name, char *defn)
{
struct nlist *np;
unsigned hashval;
if ((np = lookup(name)) == NULL) { //not found
np = (struct nlist *) malloc(sizeof(*np));
if (np == NULL || (np->name = mystrdup(name)) == NULL)
return NULL;
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
} else //already there
free((void *) np->defn); //free previous defn
if ((np->defn = mystrdup(defn)) == NULL)
return NULL;
return np;
}
//mystrdup: make a duplicate of s (the book's strdup)
char *mystrdup(char *s)
{
char *p;
p = (char *) malloc(strlen(s) + 1); //+1 for '\0'
if (p != NULL)
strcpy(p, s);
return p;
}
int buf[BUFSIZE]; //int, not char: EOF can be pushed back (ex 4-9)
int bufp = 0; //next free position in buf
int getch(void) //get a (possibly pushed back) character
{
return (bufp > 0) ? buf[--bufp] : getchar();
}
void ungetch(int c) //push character back on input
{
if (bufp >= BUFSIZE)
printf("ungetch: too many characters\n");
else
buf[bufp++] = c;
}
win@DESKTOP-MEIH88T:~/webdev-projects$ ./cc-c <<'EOF'
#define MAXLINE 1000
#define IN 1 // inside a word
#define MSG "hello, world\n"
char line[MAXLINE];
int INDEX = 0x1IN;
if (state == IN) printf(MSG);
printf("IN stays IN in a string\n"); // and IN here too
EOF
// inside a word
char line[1000];
int INDEX = 0x1IN;
if (state == 1) printf("hello, world\n");
printf("IN stays IN in a string\n"); // and IN here too
The active block in cc-c.c is K&R exercise 6-6 (lines 1–295): a small #define processor. Everything below line 297 is older exercises inside /* */. I compiled it and ran the sample input from the header. Output:
← line 1: blank (#define MAXLINE swallowed, its '\n' kept)
// inside a word ← line 2: #define IN swallowed, comment kept
← line 3: #define MSG swallowed
char line[1000];
int INDEX = 0x1IN;
if (state == 1) printf("hello, world\n");
printf("IN stays IN in a string\n"); // and IN here too
Keep that output in mind while reading. Each part of the code explains one of those lines.
1. Headers and constants (lines 1–59)
stdio.h: getchar, putchar, fputs, printf.
string.h: strcmp to compare names, strlen/strcpy in mystrdup.
stdlib.h: malloc/free for the table entries.
ctype.h: isalpha, isalnum, isdigit. These are the character-class tests the scanner uses to decide what kind of token is starting.
The four #defines set sizes:
HASHSIZE 101: number of hash buckets. It's prime, which spreads % HASHSIZE results more evenly.
MAXWORD: longest identifier.
MAXDEFN: longest replacement text.
BUFSIZE: depth of the pushback stack.
This program is itself a #define processor, so you could feed it its own source.
2. The table (lines 61–78)
struct nlist {
struct nlist *next;
char *name;
char *defn;
};
One entry is one (name, defn) pair plus a next link. Names that hash to the same bucket get chained into a linked list. The struct can contain a pointer to its own type (struct nlist *next) but not a whole struct nlist, because that would make the struct infinitely large. A pointer has a fixed size, so self-reference through a pointer is fine.
static struct nlist *hashtab[HASHSIZE];
This is an array of 101 pointers, each one the head of a chain. Two details:
static at file scope means the name isn't visible to other source files (internal linkage). It does not mean "stored statically" in this position, because every file-scope variable already is.
Because it's static storage, it's zero-initialized, so every pointer starts as NULL (empty chain). That's the "all NULL" in the comment. A local array would start with garbage instead.
Lines 69–78 are prototypes. main calls functions that are defined later in the file, and the compiler needs their types before the first call.
3. main: the dispatcher (lines 80–114)
int c, d;
int bol = 1;
char word[MAXWORD];
struct nlist *np;
c and d are int, not char, because getch can return EOF (−1), which isn't a valid char value. bol means "beginning of line". It starts at 1 because the first character of the file is at the start of a line.
while ((c = getch()) != EOF) {
This is the standard K&R loop: read, assign, test, all in one expression. The parentheses around c = getch() are required because != binds tighter than =.
The loop body is an if/else if chain that decides based on the first character of a token:
# at the start of a line (L88):
if (c == '#' && bol)
directive();
# only starts a directive at the beginning of a line (ignoring leading blanks). A # anywhere else, such as inside an expression or string, falls through to the other branches.
Identifier (L90–96):
else if (isalpha(c) || c == '_') {
ungetch(c);
getident(word, MAXWORD);
main has already consumed the first letter. Instead of passing it along separately, it pushes the letter back with ungetch so that getident can read the whole identifier from the start. That keeps getident simple, since it always starts from a clean position.
if ((np = lookup(word)) != NULL)
fputs(np->defn, stdout);
else
fputs(word, stdout);
This is the substitution itself. If the name is in the table, the replacement is written out; otherwise the word is copied unchanged. fputs is used instead of printf because it writes the string literally. If the replacement text contained a %, printf(np->defn) would treat it as a format directive, which is a bug.
Why INDEX isn't touched: getident reads the whole token INDEX, lookup("INDEX") fails, and it's copied unchanged. The code never searches for IN inside a longer word.
Number (L97–101):
} else if (isdigit(c)) {
putchar(c);
while (isalnum(d = getch()) || d == '_' || d == '.')
putchar(d);
ungetch(d);
A number begins with a digit, but it can continue with letters (0x1F, 10L, 1e5) or a . (3.14). The loop copies the whole run. That's why 0x1IN passes through: the IN inside it is never treated as a separate token. When the loop stops, d is the first character that isn't part of the number. It belongs to whatever comes next, so it's pushed back. This "read one too many, give it back" pattern appears throughout the program.
(This is looser than C's real rules. For example, 1e+5 would break at the +. It doesn't matter here, because the +5 part contains no identifiers.)
Quote (L102–103): " or ' hands off to copyquoted, which copies the literal verbatim. That's why "IN stays IN in a string" is unchanged.
Slash (L104–105): / might start a comment, so it goes to copyslash, which makes the decision.
Anything else (L106–107): spaces, operators, punctuation, and newlines are copied unchanged.
Updating bol (L109–112):
if (c == '\n')
bol = 1;
else if (c != ' ' && c != '\t')
bol = 0;
This runs after every token, using its first character c. A newline sets bol. A blank leaves it as it was, so #define still counts as start-of-line. Anything else clears it. This logic depends on directive pushing the \n back (see below): on the next iteration main reads that \n, and this code sets bol = 1 again for the following line.
4. directive (lines 119–162)
This is called just after main has consumed the #.
while ((c = getch()) == ' ' || c == '\t')
;
ungetch(c);
getident(word, MAXWORD);
Skip blanks (# define is legal C), push back the first non-blank character, then read the directive name. The empty ; is the loop body. All the work happens inside the condition.
if (strcmp(word, "define") != 0) {
printf("#%s", word);
return;
}
For anything that isn't define (#include, #if, …), print # and the word back out and return. main then copies the rest of the line as ordinary text. strcmp returns 0 when the strings are equal, so != 0 means "not define". (A side effect: # include comes out as #include, with the spaces removed.)
while ((c = getch()) == ' ' || c == '\t')
;
ungetch(c);
if (getident(name, MAXWORD) == 0) {
fprintf(stderr, "error: #define without a name\n");
return;
}
Skip blanks, then read the macro's name. getident returns the length it read. A length of 0 means the next character can't start an identifier (#define 5 x, or #define followed by end of line). The error goes to stderr, so it doesn't mix with the program's real output on stdout.
while ((c = getch()) == ' ' || c == '\t')
;
Skip the blanks between the name and the replacement text. This time there's no ungetch: c now holds the first character of the replacement text, and the for loop below starts from c as it is.
Collecting the replacement text (L145–155):
for (i = 0; c != '\n' && c != EOF && i < MAXDEFN - 1; c = getch()) {
Collect until end of line, end of file, or the buffer is full. MAXDEFN - 1 leaves one slot for the '\0'. The loop's "step" part is c = getch(), so the read happens at the bottom of each iteration, and the first c was already set before the loop started.
if (c == '/') {
int next = getch();
ungetch(next);
if (next == '/' || next == '*')
break;
}
defn[i++] = c;
This handles #define IN 1 // inside a word: the definition should be 1, not 1 // inside a word. Seeing a / alone isn't enough to tell, so it reads one more character and pushes it back right away.
There are two cases:
Plain division (#define HALF x/2): next was pushed back, '/' goes into defn, the loop step calls getch() and gets next back. Nothing is lost.
Comment: break with c == '/' and next already pushed back. Then L156 does ungetch(c). The pushback buffer is a stack, so the order is now next, then '/' on top. getch returns '/' first, then next, which is the original order. The code comment calls this out: to push back two characters, push them in reverse order.
ungetch(c);
Whether the loop stopped at \n or at a comment's /, that character belongs to main, so it's pushed back. main then outputs the comment and the newline. That's why output line 2 is // inside a word, and why the output has the same number of lines as the input: every swallowed #define still leaves its newline. Real cpp keeps line numbers aligned for the same reason, so compiler error messages point to the right lines.
while (i > 0 && (defn[i-1] == ' ' || defn[i-1] == '\t'))
i--;
defn[i] = '\0';
install(name, defn);
The four spaces before // went into defn as "1 ". This trims them by moving i back while the last character is a blank. The i > 0 check comes first so that defn[-1] is never read; && evaluates left to right and stops at the first false operand. Then it terminates the string and installs the pair.
(The spaces that were in front of // were consumed here and then trimmed, which is why output line 2 begins at // with no leading spaces.)
5. getident (lines 167–178)
c = getch();
if (isalpha(c) || c == '_')
for ( ; --lim > 0 && (isalnum(c) || c == '_'); c = getch())
*p++ = c;
ungetch(c);
*p = '\0';
return p - w;
The first character must be a letter or _. Later characters can also be digits, which is why isalpha is the first test and isalnum the loop test. That's C's identifier rule.
--lim > 0 decrements before testing, so a buffer of 100 holds at most 99 characters plus '\0'.
*p++ = c stores at p and then advances p. Postfix ++ applies to p, not to *p.
ungetch(c) always runs. Either the loop stopped on a non-identifier character, or the first if failed. In both cases c belongs to someone else.
p - w is pointer subtraction: the number of chars between the two pointers, which is the identifier's length. directive uses a return of 0 to detect a missing name.
One edge case: an identifier longer than 99 characters gets cut off. The rest stays in the input and main reads it as a separate identifier. That's acceptable for an exercise.
6. copyquoted (lines 183–199)
putchar(q);
while ((c = getch()) != EOF) {
if (c == '\n') { ungetch(c); return; }
putchar(c);
if (c == '\\') {
if ((c = getch()) != EOF)
putchar(c);
} else if (c == q)
return;
}
q is whichever quote opened the literal. Passing it in means one function handles both "..." and '...', and the literal ends only at the same kind of quote. So "it's" doesn't end at the apostrophe.
Backslash: print it, then print the next character unconditionally, without checking it. That's how "a\"b" stays one string: the \" is consumed as a pair, so the " never reaches the c == q test. '\'' works the same way. The != EOF check stops a backslash at end of file from printing EOF as a character.
Newline: C string literals can't span lines, so a newline means the literal was never closed (a typo in the input). The function stops and pushes the \n back for main, so a missing quote can't make the rest of the file be treated as one string.
7. copyslash (lines 204–227)
main has consumed the /. One more character decides what it is:
//: print both slashes, copy up to the newline, and push the newline back for main. The newline should go through main's bol logic like every other one.
/*: print the opener, then copy characters while tracking prev, until prev == '*' && c == '/'. In the for loop, prev = c is the step, so it runs after the body. Inside the body, prev is still the character before c. prev starts at 0, not *, so /*/ doesn't count as closed. The * from the opener was never assigned to prev. The closing */ is printed because putchar(c) comes before the test.
Plain division: print the / and push the lookahead back.
This is where // and IN here too stays unchanged: comment text goes straight from getch to putchar and never reaches getident or lookup.
8. hash (lines 230–236)
for (hashval = 0; *s != '\0'; s++)
hashval = *s + 31 * hashval;
return hashval % HASHSIZE;
This is K&R's string hash. Each character's value is added to 31 times the running total, which works like reading the string as a base-31 number, so "ab" and "ba" hash differently. unsigned matters here: long names overflow, and unsigned overflow is defined to wrap around (arithmetic modulo 2ⁿ), while signed overflow is undefined behavior. % HASHSIZE maps the result to a bucket index from 0 to 100.
9. lookup (lines 240–247)
for (np = hashtab[hash(s)]; np != NULL; np = np->next)
if (strcmp(s, np->name) == 0)
return np;
return NULL;
This is the standard way to walk a linked list in a for loop: start at the bucket's head, stop at NULL, and follow next each step. A matching hash only picks the bucket; strcmp checks for the actual name, because different names can share a bucket.
10. install (lines 251–267)
if ((np = lookup(name)) == NULL) {
np = (struct nlist *) malloc(sizeof(*np));
For a new name, allocate a node. sizeof(*np) is the size of the struct np points to. It's evaluated at compile time and never dereferences anything, so using it while np is uninitialized is safe. Writing it this way rather than sizeof(struct nlist) means it stays correct if np's type changes. The cast is K&R style; in modern C, void * converts implicitly.
if (np == NULL || (np->name = mystrdup(name)) == NULL)
return NULL;
Short-circuit ||: if malloc failed, the right side never runs, so np->name is never written through a null pointer. (If mystrdup fails, the node leaks. That's the book's code, and it's fine for an exercise.)
hashval = hash(name);
np->next = hashtab[hashval];
hashtab[hashval] = np;
Insert at the head of the chain: the new node points to the old head, then becomes the head. The order matters: swap the two lines and the rest of the chain is lost.
} else
free((void *) np->defn);
if ((np->defn = mystrdup(defn)) == NULL)
return NULL;
return np;
If the name already exists, it's being redefined. Free the old text first, or it leaks. Either way, store a fresh copy of the new definition.
Why copy at all? directive's name and defn are local arrays that are reused on every call. If the table stored those pointers, every entry would point at the same buffers, and the buffers no longer exist once directive returns. mystrdup gives each entry its own heap copy, which lasts for the rest of the program.
11. mystrdup (lines 271–278)
malloc(strlen(s) + 1) allocates one byte more than the visible length because strlen doesn't count the '\0' and strcpy copies it. If malloc fails, p is NULL and is returned as is. It's renamed from the book's strdup because POSIX's <string.h> already declares a strdup, and defining your own with the same name would conflict.
12. getch / ungetch (lines 281–295)
int buf[BUFSIZE];
int bufp = 0;
int getch(void) { return (bufp > 0) ? buf[--bufp] : getchar(); }
void ungetch(int c) { ... buf[bufp++] = c; }
This is a stack layered over getchar. getch returns from the stack if it isn't empty, and otherwise reads real input. bufp is the next free slot. Push is buf[bufp++] = c (store, then advance). Pop is buf[--bufp] (step back, then read). The two forms mirror each other.
buf holds int, not char, so that EOF can be pushed back. Exercise 4-9 was about exactly this, and it matters here: getident or the number loop can hit end of file and ungetch(EOF). The next getch in main has to see EOF again to exit the loop. In a char array, −1 might be stored as 255 and the loop would never end.
The program needs at most two pushed-back characters at once (the / + next case), so 100 slots is far more than enough.
Known limitations
The header comment (L52–55) lists the intentional ones: no rescanning, no \ line continuation, no #undef. Some others I noticed while reading:
Text after a non-define directive still gets substituted. In #include <stdio.h>, main reads stdio as an identifier and calls lookup on it. If you had #define stdio x, the include line would change.
Function-like macros aren't detected. #define max(a,b) ... installs max with the text (a,b) ..., because getident stops at ( and everything after it becomes the replacement text.
ungetch reports overflow with printf, which writes to stdout. In this program that message would be mixed into the processed output. fprintf(stderr, …) would be cleaner. The book's original code writes to stdout too.