QLanguage开源项目地址：
http://qlanguage.codeplex.com1.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.
7.
posted on 2011-07-01 21:51
lwch 阅读(2168)
评论(2) 编辑 收藏 引用 所属分类:
QLanguage