抽象语法树（AST）入门

发表于

参考：

AST简介

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

实例

  1. 四则运算表达式

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

image.png

  1. xml
1
2
3
4
5
6
7
8
9
xml复制代码<letter>
  <address>
    <city>ShiChuang</city>
  </address>
  <people>
    <id>12478</id>
    <name>Nosic</name>
  </people>
</letter>

image.png

  1. 程序1
1
2
3
4
5
6
7
8
java复制代码while b != 0
{
    if a > b
        a = a-b
    else
        b = b-a
}
return a

image.png

  1. 程序2
1
2
3
4
java复制代码sum=0
for i in range(0,100)
    sum=sum+i
end

image.png

使用JDT ASTView浏览抽象语法树

Eclipse JDT 提供了可以可视化AST的插件：JDT AstView，该插件可以在IDEA上使用。
image.png
如果下载失败，多半是因为DNS的原因，可以

  • 从官网获取对应插件的下载链接+迅雷 或者
  • 修改hosts文件，修改plugins.jetbrains.com/ 域名地址ip
    详细自行百度

以下是ASTView的测试代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码package test;

import java.util.LinkedList;
import java.util.List;

public class ASTTest {
    public static void main(String[] args) {
        int n = 1;
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < 10; i++) {
            n++;
            list.add(i);
        }
        System.out.println(n + list.size());
    }
}

在代码界面右键 Enable JDT AST View
image.png
点击右侧工具栏的 JDT AST，点击相应的AST节点，光标就会在相应的代码闪烁。使用该插件可以帮助快速感受一下AST。
image.png

根据Eclipse AST的定义，图中每一个节点对应一个节点名，每一个子节点也在其依附的父节点中扮演着一个角色（身份），并且叶子节点基本为名称、操作符和字面量。表1给出了图1中的for循环节点（ForStatement）的四个子节点的节点名和依附于父节点的角色。

image.png

图1 ForSatement的语法树结构

image.png
表1 各个子节点的节点名和角色

文本 -> 抽象语法树的过程

  1. 词法分析：文本 -> token列表
    • 去除空格，对token分类，去除空格，然后对token分类，那些属于语法关键字，那些属于操作符，那些属于语句的截止位置，那些属于数据
  2. 语法分析：token列表 -> 语法二叉树
    • 扫描token流，然后分析它的语法，这一步应该是分析一条以;结尾的语句具体的执行规则，然后使用逆波兰表达式组合，最后形成一个二叉树，二叉树从底部往上一步步合并

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

1
2
3
java复制代码const a = 5;
// 转换成
[{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

当词法分析源代码的时候，它会一个一个字母地读取代码，所以很形象地称之为扫描 - scans。当它遇到空格、操作符，或者特殊符号的时候，它会认为一个话已经完成了。
第二步：语法分析，也称解析器
它会将词法分析出来的数组转换成树形的形式，同时，验证语法。语法如果有错的话，抛出语法错误。

1
2
3
4
5
6
7
8
9
10
java复制代码[{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]
// 语法分析后的树形形式
{
   type: "VariableDeclarator", 
   id: {
       type: "Identifier",
       name: "a"
   },
   ...
}

当生成树的时候，解析器会删除一些没必要的标识 tokens（比如：不完整的括号），因此 AST 不是 100% 与源码匹配的。
解析器100%覆盖所有代码结构生成树叫做CST（具体语法树）。

使用ASTView浏览抽象语法树

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%