Notes on C

Note that the conditional expression can be anything. If the value of the expression is zero, the condition is false; otherwise it is true.

Hence the following:

    while (c = getchar())
        putchar(c);
            

will copy stdin to stdout until a null character (ascii 0) is read.

An even more common idiom is:

while ((c = getchar()) != EOF)
    putchar(c);
            

The above program is just like the copyin program we saw earlier. Note that the parenthesis are necessary to force the assignment to occur before the inequality test. If we wrote:

if (c = getchar() != EOF)
            

it would be interpreted as:

if (c = (getchar() != EOF))
            

This would result in c being assigned the value true (1) or false (0), not the value of c read in!

Note that in the last example we use ~0xf to indicate a bit pattern of 1's except in the last four positions instead of 0xfffffff0. The reason is not to save typing; rather, the ~0xf method is independent of the number of bits in an integer. With the other method, we would have to use 0xfff0 for 16-bit machines.

A target called goal depends on two files: a and b as illustrated graphically in the figure below:

Figure 3.1. A simple dependency tree

The above dependency tree is described to make with the following Makefile:

# Simple "Makefile" example
# Anything after a '#' is ignored 
# i.e. treated as a comment
goal: a b  # Target "goal" depends on "a" and "b"
      touch goal # rule to generate "goal" if "a"  or "b"
                 # is more recent
# "touch" is a command to set the modification
# time of a file to the current time
b:          # Depends on nothing
       touch b
a:
       touch a
# NOTE: The white space before  a rule
# must be TAB.

A more realistic example of using make involves compiling. The figure below shows the dependencies of a final program, called prog, on three object files: p1.o, p2.o and p3.o. If prog does not exist or is older than any of the three object files it depends on, it will be regenerated.

Figure 3.2. Dependency tree of simple makefile

Similarly, each of the object files depends on a corresponding C source code file. If any of the source code files is newer than its object file, the object file will be regenerated. Since this will make at least one object file newer than the executable, make will automatically re-link the object files as well.

Finally, note that two source files—p2.c and p3.c—include the custom header ex2.h. Consequently, the object files p2.o and p3.o both depend implicitly on ex2.h. Since make detects if a target file is older than anything it depends one, the object files p2.o and p3.o will be regenerated if ex2.h is more recent.

The Makefile below shows how all of this is described.

# Simple "Makefile" example using compilation
prog: p1.o p2.o p3.o
        gcc -o prog p1.o p2.o p3.o
p1.o: p1.c
        gcc -c p1.c

p2.o: p2.c
        gcc -c p2.c

p3.o: p3.c
        gcc -c p3.c

# The following lines give additional
# files that object code depends on;
# in this case, these are header files
# included in the source code.
# If any of these are newer than the
# corresponding object file, the
# rules defined above will be invoked
# to re-create the object code.
p2.o: ex2.h
p3.o: ex2.h
              

Make allows string variables to to assigned and referenced as follows:

VAR_NAME = blah blah
         .
     $(VAR_NAME)
              

By default, the first target is made when make is invoked. However, other targets may also be specified. (The next example shows the common targets clean and depend.)

Normally, if a command in a rule has a non-zero exit status, make stops. However, preceding the command with a dash (-) causes make to ignore the exit status.

This feature is used in the clean target. The rule specifies that all generated files should be deleted. Obviously, if any of these files do not exist, we still want the make program to proceed.

Putting these ideas together, we obtain a more elegant Makefile for the previous example:

# Simple "Makefile" example using compilation
SRCS = p1.c p2.c p3.c
OBJS = p1.o p2.o p3.o

prog: $OBJS)
    gcc -o prog $(OBJS)
p1.o: p1.c
    gcc -c p1.c
p2.o: p2.c
    gcc -c p2.c

p3.o: p3.c
    gcc -c p3.c

depend: $(SRCS)
    makedepend  $(SRCS)
clean:
    -rm -f $(OBJS) a.out core prog
# DO NOT DELETE THIS LINE - - make depend depends on it.
p2.o: ex2.h /usr/include/stdio.h
p3.o: ex2.h /usr/include/stdio.h
              

You can specify, in general, how to obtain a target from a dependent when they only differ in their sufixes. For example, the C compiler is used to obtain an object (.o) file from a corresponding source (.c) file.

The following generic rule states this:

.c.o:
     $(CC) -c $*.c

where $(CC) is the name of the system C compiler and $* is the variable representing the base name of the target.

Other builtin make variables include: $@—the name of the current target; $<—the name of the dependency file; $?—the list of dependencies newer than the target.

Putting these rules together, we obtain the following Makefile:

# Simple "Makefile" example using compilation
SRCS = p1.c p2.c p3.c
OBJS = p1.o p2.o p3.o
PROG = prog
HOME = /home/eccles1/kclowes
INSTALL_PATH=$(HOME)/bin
CFLAGS = -c
CC = gcc
.c.o:
    $(CC) $(CFLAGS) $*.c 
$(PROG): $(OBJS)
    gcc -o $(PROG) $(OBJS)
depend: $(SRCS)
    makedepend  $(SRCS)

clean:
    -rm -f $(OBJS) a.out core $(PROG)
install: $(PROG)
    cp $(PROG) $(INSTALL_PATH)/$(PROG)
# DO NOT DELETE THIS LINE - - make depend depends on it.
p2.o: ex2.h /usr/include/stdio.h
p3.o: ex2.h /usr/include/stdio.h

Integers may be added or subtracted from pointers.

If n is added to a pointer p pointing to an object obj, p is incremented to point n objects further. (i.e. the numerical value of p becomes p + n*sizeof(object).

It is possible to perform ordinary arithmetic on pointers (i.e. arithmetic such that adding 1 to the pointer results in incrementing the numerical value of the pointer by 1) by casting the pointer to an integer. (More precisely, it should be cast to a (void *) or (size_t). These conventions are associated with the stdlib—we will examine their precise meaning later.)

More precisely, it is normally cast to an unsigned integer, or, a void pointer (which points to data of size 1).

For example, suppose ip is 0x1000 (i.e. it points to data at address 0x1000). If the data it points to is an integer and integers occupy 4 bytes, then ip++ will result in increasing the numerical value of ip to 0x1004 (the address of the next integer).

However, if we use:

(unsigned) ip++;
        /* or */
(void *) ip++;
              

the numerical value of ip will increase from 0x1000 to 0x1001, just like an ordinary number.

The most visible changes between ANSI and K&R C are in the way that functions are declared.

In ANSI C, we use:

double pow(double x, int i)
{
        /* body of function */
}

              

In K&R C, we use:

double pow(x, i)
double x;
int i;
{
        /* body of function */
}
              

Even if you only use ANSI C, you need to be familiar with the old-fashioned method since so much code was written with it. (ANSI compilers do understand the older method.)

When a program is compiled and turned into an executable file, one may wish to alter the behavior of the executable at the time it is invoked by passing it arguments on the command line to invoke it.

The simplest such standard command is echo (in both Windows and UNIX) which simply echoes its command line arguments to stdout when it is invoked.

For example:

OS_prompt>  echo Display this

results in the output:

Display this

The command line arguments are passed to the main() function of any program in a standard way. In particular:

The following example shows the code for a modified echo command:

/*
    myecho echos its command name and
    arguments to stdout.
*/
main(int argc, char *argv[])
{
    int i;

    printf("My argument count is: %d\n", argc);
    printf("I was invoked under the name of %s\n",
        argv[0]);
    printf("My arguments were:\n");
    for (i = 1; i < argc; i++)
        printf("Arg #%d: %s\n",
            i, argv[i]);
    exit(0);
}
              

A more interesting example is shown below:

#include <stdio.h>
char progname[128];
main(int argc, char * argv[])
{
  float    princ, interest;
  int    i, n_years;
  
  strcpy(progname, argv[0]);
  if (argc != 4) {
    printf("Usage: %s principal interest num_years\n",
           progname);
    exit(1);
  }
  princ = atof(argv[1]);
  printf("argv[1]: %s, princ: %f\n", argv[1], princ);
  interest = atof(argv[2]);
  printf("argv[2]: %s, interest: %f\n", argv[2], interest);
  n_years = atoi(argv[3]);
  printf("argv[3]: %s, n_years: %d\n", argv[3], n_years);
  interest = 1. + interest/100.;
  for(i = 1; i <= n_years; i++) {
    princ = princ*interest;
    printf("After %d years, new principal is: %8.2f\n",
           i, princ);
  }
  exit(0);
}

              

Functions like printf() are passed a variable number of arguments.

The number of arguments must, however, be implicit in the arguments themselves.

In the case of printf(), for example, the number of arguments is equal to 1 plus the number of (non-escaped) % characters in the formatting string which must be the first argument.

The cat example below concatenates any number of strings. The number of strings to be concatenated is explicitly given as the first argument. (Another common way to pass a variable number of arguments is to make the last argument a null pointer.)

We will first write this function in a non-standard way, illustrating the method most C compilers use to pass parameters to functions. This can be useful information when linking with other languages that use a different convention. It is also a good exercise in the use of pointers.

In this example, we assume that arguments are passed to functions by pushing them onto the stack, that the stack grows towards lower memory, and that the first argument is the last one pushed on.

The code follows:

/*
*    Cat concatenates a variable number of strings, allocates
*    memory for the resulting string and returns a pointer to it.
*
*    arguments:
*        n - number of strings to concatenate
*        args - "n" pointers to NULL terminated character strings
*
*    returns:
*        a pointer to the string of the concatenated
*        arguments
*
*        
*/

char * cat(int n, char * args)
{
    register int i, len = 0;
    char  *malloc();
    register char **s, *x, *start;
    s = &args;  /* s points to first argument on stack */

    /* Add up the lengths of all the strings */
    for(i = n;ien-- ;) 
        len += strlen(*s++);

    /* Allocate enough memory for all strings (plus NULL) */
    x = malloc(len + 1);    
    start = x;

     s = &args;  /* Point back to first argument on stack */

    /* Concatenate all the input strings together into x */
    while (n-- )  {
        while (*x++ = *(*s)++); /* Cat next string to x */
        s++;  /* Point down stack to next argument */
        x-- ; /* Backspace over NULL */
    }

    return start;
}
              

Lexical analysis is used to translate the incoming sequence of bytes read from the source code file into more meaningful tokens.

The lexical analyzer can recognize sequences of characters as words.

For example, input that we read as:

thing := stuff*10;

would be read by the lexical analyzer as the following sequence of 18 bytes:

74 68 69 6e 67 20 3a 3d 20
73 74 75 66 66 2a 31 30 3b
              

The lexical analyzer translates these 18 bytes into a sequence of 6 tokens as follows:

<identifier (with value of ``thing'')>
<assignment operator>
<identifier (with value of ``stuff'')>
<multiply operator>
<constant (with value of 5)>
<statement terminator>
              

This is not too complicated to do. The language definition requires that keywords be separated by white space (blanks, tabs or newlines) or by special characters (like = ; > etc. not allowed to be part of keywords or identifiers (i.e. symbols).

Hence the lexical analyzer reads one byte at a time and collects them until it hits white space or a special character.

It has then collected a “word” and compares it against its list of keywords.

If it finds a match it outputs a token representing that keyword; if no match is found an “identifier token” is output along with some link to the token's “value”. The lexical analyzer also recognizes that a word beginning with a digit should be output as a “constant token” with a link to the actual digit string.

Finally, special characters (like ; + *) or groups of special characters (like := >=) are also recognized and have their own individual tokens.

The number of types of tokens is quite limited. This is a marked contrast from natural languages like English with vocabularies that are bigger by many orders of magnitude.

This limited vocabulary of programming languages (also called formal languages in contrast to natural languages) makes the lexical analyzer's job much easier.

Note that the lexical analyzer makes no judgements about the significance or sensibleness of the stream of tokens its generates.

(However, the lexical analyzer may be able to detect a non-sensical token such as a string like 123ax5 which, because it starts with a digit should generate a constant token while the string as a whole is not a number.)

Once the lexical analyzer has converted the source code into a token stream, the parser} (or semantic analyzer) takes over.

Its job is to find meaningful patterns in the token sequence and to pass these “meanings” to the final stage of compilation—the code generator— which produces the final machine language translation of the original source code.

Finding meaningful patterns is greatly simplified by the formal definition of the source code language grammar.

The syntax (or grammar) of a formal language like C can be completely described using the Backus-Nauf Form (BNF) notation. This notation describes how tokens can be combined to form semantic units.

Some of these semantic units are very simple. The “addop” semantic unit, for example, is either an addition ('+') or subtraction ('-') operator and BNF uses the following notation to describe this:

<addop> ::=
     <+ operator> | <- operator>
              

The '|' (vertical bar) symbol is used to describe alternatives. Note that the '+' and '-' characters are simple tokens recognized by the lexical analyzer.

The semantic analyzer or parser uses the above rule or pattern to recognize these simple tokens as a more abstract semantic unit.

The BNF description also describes how the addop unit can be combined with other semantic units to form yet more complex abstract entities.

For example, we know that we can add or subtract two or more “terms” and that a programmer specifies this by placing '+' or '-' characters between the terms.

Let's call something like “a + b - c” an expression. The general BNF description for an expression is:

<expression> ::=
     <term> {<addop> <term>}
              

The '{' and '}' (curly braces) indicate that the symbols within them may be repeated zero or more times.

Assuming for the moment that a term is a simple variable, all the following are valid expressions according to the above BNF definition:

<term> and 0 repetitions of <addop> <term>:
a
<term> and 1 repetition of <addop> <term>:
c - d
<term> and 2 repetitions of <addop> <term>:
a + b - c 

              

To use the BNF rule in finding these expressions, the parser would first recognize the initial term.

It would then determine if the next semantic entity was an <addop>: if it was not, the parser would return the simple expression; otherwise it would look for the <term> that must follow the <addop> and then repeat the sequence looking for another <addop> or the end of the expression.

The ultimate goal of the parser is to combine all the tokens and all the semantic units into the highest-level unit of all: the <program>. As the higher-level units are formed, information about their structure is passed to the code generator which then has sufficient information to perform “actions” based on the semantic structure.

These actions generate the machine code equivalent to the semantic structures of the source code.

We will consider the the example of an assignment statement to illustrate this point.

Consider the BNF:

<assignment statement> ::=
     <variable> := <expression>

<expression> ::=
     <term> {<addop> <term>}

<addop> ::=  + | -

<term> ::=
     <factor> { * <factor> }

<factor> ::=
     <variable> | ( <expression> )

              

If we look at how expressions are defined here, we see that any arithmetic expression involving the '+', '-' and '*' opererators and the '(' and ')' grouping characters is defined.

The definitions are recursive as an expression is defined as a grouping of <term>s; terms in turn are defined using <factor>s; finally factors are defined using <variable>s and again with <expression>s.

This method of defining something in terms of itself looks strange at first glance but it is a powerful method for simple, elegant definitions of grammars.

Consider how the parser would treat the following expression:

(a + b) * c

When the expression detecting routine is called, it first invokes another routine to look for the first thing in an expression—in this case a term. As soon as the term routine is called, it immediately looks for its first item—a factor.

A factor, in turn, has two alternative definitions: either it is a simple variable or it is an expression enclosed within parenthesis.

The factor routine examines the first character to see if it is a simple variable or a '('.

In this case, it finds the '(' special character; it then moves to the next input token which it expects to be the start of an expression and calls the expression recognition routine once again.

When the expression routine starts a second time, it again calls term and then factor.

This time, however, factor finds a simple variable and returns immediately. The term routine then looks for a '*' to see if it should call factor again; it doesn't find one, so it returns immediately. Now the second invocation of expression looks for a '+' sign to see if it should again call term again to find out what should be added to the first term it found.

Expression finds a simple variable, 'c', on the other sign of the + sign. It then looks for another '+' or '-' to see if it should continue. Since the next character is a ')', this second invocation of expression terminates and returns to the factor routine that called it.

Factor then expects to find a ')' to balance the first one it detected and it returns to term after finding the next token following the ')'. Term examines this token to see if it is a '*'. Since it is, term calls factor again to find the other factor of the multiplication. Term then finds no more '*'s and returns to the first invocation of expression.

We are now almost done. Expression looks for another '+' or '-', finds none, and terminates. The entire expression has now been completely parsed. We now know what has to added, subtracted and multiplied and are in a position to generate machine code to perform these operations and evaluate the expression.

We can, of course, write a program to parse expressions based on the above syntax. Such a program, written in C, is shown below. This program does more, however, than merely recognize expressions. It also does some translation; in particular, it translates algebraic notation for expressions defined in the BNF for expressions into Reverse Polish Notation (RPN).

With Reverse Polish Notation (used for example to enter expressions in Hewlett-Packard calculators), the expression is read and each variable or constant is pushed onto a stack. When an operator is encountered, the top two elements are popped off the stack, the operation performed on them, and the result pushed back on the stack.

Consider the following expression and its RPN equivalent:

(a+b)*(c + d +e)  //algebraic
ab+cd+e+*  //RPN equivalent
              

If the RPN expression is examined one token at a time, then, just before encountering the first '+' operator, the stack would look like the figure below:

Figure 6.1. RPN stack before processing first '+' in ab+cd+e+*

After processing the first two characters (i.e. “ab”) in the RPN expression, the stack would look like the figure below:

Figure 6.2. RPN stack after processing “ab” in ab+cd+e+*

It would then undergo the following transformations:

Figure 6.3. RPN stack when interpreting ab+cd+e+*

To make the parser program convert the algebraic expression to reverse polish notation at the same time that it is parsing it we simply add the following: print identifiers as they are encountered but defer printing a '+', '-' or '*' until both of its terms (or factors) have been found.

The C program (available at parseRPN.c) is:

#include <stdio.h>
/*
 * The program works on expressions conforming to the following BNF syntax
 * rules:
 *    <expression> ::= <term> [ <addop> <term> ]
 *    <term> ::= <factor> [  <factor> ]
 *    <factor> ::= ( <expression> ) | <id>
 *    <addop> ::= + | -
 *    <id> ::= any single character except ()*+-
 * 
 * How to run the program: The program reads algebraic expressions for stdin and
 * writes their Reverse Polish Notation (rpn) equivalent to stdout. In order
 * to avoid seeing all of this on the screen, redirect stdin or stdout. For
 * example, postfix1 < exprs will read expressions from the file "exprs"
 * (which you have to create previously).
 */

char      ch;

main()
{
  find();
  do
  {
    expression();
    putchar('\n');
  } while (ch != '.');
}

find()  /* Read input until non-white space or
         * end-of-line reached */
{
  while (((ch = getchar()) == ' ') || (ch == '\n'))
  ;
}

expression()
   /*
    * Look for an expression and print
    * the + or - operand if and when a "term"
    * is found after such an operand
    */
   
{
  char      op;
  term();
  while ((ch == '+') || (ch == '-'))
  {
    op = ch;
    find();
    term();
    putchar(op);
  }
}


term()
   /*
    * Look for a term and print the * operand if and when a "factor" is found
    * after such an operand
    */
{
  factor();    /* Find the initial factor and print rpn for
       * it */
  /*
   * Move around the "factor*factor" loop as long as the next character
   * is the '*' operand'
   */
  while (ch == '*')
  {
    find();    /* Move to next non-blank character */
    factor();  /* Find the factor after the '*' and,
                * if it is a simple identfier, print it */
    putchar('*');  /* Complete the rpn for the factor by
                    * printing the '*' operand */
  }
}


factor()
   /* Look for a factor; if the factor is a simple identifier, print it */
{
  if (ch == '(')
  {
    find();    /* Move to the next non-white character */
    expression();  /* Find the expression & print rpn for it */
    /* After returning "ch" should be a ')' if syntax is correct */
  } else
    {
  /*
   * If not an expression enclosed in "(...)", it has to be a
   * simple identifier so print it
   */
      putchar(ch);
    }
  find();      /* Now move to next non-blank character */
}

              

The #include directive simply inserts the named file into the source code. The file is called a “header file” and, by convention, its name ends with .h.

The most common type of include statement looks like:

#include <header_name.h>

This is usually used to include a header file associated with functions (or macros) supplied with the compiler. For example, #include <stdio.h>.

The compiler knows where to find the file.

However, the compiler can be instructed to look for the include file in other directories by giving their names to the -I option in the compiler. Thus, if the compiler should look for header files in directory /usr/me/my_includes, use the command line:

UNIX_PROMPT% cc -I/usr/me/includes source_file.c
              

The other way to specify an include file is with:

#include "path_file"
              

In this case, the exact path (relative or absolute) for the file is given.

For example, if the header file head.h is in the same directory as the source code, simply use:

#include "head.h"
              

It is also very common for a large project to be divided into several sub-directories: src for source code, doc for documentation, include for header files, etc.

Thus a source code files in sub-directory src can access header files by moving up to the parent directory (..) and down to the include directory as follows:

#include "../include/head.h"
              

We have used #define to define the values of symbolic constants. It can be used to define anything.

Symbolic constants can be re-used in other #define statements as shown below:

/*Clock freq (kHz)  divided by prescaler*/
#define CLOCK 4000/32
#define INT_TIME 200    /* in units of milliseconds */
#define COUNT    (INT_TIME*CLOCK)
/* Split 24 bit COUNT into 8 bit parts (hi, mid, lo) */
#define COUNTHI (COUNT/(256*256))
#define COUNTMID (COUNT/256 - COUNTHI*256)
#define COUNTLO (COUNT%256)
              

#define directives can also be parameterized to define macros. For example:

#define max(A, B) (((A) > (B) ? (A) : (B))
              

If, later in the source code, we see:

j = max(i+2, k);

the preprocessor replaces this with:

j = (((i+2) > (k) ? (i+2) : (k))

A macro appears to behave like a function. However, it is more efficient since it is expanded in-line. (There is no subroutine call or return.)

For example, we have been using getchar() as if it were a function. In fact it is (usually) a macro defined in stdio.h.

There are dangers, however, in the fact that macros and functions look the same. In particular:

The #ifdef (if defined) preprocessor directive is used to conditionally compile certain sections of code. This often leads to more portable code and code that can easily be recompiled to behave in a different, configurable way.

The form:

#ifdef Symbol
   ...
   ...
#endif
              

results in the statements between the #ifdef and the matching #endif being compiled only if the string Symbol has been defined by a previous #define statement (or command line option when the compiler was invoked).

For example, consider:

#ifdef MOT68K
typedef unsigned int big_numbers;
#endif
#ifdef INTEL8088
typedef unsigned long big_numbers;
#endif
              

Here, the proper typedef will be compiled so that the type big_numbers} will be an unsigned 32-bit integer on both PCs (which use Intel 8088 chips) and UNIX 680x0 machines.

A very common use for #ifdef is to surround debugging statements with #ifdef DEBUG as shown below:

#ifdef DEBUG
  printf("i: %d now\n", i);
#endif
               

When developing the code, DEBUG is defined; hence the debug statements are compiled and executed at run time. Once the program works, it is re-compiled without defining DEBUG and it will now run without the debugging statements.

Note that this is preferable to deleting the debugging statements. After all, a hidden bug may be reported later on. In this case, the program has to be debugged again but there is no need to re-write the debugging statements; simply re-compile with DEBUG defined.

Note that a symbol can be defined on the command line that invokes the compiler instead of in the program itself. Thus, to compile with debugging statements, we write:

SHELL_PROMPT% gcc -DDEBUG source_file.c
              

The directive #ifndef works just like #ifdef except that the statements following it up to the #endif are only compiled if the symbol is not defined.

The effect of a #define statement can be undone with the #undef directive.

This is often useful if you want to use a function for something that is normally a macro. For example, if you want to use your own function getchar() (which is a macro expansion by default), use:

#undef getchar
        .
        .
int getchar() {
        /* Your function body */
}
              

Another way of forcing getchar() to be a function rather than a macro is to use: (getchar)().

In addition to the familiar #include, #define, #ifdef, etc., the following features have been added to the preprocessor in ANSI C.

The #if constant integer expression has been added for conditional compilation. The “constant integer expression” is considered true if it evaluates non-zero and false if it is zero. The expression can use C style syntax as well as the defined(name) which evaluates as true if “name” has been defined.

The new directives #else and #elif (else if) have also been included. For example:

#if SYSTEM == UNIXV.3\
        || SYSTEM == SUNOS\
        || SYSTEM == XENIX
#define UNIX
#endif
#if !defined(UNIX) && SYSTEM != MSDOS
#error Do not know operating system
#endif
#if defined(DEBUG)
#if defined(UNIX)
#define INCLUDE unixdebug.h
#elif defined(MSDOS)
#define INCLUDE msdosdebug.h
#endif
#else
#if defined(UNIX)
#define INCLUDE unix.h
#elif defined(MSDOS)
#define INCLUDE msdos.h
#endif
#endif
#include < HEADER >
              

The new operators # and ## can be used to generate strings by concatenation by the preprocessor.

When a parameter name in a macro is preceded by a #, the parameter will be quoted and concatenated with any surrounding strings.

The ## operator is used to quote and concatenate adjacent macro arguments.

The predefined identifiers __LINE__, __FILE__, __DATE__, __TIME__, and __STDC__ have been added to the preprocessor. They contain, respectively, the decimal number of the current line, the name of the current source code file, the date and the time. __STDC__ is defined as 1 if the compiler conforms to the ANSI standard. For example:

#define err( m )    fprintf(stderr,\
                "Error on line %d:" #m "\n", __LINE__)
 ...
        err(print this message after colon);
              

The use of ## is shown below:

#define instance( prefix, root, postfix)\
        prefix ## root ## postfix
 ...
i = j + instance(pre, _body_, 5);
/* Above is creates i = j + pre_body_5; */
              

The ctype.h header file is a good example of how the power of the preprocessor can be exploited to yield very efficient code.

Here is a typical (abridged) example:

#define    _U    01
#define    _L    02
#define    _N    04
#define    _S    010
#define    _P    020
#define    _C    040
#define    _B    0100
#define    _X    0200
extern    char    _ctype[];
#define    isalpha(c)    ((_ctype+1)[c]&(_U|_L))
#define    isupper(c)    ((_ctype+1)[c]&_U)
#define    islower(c)    ((_ctype+1)[c]&_L)
#define    isdigit(c)    ((_ctype+1)[c]&_N)
#define    isxdigit(c)    ((_ctype+1)[c]&_X)
#define    isspace(c)    ((_ctype+1)[c]&_S)
#define    ispunct(c)    ((_ctype+1)[c]&(_P))
#define    isalnum(c)    ((_ctype+1)[c]&(_U|_L|_N))
#define    isprint(c)    ((_ctype+1)[c]&(_P|_U|_L|_N|_B))
#define    isgraph(c)    ((_ctype+1)[c]&(_P|_U|_L|_N))
#define    iscntrl(c)    ((_ctype+1)[c]&_C)
#define    isascii(c)    ((unsigned)(c)<=0177)
#define    _toupper(c)    ((c)-'a'+'A')
#define    toupper(c)    (islower(c) ? _toupper(c) : (c))

              

Note how the macro like isdigit works. Given:

#define    _S    010
#define    isspace(c)    ((_ctype+1)[c]&_S)
              

The array _ctype is 257 characters long and each entry contains a bit pattern indicating if the corresponding ascii code is a lower case letter, a digit, etc. (each of the 8 bit positions corresponds to one of the primitive types).

The bitwise “and” (&) isolates an appropriate bit of the _ctype array element and the expression evaluates to either 0 or 010 (i.e. 8 decimal) which are interpreted respectively as false and true. (Note that the macro exploits the fact that C considers any non-zero value to be true. It is only the results of logical operations (&&, >=, etc.) that guarantee that “true” will be 1 (one).)

The following is the most atrocious C program I hope you will ever see. Hopefully, a bad example will encourage thoughtful solutions.

/*
 This program illustrates the WRONG WAY of
 writing programs.  The program is an attempt to
 simulate a state machine having three states;
 the algorithm chosen seems straight forward,
 but solves the problem through brute force
 instead of examining the fundamentals.
 
 The program "goodstate3" shows the correct method.
*/

#include <stdio.h>
#include <ctype.h>
#define RED (0)
#define GREEN (1)
#define BLUE (2)

main()
{
  int    switch_code, c, new_state, state;
  
  state = RED;
  printf("Initial state is RED\n");
  printf("Enter switch_code value: ");
  
  while ((c = getchar()) != EOF ) {
    switch_code = c - '0';
    if (state == RED) {
      if (switch_code == 0) {
        new_state = GREEN;
      } else
        new_state = BLUE;
    } else if (state == GREEN) {
      if (switch_code == 0)
        new_state = RED;
      else     {
        new_state = BLUE;
      }
    } else if (switch_code == 0)
      new_state = BLUE;
    else
      new_state = RED;
    printf("New state is ");
    state = new_state;
    if (state == RED)
      printf("RED\n");
    else if (state == GREEN)
      printf("GREEN\n");
    else
      printf("BLUE\n");
    printf("\nEnter switch_code value: ");
    while (!isdigit(c = getchar()))
      ;
    ungetc(c, stdin);
  }
}
              

Recognizing that the entire pictorial representation of a state machine may be translated into data structures, the far superior solution to the the state machine problem is shown below:

/*

 This program illustrates the BETTER WAY of writing programs.
 We again  attempt to simulate a state machine
 having three states.

 The algorithm used here is simplicity itself (the heart of
 the program is one line long and can be used for any state
 machine of arbitrary complexity!).

 All the information about the state machine is maintained
 as data (in data structures) not in the program code itself.
*/

#include <stdio.h>

typedef struct State State, *StatePtr;
/* Note that a state has 3 associated properties:
 *    - the state's name;
 *    - an indicator of the next state if the input is 0
 *    - an indicator of the next state if the input is 1
 *
 *  This initial description of the state's fields
 *  can be improved.
 *
 *  In particular, the last 2 properties (next state if input is 0,
 *  next state if input is 1) share a common property: each indicates
 *  a "next state".
 *  Furthermore, the one to follow is chosen using the input (either
 *  0 or 1).
 *
 *  This suggests putting both of these "next state indicators" into
 *  an array.  The program can use the input to index into the
 *  array (i.e. either next[0] or next[1]).
 *
 *  With this approach, the program does not have to use
 *  If/Else logic to select which arrow to follow; if the
 *  input is "input_value", the next state can be directly
 *  accessed as next[input_value].
 *
 *  Finally, this approach is much more general and flexible.
 *  Suppose, for example, that we had to simulate a state machine
 *  that had 8 possible inputs.
 *  All that need be done would be to dimension the "next" array
 *  to have 8 elements and define the data stuctures properly.
 *
*/

struct State {
  char * name;
  StatePtr next[2];
};

State red, green, blue;
/* Define the fields of each state */
State red   = {"Red", {&green, &blue}};
State green = {"Green", {&red, &green}};
State blue  = {"Blue", {&red, &green}};

int main()
{
  int sw;
  int ch;
  StatePtr currentStatePtr = &red;

  printf("%s\n", currentStatePtr->name);
  while((ch = getchar()) != EOF) {
    if((ch != '0') && (ch != '1')) /* Ignore all chars except 0 & 1 */
      continue;
    sw = ch - '0';

    /* Heart of program! */
    currentStatePtr = currentStatePtr->next[sw];

    /* Display new state */
    printf("%s\n", currentStatePtr->name);
  }
}
            

The only state machine dependencies in the previous code is the declarations and definitions.

Let's write a C program that takes a description of a state machine with any number of states and any number of inputs. The program is:

/*
 genStateMachine takes the description of a state machine (from stdin)
 and produces (on stdout) the C source code to simulate
 the state machine.
 
 The format of the input describing the state machine must be:
 
 number of states
 number of switches
 name of 1st state
 name of 2nd state
 .
 .
 name of nth state
 next state when in 1st state and switch input = 0
 next state when in 1st state and switch input = 1
 .    .    .
 .    .    .
 next state when in 1st state and switch input = (2**n_switches) -1
 next state when in 2nd state and switch input = 0
 .    .    .
 .    .    .
 next state when in 2nd state and switch input = (2**n_switches) -1
 .    .    .
 .    .    .
 .    .    .
 .    .    .
 next state when in nth state and switch input = (2**n_switches) -1
 
 
 Normally the program would be run with redirection of stdin & stdout.
 
 For example, to generate a C program called test.c from
 a state machine description in file "test.state", use:
 
 genStateMachine < rgbMachine.state > rgbMachine.c
 
 Of course, "cc -o rgbMachine rgbMachine.c" is then used to compile the mechanically
 generated program; "rgbMachine" is subsequently used to run the
 simulator.
 
 Note that the format of the input description of the state machine
 is very strict.
 The solution, naturally, is to write yet another program that
 allows a user to enter the description of a state machine
 in a much more convenient (i.e. "user-friendly") way and which
 in turn mechanically generates the more formal description
 required here.
*/

int n_switches, n_states, n_arrows, i, j;
char next_state[16], state_name[16][100];

#include <stdio.h>
main()
{
  scanf("%d%d", &n_states, &n_switches);
  n_arrows = power(2, n_switches);
  
  printf("/* This program was generated mechanically by genStateMachine */\n");
  printf("#include <stdio.h>\n");
  printf("#include <ctype.h>\n");
  printf("typedef struct State State, *StatePtr;\n");
  printf("struct State {\n");
  printf("   char * name;\n");
  printf("   StatePtr next[%d];\n};\n", n_arrows);
  printf("State ");
  
  for(i = 0; i < n_states; i++) {
    scanf("%s", state_name[i]);
    printf("%s", state_name[i]);
    printf("%s", i < n_states-1 ? ", " : ";\n");
  }
  
  for(i = 0; i < n_states; i++) {
    printf("State %s = {\"%s\", {",  state_name[i], state_name[i]);
      for(j = 0; j <  n_arrows; j++) {
      scanf("%s", next_state);
      printf("&%s%s", next_state, j < n_arrows-1 ? ", " : "}};\n");
    }
  }
  
  printf("int main()\n{\n  int sw;\n  int ch;\n  StatePtr currentStatePtr = &");
  printf("%s;\n", state_name[0]);
  printf("  printf(\"%%s\\n\", currentStatePtr->name);\n");
  printf("  while((ch = getchar()) != EOF) {\n");
  printf("    if (!isdigit(ch)) continue;\n");
  printf("    sw = ch - '0';\n");
  printf("    currentStatePtr = currentStatePtr->next[sw];\n");
  printf("    printf(\"%%s\\n\", currentStatePtr->name);\n");
  printf("  }\n  exit(0);\n}\n");
}

power(n, i)
     int n, i;
{
  int temp;
  
  temp = 1;
  while (i > 0) {
    i = i -1;
    temp = temp*n;
  }
  return temp;
}