Come progettare parti di un Abstract Syntax Tree?

Sto scrivendo un interprete C# da zero per l'esperienza di apprendimento, e finora tutto è andato liscio. Ho un lexer C# completamente funzionale che emette tutti i tipi di token per il parser. So come analizzerò i token, ma non sono sicuro di come strutturare il mio AST (abstract syntax tree).Come progettare parti di un Abstract Syntax Tree?

Per esempio, se ho un semplice frammento di codice:

using System.Xml;

quale sarebbe l'albero simile a quando analizzati?

Ti piace questo?

UsingDirective 
    Identifier(System) 
     Identifier(Xml)

o simile?

UsingDirective 
    Identifier(System) 
    Identifier(Xml)

Se potessi ottenere alcuni suggerimenti e/o esempi quanto a come avrei potuto strutturare le cose come identificatori con i puntini in loro, if/else if/else, dichiarazione di variabile/assegnazione combinati in un unico prospetto (int i = 0;), definizioni di funzioni, ecc. Che sarebbero utili. Ho solo bisogno di avere un'idea migliore di come strutturare l'albero e posso capire io stesso il resto. Grazie.

fonte

2012-03-07 Cole Shepherd

Questa sarà una lunga esperienza di apprendimento, se si desidera implementare tutto il C# :-) – svick

Beh, sto tralasciando la maggior parte della libreria di classi. Fondamentalmente sto solo implementando ciò che deve essere implementato per le definizioni di classi/funzioni di base, creazione/utilizzo di variabili e chiamate di funzione. –

Ho scritto un paio di parser in passato, e mi sarebbe generalmente andare per qualcosa di simile:

UsingDirective 
    IdentifierList 
    Identifier (LeftNode) (System) 
    Identifier (RightNode) (Xml)

In caso di questo using System.Collections.Generic

UsingDirective 
    IdentifierList 
     IdentifierList (LeftNode) 
      Identifier (LeftNode) (System) 
      Identifier (RightNode) (Collections) 
     Identifier (RightNode) (Generic)

A differenza di Roslyn, preferisco mantenendo i miei AST chiari non includendo i token come punto e virgola, la parola chiave using ecc poiché il compilatore non ne ha bisogno.

I parser che ho scritto appositamente per IDE sono diversi: trasportano tutte queste cose extra insieme ad altre informazioni come i numeri di riga e di colonna.

fonte

2012-03-07 01:54:48 xbonez

Perché hai fatto il tuo 'IdentifierList' avere solo due figli? Perché non avere un solo 'IdentifierList' con tutti i bambini necessari? – svick

Sì, penso che una sola IdentifierList con figli illimitati sarebbe meglio. In ogni caso, grazie per la tua risposta xbonez. –

Sono sicuro che funzionerebbe pure. Personalmente trovo più facile attraversarlo in questo modo (ricorsivamente), che se fosse solo una lista di idents. Avrei impostato una funzione 'traverIdentList':' if (identlist.leftnode è identlistnode) {traverseIdentList (leftnode); } else {traverseident (leftnode); } traverseident (rightnode); ' – xbonez

Si potrebbe vedere come Microsoft sta facendo questo con Roslyn. Potresti vedere come hanno dichiarato alberi di sintassi per C# (e VB.NET) e forse potresti anche usarlo al posto di parti del tuo interprete prima di scriverlo.

In particolare, albero sintattico Roslyn per la direttiva using si presenta così:

UsingDirective 
    UsingKeyword 
    QualifiedName 
     IdentifierName (System) 
     DotToken 
     IdentifierName (Xml) 
    SemicolonToken

Così, simile alla vostra seconda versione, ma più dettagliata.

Penso che la tua prima versione non abbia molto senso. Xml non è un figlio di System a livello sintattico (anche se potresti avere un concetto di "spazio dei nomi padre" più avanti sul livello semantico).

fonte

2012-03-07 01:41:24 svick

Ma questo non è un albero di sintassi astratto, è un albero di sintassi concreto, in quanto include parti del codice sorgente come il punto e il punto e virgola. –

Sì, hai ragione. Ma penso che potresti basare il tuo AST su questo. – svick

Sì, grazie per la tua risposta! Ha aiutato. –

Come progettare parti di un Abstract Syntax Tree?

risposta

Problemi correlati