I love Yacc, but the discriminating union stack does present a challenge.
I don't know whether you are using C or C++. I've modified Yacc to generate C++ for my own purposes, but this solution can be adapted to C.
My preferred solution is to pass an interface to the owner down the parse tree, rather than constructed objects up the stack. Do this by creating your own stack outside of Yacc's. Before you invoke a non-terminal that allocates an object, push the owner of that object to this stack.
For example:
class IExpressionOwner
{
public:
virtual ExpressionAdd *newExpressionAdd() = 0;
virtual ExpressionSubstract *newExpressionSubtract() = 0;
virtual ExpressionMultiply *newExpressionMultiply() = 0;
virtual ExpressionDivide *newExpressionDivide() = 0;
};
class ExpressionAdd : public Expression, public IExpressionOwner
{
private:
std::auto_ptr<Expression> left;
std::auto_ptr<Expression> right;
public:
ExpressionAdd *newExpressionAdd()
{
ExpressionAdd *newExpression = new ExpressionAdd();
std::auto_ptr<Expression> autoPtr(newExpression);
if (left.get() == NULL)
left = autoPtr;
else
right = autoPtr;
return newExpression;
}
...
};
class Parser
{
private:
std::stack<IExpressionOwner *> expressionOwner;
...
};
Everything that wants an expression has to implement the IExpressionOwner interface and push itself to the stack before invoking the expression non-terminal. It's a lot of extra code, but it controls object lifetime.
Update
The expression example is a bad one, since you don't know the operation until after you've reduced the left operand. Still, this technique works in many cases, and requires just a little tweaking for expressions.