Manière correcte d'analyser les expressions S en POO

Question

Je cherche un moyen d'implémenter un lecteur d'expression S (à utiliser plus tard avec un interpréteur Scheme et un compilateur), mais je me demande comment (le cas échéant) je devrais écrire un AST pour cela.

J'ai lu SICP, et c'est assez simple depuis Scheme, mais je cherche à implémenter l'interpréteur et le compilateur en C++, en mode OO.

S'il vous plaît, gardez à l'esprit que je fais cela uniquement à des fins d'apprentissage, donc je ne cherche pas vraiment le moyen le plus simple ou le plus rapide de le faire, mais plutôt la manière correcte et réutilisable de le faire.

J'ai vu dans certaines implémentations de Scheme que les gens analysent les expressions s et génèrent facilement des cellules contre, quelque chose comme ceci :

  struct Sexpr
  {
  };

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

  struct IntAtom : Sexpr
  {
    int value;
  };

Et une sous-classe de Sexpr pour chaque type de schéma Atom, Ou quelque chose de ce genre.

Je ne suis pas sûr, mais cela me semble être un hack...Ce travail ne devrait-il pas être effectué par un interprète plutôt que par le lecteur ?

Ce que je veux savoir, c'est si cela est considéré comme la meilleure (ou la bonne) façon de lire les expressions S, ou est-ce plus le travail de l'interprète que de l'analyseur ?L'analyseur devrait-il avoir son propre AST au lieu de s'appuyer sur des cellules contre ?

Answer 1

Pour effectuer un suivi du côté Scheme/Racket de la clôture :

Racket (et certaines autres implémentations de Scheme) utilisent une représentation plus riche pour les objets de syntaxe, afin qu'ils puissent avoir des propriétés qui leur sont attachées indiquant (dans Racket, au moins) dans quel contexte ils sont liés, de quel emplacement source ils proviennent, quelle passe du compilateur les a insérés, ainsi que toute autre information que vous souhaiteriez stocker (cf."propriétés de syntaxe" dans Racket).

Ces informations supplémentaires permettent des choses telles que des messages d'erreur avec des pointeurs vers la source et des macros hygiéniques.

Veuillez noter que je veux dire ici « plus riche » simplement dans le sens « contient plus de valeurs », et non d'une manière non neutre en termes de valeur.

Je devrais également ajouter --- avant de tomber dans la fosse de goudron de Turing --- que vous pouvez également représenter cela exactement les mêmes informations utiliser une table sur le côté ;en supposant que vous ayez des comparaisons de pointeurs, il n'y a aucune différence d'expressivité entre mettre une valeur à l'intérieur d'une structure et utiliser une table pour associer la structure à la valeur.

Answer 2

Si vous souhaitez être quelque peu complet dans votre syntaxe, vous devrez prendre en charge

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

Mais c’est plus général que la plupart des sexprs que vous rencontrerez.La forme la plus simple et la plus courante de S-expr qui dans LISP/Scheme est comme (ab c d) où chacun des a, b, c, d sont des atomes ou des listes.Sous forme de paire, c'est [a [b [c [d nil] ] ] ], ce qui signifie que tous les côtés droits de vos cons sont des listes.

Donc, si vous optez pour la propreté, vous pourriez simplement le faire

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

Answer 3

Bien que l'on puisse probablement débattre de ce qu'est l'approche « correcte », à mon avis, l'approche que vous suggérez : utiliser les mêmes structures de données pour la lecture, la compilation, l'évaluation, et traitement - est celui qui vous apprendra le plus sur ce que sont Lisp et le mantra « le code est des données », et en particulier, ce que signifie le traitement. quote opérateur signifie réellement (ce qui est une chose assez profonde).

C'est aussi, incidemment, la façon dont fonctionnent traditionnellement la plupart des Lisps (fait intéressant, sans compter Scheme).

Alors oui, demandez au lecteur de générer des données Lisp :cons, symboles, nombres Lisp, chaînes, et cetera, exactement les mêmes éléments que le code Lisp au niveau utilisateur traitera.Cela rendra le reste de la mise en œuvre à la fois plus simple et plus instructif.

Answer 4

Vous voudrez peut-être jeter un oeil à cette bibliothèque d'analyseur c/c++ s-expr pour un exemple de la façon dont cela a été fait.

Il semble que la représentation de base soit :

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

Et je cite leurs documents :

Puisqu'un élément peut être une liste ou un atome, la structure de l'élément possède un indicateur de type qui peut être LISTE ou VALEUR.Si l'indicateur de type est LIST, alors le membre de structure "list" sera un pointeur vers la tête de la liste représentée par cet élément.Si l'indicateur de type est VALUE, alors le membre de structure "val" contiendra l'atome représenté par l'élément sous forme de chaîne.Dans les deux cas, le pointeur « suivant » pointera vers l’élément suivant de l’expression s actuelle.

En plus ici est toute une liste d'autres implémentations de lecteurs s-expr dans de nombreuses langues qui peuvent être intéressantes.