基本内容
在进行了正确的语法分析之后,会生成抽象语法树。
一般情况下是一段代码生成一个抽象语法树。 (常见的情况是一个文件或者一块代码。)
本篇来简单的描述一下抽象语法树的内容, 由于笔者的知识储备并不是特别的深,所以可能还需要读者阅读更多的资料。
抽象语法树就是一个树,树是一种基本的数据结构, 主要是由节点构成。
下面定义来自维基百科。
- 每个节点都只有有限个子节点或无子节点;
- 没有父节点的节点称为根节点;
- 每一个非根节点有且只有一个父节点;
- 除了根节点外,每个子节点可以分为多个不相交的子树;
- 树里面没有环路(cycle)
词法分析会从字符流中生成出词法单元, 然后由语法分析进行组装,产生一个AST(抽象语法树)。 基本上来说,树上的每一个节点都是一个词法单元。
下面来看一些示例图。(点击图片可以查看大图)
数值运算

if语句

实际上的树要比笔者给的图更加复杂, 因为在设计的时候, 会考虑如何复用, 所以会进行抽象。 再进行了一定的抽象之后, 会多出一些层次, 但是那些多出来的内容在理解AST的时候是不太重要的。
只要能够组织基本的AST, 那么复杂的其实也不难。 基本上来说, 复杂的AST只是一个量变和正常量变带来的些许复杂度。
代码示例
下面给出一些langX的代码示例, 辅助读者理解这部分内容。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
struct Node
{
NodeType type;
// 在执行结束之后是否进行 free 操作
bool freeOnExecuted;
// 当前节点的值 . 如果当前结点是一个常量数字, 则free 的时候会施放这个值得内存
Object *value;
// 万能指针 , 主要用于放置参数什么的
void *ptr_u;
// 节点状态
NodeState state;
// 当前节点所在的文件信息
NodeFileInfo fileinfo;
// 后置值 , 如果当前节点为一个 变量节点, 当前属性则为有用
Object *postposition;
Variable *var_obj;
Constant *con_obj;
Operator *opr_obj;
ArrayInfo *arr_obj;
};
// 节点的文件信息
struct NodeFileInfo
{
// 文件名
// const char * filename;
// 修改成 std::string 试试,上面的那个类型要处理一下
std::string filename;
// 行号
int lineno;
};
struct Constant
{
int iValue;
double dValue;
char* sValue;
char cValue;
// 当前常量是否是一个 bool 类型得元素
bool flagBool = false;
};
// 数组声明时使用
struct XArrayNode
{
// 数组名字
char * name;
// 数组长度
int length;
// 变量长度索引 . 如果变量索引节点存在, 则使用这个, 否则使用 length
Node * lengthNode;
};
struct Operator
{
// 子节点列表 | 实现树的主要部分内容
struct Node** op;
int op_count;
// 操作符是什么
int opr;
};
|
本部分内容的代码在 Object.h
文件里面。
如果读者阅读了langX的 代码, 会发现还有一个类似的结构, 叫做NodeLink
。 这个不用深入探究,这个是因为笔者当时的知识水平有限, 误入了歧路而产生的东西。
接上一篇的一些内容
由上面的代码示例可以看出, 每一个节点都有一个Object *value;
的属性。 这个属性用于存放该节点的运算结果。
这种方式是属于直接再AST上进行运算, 不建议读者这么使用, 因为这个方式并不好, 会产生很多问题。