3

言語の BNF を定義しましたが、そこから AST を設計する方法がわかりません。

たとえば、私の BNF の最初の数行から:

<program> ::= <import declarations>? <class declaration>?
<import declarations> ::= <import declaration> | <import declarations> <import declaration>
<class declaration> ::= class <identifier> <class body>
<import declaration> ::= import <type name> ';'

これを AST からどのように表現できますか? このように設計する必要がありますか？

typedef vector<ImportDeclaration*> ImportDeclarationList;

class Program {
    ImportDeclarationList importDeclarations;
    ClassDeclaration classDeclaration;
};

class ImportDeclaration {
    TypeName typeName;
};

class ClassDeclaration {
    Identifier identifer;
    ClassBody classbody;
};

thess クラス間で継承を追加する必要がありますか?

BNF から AST を設計する方法についての本はありますか?

4

1 に答える 1

3

ツリーデータ構造を実装するだけです。これは、AST の他のすべての可能な要素を継承する必要があるクラス、たとえば Node が必要になることを意味します。その後、メンバー ポインター (Node*) を使用できます。子の数が異なる場合は、それらを std::vector に格納できます。例えば。非常に単純な生成の場合 (IntLiteral が端末であると仮定):

Addition := IntLiteral + IntLiteral

AST に対して次のコードを記述することができます。

struct Node {
    virtual Node* clone() { return new Node(*this);};
    virtual ~Node() {}
};
class IntLiteral : Node {
    int value;
public:
    IntLiteral(int v) : value(v) {}
    virtual IntLiteral* clone()
    {
        return new IntLiteral(*this);
    }
};
class Addition : Node {
    Node* left;
    Node* right;
public:
    Addition(Node* l, Node* r)
        : Node(), left(l->clone()), right(r->clone()) {}
    virtual Addition* clone()
    {
        return new Addition(*this);
    }
};

手動で実装すると仮定すると、パーサー コードの受け入れ関数でルート ノード (この場合は Addition* 型) にノードを追加できます。

generate実際には、すべてのノードに関数を持たせたいと思うでしょう。または、おそらくこれはより良いアイデアですが、コードを生成するにはアクセサーとツリー トラバーサーが必要です。

パーサーに関する書籍は数多くありますが、実際にはコンパイラに焦点が当てられていますが、そのうちの 1 つに古典的な「ドラゴン ブック」があります。

于 2012-10-27T12:02:01.577 に答える