Modo corretto di analizzare le espressioni S in OOP

Question

Sto cercando un modo per implementare un lettore di espressione S (da usare in seguito sia con un interprete di schema che con un compilatore), ma mi sono chiesto come (se non del tutto) dovrei scrivere un AST per questo.

Ho letto SICP, e questo è abbastanza semplice dallo schema all'interno, ma sto cercando di implementare l'interprete e il compilatore in C ++, in modo oo.

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

Ho visto in alcune implementazioni di schemi che le persone analizzano le espressioni S e le celle di consumo prontamente sugli.

  struct Sexpr
  {
  };

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

  struct IntAtom : Sexpr
  {
    int value;
  };

E una sottoclasse di sexpr per ogni tipo di schema Atom, o qualcosa del genere.

Non sono sicuro, ma questo mi sembra un hack ... non dovrebbe essere fatto questo lavoro da un interprete piuttosto che da il lettore?

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

Answer 1

Seguire dal lato dello schema/racchetta della recinzione:

Racket (e alcune altre implementazioni dello schema) usano una rappresentazione più ricca per gli oggetti di sintassi, in modo che possano avere proprietà ad essi collegate che indicano (in Racket, almeno) in quale contesto sono legati, da quale posizione provengono, da cosa passano Del compilatore li ha inseriti e qualsiasi altra informazione che potresti voler archiviare (cfr. "Proprietà di sintassi" in Racket).

Queste informazioni aggiuntive consentono cose come messaggi di errore con puntatori da fonte e macro igieniche.

Si prega di notare che intendo "più ricco" qui semplicemente nel senso "contiene più valori", non in alcun modo non neutrale.

Dovrei anche aggiungere --- prima di cadere nella fossa del catrame Turing --- che puoi anche rappresentare questo Enate stesse informazioni usando una tabella sul lato; Supponendo che tu abbia confronti di puntatore, non esiste alcuna differenza di espressività tra mettere un valore all'interno di una struttura e l'uso di una tabella per associare la struttura al valore.

Answer 2

Se vuoi essere in qualche modo completo nella tua sintassi, dovrai supportare

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

Ma questo è più generale della maggior parte dei sexpr che incontrerai. La forma più semplice e comune di S-EXPR che in LISP/Scheme è come (ABCD) dove ciascuno di A, B, C, D sono atomi o elenchi. Nella forma di coppia questo è [a [b [c [d nil]]]], il che significa che tutti i lati giusti dei tuoi consmi sono elenchi.

Quindi, se stai andando pulito, potresti farlo

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

Answer 3

Mentre probabilmente si può discutere avanti e indietro su ciò che l'approccio "corretto" è, secondo me, l'approccio che suggerisci, utilizzando le stesse strutture di dati per la lettura, la compilation, la valutazione, e elaborazione: è quello che ti insegnerà di più su ciò che Lisp e il mantra "Codice sono dati", e in particolare di cosa quote L'operatore in realtà significa (che è piuttosto profonda).

È anche, per inciso, il modo in cui la maggior parte dei LISP (interessante, esclusi lo schema) lavora tradizionalmente.

Quindi sì, chiedi al lettore di generare dati LISP: consri, simboli, numeri LISP, stringhe, et cetera, le stesse cose identiche che il codice LISP a livello di utente affronterà. Renderà il resto dell'implementazione sia più semplice che più istruttivo.

Answer 4

Potresti voler dare un'occhiata Questa libreria c/c ++ s-expr parser Per un esempio di come è stato fatto.

Sembra che la rappresentazione di base sia:

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

E cito dai loro documenti:

Poiché un elemento può essere un elenco o un atomo, la struttura dell'elemento ha un indicatore di tipo che può essere elenco o valore. Se l'indicatore di tipo è elenco, l'elemento della struttura "Elenco" sarà un puntatore alla testa dell'elenco rappresentato da questo elemento. Se l'indicatore di tipo è valore, il membro della struttura "Val" conterrà l'atomo rappresentato dall'elemento come stringa. In entrambi i casi, il puntatore "successivo" indicherà l'elemento successivo dell'espressione S corrente.

Inoltre qui è un intero elenco di altre implementazioni di lettori S-EXPR in molte lingue che potrebbero essere di interesse.