Quando un albero di espressione deve contenere puntatori e quando deve contenere valori di sottoespressioni?

Question

Quando un albero di espressione deve contenere puntatori e quando deve contenere valori di sottoespressioni?

#1 da (2 voti)

0

Stavo pensando che dovrebbe contenere dei puntatori:

struct Expr
{
    string sym;
    Expr*[] sub;

    this(self, string sym) {
        this.sym = sym;
    }

    @property auto dup() const {
        auto e = new Expr(sym);

        foreach (s; sub) {
            e.sub ~= s.dup;
        }

        return e;
    }
}

Ma allora quella funzione .dup duplicherà i nodi; N copie del nodo quando in origine c'era solo 1; quindi deve essere molto più complicato di così.

D'altra parte, con i valori di Expr, potrebbe esserci una maggiore proliferazione di oggetti Expr, ad esempio se li stessimo raggruppando.

Quindi, in che modo funziona meglio nei progetti di computazione simbolica?

algorithms evaluation trees computation-expressions

posta EnjoysMath 17.01.2017 - 21:01

fonte

1 risposta

Leggi altre domande sui tag algorithms evaluation trees computation-expressions

Controllo del codice sorgente per il team SaaS API Web vs Entity Framework con pattern di repository che utilizza Xamarin

score 2 · Answer 1

La maggior parte degli alberi di espressioni usa puntatori perché le strutture dati ricorsive sono impossibili da un valore. Per esempio. qualcosa del genere non funzionerà:

struct Expr {
  Expr left;
  Expr right;
  ...
}

Inoltre, gli alberi di espressione di solito contengono più tipi di espressioni differenti. Potrebbero esserci nodi per

espressioni terminali come letterali o variabili,
espressioni unarie come accesso al campo o negazione
espressioni binarie come addizione, moltiplicazione o
espressioni ternarie come condizionali if-then-else.

Nei linguaggi OOP, di solito viene modellato con una gerarchia di classi con un'interfaccia Expr su sottoclassi superiore e varie. Tuttavia, il polimorfismo del sottotipo richiede il puntatore indiretto. Poiché la dimensione di un sottotipo non è nota, non è possibile assegnare un'istanza sottotipo per valore alla memoria allocata per una classe base. Alcune lingue potrebbero nasconderlo in qualche modo.

Nel tuo esempio, stai già utilizzando un puntatore per aggirare questo problema: la Expr[] array . Poiché la memoria dell'array è separata dalla variabile dell'array, questo aggira il problema della dimensione ricorsiva. Dato che (in modo abbastanza insolito) esiste un solo tipo Expr , non si verificano problemi di sottotitoli. (Per caso stai modellando le espressioni S? Anche loro generalmente hanno atomi per letterali e simboli.)

L'uso dei puntatori è interessante se i nodi delle espressioni sono anche immutabili. Qualsiasi trasformazione AST (come la piegatura costante) sostituirà alcuni nodi ma riutilizzerà gli altri nodi invariati. Se possono essere semplicemente agganciati al nuovo AST tramite puntatore, è molto più economico rispetto alla duplicazione dell'intera sottostruttura AST.