Правильный способ парсинга S-выражений в ООП

Question

Я ищу способ реализовать программу чтения S-выражений (которая будет использоваться позже и с интерпретатором Scheme, и с компилятором), но я спрашиваю себя, как (если вообще нужно) писать AST за это.

Я читал SICP, и это довольно просто изнутри Scheme, но я собираюсь реализовать интерпретатор и компилятор в C ++, в форме OO.

Пожалуйста, имейте в виду, что я делаю это только для учебных целей, поэтому я не ищу самый простой или быстрый способ сделать это, а скорее правильный и многократно используемый способ сделать это.

Я видел в некоторых реализациях Scheme, что люди анализируют s-выражения и легко выводят cons-ячейки, что-то вроде этого:

  struct Sexpr
  {
  };

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

  struct IntAtom : Sexpr
  {
    int value;
  };

И один подкласс Sexpr для каждого вида Схемы Atom, или что-то в этом роде.

Я не уверен, но мне это кажется хаком ... Разве эта работа не должна выполняться переводчиком, а не читателем?

Что я хочу знать, так это то, считается ли это лучшим (или правильным) способом чтения S-выражений, или это скорее работа интерпретатора, чем анализатора? Должен ли синтаксический анализатор иметь свой собственный AST вместо использования cons-ячеек?

Answer 1

Хотя можно, вероятно, спорить взад и вперед о том, что такое «правильный» подход, на мой взгляд, тот подход, который вы предлагаете - использование тех же структур данных для чтения, компиляции, оценки, и обработки -это тот, который научит вас больше всего о том, что такое Лисп и мантра «код - данные», и, в частности, что на самом деле означает оператор quote (что довольно глубоко).

Кстати, именно так традиционно работает большинство Лиспов (что интересно, не считая Схемы).

Так что да, пусть читатель генерирует данные Лиспа: выражения, символы, числа Лиспа, строки и так далее, точныето же самое, с чем будет работать пользовательский код на Лиспе.Это сделает остальную часть реализации более простой и поучительной.

Answer 2

Чтобы продолжить со стороны Схемы / Ракетки забора:

Ракетка (и некоторые другие реализации Схемы) используют более богатое представление для объектов синтаксиса, так что они могут иметь прикрепленные к ним свойства, указывающие (вРакетка, по крайней мере) с каким контекстом они связаны, из какого источника они получены, какой этап компилятора их вставил, и любая другая информация, которую вы можете захотеть сохранить (см. «Свойства синтаксиса» в Racket).

Эта дополнительная информация включает такие вещи, как сообщения об ошибках с указателями на источник и гигиенические макросы.

Обратите внимание, что здесь я имею в виду «богаче» просто в смысле «содержит больше значений», а не влюбой не-нейтральный способ.

Я должен также добавить - прежде чем попасть в Яму Тьюринга - что вы также можете представить эту точно такую ​​же информацию , используя таблицу насторона;при условии, что у вас есть сравнения указателей, нет никакой разницы в выразительности между помещением значения в структуру и использованием таблицы для связи структуры со значением.

Answer 3

Если вы хотите быть немного законченным в своем синтаксисе, вам нужно будет поддержать

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

Но это более общий характер, чем у большинства секспр, с которыми вы столкнетесь. Самая простая и наиболее распространенная форма S-expr, которая в LISP / Scheme похожа на (a b c d), где каждый из a, b, c, d является атомом или списком. В парной форме это [a [b [c [d nil]]]], что означает, что все правые стороны ваших конусов являются списками.

Так что, если вы собираетесь на чистую, вы могли бы просто сделать

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

Answer 4

Возможно, вы захотите взглянуть на эту библиотеку синтаксического анализатора c / c ++ s-expr , чтобы узнать, как это было сделано.

Похоже, что базовое представление выглядит так:

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

И я цитирую их документы:

Поскольку элемент может быть списком или атомом,структура элемента имеет индикатор типа, который может быть LIST или VALUE.Если индикатором типа является LIST, то член структуры "list" будет указателем на заголовок списка, представленного этим элементом.Если индикатором типа является VALUE, то член структуры "val" будет содержать атом, представленный элементом в виде строки.В обоих случаях указатель «next» будет указывать на следующий элемент текущего s-выражения.

Дополнительно here - это целый список других реализаций s-exprчитателей на многих языках, которые могут представлять интерес.