How to Create a Program: a Small Software Project in C++

Final Implementation (Not!)

There is no "final" implementation. Let me reiterate: There is no "final" implementation.

So how do we know when to stop? The truth is, we don't! Sometimes we just get bored with the program; sometimes we start a new interesting project and we abandon the current one (promising ourselves that we'll come back to it later). Sometimes it might help to have a delivery date planned ahead (even if we slip a little), and a manager who tells us to stop adding new features and just ship the product.

With this caveat in mind, let me go over the pseudo-final version of the calculator to show how the stubs get expanded to create a working program.

Scanner

The list of tokens is enlarged to include four arithmetic operators, the assignment operator, parentheses, and a token representing an identifier. An identifier is a symbolic name, like pi, sin, x, and so on.

enum EToken
{
  tEnd,
  tError,
  tNumber,  // literal number
  tPlus,   // +
  tMult,   // *
  tMinus,   // -
  tDivide,  // /
  tLParen,  // (
  tRParen,  // )
  tAssign,  // =
  tIdent   // identifier (symbolic name)
};

The Scanner now has the ability to recognize symbolic names. So, besides the new method GetSymbolName, it has two additional data members: _lenSymbol, which specifies the length of the currently recognized symbolic name, and _iSymbol, which marks the beginning of the name in the Scanner's buffer.

class Scanner
{
public:
  ...
  void GetSymbolName (char * strOut, int & len);
private:
  ...
  int  _lenSymbol;
  int  _iSymbol;
};

The Accept method is expanded to recognize the additional arithmetic symbols (the minus sign, the division sign, the two parentheses, and the equal sign), as well as floating-point numbers and identifiers. The decimal point is added to the list of digits in the scanner's switch statement, so the scanner can recognize numbers that start with the decimal point (such as .5).

The library function strtod (string to double) not only converts a string to a floating-point number, but updates the pointer to the first character that cannot possibly be part of the number. This is very useful, since it lets us easily calculate the new value of _iLook after scanning the number.

case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case '.':
{
  _token = tNumber;
  char * p;
  _number = std::strtod (&_buf [_iLook], &p);
  _iLook = p - _buf; // pointer subtraction
  break;
}

The function strtod has two outputs: the value of the number that it has recognized and the pointer to the first unrecognized character.

double strtod (char const * str, char ** ppEnd);

How can a function have more than one output? The trick is to pass an argument that's a reference or a pointer to the value to be modified by the function. In our case, the additional output is a pointer to char. We have to pass a reference or a pointer to this pointer. (Because strtod is a function from the standard C library, it uses pointers rather than references.)

Let's see what happens, step by step. We first define the variable to be modified by strtod. This variable is a pointer to a char:

char * p;

Notice that we don't have to initialize it to anything; it will be overwritten in the subsequent call anyway. Next, we pass the address of this variable to strtod:

_number = std::strtod (&_buf [_iLook], &p);

The function expects a pointer to a pointer to a char:

double strtod (char const * str, char ** ppEnd);

By dereferencing this pointer to a pointer, strtod can overwrite the value of the pointer. For instance, it could do this:

*ppEnd = pCurrent;

This would make the original p point to whatever pCurrent was pointing to (see Figure 2).

Figure 2 ppEnd contains the address of the pointer p. Pointer p can thus be changed through ppEnd.

In C++, we could have passed a reference to a pointer instead (not that it's much more readable):

char *& pEnd

It's not clear that passing simple types like char* or int by reference leads to more readable code. Consider this:

char * p;
_number = StrToDouble2 (&_buf [iLook], p);

It looks like an uninitialized variable is being passed to a function. Only by looking up the declaration of StrToDouble2 would you know that p is passed by reference:

double StrToDouble2 (char const * str, char *& rpEnd)
{
  ...
  rpEnd = pCurrent;
  ...
}

Although it's definitely good programming practice to look up at least the declaration of the function you're about to call, you might argue that it shouldn't be necessary to look it up when you're reading somebody else's code. Then again, how can you understand the code if you don't know what StrToDouble2 is doing? And how about a comment that will immediately explain what's going on?

char * p; // p will be initialized by StrToDouble2
_number = StrToDouble2 (&_buf [_iLook], p);

You should definitely include a comment whenever you define a variable without immediately initializing it. Otherwise, the reader of your code will suspect a bug.

Taking all of this into account, my recommendation would be to go ahead and use C++ references for passing simple as well as user-defined types by reference.

Of course, if strtod was not written by a human optimizing compiler, the code would probably look more like this:

case '0': case '1': case '2': case '3': case '4':
case '5': case '6': case '7': case '8': case '9':
case '.':
{
  _token = tNumber;
  _number = StrToDouble (_buf, _iLook); // updates _iLook
  break;
}

with StrToDouble declared as follows:

double StrToDouble (char const * pBuf, int & iCurrent);

It would convert the string to a double starting from pBuf [iCurrent] and advance iCurrent past the end of the number.

Back to Scanner::Accept. Identifiers are recognized in the default statement of the big switch. The idea is that if the character is not a digit, a decimal point, or an operator, it must either be an identifier or an error. We require an identifier to start with an uppercase or lowercase letter, or with an underscore. By the way, this is exactly the same requirement that C++ identifiers must fulfill. We use the isalpha function (really a macro) to check for the letters of the alphabet. Inside the identifier, we (and C++) allow digits as well. The macro isalnum checks whether the character is alphanumeric. Examples of identifiers are i, pEnd, _token, __iscsymf, Istop4digits, SERIOUS_ERROR_1, and so on.

default:
  if (std::isalpha (_buf [_iLook])
   || _buf [_iLook] == '_')
  {
   _token = tIdent;
   _iSymbol = _iLook;

   int cLook; // initialized in the do loop
   do {
     ++_iLook;
     cLook = _buf [_iLook];
   } while (std::isalnum (cLook) || cLook == '_');

   _lenSymbol = _iLook - _iSymbol;
   if (_lenSymbol >= maxSymLen)
     _lenSymbol = maxSymLen - 1;
  }
  else
   _token = tError;
  break;

To simplify our lives as programmers, we'll limit the size of symbols to maxSymLen.

Once the Scanner recognizes an identifier, it should be able to provide its name for use by other parts of the program. To retrieve a symbol name, we call the following method:

void Scanner::GetSymbolName (char * strOut, int & len)
{
  assert (len >= maxSymLen);
  assert (_lenSymbol <= maxSymLen);
  std::strncpy (strOut, &_buf [_iSymbol], _lenSymbol);
  strOut [_lenSymbol] = '\0';
  len = _lenSymbol;
}

Notice that we have to make a copy of the string, because the original in the buffer is not null-terminated. We copy the string to the caller's buffer strOut of length len. We do it by calling the function strncpy ("string-n-copy," where n means that there is a maximum number of characters to be copied). The length is an in/out parameter of the method GetSymbolName. It should be initialized by the caller to the size of the buffer strOut. After GetSymbolName returns, its value reflects the actual length of the string copied.

How do we know that the buffer is big enough? We make it part of the contract—see the assertions.

The method GetSymbolName is an example of a more general pattern of passing buffers of data between objects. There are three main schemes: caller's fixed buffer, caller-allocated buffer, and callee-allocated buffer. In our case the buffer is passed by the caller and its size is fixed. This allows the caller to use a local fixed buffer—there is no need to allocate or reallocate it every time the function is called. Here's the Parser code that makes this call (the buffer strSymbol is a local array):

char strSymbol [maxSymLen];
int lenSym = maxSymLen;
_scanner.GetSymbolName (strSymbol, lenSym);

Notice that this method can only be used when there is a well-defined and reasonable maximum size for the buffer, or when the data can be retrieved incrementally in multiple calls. Here, we were clever enough to always truncate the size of our identifiers to maxSymLen.

If the size of the data to be passed in the buffer is not limited, we have to be able to allocate the buffer on demand. In the case of a caller-allocated buffer, we have two options. Optimally, the caller should be able to first ask for the size of the data, allocate the appropriate buffer, and call the method to fill the buffer. There is a variation of the scheme—the caller reallocated buffer—where the caller allocates the buffer of some arbitrary size that covers, say, 99% of the cases. When the data doesn't fit into the buffer, the callee returns the appropriate failure code and lets the caller allocate a bigger buffer.

char * pBuf = new char [goodSize];
int len = goodSize;
if (FillBuffer (pBuf, len) == errOverflow)
{
  // rarely necessary
  delete [] pBuf;
  pBuf = new char [len]; // len updated by FillBuffer
  FillBuffer (pBuf, len);
}

This may seem like a strange optimization until you encounter situations where the call to ask for the size of data is really expensive. For instance, you might be calling across the network, or require disk access to find the size, and so on.

The callee-allocated buffer seems a simple enough scheme. Since the called function knows how much space is needed, it allocates the buffer and returns a pointer to it. The most likely complication is a memory leak when the caller forgets to deallocate the buffer (which, we should remember, hasn't been explicitly allocated by the caller). We'll see how to protect ourselves from such problems using smart pointers (see the chapter on Resource Management). Other complications arise when the callee uses a different memory allocator than the caller, or when the call is remoted using, for instance, Remote Procedure Call (RPC, a protocol for programs to talk to each other). Usually we let the callee allocate memory when dealing with functions that have to return dynamic data structures (lists, trees, and so on). Here's a simple code example of a callee-allocated buffer:

char * pBuf = AcquireData ();
// use pBuf
delete pBuf;

The following decision tree summarizes various methods of passing data to the caller:

if (max data size well-defined)
{
  use caller's fixed buffer
}
else if (it's cheap to ask for size)
{
  use caller-allocated buffer
}
else if ((caller trusted to free memory
     && caller uses the same allocator
     && no problems with remoting)
   || returning dynamic data structures)
{
  use callee-allocated buffer
}
else
{
  use caller-reallocated buffer
}

In Part 2 of this book we'll talk about some interesting ways of making the callee-allocated buffer a much more attractive and convenient mechanism.

Symbol Table

With a few minor modifications, we are going to reuse the hash table and the string buffer code to implement the symbol table. But first we'll make it so the size of the hash table can be set during construction.

explicit HTable (int size): _size (size)
{
  _aList = new List [size];
}

~HTable ()
{
  delete []_aList;
}

Notice the keyword explicit in front of the constructor. I put it there to tell the compiler not to use this constructor to do implicit conversions. Normally, when you define a constructor that takes a single argument of type T, the compiler can use it to quietly convert an object of type T to an object of the class whose constructor it is. For instance, since the constructor of the hash table takes a single argument of type int, the compiler would accept a statement like this:

HTable table (13);
table = 5;

It would just "convert" an integer, 5, to a hash table as easily as it converts an integer to a double. Such implicit conversions are sometimes extremely useful, but at other times they are a source of unexpected problems. The code above makes little sense and the error would be easy to spot. Imagine, however, that somebody by mistake passed an int to a function expecting a const reference to a hash table. The compiler would actually create a temporary hash table of the size equal to the value of the integer and pass it to the function. To protect yourself from this kind of error, you should make it a habit to declare single-argument constructors explicit—that is, unless you really want to define an implicit conversion.

The symbol table is a simple modification of our earlier string table. It uses a hash table to map strings into short lists of string IDs. New strings are stored in the string buffer at the first available offset and are given the first available ID, _curId. The offset of the string in the buffer is then stored in a separate array _offStr. String ID doubles as an index to this array.

const int idNotFound = -1;

class SymbolTable
{
public:
  explicit SymbolTable (int size);
  ~SymbolTable ();
  int ForceAdd (char const * str, int len);
  int Find (char const * str) const;
  char const * GetString (int id) const;
private:
  HTable   _htab;
  int     _maxId;  // the size of _offStr
  int     * _offStr; // offsets of strings in buffer
  int     _curId;
  StringBuffer  _strBuf;
};

Here are the constructor and the destructor of the symbol table. Other methods are just copied from our earlier implementation of the string table, except for the fact that the string buffer now has a dynamically allocated buffer whose size is passed in the constructor.

SymbolTable::SymbolTable (int size)
: _curId (0),
  _maxId (size),
  _htab (size + 1),
  _strBuf (size * 10)
{
  _offStr = new int [size];
}

SymbolTable::~SymbolTable ()
{
  delete []_offStr;
}

The values used to initialize the hash table and the string buffer are a bit heuristic.

Store

Our calculator can also deal with symbolic variables. The user creates a variable by inventing a name for it and then using it in arithmetic operations. Every variable has to be initialized—assigned a value in an assignment expression—before it can be used in evaluating other expressions. To store the values of user-defined variables, our calculator will need some kind of "memory." We will create a class Store that contains a fixed number, called size, of memory cells. Each cell can store a value of the type double. The cells are numbered from zero to size-1. Each cell can be in either of two states—uninitialized or initialized.

enum { stNotInit, stInit };

The association between a symbolic name—a string—and the cell number is handled by the symbol table. For instance, when the user first introduces a given variable, say x, the string "x" is added to the symbol table and assigned an integer, say 3. From that point on, the value of the variable x will be stored in cell number 3 in the Store object.

We would also like to preinitialize the symbol table and the store with some useful constants like e (the base of natural logarithms) and pi (the ratio of the circumference of a circle to its diameter). We would like to do it in the constructor of Store, so we need to pass it a reference to the symbol table. Now here's a little snag: We want to put the definition of the class Store in a separate header file, store.h. The definition of the class SymbolTable is in a different file, symtab.h. When the compiler is looking at the declaration of the constructor of Store,

Store (int size, SymbolTable & symTab);

it has no idea what SymbolTable is. The simple-minded solution is to include the file symtab.h in store.h. There is nothing wrong with doing that, except that it burdens the compiler with the processing of one more file whenever it's processing symtab.h or any file that includes it. In a really big project, with a lot of header files including one another, this might become a real headache. Also, if you're using any type of dependency checker, it will assume that a change in symtab.h requires the recompilation of all the files that include it directly or indirectly. In particular, any file that includes store.h will have to be recompiled too. All this unnecessary processing would be done because we needed to let the compiler know that SymbolTable is a name of a class. Why don't we just say that? Indeed, the syntax of such a forward declaration is as follows:

class SymbolTable;

As long as we are only using pointers or references to SymbolTable, this will do. We don't need to include symtab.h.

On the other hand, a forward declaration would not be sufficient if we wanted to call any of the methods of SymbolTable (including the constructor or the destructor) or if we tried to embed or inherit from SymbolTable.

Here's the definition of Store:

class SymbolTable; // forward declaration

class Store
{
public:
  Store (int size, SymbolTable & symTab);
  ~Store ()
  {
   delete []_cell;
   delete []_status;
  }
  bool IsInit (int id) const
  {
   return (id < _size && _status [id] != stNotInit);
  }
  double Value (int id) const
  {
   assert (IsInit (id));
   return _cell [id];
  }
  void SetValue (int id, double val)
  {
   if (id < _size)
   {
     _cell [id] = val;
     _status [id] = stInit;
   }
  }
private:
  int       _size;
  double    * _cell;
  unsigned char * _status;
};

Store contains two arrays: the array of cells and the array of statuses (initialized or uninitialized). The arrays are initialized in the constructor and deleted in the destructor. We also store the size of these arrays (it's used for error checking). The client of Store can check whether a given cell has been initialized, get the value stored there, as well as set (and initialize) this value.

Why am I using two arrays instead of a single array of two-field objects? I could have defined a class Cell:

class Cell
{
  // ...
private:
  double     _value;
  unsigned char   _status;
};

I could have had a single array of Cells in Store instead of two separate arrays for values and statuses.

Both solutions have their merits. Using Cell improves code understandability and maintenance. On the other hand, using two separate arrays may be more space efficient. How come? Because of the alignment of data.

On most computer architectures it's cheaper to retrieve data from memory if it's aligned on a 32-bit or 64-bit boundary. So, unless you specify otherwise, the compiler will force the alignment of user-defined data structures on such boundaries. In particular, it might add padding to your data structures. It's very likely that the compiler will add 3 (or even 7) bytes of padding to every Cell. This way, the size of a Cell in memory will be guaranteed to be a multiple of 32 (or 64) bits, and accessing an array of Cells will be very fast.

As long as you're dealing with reasonably small arrays, you shouldn't care. But if your program uses lots of memory, you might want to be more careful. In our implementation we tried to reduce the memory overhead by declaring the array _status to be an array of bytes (unsigned chars). In fact, we could get away with an array of bits. After all, status is a two-valued variable and can be encoded using a single bit. Implementing a bit array is nontrivial and involves explicit bitwise operations on every access, but in some cases it might save you oodles of memory.

So here's a rule: If you anticipate that you might have to shrink your data structures because of memory constraints, implementing the shrinkable part separately will give you more flexibility. In our case, we could, in the future, reimplement the _status array as a bit array without changing much code around it. On the other hand, if you anticipate that you might have to add more undersized variables to each element of the array, you'd be better off combining them into a single class. In our case, if we expected that we might need, say, some kind of type enumeration for every variable, we could easily add it to the Cell class.

Making choices like this is what makes programming interesting.

The constructor of Store is defined in the source file store.cpp. Since the constructor calls actual methods of the SymbolTable, the forward declaration of this class is no longer sufficient and we need to explicitly include the header symtab.h in store.cpp.

Store::Store (int size, SymbolTable & symTab)
: _size (size)
{

  _cell = new double [size];
  _status = new unsigned char [size];
  for (int i = 0; i < size; ++i)
   _status [i] = stNotInit;

  // add predefined constants
  // Note: if more needed, do a more general job
  std::cout << "e = " << std::exp (1) << std::endl;
  int id = symTab.ForceAdd ("e", 1);
  SetValue (id, std::exp (1));
  std::cout << "pi = " << 2 * std::acos (0.0)
     << std::endl;
  id = symTab.ForceAdd ("pi", 2);
  SetValue (id, 2.0 * std::acos (0.0));
}

We add the mapping of the string "e" of size 1 to the symbol table and then use the returned integer as a cell number in the call to SetValue. The same procedure is used to initialize the value of pi.

Function Table

For a good scientific calculator, built-in functions are a must. We have to be able to calculate square roots, logarithms, trigonometric functions, and so on. We are quite lucky because the standard C library implements most of the basic math functions. All we need is for the parser to recognize a function call and then call the appropriate library function. The only tricky part is to make the connection between the function name—the string recognized by the parser—and the call to the appropriate function.

One way would be to create a multi-way conditional that compares the string to a list of predefined function names, and, when successful, calls the corresponding function.

if (std::strcmp (string, "sin") == 0)
{
  result = sin (arg);
}
else if ...
...

As long as the number of built-in functions is reasonably small, this solution is good enough. Let's pretend though that instead of a toy calculator we're writing an industrial-strength program that will have to handle hundreds, if not thousands, of built-in functions. The problem then becomes: Given a string, match it against hundreds of predefined strings. Clearly, doing hundreds of string comparisons every time is unacceptable.

But wait! We already have a string-matching object—the symbol table. Since it's implemented as a hash table, it can perform a match in constant time, independent of the size of the table. The symbol table converts a string into an integer. We can prefill the table with built-in function names (just like we did with built-in constants) and dispatch the function calls based on integers rather than strings. We could, for instance, insert the string "sin" in the 0th slot of the symbol table, "cos" in the first slot, and so on, and then dispatch calls using a switch statement:

case 0:
result = sin (arg);
  break;
case 1:
  result = cos (arg);
  break;
...

A switch statement that uses a set of consecutive labels,—0, 1, 2, and so on—is implemented by the compiler as a jump table with a constant switching time independent of the number of labels. This seems like a perfect, constant-time solution.

But how do we make sure that sin always corresponds to 0, cos to 1, and so on? Well, we can always initialize the symbol table with these strings in this particular order. After all, we know that the symbol table assigns consecutive indexes starting with zero. Is it okay, though? These are implementation secrets of the symbol table. What if the next person who maintains our program rewrites the symbol table to use an even better algorithm—one that doesn't assign consecutive indexes starting with zero?

And how about expandability of such code? Suppose that at some point in the future we want to add one more built-in function. What kind of changes will we have to make to this implementation? We'll have to

• Add one more case to the switch statement

• Add one more string to the symbol table

• Make sure that the string inserted at the offset is the case label of the corresponding function

Notice what we've just done. We've written a metaprogram—a set of instructions to be followed in order to add a new built-in function to our calculator. These are not machine instructions; these are instructions for the programmer. In fact, they don't appear anywhere in the program, not even as comments—they're implicit. This kind of invisible metacode adds to the hidden complexity of a program. What does metacode describe? It describes the steps to be taken to implement the most likely extension to the program, as well as the assertions that have to be preserved when making such extensions.

When comparing various implementations, take into account not only the complexity of the code but also the complexity of the metacode.

Let's see if we can find a better implementation for built-in functions. Optimally, we would like to have some kind of table listing all the functions. (It's almost always a good idea to shift the complexity from code to data structures.) Adding a new function would be equivalent to adding a new entry to this table. The metaprogram for such an implementation would consist of a single statement:

• Add a new entry to the function array.

To make a connection between data and executable code we need a new device: pointers to functions. A pointer to a function is just like a regular pointer, but instead of pointing to data it points to executable code. By using a pointer to data you can read or modify data; by using a pointer to a function you can call functions. Just like with any other type of pointer, we'll have to be able to

• Declare a pointer to a function

• Initialize a pointer to point to a particular function

• Make a function call through a pointer

For instance, we may declare a pointer to a function taking a double (as an argument) and returning a double. There are many such functions and we can initialize the pointer to point to any one of these. In particular, we may initialize the pointer to point to the function double sin (double x). After that, if we make a function call through our pointer, we'll be calling sin. Had we initialized the pointer to point to double cos (double x), we would have called cos instead. The beauty of a pointer to a function is that the same pointer can point to different functions during the execution of the program. The part of the program that makes the function call doesn't have to know what function it's calling.

Let's look at some actual code to see what the syntax looks like. First, let's declare a pointer pFun to a function taking a double and returning a double:

double (* pFun) (double x);

Compare it with the declaration of a function sin taking a double and returning a double:

double sin (double x);

Why did we have to enclose the asterisk and the pointer name within parentheses? We had to do it in order to distinguish the declaration of a pointer to a function from a declaration of a function returning a pointer. Without the parentheses,

double * pFun (double x);

declares a function taking a double and returning a pointer to double. Quite a difference!

You can declare a pointer to any type of a function by taking the declaration of any function of this type and replacing the function name with (* pFun). Of course, you can use an arbitrary name instead of pFun.

Remember the function strtod? Its declaration was

double strtod (char const * str, char ** ppEnd);

A pointer to a function of this type would be declared as follows:

double (* pStrtod) (char const * str, char ** ppEnd);

It's that simple!

Because of pointers to functions, we have to augment the rules of reading declarations. We start reading backwards, as usual: pStrtod is a pointer...But when we hit the parenthesis, we immediately go to the matching parenthesis and change the direction of parsing. The first thing we see now is a left parenthesis that starts the argument list. A parenthesized argument list means that we're dealing with a function, so we continue reading: ...to a function taking str, which is a pointer to a const char, and ppEnd, which is a pointer to a pointer to a char. Here we hit the closing parenthesis, so we zigzag back to where we left our leftward scanning and continue: ...returning double. Similarly, when we encounter a left square bracket, we know we're dealing with an array, so, for instance

int (* pArr) [3];

reads like this:

<- pArr is a pointer -> to an array of three <- integers.

The arrows mark the change of direction. Let's try something more complicated:

double (* (* pFunArr) [6]) (double x);

<- pFunArr is a pointer -> to an array of six <- pointers -> to functions taking double x <- and returning a double.

Finally, as an exercise to the reader, a nice little declaration:

double (* (* pFunFunFun)(double (* pFun)(double x)))(double x);

Please don't try these at home!

Now for the second step: the initialization. In order to make the pointer point to a function, we have to take the address of the function and assign it to the pointer. It so happens that the name of the function is the address of the function. We can therefore initialize our pointer like this:

double (* pFun) (double x) = std::sin;

or do the assignment at a later point:

pFun = std::sin;

Finally, in order to invoke a function through a pointer, we dereference the pointer and pass the appropriate argument(s):

double x = 3.1415;
double y = (* pFun) (x);

Pointers to functions can be used as building blocks in more complex data structures such as arrays, classes, pointers to pointers, and so on. To simplify the declarations of such data structures, type definitions are often used.

All our built-in functions take one argument of the type double and return a result which is also double, so we start our implementation of the built-in function table with a type definition:

typedef double (*PtrFun) (double);

The connection between a function and its string name is established through the class FunctionEntry.

class FunctionEntry
{
public:
  PtrFun   pFun;
  char*   strFun;
};

You might be wondering why we've made all the data members of this class public but not provided a constructor to initialize them. That's because we want to be able to initialize them explicitly, like this:

FunctionEntry funEntry = { std::sin, "sin" };

This kind of initialization, where you assign values directly to the object's data members, is possible if and only if the object doesn't have both private data and a constructor. Still, I haven't explained why anyone would want to use this kind of direct initialization instead of simply providing an appropriate constructor. Here's why:

const int maxIdFun = 16;

FunctionEntry funArr [maxIdFun] =
{
  std::log,   "log",
  std::log10,  "log10",
  std::exp,   "exp",
  std::sqrt,  "sqrt",
  std::sin,   "sin",
  std::cos,   "cos",
  std::tan,   "tan",
  CoTan,     "cotan",
  std::sinh,  "sinh",
  std::cosh,  "cosh",
  std::tanh,  "tanh",
  std::asin,  "asin",
  std::acos,  "acos",
  std::atan,  "atan",
  0,      ""
};

In one fell swoop we've been able to initialize the whole array of FunctionEntries. That's exactly what we were striving for. Notice how easy it will be now to add a new built-in function: Just add one more line with a function pointer and string name between any two lines in this list and it'll just work. (You'll need to increment maxIdFun as well, but that's something the compiler will remind you of, if you forget.)

Now that we're through with the preliminaries, let's get back to our original problem: the initialization of the symbol table with built-in function names. This should be done in the construction stages of the program—the calculator is not ready to be used unless the symbol table is filled in advance. We will therefore define an object called the FunctionTable with the dual purpose of initializing the symbol table with the names and translating symbol IDs to function pointers for all the built-in functions.

class SymbolTable;

class FunctionTable
{
public:
  FunctionTable (SymbolTable & symTab,
      FunctionEntry funArr []);
  int Size () const { return _size; }
  PtrFun GetFun (int id) const
  {
   return _pFun [id];
  }
private:
  PtrFun  _pFun [maxIdFun];
  int   _size;
};

The constructor of the FunctionTable takes a reference to the symbol table and fills it with strings from our array funArr of FunctionEntrys. At the same time, it copies corresponding function pointers into its own array. (Strictly speaking, the copying could be avoided if we let the function table use the function array directly—that's an optimization that's best left as an exercise to the reader.)

FunctionTable::FunctionTable (
   SymbolTable & symTab,FunctionEntry funArr [])
  : _size (0)
{
  for (int i = 0; i < maxIdFun; ++i)
  {
   int len = std::strlen (funArr [i].strFun);
   if (len == 0)
     break;
   _pFun [i] = funArr [i].pFun;
   std::cout << funArr[i].strFun << std::endl;
   int j = symTab.ForceAdd (funArr [i].strFun, len);
   assert (i == j);
   ++_size;
  }
}

Notice the very important assertion in the loop. We're making sure that the assumption that the symbol table assigns consecutive indexes to our functions is indeed true. We want the string "log" to correspond to ID 0, because we store the pointer to the function log at offset 0, and so on.

All of the built-in functions so far have been library functions (defined in the standard C library) except for one, the cotangent. The cotangent is just the inverse of the tangent, so it's easy to write our own implementation of it. The only tricky part is dealing with the inverse of zero—division by zero causes an exception, which would terminate the program. That's why we test for zero and return HUGE_VAL (defined in <cmath>) as its inverse. That's not entirely correct (the result of division by zero is undefined), but it'll do for now:

double CoTan (double x)
{
  double y = std::tan (x);
  if (y == 0)
  {
   std::cout << "cotan of " << x << " undefined\n";
   return HUGE_VAL;
  }
  return 1.0 / y;
}

Note that the appropriate line in the initialization of funArr,

CoTan, "cotan",

contains the pointer to our own implementation of cotangent, namely CoTan. To let the compiler know what CoTan is and how to call it correctly, I added the declaration of this function at the top of the file FunTab.cpp. The difference between a declaration and the definition is that the former doesn't provide the implementation; it only specifies the function's signature—the number and the types of arguments and the return type.

double CoTan (double x);

A function declaration, also called a prototype, is always followed by a semicolon. If you try to call (or, as in our case, assign to a pointer) a function that hasn't been prototyped, the compiler will tell you about the "missing prototype." Unlike a definition, a declaration can be repeated in the same file or in different files. You can also put declarations inside a header file.

Objects, variables, and other data structures can also be declared before being defined. However, since a definition of a data structure doesn't necessarily require its initialization, it would be hard for the compiler to distinguish them from declarations. For instance,

int x;

is always interpreted as a definition. Upon seeing this definition, the compiler will allocate storage (either global or on the stack) for the variable x. If you repeat this definition or put it in a header file that's included in more than one implementation file, you'll get an error—"symbol multiply defined."

Therefore, a declaration of data has to be preceded by the keyword extern. For instance, to tell the compiler that there is an integer variable called x defined in some implementation file, you'd declare it like this (no initialization is allowed):

extern int x;

Similarly, to tell everybody that there is an array funArr that can be used in other files, we'll add the following declaration to the header FunTab.h:

extern FunctionEntry funArr [];

To summarize: We went through quite a bit of trouble in order to produce an implementation that avoids some of the hidden complexities of something we called metacode. In this particular case, it was well worth the effort because we knew that the table of built-in functions would be the first thing to be modified in the future. We made sure such modifications would be easy and virtually foolproof. We have gathered them in one place (the initialization of funArr), made trivial mistakes compiler-detectable (forgetting to update maxIdFun), and positioned an assertion in a strategic place (inside the FunctionTable constructor). The function table works, but its implementation is not yet totally satisfactory from a design point of view. We'll come back to it later.

Nodes

We'll use the implementation of the parsing tree from the polymorphism article. It's time to add a few more node types (see Figure 3).

Figure 3 The hierarchy of node classes.

Corresponding to built-in functions are the objects of type FunNode.

class FunNode: public UniNode
{
public:
  FunNode (PtrFun pFun, Node * pNode)
   : UniNode (pNode), _pFun (pFun)
  {}
  double Calc () const;
private:
  PtrFun    _pFun;
};

The base class UniNode is very similar to BinNode, except that it has one child instead of two (we'll also derive UMinusNode from this class). The Calc method of FunNode illustrates the syntax for the invocation of a function through a pointer.

double FunNode::Calc () const
{
  assert (_pFun != 0);
  return (*_pFun)(_pNode->Calc ());
}

By the way, there's an alternative syntax for calling a function through a pointer. You can simply treat the pointer as if it was a function name, like this:

return _pFun (_pNode->Calc ());

The assignment node is a little trickier. It's a binary node with the children corresponding to the left and right side of the assignment. For instance, the parsing of the line

x = 1

will produce an assignment node with the left node corresponding to the symbolic variable x and the right node corresponding to the value 1. First of all, not every node can be a left side of an assignment. For instance,

2 = 1

is clearly unacceptable. We need a way of deciding whether a given node can appear on the left side of an assignment—whether it can be an lvalue. In our calculator, the only possible lvalue is a symbolic variable.

To be able to verify whether a given node is an lvalue, we'll add the virtual method IsLvalue to the base class Node and provide the default implementation.

bool Node::IsLvalue () const
{
  return false;
}

The only type of node that will override this default will be the symbolic-variable node. We'll make the parser perform the IsLvalue test on the left side of the assignment before creating the AssignNode. Inside the assignment node, we'll only assert that the parser did its job.

class AssignNode : public BinNode
{
public:
  AssignNode (Node * pLeft, Node * pRight)
   : BinNode (pLeft, pRight)
  {
   assert (pLeft->IsLvalue ());
  }
  double Calc () const;
};

The Calc method calls the Assign method of the left child with the value calculated by the right child. Again, we'll add the virtual method Assign to the base class Node, together with the default implementation that does nothing.

virtual void Assign (double value) {}

Only the variable node will override this implementation.

Having said that, the implementation of AssignNode::Calc is straightforward:

double AssignNode::Calc () const
{
  double x = _pRight->Calc ();
  _pLeft->Assign (x);
  return x;
}

Next, we have to define the node corresponding to a symbolic variable. The value of the variable is stored in the Store object. VarNode needs access to this object in order to calculate itself. But, as we've just stated, VarNode can also be used on the left side of an assignment, so it has to override the virtual methods IsLvalue and Assign.

class Store;

class VarNode: public Node
{
public:
  VarNode (int id, Store & store)
   : _id (id), _store (store) {}
  double Calc () const;
  bool IsLvalue () const;
  void Assign (double val);
private:
  const int _id;
  Store & _store;
};

double VarNode::Calc () const
{
  double x = 0.0;
  if (_store.IsInit (_id))
   x = _store.Value (_id);
  else
   std::cout << "Use of uninitialized variable\n";
  return x;
}

void VarNode::Assign (double val)
{
  _store.SetValue (_id, val);
}

bool VarNode::IsLvalue () const
{
  return true;
}

There are a few more node classes that the parser needs: SubNode for subtractions, DivideNode for divisions, and UMinusNode for unary negations. They're very simple to implement.

Parser

The parser requires a major makeover. Let's start with the header file, parse.h. It contains a lot of forward declarations :

class Node;
class Scanner;
class Store;
class FunctionTable;
class SymbolTable;

All these classes are mentioned in parse.h either through pointers or references—there's no need to include the header files that define them.

The class Parser has a constructor that takes references to all the major objects it will need in order to parse the stream of tokens from the Scanner. It needs Store to create VarNodes, FunctionTable to create FunNodes, and the SymbolTable to recognize variables and function names. Once the Parser is created, we can only ask it to evaluate the expression passed to it in the Scanner. The Eval method has the side effect of printing the result on the screen. (If you're cringing now, I promise you'll be relieved when you read the next chapter of this book.)

Parser uses a number of private methods to parse expressions, terms, and factors, and a method to execute the evaluation of the expression tree. Private methods are a useful device for code structuring. They can't be called from outside of the class—they're just helper functions used in the implementation of other (public or private) methods.

class Parser
{
public:
  Parser (Scanner & scanner,
   Store & store,
   FunctionTable & funTab,
   SymbolTable & symTab);
  ~Parser ();
  Status Eval ();
private:
  void  Parse();
  Node * Expr();
  Node * Term();
  Node * Factor();
  void  Execute ();

  Scanner    & _scanner;
  Node      * _pTree;
  Status      _status;
  Store     & _store;
  FunctionTable & _funTab;
  SymbolTable  & _symTab;
};

The constructor (we're already looking at the implementation file parse.cpp) initializes all of the Parser's private member variables.

Parser::Parser (Scanner & scanner,
     Store & store,
     FunctionTable & funTab,
     SymbolTable & symTab)
: _scanner (scanner),
  _pTree (0),
  _status (stOk),
  _funTab (funTab),
  _store (store),
  _symTab (symTab)
{}

The destructor recursively deletes the parse tree:

Parser::~Parser ()
{
  delete _pTree;
}

The Eval method calls private methods to parse the input and execute the calculation:

Status Parser::Eval ()
{
  Parse ();
  if (_status == stOk)
   Execute ();
  else
   _status = stQuit;
  return _status;
}

Execute calls the Calc method of the top node of the parse tree and prints the result of the (recursive) calculation:

void Parser::Execute ()
{
  if (_pTree)
  {
   double result = _pTree->Calc ();
   std::cout << " " << result << std::endl;
  }
}

The parsing starts with the assumption that everything is an expression.

void Parser::Parse ()
{
  _pTree = Expr ();
}

The expression starts with a term. The term can be followed by an operator that binds terms—the plus sign, minus sign, or assignment sign—or nothing at all. These correspond to the four productions (see our original description of the grammar):

Expression is Term + Expression
or Term - Expression
or Term = Expression // the Term must be an lvalue
or just Term

As you might recall, these productions define right-associative arithmetics. Unfortunately, that also means that the assignment is right-associative and an expression like this is legal:

1 + x = 2

It's parsed as

1 + (x = 2)

For the time being, we'll have to live with this flaw. It will be fixed in Part 2 of this book.

According to our grammar, after parsing a term we should ask the Scanner for the next token and test it against tPlus, tMinus, and tAssign.

Immediately after a token is recognized, we tell the Scanner to accept it.

Node * Parser::Expr ()
{
  Node * pNode = Term ();
  EToken token = _scanner.Token ();
  if (token == tPlus)
  {
   _scanner.Accept ();
   Node * pRight = Expr ();
   pNode = new AddNode (pNode, pRight);
  }
  else if (token == tMinus)
  {
   _scanner.Accept ();
   Node * pRight = Expr ();
   pNode = new SubNode (pNode, pRight);
  }
  else if (token == tAssign)
  {
   _scanner.Accept ();
   Node * pRight = Expr ();
   if (pNode->IsLvalue ())
   {
     pNode = new AssignNode (pNode, pRight);
   }
   else
   {
     _status = stError;
     delete pNode;
     pNode = Expr ();
   }
  }
  return pNode;
}

Error recovery in parsers involves a bit of heuristics. Here, for instance, when we detect that the expression on the left side of an assignment is not an lvalue, we discard it and proceed to evaluate the right side. In more complex parsers it makes sense to continue parsing after the first error, if only to be able to report more errors to the user. We'll get more into error processing in Part 2 of this book.

We proceed in a similar fashion with Term, following the productions:

Term is Factor * Term
or Factor / Term
or just Factor

The method Term should look like this:

Node * Parser::Term ()
{
  Node * pNode = Factor ();
  if (_scanner.Token () == tMult)
  {
   _scanner.Accept ();
   Node * pRight = Term ();
   pNode = new MultNode (pNode, pRight);
  }
  else if (_scanner.Token () == tDivide)
  {
   _scanner.Accept ();
   Node * pRight = Term ();
   pNode = new DivideNode (pNode, pRight);
  }
  return pNode;
}

A Factor, in turn, can be one of these:

Factor is ( Expression ) // parenthesized expression
or Number // literal floating-point number
or Identifier ( Expression ) // function call
or Identifier // symbolic variable
or - Factor // unary minus

Node * Parser::Factor ()
{
  Node * pNode;
  EToken token = _scanner.Token ();

  if (token == tLParen)
  {
   _scanner.Accept (); // accept '('
   pNode = Expr ();
   if (_scanner.Token() != tRParen)
     _status = stError;
   else
     _scanner.Accept (); // accept ')'
  }
  else if (token == tNumber)
  {
   pNode = new NumNode (_scanner.Number ());
   _scanner.Accept ();
  }
  else if (token == tIdent)
  {
   char strSymbol [maxSymLen];
   int lenSym = maxSymLen;
   // copy the symbol into strSymbol
   _scanner.GetSymbolName (strSymbol, lenSym);
   int id = _symTab.Find (strSymbol);
   _scanner.Accept ();
   if (_scanner.Token() == tLParen) // function call
   {
     _scanner.Accept (); // accept '('
     pNode = Expr ();
     if (_scanner.Token () == tRParen)
      _scanner.Accept (); // accept ')'
     else
      _status = stError;
     if (id != idNotFound && id < _funTab.Size ())
     {
      pNode = new FunNode (
        _funTab.GetFun (id), pNode);
     }
     else
     {
      std::cout << "Unknown function \"";
      std::cout << strSymbol << "\"\n";
     }
   }
   else
   {
     if (id == idNotFound)
      id = _symTab.ForceAdd (strSymbol, lenSym);
     pNode = new VarNode (id, _store);
   }
  }
  else if (token == tMinus) // unary minus
  {
   _scanner.Accept (); // accept minus
   pNode = new UMinusNode (Factor ());
  }
  else
  {
   _scanner.Accept ();
   _status = stError;
   pNode = 0;
  }
  return pNode;
}

To see how the parser works, let's step through a simple example. Suppose that the user typed this:

x = 1

First, a scanner containing the input string is created. It scans the first token and decides that it's an identifier, tIdent. Next, the parser is called to Eval the expression. It starts parsing it by assuming that it is, indeed, an expression.

_pTree = Expr ();

The expression must start with a term, so Expr calls Term.

Node * pNode = Term ();

Term, on the other hand, expects to see a Factor.

Node * pNode = Factor ();

Finally, Factor looks at the first token,

EToken token = _scanner.Token ();

and compares it to tLParen, tNumber, tIdent, and tMinus. In our case, the first token is an identifier, tIdent. It then asks the scanner for the name of the symbol (it's "x") and searches for it in the symbol table. Now it's done with the first token, so it tells the scanner to accept the token.

// copy the symbol into strSymbol
_scanner.GetSymbolName (strSymbol, lenSym);
int id = _symTab.Find (strSymbol, lenSym);
_scanner.Accept ();

The scanner scans for the next token, which is the assignment operator tAssign. The parser looks at this token to see whether it's a left parenthesis—that would signify a function call. Since it isn't, the parser creates a VarNode using the ID of the symbol found in the symbol table. If this is a new symbol for which there wasn't any ID, the parser just adds it to the symbol table and creates a new ID.

if (id == idNotFound)
id = _symTab.ForceAdd (strSymbol, lenSym);
pNode = new VarNode (id, _store);

Factor is now done and it returns a pointer to the node it has just created. Back to Term. It has a node, so now it looks at the next token to see whether it's either tMult or tDivide. Since it's not, it returns the same node. Back to Expr. Again, a look at the token: Is it tPlus, tMinus, or tAssign? It's tAssign! It accepts the token. (The scanner positions itself at tNumber, whose value is 1.) So far, the parser has seen a node followed by an equal sign. An equal sign can be followed by an arbitrary expression, so Expr now calls itself to parse the rest of the input, which is "1".

_scanner.Accept ();
Node* pRight = Expr ();

Expr again goes through Term and Factor, which creates a NumNode.

pNode = new NumNode (_scanner.Number ());
_scanner.Accept ();

Back to Term and Expr with the new node pRight. The parser has now seen a node, pNode, followed by the equal sign and another node, pRight. It looks very much like an assignment statement, except that we don't know whether pNode represents an lvalue. In our case, the node, VarNode, does. An assignment node is created:

if (pNode->IsLvalue ())
{
  pNode = new AssignNode (pNode, pRight);
}

Expr returns this AssignNode to Parse. The parse tree now looks like Figure 4.

Figure 4 Parse tree of the expression x = 1.

Since the parsing was successful, we call Execute, which calls _pTree->Calc(). The virtual Calc method of AssignNode calculates the value of the right node—NumNode returns 1—and calls the Assign method of VarNode with this value. VarNode has access to Store and stores the value of 1 in the slot corresponding to "x".