Modo corretto di analizzare le espressioni S in OOP

Question

Sto cercando un modo per implementare un lettore di espressioni S (da utilizzare in seguito con un interprete Scheme e un compilatore), ma mi sono chiesto come (se non del tutto) dovrei scrivere un AST per questo.

Ho letto SICP e questo è abbastanza semplice da Scheme, ma sto cercando di implementare l'interprete e il compilatore in C++, in modo OO.

Per favore, tieni presente che lo sto facendo solo a scopo di apprendimento, quindi non sto davvero cercando il modo più semplice o più veloce per farlo, ma piuttosto il modo corretto e riusabile di farlo.

che ho visto in alcune implementazioni Schema che le persone analizzano s-espressioni e le celle cons prontamente uscita, qualcosa di simile:

struct Sexpr 
    { 
    }; 

    struct Cons : public Sexpr 
    { 
    Sexpr* left; 
    Sexpr* right; 
    }; 

    struct IntAtom : Sexpr 
    { 
    int value; 
    }; 

E una sottoclasse di sEspr per ogni tipo di regime Atom, o qualcosa del genere quelle linee.

Non sono sicuro, ma questo mi sembra un trucco ... Non dovrebbe questo lavoro essere eseguito da un interprete piuttosto che dal lettore?

Quello che voglio sapere è se questo è considerato il modo migliore (o corretto) di leggere le S-espressioni, o è più un lavoro dell'interprete che del parser? Il parser dovrebbe avere il proprio AST invece di fare affidamento sulle celle contro?

Answer 1

Per seguire dal lato Scheme/Racket della recinzione:

Racket (e alcune altre implementazioni Scheme) utilizzare una rappresentazione più ricco per oggetti di sintassi, in modo che possano avere proprietà ad essi indicano (in Racket almeno) in quale contesto sono associati, da quale fonte di provenienza provengono, quale passata del compilatore è stato inserito e qualsiasi altra informazione che potresti voler memorizzare (vedere "proprietà della sintassi" in Racket).

Questa informazione aggiuntiva abilita le cose come i messaggi di errore con i puntatori all'origine e i macro igienici.

Si noti che intendo "più ricco" qui semplicemente nel senso "contiene più valori", non in alcun modo non neutro rispetto al valore.

Dovrei anche aggiungere --- prima di cadere nel pozzo del Turing Tar --- che puoi anche rappresentare questa stessa identica informazione usando un tavolo sul lato; supponendo di avere confronti tra puntatori, non c'è alcuna differenza di espressività tra l'inserimento di un valore all'interno di una struttura e l'utilizzo di una tabella per associare la struttura al valore.

Answer 2

Se si vuole essere un po 'completo nella tua sintassi, sarà necessario sostenere

sexpr ::= atom | sexpr sexpr 
atom ::= nil | intatom | etc. 

ma che è più generale rispetto alla maggior parte sEspr si incontrano. La forma più semplice e più comune di S-expr che è in LISP/Scheme (a b c d) dove ognuno di a, b, c, d è un atomo o una lista. In coppia questo è [a [b [c [d nil]]], il che significa che tutti i lati positivi delle tue consegne sono elenchi.

Quindi, se si sta andando per la pulizia, si potrebbe anche fare

class sexpr {}; 
class atom : sexpr {}; 
class s_list : forward_list<smart_ptr<sexpr>> {}; 

Answer 3

Mentre si può probabilmente affermare avanti e indietro su ciò che l'approccio “corretto” è, a mio parere, l'approccio suggerisci-using le stesse strutture di dati per la lettura, la compilazione, la valutazione, e l'elaborazione - è quella che ti insegnerà di più su cosa siano i mantra di Lisp e del "codice è dati", e in particolare cosa significhi realmente l'operatore quote (che è una cosa abbastanza profonda).

E 'anche, per inciso, il modo in cui la maggior parte dei Lisps (interessante, non incluso Schema) funziona tradizionalmente.

Quindi sì, è necessario che il lettore generi dati Lisp: conses, simboli, numeri Lisp, stringhe eccetera, esattamente lo stesso materiale con cui il codice Lisp a livello utente dovrà occuparsi. Renderà il resto dell'implementazione sia più semplice che più istruttivo.

Answer 4

Si potrebbe dare un'occhiata a this c/c++ s-expr parser library per un esempio di come è stato fatto.

Sembra che la rappresentazione di base è:

struct elt { 
    int type; 
    char *val; 
    struct elt *list; 
    struct elt *next; 
}; 

e cito dai loro documenti:

Poiché un elemento può essere sia una lista o atomo, la struttura di elemento ha un indicatore del tipo che può essere LISTA o VALORE. Se l'indicatore di tipo è ELENCO, il membro della struttura "lista" sarà un puntatore alla testa dell'elenco rappresentato da questo elemento. Se l'indicatore del tipo è VALUE, il membro della struttura "val" conterrà l'atomo rappresentato dall'elemento come una stringa. In entrambi i casi, il puntatore "successivo" punterà sull'elemento successivo dell'espressione s corrente.

Inoltre here è un intero elenco di altre implementazioni di lettori s-expr in molte lingue che potrebbero essere di interesse.