自制脚本语言[3.2]抽象语法树的简单介绍

Aincvy

2021-02-07 2023-07-30 约 1200 字预计阅读 3 分钟

注意

本文最后更新于 2023-07-30，文中内容可能已过时。

基本内容

在进行了正确的语法分析之后，会生成抽象语法树。

一般情况下是一段代码生成一个抽象语法树。 （常见的情况是一个文件或者一块代码。）

本篇来简单的描述一下抽象语法树的内容，由于笔者的知识储备并不是特别的深，所以可能还需要读者阅读更多的资料。

抽象语法树就是一个树，树是一种基本的数据结构，主要是由节点构成。

下面定义来自维基百科。

每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
树里面没有环路(cycle)

词法分析会从字符流中生成出词法单元，然后由语法分析进行组装，产生一个AST（抽象语法树）。基本上来说，树上的每一个节点都是一个词法单元。

下面来看一些示例图。(点击图片可以查看大图)

数值运算

AST1

if语句

if-else语法树

实际上的树要比笔者给的图更加复杂，因为在设计的时候，会考虑如何复用，所以会进行抽象。再进行了一定的抽象之后，会多出一些层次，但是那些多出来的内容在理解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上进行运算，不建议读者这么使用，因为这个方式并不好，会产生很多问题。