Reliable Software Logo

C++ In Action: Language

Nodes

We have to add a few more node types. Corresponding to built-in functions are the objects of type FunNode. A FunNode contains a pointer to function and a child node—the argument to the function. I have a confession to make: When I was writing this program I forgot to add the destructor to FunNode. The program worked fine, it was just leaking memory. Every time a FunNode was constructed and then destroyed, it would leave its child node orphaned. The memory for the whole subnode would never be reclaimed. If you kept this program running for hours and hours (which I never did), it would eventually chew up all its memory and die. I caught this bug by instrumenting the memory allocator when I was writing the second part of the book—The Techniques.

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

The Calc method illustrates the syntax for the invocation of a function through a pointer.

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

The assignment node is a little trickier. It is a binary node with the children corresponding to the left hand side and the right hand 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 hand side of an assignment. For instance

1 + 2 = 1
                    

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

In order to be able to verify if a given node is an lvalue, we will add the virtual method IsLvalue to the base class Node and provide the default implementation

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

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 hand side of the assignment before creating the AssignNode. Here, 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 Assign method of the left child with the value calculated by the right child. Again, we will 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 has to have access to this object in order to calculate itself. But, as we know, VarNode can also be used on the left hand 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
        cout << "Use of uninitialized variable\n";
    return x;
}

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

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

NextNext: Parser