Come vengono memorizzate singole righe di codice e funzioni in un Concrete Syntax Tree?

1

Sto cercando di scrivere un semplice compilatore per scopi di apprendimento. Ho letto Dragon Book e Modern Compiler Design e una parte che non capisco è come viene creato e archiviato il Concrete Syntax Tree.

Comprendo che collegando i token prodotti dal Lexer è semplice raccogliere tutti i pezzi di un operatore di assegnazione; ad esempio:

int i = 0;

è piuttosto semplice per raccogliere type , identifier e che stiamo assign su un valore di const_number zero. E capisco come si presenta questo albero sintattico.

E se è assegnato come un'espressione come:

int i = a * b;

Capisco anche come sarebbe questo albero sintattico concreto.

Ma allora diciamo che ho:

int i = functionCall();

Che aspetto ha questo in un albero di sintassi concreto?

Inoltre, considerando un linguaggio come C che è un insieme di funzioni, con una di esse, la funzione main viene indicata come punto di ingresso; come si inserisce tutto questo in un albero di sintassi concreto?

Ciascuno ha il suo albero?

La creazione di un'erarchia di tipi Node per il mio albero, ognuno con le componenti specifiche di cui ha bisogno ha senso per me; ma non come chiama questo fattore nella funzione; a meno che ogni singola funzione sia stata sottolineata.

Informazioni aggiuntive dai commenti

Quindi, diciamo che ho un codice che assomiglia a:

int AddProc(int i, int j)
{
    return i + j;
}

void main()
{
    int x = 8;
    int y = 0;
    int z = x + y;
    x = AddProc(y,z);
}

Il flusso di token inizia dall'alto verso il basso; semplice; ogni token indica al parser se è un TYPE o ID o CONST o ADD_OP qualunque. Il primo stadio del parser consiste nel produrre un Concrete Syntax Tree, che viene poi trasformato in un Abstract Syntax Tree.

La mia domanda è: come appare il Concrete Syntax Tree per quanto sopra; e inoltre, anche l'AST?

    
posta NeomerArcana 28.11.2015 - 12:44
fonte

4 risposte

2

Gli alberi di sintassi concreti derivano direttamente dalle regole grammaticali di produzione della lingua (cioè la sua grammatica). Sono complessi, prolissi e offrono pochi vantaggi per le prossime fasi del compilatore (analisi e generazione di codice).

Non penso che la maggior parte dei compilatori rappresentino o memorizzino la sintassi concreta (per non parlare di alberi di sintassi concreti), la sintassi concreta è nella migliore delle ipotesi all'interno dell'algoritmo di analisi stesso (ad esempio, a volte usando la ricorsione); generalmente, analizzando con successo qualcosa il parser genera una struttura di dati intermedia, e se questo è un albero, è probabilmente più riflettente di un albero di sintassi astratto.

Guarda il diagramma per "Parse Tree" in questa risposta e link e confronta con l'AST più avanti nella risposta di @ Guy.

link

    
risposta data 28.11.2015 - 21:19
fonte
2

Se il tuo codice contiene una riga come

x = AddProc(y,z);

quindi l'albero di sintassi per quell'espressione sarebbe simile a questo:

       assignment
      /          \
    ID(x)  FunctionCall(AddProc)
                /      \
              ID(y)   ID(z)

Una cosa importante da notare è che l'implementazione di AddProc è parte non di questo albero di sintassi. Invece, l'albero del systax per il programma completo avrà un sottoalbero della sintassi separato per la definizione di AddProc.

In linguaggi come C, dove i programmi possono essere distribuiti su più file e contengono più funzioni, il compilatore creerà un albero di sintassi separato per ogni file, che a sua volta contiene sotto-alberi separati per ogni dichiarazione e definizione che si trova in livello file.
Per la creazione di alberi di sintassi, la funzione main non è considerata speciale. Questa funzione riceve un trattamento speciale solo quando si verificano errori del programma e durante la generazione del codice.

    
risposta data 28.11.2015 - 15:36
fonte
2

In pratica, i compilatori mantengono alcuni albero di sintassi astratto (forse diversi tipi di essi, es. sia AST tipizzati che non tipizzati) con ulteriori meta-informazioni (es. posizione sorgente come nome file + linea, ecc ...). Quella meta-informazione potrebbe essere conservata all'interno di alberi o al di fuori di essi. E molti compilatori mantengono anche una tabella dei simboli .

Quindi il tuo "albero di sintassi concreto" è spesso una forma iniziale dell'AST decorata con alcuni metadati iniziali.

Hai esaminato l'implementazione di compilatori concreti come Ocaml , GCC , Clang , ecc ...? Hai considerato la compilazione in C, in LLVM , in GCCJIT , ecc ...? Il diavolo è nei dettagli!

Per GCC , la mia documentazione pagina di GCC MELT contiene collegamenti a molti altri siti e centinaia di diapositive che spiegano maggiori dettagli. Leggi anche la documentazione interna GCC , in particolare i capitoli su GENERIC alberi e su GIMPLE .

Si noti inoltre che la maggior parte dei compilatori ha numerosi passaggi (GCC ne ha diverse centinaia) e un passaggio sta trasformando una rappresentazione interna (spesso un AST decorato) in un'altra (spesso, ma non sempre, la sorgente e il target IR ha tipi simili: Ocaml ha sia alberi senza nome che alberi digitati dopo il tipo di inferenza passaggio).

(non esiste un'unica risposta universale alle tue domande, è una questione di opinione, di lingua di partenza, di lingua di arrivo, di obiettivi, di recupero degli errori durante la compilazione, ecc. . potresti ricevere informazioni debug , ad esempio in NANO !)

Se hai familiarità con Lisp o Scheme, considera la lettura del libro di C.Queinnec Lisp In Small Pieces (che fornisce diverse implementazioni di Lisp e la teoria dietro di esse). Leggi anche la programmazione Pragmatica dei linguaggi

di Scott

Spesso, un compilatore può canonicizzare o semplificare alcuni AST, ad es. in modulo A-normale o CPS form (o trasformazione di un for loop in C in qualcosa di più semplice con while o if & goto )

Naturalmente, imparerai molto studiando il codice sorgente di diversi software gratuito compilatori e interpreti, e codificando il proprio compilatore (magari con targeting C, o Javascript, o LLVM, o GCCJIT, o libjit ...); la struttura della lingua di destinazione e la lingua di origine possono dettare le trasformazioni e le rappresentazioni interne del compilatore.

Leggi la semantica ( semantica operativa , semantica denotazionale , tipi e linguaggi di programmazione ....) & su comportamento non definito (in particolare, ciò che ogni programmatore C dovrebbe sapere su UB)

    
risposta data 28.11.2015 - 21:42
fonte
1

L'albero di sintassi concreto è un primo passo nel processo di compilazione e contiene solo le informazioni dal livello lessicale. Il nodo per una chiamata di funzione non "conosce" nulla sulla funzione chiamata o anche se esiste.

Nelle fasi successive verrà verificato se l'identificatore è il nome di una funzione dichiarata da qualche altra parte nel programma, che i tipi di parametri corrispondono all'argomento nel sito di chiamata e così via. Ma questi controlli semantici avvengono in una fase successiva, e non è presente nell'albero della sintassi.

    
risposta data 28.11.2015 - 22:20
fonte

Leggi altre domande sui tag