Мне нравится Yacc, но стек различающихся объединений представляет собой проблему.
Я не знаю, используете ли вы C или C ++. Я изменил Yacc для генерации C ++ для своих собственных целей, но это решение можно адаптировать для C.
Мое предпочтительное решение - передавать интерфейс владельцу по дереву разбора, а не создавать объекты в стеке. Сделайте это, создав собственный стек вне Yacc. Прежде чем вызывать нетерминал, который выделяет объект, поместите владельца этого объекта в этот стек.
Например:
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;
...
};
Все, что хочет выражение, должно реализовывать интерфейс IExpressionOwner и помещать себя в стек перед вызовом выражения нетерминально. Это много лишнего кода, но он управляет временем жизни объекта.
Обновление
Пример выражения является плохим, поскольку вы не знаете операцию до тех пор, пока не уменьшите левый операнд. Тем не менее, этот метод работает во многих случаях и требует лишь небольшой настройки для выражений.