OOPでS式を解析する正しい方法

Question

S式のリーダー（後でSchemeインタプリタとコンパイラの両方で使用する）を実装する方法を探していますが、私はASTを書くべきです）。

私はSICPを読んできましたが、これはSchemeの中ではとても簡単ですが、私はOOの方法でC++でインタープリタとコンパイラを実装しようとしています。

私は学習目的でのみこれをやっているので、実際にこれを行うのが最も簡単で簡単な方法ではなく、正しいやり直しができる方法を探しています。

私は、人々がS式と容易に出力コンスセルを解析し、いくつかのSchemeの実装では、このような何かを見てきました

：

struct Sexpr 
    { 
    }; 

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

    struct IntAtom : Sexpr 
    { 
    int value; 
    }; 

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

私は確信していませんが、これは私にとってハックのようです...この作業は読者ではなく通訳者によって行われるべきではありませんか？

私が知りたいのは、これがS式を読み込む最良の（正しい）方法と考えられるのか、それともパーサー以外の通訳者の仕事なのでしょうか？パーサーはコンスセルに頼るのではなく、独自のASTを持つべきですか？

Answer 1

、少なくともどこにバインドされているのか、どこから来たのか、コンパイラのパスとその他の情報が格納されています（「ラケットの構文プロパティ」を参照）。

この追加情報により、ソースへのポインタと衛生的なマクロのエラーメッセージなどが表示されます。

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

私はTuring Tar Pitに落ちる前に--- と同じ情報を正確に表すこともできます。の表を使用してください。ポインタの比較があると仮定すると、構造体内に値を置くことと構造体を値に関連付けるテーブルを使用することの間には表現力の違いはありません。

Answer 2

あなたの構文でやや完全なものにしたい場合は、

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

をサポートする必要があります。しかし、それはあなたが遭遇する最もsexprよりも一般的です。 Lisp/Schemeの中で最も簡単で最も一般的な形式のS-exprは、a、b、c、dのそれぞれが原子またはリストである（a b c d）のようなものです。ペア形式では、これは[a [b [c [d nil]]]]であり、これはコンスエントのすべての右側がリストであることを意味します。あなたはきれいなのために行くされている場合は、1つは、おそらく前後に主張することができますが、「正しい」アプローチとは何か、私の意見、あなたがアプローチで提案し、使用上

だから、あなただけ

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

Answer 3

を行う可能性がありますとの処理のための同じデータ構造は、Lispと "コードがデータ"のマントラについて、特にquoteが実際に何を意味するのかを最もよく教えるものですそれはかなり深遠なものです）。

また、ほとんどのLisps（興味深いことに、Schemeを含まない）が伝統的に動作する方法です。

そうですね、読者にLispデータを生成させる：コンス、シンボル、Lisp番号、文字列など、ユーザーレベルのLispコードが扱うものとまったく同じもの。それは、実装の残りの部分をより簡単でより有益なものにするでしょう。

ラケット（およびいくつかの他のスキームの実装を）は、ラケットに（示すそれらに取り付けられた特性を有することができるように、構文オブジェクトの豊かな表現を使用する：フェンスのスキーム/ラケット側から追従する

Answer 4

どのように行われたかの例は、this c/c++ s-expr parser libraryをご覧ください。

ベース表現があるように見えます：

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

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

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

さらに、hereは、興味のある多くの言語のs-exprリーダーの他の実装の全リストです。