What is the best way to prevent memory leaks in a yacc-based parser?

Question

Yacc does not allow passing objects. Since% union can only contain POD types, complex objects must be new'd and passed in with a pointer. If a syntax error occurs, the yacc parser simply stops working, and links to all created objects are lost.

The only solution I came up with is that the whole new'd object inherits a certain base class, is added to the container when it is allocated, and if there is an error, the entire contents of this container can be deleted.

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

Please do not tell me to choose another parser.

Answer 1

I like Yacc, but the discriminating union stack is a challenge.

I do not know if you use C or C ++. I modified Yacc to generate C ++ for my own purposes, but this solution can be adapted to C.

My preferred solution is to pass the interface to the owner in the parse tree, rather than constructing objects on the stack. Do this by creating your own stack outside of Yacc's. Before calling the non-terminal that allocates an object, push the owner of this object onto this stack.

For instance:

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; ... }; 

All that the expression wants is to implement the IExpressionOwner interface and push itself onto the stack before calling the expression without a term. This is a lot of extra code, but it controls the lifetime of the object.

Update

An example expression is bad because you do not know the operation until you reduce the left operand. However, this technique works in many cases and requires a little adjustment for expressions.

Answer 2

If this is appropriate for your project, consider using a Boehm garbage collector. Thus, you can freely select new objects and allow the collector to process deleted ones. Of course, there are trade-offs associated with using the garbage collector. You will have to weigh the costs and benefits.

Answer 3

Why is such a parser used? Bison is easily accessible, and (at least on linux) yacc is usually implemented as a bison. You do not need any changes to your grammar to use (other than adding% destructor to solve your problem).

Answer 4

Use smart pointers !

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