tags:

views:

433

answers:

4

Yacc does not permit objects to be passed around. Because the %union can only contain POD types, complex objects must be new'd and passed around by pointer. If a syntax error occurs, the yacc parser just stops running, and references to all of those created objects are lost.

The only solution I've come up with is that all new'd object inherit a particular base class, be added to a container when allocated, and if there is an error everything in that container can be deleted.

Does anyone know of any better yacc tricks to solve this problem?

Please don't tell me to choose a different parser.

+1  A: 

If it suits your project, consider using the Boehm Garbage collector. That way you can freely allocate new objects and let the collector handle the deletes. Of course there are tradeoffs involved in using a garbage collector. You would have to weigh the costs and benefits.

Ron
A: 

Use smart pointers!

Or, if you're uncomfortable depending on yet another library, you can always use auto_ptr from the C++ standard library.

auto_ptr is a complex object that cannot be passed
David Dolson
+2  A: 

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.

Michael L Perry
can you show how this would be used in the .ypp file?
David Dolson
I accept that the best solution is to create a parallel data structure outside of the syntax parser. It makes the parser non-reentrant, since the parser must access global variables, but I can live with that.
David Dolson
+1  A: 

Why is using a different parser such a problem? Bison is readily available, and (at least on linux) yacc is usually implemented as bison. You shouldn't need any changes to your grammar to use it (except for adding %destructor to solve your issue).

Bison is just GNU's yacc. Same question applies.
David Dolson