5

S式リーダーを実装する方法を探しています（後でSchemeインタープリターとコンパイラーの両方で使用されます）が、ASTをどのように記述すればよいか（もしあったとしても）自問自答しています。

私は SICP を読んできました。これは、Scheme 内からは非常に簡単ですが、インタープリターとコンパイラーを C++ でオブジェクト指向の方法で実装しようとしています。

私は学習目的でのみこれを行っていることに注意してください。そのため、これを行う最も簡単で迅速な方法を実際に探しているのではなく、正しく再利用可能な方法を探しています。

いくつかの Scheme 実装で、人々が s 式を解析して、次のようなコンス セルを簡単に出力するのを見てきました。

  struct Sexpr
  {
  };

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

  struct IntAtom : Sexpr
  {
    int value;
  };

そして、Scheme の種類ごとに 1 つの Sexpr のサブクラスAtom、またはそれらに沿った何か。

よくわかりませんが、これはハックのように思えます... この作業は、読者ではなく通訳者が行うべきではありませんか?

私が知りたいのは、これが S 式を読む最良の (または正しい) 方法であると考えられるか、それともパーサーよりもインタープリターの仕事ですか? パーサーは、コンス セルに依存するのではなく、独自の AST を持つ必要がありますか?

4

4 に答える 4

3

おそらく「正しい」アプローチが何であるかについて議論することができますが、私の意見では、読み取り、コンパイル、評価、および処理に同じデータ構造を使用することで、あなたが提案するアプローチが最も多くのことを教えてくれます。 Lisp と「コードはデータである」というマントラが何であるかについて、特にquote演算子が実際に何を意味するかについて (これは非常に深遠なことです)。

ちなみに、これはほとんどの Lisp (興味深いことに、Scheme を除く) が伝統的に機能する方法でもあります。

そうです、リーダに Lisp データを生成させます: コンス、シンボル、Lisp 数値、文字列など、ユーザーレベルの Lisp コードが扱うのとまったく同じものです。これにより、残りの実装がより単純になり、より有益になります。

于 2012-02-24T18:08:52.480 に答える
3

構文をある程度完全にしたい場合は、サポートする必要があります

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

しかし、それはあなたが遭遇するほとんどのsexprよりも一般的です. LISP/Scheme では (abcd) のような S-expr の最も簡単で最も一般的な形式で、a、b、c、d のそれぞれがアトムまたはリストです。ペア形式では、これは [a [b [c [d nil] ] ] ] です。これは、cons のすべての右側がリストであることを意味します。

したがって、きれいにする場合は、そうするだけです

class sexpr {};
class atom : sexpr {};
class s_list : forward_list<smart_ptr<sexpr>> {};
于 2012-02-24T18:00:40.903 に答える
3

フェンスのスキーム/ラケット側からフォローアップするには:

Racket (およびその他の一部の Scheme 実装) は、構文オブジェクトのより豊富な表現を使用するため、(少なくとも Racket では) どのコンテキストでバインドされているか、どのソースの場所から来たか、どのパスを通過したかを示すプロパティをオブジェクトに関連付けることができます。コンパイラの挿入、および保存したいその他の情報 (Racket の「構文プロパティ」を参照)。

この追加情報により、ソースへのポインタを含むエラー メッセージや衛生的なマクロなどが有効になります。

ここで言う「より豊かな」というのは、単に「より多くの値を含む」という意味であり、価値に中立でない意味ではないことに注意してください。

また、チューリング タール ピットに陥る前に、横のテーブルを使用して、これとまったく同じ情報を表すこともできます。ポインター比較があると仮定すると、構造内に値を入れることと、テーブルを使用して構造を値に関連付けることの間に、表現力の違いはありません。

于 2012-02-24T20:01:08.953 に答える
1

どのように行われたかの例として、この c/c++ s-expr パーサー ライブラリを参照してください。

基本表現は次のようになります。

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

そして、私は彼らのドキュメントから引用します：

要素はリストまたはアトムのいずれかになる可能性があるため、要素構造には LIST または VALUE のいずれかになる型インジケータがあります。型指示子が LIST の場合、構造体メンバ "list" は、この要素が表すリストの先頭へのポインタになります。タイプ インジケータが VALUE の場合、構造体メンバ "val" には、要素によって表されるアトムが文字列として含まれます。どちらの場合も、「次の」ポインターは、現在の s 式の次の要素を指します。

さらに、多くの言語での s-expr リーダーのその他の実装の完全なリストを示します。

于 2013-10-09T03:25:53.230 に答える