QLanguage開源項(xiàng)目地址：
http://qlanguage.codeplex.com1.AST的每個(gè)節(jié)點(diǎn)由2個(gè)域組成,這2個(gè)域分別表示當(dāng)前節(jié)點(diǎn)的類型和附加信息。
2.AST的每個(gè)節(jié)點(diǎn)包含一個(gè)指向其子節(jié)點(diǎn)的順序表。
3.AST的每個(gè)節(jié)點(diǎn)包含指向下一個(gè)節(jié)點(diǎn)的指針。
綜上所述我們得到AST節(jié)點(diǎn)的代碼：
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 };
然后我們給出了部分枚舉來標(biāo)識節(jié)點(diǎn)的類型：
1 // for type
2 enum TYPE
3 {
4 stNull,
5 stDeclare,
6 stFunction,
7 stParamterList,
8 stIf,
9 stDo,
10 stExp,
11 };
最后是一棵AST的整體結(jié)構(gòu)：
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; // 語法樹根節(jié)點(diǎn)
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生成一個(gè)類型為exp的節(jié)點(diǎn)并壓入AST的語法樹棧。
2.if a被歸約生成一個(gè)類型為stIf的節(jié)點(diǎn)并彈出棧頂?shù)膃xp節(jié)點(diǎn)填充到新生成的stIf節(jié)點(diǎn)的第一個(gè)子節(jié)點(diǎn)。
3.讀入then declare b as integer，integer被歸約生成一個(gè)生類型為stDeclare的節(jié)點(diǎn)并壓入語法樹棧。
4.declare b as integer被歸約為棧頂?shù)膕tDeclare節(jié)點(diǎn)填充一個(gè)b標(biāo)識符的子節(jié)點(diǎn)。
5.then declare b as integer被歸約，首先彈出棧頂?shù)膕tmt_list因?yàn)檫@里是stDeclare說明stmt_list有內(nèi)容應(yīng)此將棧頂?shù)膕tIf的值域的最低位置為1。
6.else子句不存在。
7.整體被歸約。
此時(shí)棧頂為stIf節(jié)點(diǎn)，其不包含next節(jié)點(diǎn)，有兩個(gè)子節(jié)點(diǎn)分別為stExp和stDeclare。
分析過程如下圖：
1.
2.
3.
4.
5.
6.
7.
posted on 2011-07-01 21:51
lwch 閱讀(2187)
評論(2) 編輯 收藏 引用 所屬分類:
QLanguage