如何從BNF設計抽象語法樹（AST）

我已經定義了我的語言的BNF並且不知道如何從中設計AST。如何從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; 
};

是否需要在這些類之間添加一些繼承？

有沒有關於如何從BNF設計AST的書籍？

來源

2012-10-22 47dev47null

節點需要包含「抽象」語法類別（通常接近許多規則的LHS）。有關AST與CST的討論，請參閱http://stackoverflow.com/a/1916687/120163，以及爲什麼您可能希望節點包含具體的語法類別（例如，準則的LHS或具體的名稱樹葉）。 –

你只需要實現一個樹型數據結構。這意味着你需要一些類，比如說Node，AST的所有其他可能的元素都必須繼承它。然後你可以使用成員指針（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函數。另外，也許這是一個更好的主意，您將需要訪問器和樹遍歷器來生成代碼。

關於解析器的書籍很多，其中之一就是經典的「龍書」，儘管實際上關注的是編譯器。

來源

2012-10-27 12:02:01 Aleph

謝謝你的回覆！ – 47dev47null

如何從BNF設計抽象語法樹（AST）

回答

相關問題