1.AST的每個節點由2個域組成,這2個域分別表示當前節點的類型和附加信息。
2.AST的每個節點包含一個指向其子節點的順序表。
3.AST的每個節點包含指向下一個節點的指針。
綜上所述我們得到AST節點的代碼： 1 class CSyntaxTreeNode
2 {
3 public:
4 CSyntaxTreeNode(int _type,int _value) : type(_type),value(_value){}
5
6 inline List<NAutoPtr<CSyntaxTreeNode>>& Child()
7 {
8 return child;
9 }
10
11 inline NAutoPtr<CSyntaxTreeNode> Next()
12 {
13 return next;
14 }
15
16 inline int& Type()
17 {
18 return type;
19 }
20
21 inline int& Value()
22 {
23 return value;
24 }
25 protected:
26 int type;
27 int value;
28 List<NAutoPtr<CSyntaxTreeNode>> child;
29 NAutoPtr<CSyntaxTreeNode> next;
30 };然後我們給出了部分枚舉來標識節點的類型：
1 // for type
2 enum TYPE
3 {
4 stNull,
5 stDeclare,
6 stFunction,
7 stParamterList,
8 stIf,
9 stDo,
10 stExp,
11 };最後是一棵AST的整體結構：
1 class CParserAnalyze
2 {
3 public:
4 inline void Push(NAutoPtr<CSyntaxTreeNode>& Node)
5 {
6 SyntaxTreeStack.Push(Node);
7 }
8
9 inline NAutoPtr<CSyntaxTreeNode> Pop()
10 {
11 return SyntaxTreeStack.Pop();
12 }
13
14 inline NAutoPtr<CSyntaxTreeNode> Top()
15 {
16 return SyntaxTreeStack.Top();
17 }
18
19 inline NAutoPtr<CSyntaxTreeNode> Root()
20 {
21 return SyntaxTreeRoot;
22 }
23 protected:
24 NAutoPtr<CSyntaxTreeNode> SyntaxTreeRoot; // 語法樹根節點
25 Stack<NAutoPtr<CSyntaxTreeNode>> SyntaxTreeStack; // 語法樹棧
26 };
這裡我們簡單的分析一下分析過程：
以if語句為例，其組合子代碼為：
1 if_desc = (str_if + exp_desc)[if_desc_first] +
2 (str_then + stmt_list)[if_desc_second] +
3 Parser_Combinator_Node::opt((str_else + stmt_list)[if_desc_third]) +
4 (str_end + str_if)[if_desc_fourth];我們輸入代碼：
1 if a then
2 declare b as integer
3 end if在做語法分析：
1.讀入if a，a被歸約為一條exp生成一個類型為exp的節點並壓入AST的語法樹棧。
2.if a被歸約生成一個類型為stIf的節點並彈出棧頂的exp節點填充到新生成的stIf節點的第一個子節點。
3.讀入then declare b as integer，integer被歸約生成一個生類型為stDeclare的節點並壓入語法樹棧。
4.declare b as integer被歸約為棧頂的stDeclare節點填充一個b標識符的子節點。
5.then declare b as integer被歸約，首先彈出棧頂的stmt_list因為這裡是stDeclare說明stmt_list有內容應此將棧頂的stIf的值域的最低位置為1。
6.else子句不存在。
7.整體被歸約。
此時棧頂為stIf節點，其不包含next節點，有兩個子節點分別為stExp和stDeclare。
分析過程如下圖：
1.
2.
3.
4.
5.
6.
