AST-抽象语法树学习总结

谁践踏了优雅 2022-12-21 06:07 185阅读 0赞

抽象语法树简介

(一)简介

抽象语法树（abstract syntax code，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，这所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节，比如说，嵌套括号被隐含在树的结构中，并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法，也就是说语法分析阶段所采用的上下文无文文法，因为在写文法时，经常会对文法进行等价的转换（消除左递归，回溯，二义性等），这样会给文法分析引入一些多余的成分，对后续阶段造成不利影响，甚至会使合个阶段变得混乱。因些，很多编译器经常要独立地构造语法分析树，为前端，后端建立一个清晰的接口。

抽象语法树在很多领域有广泛的应用，比如浏览器，智能编辑器，编译器。

（二）举例  
现在，我们拆解一个简单的add函数

function add(a, b) { 
        return a + b
    }

首先，我们拿到的这个语法块，是一个FunctionDeclaration(函数定义)对象。

用力拆开，它成了三块：

一个id，就是它的名字，即add  
两个params，就是它的参数，即\[a, b\]  
一块body，也就是大括号内的一堆东西  
add没办法继续拆下去了，它是一个最基础Identifier（标志）对象，用来作为函数的唯一标志，就像人的姓名一样。

{
        name: 'add'
        type: 'identifier'
        ...
    }

params继续拆下去，其实是两个Identifier组成的数组。之后也没办法拆下去了。

[
        {
            name: 'a'
            type: 'identifier'
            ...
        },
        {
            name: 'b'
            type: 'identifier'
            ...
        }
    ]

接下来，我们继续拆开body  
我们发现，body其实是一个BlockStatement（块状域）对象，用来表示是\{return a + b\}

打开Blockstatement，里面藏着一个ReturnStatement（Return域）对象，用来表示return a + b

继续打开ReturnStatement,里面是一个BinaryExpression(二项式)对象，用来表示a + b

继续打开BinaryExpression，它成了三部分，left，operator，right

operator 即+  
left 里面装的，是Identifier对象 a  
right 里面装的，是Identifer对象 b  
就这样，我们把一个简单的add函数拆解完毕，用图表示就是

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center]

看！抽象语法树(Abstract Syntax Tree)，的确是一种标准的树结构。

那么，上面我们提到的Identifier、Blockstatement、ReturnStatement、BinaryExpression， 这一个个小部件的说明书去哪查？

请查看 :AST对象官方文档 [link][].

(三）抽象语法树实例

(1)四则运算表达式

表达式: 1+3\*(4-1)+2

抽象语法树为：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 1]  
（2)xml

代码2.1：

<letter>
      <address>
        <city>ShiChuang</city>
      </address>
      <people>
        <id>12478</id>
        <name>Nosic</name>
      </people>
    </letter>

抽象语法树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 2]

(3)程序1

代码2.2

while b != 0
    { 
        if a > b
            a = a-b
        else
            b = b-a
    }
    return a

抽象语法树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 3]  
(4)程序2

代码2.3

sum=0
    for i in range(0,100)
        sum=sum+i
    end

抽象语法树  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 4]  
(三)为什么需要抽象语法树

当在源程序语法分析工作时，是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语法成分的组成结构，通常可以用所谓的前后文无关文法或与之等价的Backus-Naur范式(BNF)将一个程序设计语言的语法规则确切的描述出来。前后文无关文法有分为这么几类：LL(1)，LR(0)，LR(1)， LR(k) ,LALR(1)等。每一种文法都有不同的要求，如LL(1)要求文法无二义性和不存在左递归。当把一个文法改为LL(1)文法时，需要引入一些隔外的文法符号与产生式。

例如，四则运算表达式的文法为：

文法1.1

E->T|EAT
    T->F|TMF
    F->(E)|i
    A->+|-
    M->*|/

改为LL(1)后为：

文法1.2

E->TE'
    E'->ATE'|e_symbol
    T->FT'
    T'->MFT'|e_symbol
    F->(E)|i
    A->+|-
    M->*|/

例如，当在开发语言时，可能在开始的时候，选择LL(1)文法来描述语言的语法规则，编译器前端生成LL(1)语法树，编译器后端对LL(1)语法树进行处理，生成字节码或者是汇编代码。但是随着工程的开发，在语言中加入了更多的特性，用LL(1)文法描述时，感觉限制很大，并且编写文法时很吃力，所以这个时候决定采用LR(1)文法来描述语言的语法规则，把编译器前端改生成LR(1)语法树，但在这个时候，你会发现很糟糕，因为以前编译器后端是对LL(1)语树进行处理，不得不同时也修改后端的代码。

抽象语法树的第一个特点为:不依赖于具体的文法。无论是LL(1)文法，还是LR(1)，或者还是其它的方法，都要求在语法分析时候，构造出相同的语法树，这样可以给编译器后端提供了清晰，统一的接口。即使是前端采用了不同的文法，都只需要改变前端代码，而不用连累到后端。即减少了工作量，也提高的编译器的可维护性。

抽象语法树的第二个特点为:不依赖于语言的细节。在编译器家族中，大名鼎鼎的gcc算得上是一个老大哥了，它可以编译多种语言，例如c，c＋＋，java，ADA，Object C， FORTRAN， PASCAL， COBOL等等。在前端gcc对不同的语言进行词法，语法分析和语义分析后，产生抽象语法树形成中间代码作为输出，供后端处理。要做到这一点，就必须在构造语法树时，不依赖于语言的细节，例如在不同的语言中，类似于if－condition－then这样的语句有不同的表示方法

在c中为：

if(condition)
    {
        do_something();
    }

在fortran中为：

If condition then
        do_somthing()
    end if

在构造if－condition－then语句的抽象语法树时，只需要用两个分支节点来表于，一个为condition，一个为if\_body。如下图：  
![在这里插入图片描述][20201115094300853.png_pic_center]  
在源程序中出现的括号，或者是关键字，都会被丢掉。  
（四）应用在编译器  
先来看一下把一个简单的函数转换成AST之后的样子。

// 简单函数
    function square(n) { 
        return n * n;
    }
     
    // 转换后的AST
    { 
       type: "FunctionDeclaration",
       id: { 
           type: "Identifier",
           name: "square"
       },
       params: [
          { 
               type: "Identifier",
               name: "n"
          }
       ],
       ...
    }

从纯文本转换成树形结构的数据，每个条目和树中的节点一一对应。

纯文本转AST的实现

当下的编译器都做了纯文本转AST的事情。

一款编译器的编译流程是很复杂的，但我们只需要关注词法分析和语法分析，这两步是从代码生成AST的关键所在。

第一步：词法分析，也叫扫描scanner

它读取我们的代码，然后把它们按照预定的规则合并成一个个的标识 tokens。同时，它会移除空白符、注释等。最后，整个代码将被分割进一个 tokens 列表（或者说一维数组）。

const a = 5;
    // 转换成
    [{ value: 'const', type: 'keyword'}, { value: 'a', type: 'identifier'}, ...]

当词法分析源代码的时候，它会一个一个字母地读取代码，所以很形象地称之为扫描 - scans。当它遇到空格、操作符，或者特殊符号的时候，它会认为一个话已经完成了。

第二步：语法分析，也称解析器

它会将词法分析出来的数组转换成树形的形式，同时，验证语法。语法如果有错的话，抛出语法错误。

[{ value: 'const', type: 'keyword'}, { value: 'a', type: 'identifier'}, ...]
    // 语法分析后的树形形式
    { 
       type: "VariableDeclarator", 
       id: { 
           type: "Identifier",
           name: "a"
       },
       ...
    }

当生成树的时候，解析器会删除一些没必要的标识 tokens（比如：不完整的括号），因此 AST 不是 100% 与源码匹配的。

解析器100%覆盖所有代码结构生成树叫做CST（具体语法树）。

（五）实际生成  
生成过程  
源码–词法分析–语法分析–抽象语法树  
源码:

let sum = 10 + 66;

词法分析:  
从左到右一个字符一个字符地读入源程序，从中识别出一个个“单词”"符号"等

单词   let     单词    sum      符号    =      数字   10      符号   +    数字   66      符号  ;

[
     { "type": "word", value: "let"}
     { "type": "word", value: "sum"}
     { "type": "Punctuator", value: "="}
     { "type": "Numeric", value: "10"}
     { "type": "Punctuator", value: "+"}
     { "type": "Numeric", value: "66""}
     { "type": "Punctuator", value: ";"}
     ]

语法分析:  
在词法分析的基础上根据当前编程语言的语法,将单词序列组合成各类语法短语

关键字  let   标识符  sum   赋值运算符  =    字面量  10   二元运算符  +    字面量  66   结束符号 ;

AST作用

开发大型框架或第三方工具，例如：babel、webpack、JD Taro、uni-app

利用webpack打包js代码时, webpack会在原有代码的基础新增一些代码，在利用babel打包js代码的时候, 我们可以将高级代码转换为低级代码

那么webpack、babel是如何新增代码, 如何修改的呢, 答案就是通过AST来新增和修改的  
如果不想做一只菜鸟, 想进一步深入学习各种工具、框架的底层实现原理, 那么AST是必修之课

AST使用

代码转换成AST  
将JS代码转换成AST, 其实就是将源代码的每一个组成部分拆解出来放到树中  
拆解的过程非常复杂, 所以我们可以借助第三方模块来帮我们实现拆解  
利用@babel/parser解析器:  
`npm install --save @babel/parser`

注意点: 最新版本babylon已经更名为@babel/parser

修改AST中的内容  
要想修改AST中的内容必须先遍历拿到需要修改的节点才能修改

遍历AST抽象语法树  
可以通过babel的traverse模块来遍历

文档

修改之后的语法树转换成代码  
可以通过@babel的generator模块来转换

import * as parser from "@babel/parser";
    import traverse from "@babel/traverse";
    import generate from '@babel/generator';
    
    // 1.转换成抽象语法树
    const code = `let sum = 10 + 66;`;
    const ast = parser.parse(code);
    console.log(ast);
    
    // 2.遍历抽象语法树
    traverse(ast, { 
        enter(path) { 
            // console.log(path.node.type);
            if(path.node.type === "Identifier"){ 
                // 3.修改满足条件的语法树节点
                path.node.name = "add";
                path.stop();
            }
        }
    });
    console.log(ast);
    
    // 4.将抽象语法树转换成代码
    const res = generate(ast);
    console.log(res);

创建AST抽象语法树  
可以通过babel的types模块来创建语法树节点然后push到body中

文档

import * as parser from "@babel/parser";
    import traverse from "@babel/traverse";
    import generate from '@babel/generator';
    import * as t from '@babel/types';
    
    let code = ``;
    
    let ast = parser.parse(code);
    console.log(ast);
    
    // 需求: 要求手动创建 let sum = 10 + 66;的节点, 添加到body
    // 推荐从内向外创建
    // 1.创建二元运算符左右参与运算的 字面量节点
    let left = t.numericLiteral(10);
    let right = t.numericLiteral(66);
    // 2.创建二元运算符节点
    let init = t.binaryExpression("+", left, right);
    // 3.创建表达式标识符节点
    let id = t.identifier("sum");
    // 4.创建内部变量表达式节点
    let variable = t.variableDeclarator(id, init);
    // 5.创建外部变量表达式节点
    let declaration = t.variableDeclaration("let", [variable]);
    // 6.将组合好的节点添加到body中
    ast.program.body.push(declaration);
    
    let resultCode = generate(ast);
    console.log(resultCode.code);

创建技巧  
在@babel/types模块中, 所有语法树的节点类型都有对应的方法, 直接调用对应方法即可创建  
在创建的时候建议从内向外创建, 最后再添加到body中

NodePath常用属性和方法

── 属性
      - node   当前节点
      - parent  父节点
      - parentPath 父path
      - scope   作用域
      - context  上下文
      - ...
    ── 方法
      - get   当前节点
      - findParent  向父节点搜寻节点
      - getSibling 获取兄弟节点
      - replaceWith  用AST节点替换该节点
      - replaceWithMultiple 用多个AST节点替换该节点
      - insertBefore  在节点前插入节点
      - insertAfter 在节点后插入节点
      - remove   删除节点
      - ...

AST使用比较简单，可以在线生成后，根据其属性查找对应的文档。  
推荐阅读： [link][link 1]  
在线生成： [link][link 2].  
文档1: [link][link 3].  
文档2: [link][link 4].  
文档3: [link][link 5].

（六）使用Condesensor生产AST  
https://github.com/fabsx00/codesensor/issues/1 看到这里有人在求文档，就知道肯定不是我一个人看了论文之后想试试。

首先，在这里https://github.com/fabsx00/codesensor/blob/master/INSTALL，看到作者说是需要Antlr的特殊版本的，如果按照这里面给的网址（https://www.antlr.org/download/antlr-3.4-complete-no-antlrv2.jar），可以预见是下不了的。不过实际上Antlr的所有Jar包都可以在这里下到：https://github.com/antlr/website-antlr3/tree/gh-pages/download

把下载的Jar包放到codesensor目录下，然后借助Git的sh.exe来运行codesensor目录下的build.sh（具体方法参看这里），竟然就可以成功生成CodeSensor.jar了，然后假设我们分析的源码文件是test.c，那么我们只需要运行：

java -jar CodeSensor.jar test.c > output.txt

就可以把codesensor的输出结果存入output.txt这个文件中。我们可以看到其可以将AST生成一个序列化的形式，然后就可以在这个基础上做进一步的分析了。例如针对下面这个c function：

short add (short b){ 
    	short a=32767;
    	if(b>0){ 
    		a=a+b;
    	}
    	return a;
    }

其生成的序列形式是：

SOURCE_FILE	1:0	1:0	0	
    FUNCTION_DEF	1:0	7:0	1	
    RETURN_TYPE	1:0	1:0	2	short
    TYPE_NAME	1:0	1:0	3	short
    LEAF_NODE	1:0	1:0	4	short
    FUNCTION_NAME	1:6	1:6	2	add
    LEAF_NODE	1:6	1:6	3	add
    PARAMETER_LIST	1:10	1:18	2	( short b )
    LEAF_NODE	1:10	1:10	3	(
    PARAMETER_DECL	1:11	1:17	3	short b
    TYPE	1:11	1:11	4	short
    TYPE_NAME	1:11	1:11	5	short
    LEAF_NODE	1:11	1:11	6	short
    NAME	1:17	1:17	4	b
    LEAF_NODE	1:17	1:17	5	b
    LEAF_NODE	1:18	1:18	3	)
    LEAF_NODE	1:19	1:19	2	{ 
    STATEMENTS	2:1	6:1	2	
    SIMPLE_DECL	2:1	2:14	3	short a ; a = 32767 ;
    VAR_DECL	2:1	2:7	4	short a ; a = 32767
    TYPE	2:1	2:1	5	short
    TYPE_NAME	2:1	2:1	6	short
    LEAF_NODE	2:1	2:1	7	short
    NAME	2:7	2:7	5	a
    LEAF_NODE	2:7	2:7	6	a
    LEAF_NODE	0:0	0:0	5	;
    INIT	2:7	2:7	5	a = 32767
    ASSIGN	2:7	2:9	6	a = 32767
    LVAL	2:7	2:7	7	a
    NAME	2:7	2:7	8	a
    LEAF_NODE	2:7	2:7	9	a
    ASSIGN_OP	2:8	2:8	7	=
    LEAF_NODE	2:8	2:8	8	=
    RVAL	2:9	2:9	7	32767
    FIELD	2:9	2:9	8	32767
    LEAF_NODE	2:9	2:9	9	32767
    LEAF_NODE	2:14	2:14	4	;
    SELECTION	3:1	3:8	3	
    KEYWORD	3:1	3:1	4	if
    LEAF_NODE	3:1	3:1	5	if
    LEAF_NODE	3:3	3:3	4	(
    CONDITION	3:4	3:4	4	b > 0
    EXPR	3:4	3:6	5	b > 0
    FIELD	3:4	3:4	6	b
    LEAF_NODE	3:4	3:4	7	b
    REL_OPERATOR	3:5	3:5	6	>
    LEAF_NODE	3:5	3:5	7	>
    FIELD	3:6	3:6	6	0
    LEAF_NODE	3:6	3:6	7	0
    LEAF_NODE	3:7	3:7	4	)
    STATEMENTS	3:8	5:1	4	
    LEAF_NODE	3:8	3:8	5	{ 
    STATEMENTS	4:2	4:2	5	
    EXPR_STATEMENT	4:2	4:7	6	a = a + b ;
    EXPR	4:2	4:2	7	a = a + b
    ASSIGN	4:2	4:4	8	a = a + b
    LVAL	4:2	4:2	9	a
    FIELD	4:2	4:2	10	a
    LEAF_NODE	4:2	4:2	11	a
    ASSIGN_OP	4:3	4:3	9	=
    LEAF_NODE	4:3	4:3	10	=
    RVAL	4:4	4:6	9	a + b
    FIELD	4:4	4:4	10	a
    LEAF_NODE	4:4	4:4	11	a
    LEAF_NODE	4:5	4:5	10	+
    FIELD	4:6	4:6	10	b
    LEAF_NODE	4:6	4:6	11	b
    LEAF_NODE	4:7	4:7	7	;
    LEAF_NODE	5:1	5:1	5	}
    JUMP_STATEMENT	6:1	6:9	3	return a ;
    KEYWORD	6:1	6:1	4	return
    LEAF_NODE	6:1	6:1	5	return
    DESTINATION	6:8	6:8	4	a
    EXPR	6:8	6:8	5	a
    FIELD	6:8	6:8	6	a
    LEAF_NODE	6:8	6:8	7	a
    LEAF_NODE	6:9	6:9	4	;
    LEAF_NODE	7:0	7:0	2	}

和文章中相比要更复杂一些，并且感觉有一些冗余。

不过8年前的工具竟然能在现在的系统上正常运行，不得不说是很感人的一件事情了。

（七）转载注明  
本文转载自：  
https://blog.csdn.net/philosophyatmath/article/details/38170131  
https://blog.csdn.net/l20001109/article/details/109258879?biz\_id=102&utm\_term=AST&utm\_medium=distribute.pc\_search\_result.none-task-blog-2allsobaiduweb~default-1-109258879&spm=1018.2118.3001.4449

https://blog.csdn.net/wang1472jian1110/article/details/109504948?biz\_id=102&utm\_term=AST&utm\_medium=distribute.pc\_search\_result.none-task-blog-2allsobaiduweb~default-0-109504948&spm=1018.2118.3001.4449

https://blog.csdn.net/qysh123/article/details/106395599

以上就是对AST的所有总结，只是初步的知识，文章可能存在各种问题，希望大家原谅并及时纠正 —厚点（thicker）

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4f88f464c45844f49248acb3fab68853.png
[link]: https://developer.mozilla.org/en-US/docs/Mozilla/Projects/SpiderMonkey/Parser_API#Node_objects
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201115093517633.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20201115105115961.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20201115094123418.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20201115094211555.jpeg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvY2tob3U=,size_16,color_FFFFFF,t_70#pic_center
[20201115094300853.png_pic_center]: https://img-blog.csdnimg.cn/20201115094300853.png#pic_center
[link 1]: https://www.csdn.https://github.com/jamiebuilds/babel-handbook/blob/master/translations/en/plugin-handbook.md
[link 2]: https://astexplorer.net
[link 3]: https://babeljs.io/docs/en/babel-parser
[link 4]: https://babeljs.io/docs/en/babel-traverse#docsNav
[link 5]: https://babeljs.io/docs/en/babel-types