Rappresentazione AST omogenea e eterogenea

Question

Rappresentazione AST omogenea e eterogenea

#1 da (5 voti)

5

Quali sono i motivi per scegliere una rappresentazione AST omogenea o eterogenea per l'implementazione di un linguaggio di programmazione complesso specifico per il dominio?

Per essere molto chiari su ciò che sto chiedendo, ecco qualche altro background:

Per omogeneo, intendo un albero costituito da nodi che sono un singolo tipo generico . Per esempio, penso che questa domanda sia realmente indipendente dal linguaggio, ma usando una struct di tipo C ++ per l'illustrazione, considererei questo un nodo di sintassi astratto omogeneo e minimale:

struct Node {
  int tag;
  void *data;

  Node *first_child;
  Node *next_sibling;
};

Per eterogeneo, intendo un albero costituito da nodi che sono singoli tipi multipli (ad esempio uno per ogni produzione di grammatica). Per esempio, non voglio assumere un particolare linguaggio, ma usando ancora le strutture simili a C ++ per l'illustrazione, considererei questi tipi parte di una gerarchia usata per costruire un albero di sintassi astratto eterogeneo:

struct Node {};

struct Integer_Node : Node {
  int value;
};

struct Plus_Node : Node {
  Node *right;
  Node *left;
};

struct If_Statement : Node {
  Node *Condition;
  Node *Then_Expression;
  Node *Else_Expression;  
};

// ... more types, depending on the language ...

Nel corso degli anni, ho implementato diversi piccoli compilatori speciali, di solito in un modo molto specifico. Non ho mai usato un vero "AST" perché solitamente la traduzione diretta della sintassi è stata abbastanza buona.

Ora sono in procinto di progettare e implementare un nuovo linguaggio molto più complesso, dove costruirò un AST e poi lo passerò sopra con più passaggi per la verifica, l'analisi semantica e così via.

Ad esempio, sembra che l'uso di uno schema omogeneo riduca la quantità di codice in anticipo, ma mi chiedo se un sistema eterogeneo si ripaga meglio a lungo termine per ragioni che non sto considerando. D'altra parte, lo schema eterogeneo sembra che possa trarre beneficio dal controllo di tipo statico del compilatore, dalla distribuzione del metodo virtuale, ecc., Ma mi chiedo se una cosa del genere sia davvero molto utile nello sviluppo di passaggi semantici e così via.

Fondamentalmente, spero di ottenere alcune informazioni da coloro che potrebbero avere qualche esperienza reale qui. Ho letto molti libri di compilatori e ho una discreta quantità di esperienza di scrittura di compilatori di base, ma non ho visto questa particolare dicotomia affrontata in nessuna letteratura che riesco a mettere le mani su.

data-structures compiler trees

posta wjl 27.05.2013 - 04:02

fonte

1 risposta

Leggi altre domande sui tag data-structures compiler trees

Quanta attenzione dovrebbe essere prestata ai brevetti nello sviluppo del software? Progettazione OOP - Un possibile approccio errato rende impossibile l'implementazione in codice

score 5 · Accepted Answer

Per me, il grande vantaggio dell'AST eterogeneo è che forma un tipo di dichiarazioneswitch forzata e annotata (assumendo un linguaggio simile a C).

Per l'AST omogeneo di solito si finisce con qualche tipo di routine o classe con una grande dichiarazione switch . È necessario tenere traccia di quale nodo figlio è ciò che si è. "Il primo figlio è il condizionale, il secondo il vero blocco, il terzo il falso blocco." Ogni volta che cambi il codice, ti ritrovi facilmente a creare un'immagine mentale della sintassi DSL ripetutamente.

Naturalmente puoi documentare molto, ma un buon programma dovrebbe essere il più possibile auto-documentante. L'AST eterogeneo fa proprio questo.

Inoltre, puoi facilmente trasformare un AST eterogeneo in uno omogeneo, ma non viceversa. Aggiungi le informazioni sui tag (che è una buona idea, a meno che la tua lingua supporti una query is-a economica). È possibile aggiungere metodi Node(int index) per restituire i campi con nome. Quindi non perdi nulla in generalità usando l'AST eterogeneo.

Non dirò che l'AST eterogeneo è ideale per il pattern Visitor, poiché è altrettanto facile usare il pattern Strategy con la routine switch omogenea. È è più semplice aggiungere funzionalità specifiche all'AST eterogeneo stesso. Se vuoi trasformarlo in un interprete, tutto ciò che devi fare è aggiungere alcuni metodi di "valutazione".

Considererei un AST omogeneo se ci sono circostanze limitanti . Se è necessario portare il compilatore su un sistema senza lingua OOP disponibile o se è necessario ottimizzare per la velocità. L'AST omogeneo è più facile da combinare con un FSM. Quest'ultimo può anche essere un vantaggio se si desidera avere un compilatore generale multiuso che carichi le regole di sintassi al volo. Ma è più facile iniziare con un AST eterogeneo che genererà quelle tabelle, dopo che il compilatore è stato accuratamente testato.

Quindi, tutto sommato, direi che nessuno degli alberi offre vantaggi specifici in termini di "questo albero aiuta o ostacola, diciamo, 'passaggi semantici'?" Il vantaggio dell'AST eterogeneo è, secondo la mia esperienza, ridurre la quantità di pensiero e concentrazione che devi mettere nella codifica del roba tedioso del compilatore. C'è un sacco di ripetitività e contabilità in corso, quindi lascia che il computer faccia il lavoro per te il più possibile, è il mio motto.