Qual è il modo migliore per prevenire perdite di memoria in un parser basato su yacc?

Question

Yacc non consente lo scambio di oggetti.Poiché %union può contenere solo tipi POD, gli oggetti complessi devono essere nuovi e passati tramite puntatore.Se si verifica un errore di sintassi, il parser yacc smette di funzionare e i riferimenti a tutti gli oggetti creati vengono persi.

L'unica soluzione che ho trovato è che tutti i nuovi oggetti ereditino una particolare classe base, vengano aggiunti a un contenitore quando allocato e, se si verifica un errore, tutto in quel contenitore può essere eliminato.

Qualcuno conosce qualche trucco yacc migliore per risolvere questo problema?

Per favore, non dirmi di scegliere un parser diverso.

Answer 1

Adoro Yacc, ma lo stack sindacale discriminante rappresenta una sfida.

Non so se stai usando C o C++.Ho modificato Yacc per generare C++ per i miei scopi, ma questa soluzione può essere adattata al C.

La mia soluzione preferita è passare un'interfaccia al proprietario lungo l'albero di analisi, piuttosto che oggetti costruiti nello stack.Fallo creando il tuo stack esterno a quello di Yacc.Prima di invocare un non terminale che alloca un oggetto, inserisci il proprietario di quell'oggetto in questo stack.

Per esempio:

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;

    ...
};

Tutto ciò che richiede un'espressione deve implementare l'interfaccia IExpressionOwner e inserirsi nello stack prima di invocare l'espressione non terminale.È molto codice aggiuntivo, ma controlla la durata dell'oggetto.

Aggiornamento

L'esempio dell'espressione è negativo, poiché non conosci l'operazione finché non hai ridotto l'operando sinistro.Tuttavia, questa tecnica funziona in molti casi e richiede solo qualche modifica per le espressioni.

Answer 2

Se è adatto al tuo progetto, considera l'utilizzo del Boehm Garbage Collector.In questo modo puoi allocare liberamente nuovi oggetti e lasciare che sia il raccoglitore a gestire le eliminazioni.Naturalmente ci sono dei compromessi nell'utilizzo di un garbage collector.Dovresti valutare costi e benefici.

Answer 3

Utilizzo puntatori intelligenti!

Oppure, se ti senti a disagio nel dipendere da un'altra libreria, puoi sempre usarla auto_ptr dalla libreria standard C++.

Answer 4

Perché l'utilizzo di un parser diverso è un problema del genere?Bison è facilmente disponibile e (almeno su Linux) yacc è solitamente implementato come bison.Non dovresti aver bisogno di modifiche alla grammatica per usarlo (ad eccezione dell'aggiunta di %destructor per risolvere il tuo problema).