AST(抽象语法树)

在所有计算机上运行的所有软件都是用某种程序设计语言编写的，但是在一个程序可以运行之前，它首先需要被翻译成一种能够被计算机执行的形式，完成这项翻译工作的软件系统称为编译器(compiler)

语言处理器

编译器

简单地说，一个编译器就是一个程序，它可以阅读以某一种语言(源语言)编写的程序，并把该程序翻译成一个等价、用另一种语言(目标语言)编写的程序，编译器的重要任务之一是报告它在翻译过程中发现的原程序中的错误

解释器

解释器(interpreter)是另一种常见的语言处理器，它并不通过翻译的方式生成目标程序，解释器直接利用用户提供的输入执行源程序中指定的操作

在把用于输入映射成为输出的过程中，由一个编译器产生的机器语言目标程序通常比一个解释器要快很多，然而，解释器的错误诊断效果通常比编译器更好，因为它逐个语句地执行源程序

java语言处理器结合了编译和解释过程，一个java源程序首先被编译成一个称为字节码(bytecode)的中间表示形式，然后由一个虚拟机对得到的字节码加以解释执行，这样设计的好处之一是在一台机器上编译得到的字节码可以在另一台机器上解释执行，通过网络就可以完成机器之间的迁移
为了更快地完成输入到输出的处理，有些被称为即时(just in time)编译器的java编译器在运行中间程序处理输入的前一刻先把字节码翻译成为机器语言，然后再执行程序

抽象语法树简介

抽象语法树（abstract syntax code，AST）是源代码的抽象语法结构的树状表示，树上的每个节点都表示源代码中的一种结构，这所以说是抽象的，是因为抽象语法树并不会表示出真实语法出现的每一个细节——AST不依赖于具体的文法，不依赖于语言的细节。

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

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

为什么需要将源代码转化为AST

源码转AST

function square(n) {
    return n * n;
}

转换后的AST

{
  type: "FunctionDeclaration",
  id: {
    type: "Identifier",
    name: "square"
  },
  params: [
    {
      type: "Identifier",
      name: "n"
    }
  ],
  ...
};

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

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

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

词法分析

编译器的第一个步骤称为词法分析(lexical analysis)或扫描(scanning)，词法分析器读入组成源程序的字符流，并且将它们组织成为有意义的词素(lexeme)的序列，对于每个词素，词法分析器产生如下形式的词法单元(token)作为输出

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

const a = 5;

// 转换成

[{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

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

这个词法单元被传送给下一个步骤，即语法分析，分割词素的空格会被词法分析器忽略掉

可以看到，在静态分析、编译原理应用领域，代码优化器这一步可以推广到WEBSHELL恶意代码检测技术上，利用这一步得到的"归一化"代码，可以进行纯词法层面的"恶意特征字符串模式匹配"

语法分析，也称解析器

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

语法分析器使用由词法分析器生成的各个词法单元的第一个分量来创建树形的中间表示，该中间表示给出了词法分析产生的词法单元流的语法结构，一个常用的表示方法是语法树(syntax tree)，树中的每个内部结点表示一个运算，而该结点的子节点表示该预算的分量(左右参数)

[{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

语法分析后的树形形式

{
  type: "VariableDeclarator",
  id: {
    type: "Identifier",
    name: "a"
  },
  ...
}

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

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

语义分析

语义分析器(semantic analyzer)使用语法树和符号表中的信息来检查源程序是否和语言定义的语义一致，它同时也收集类型信息，并把这些信息存放在语法树或符号表中，以便在随后的中间代码生成过程中使用

语义分析的一个重要部分是类型检查(type checking)，编译器检查每个运算符是否具有匹配的运算分量

程序设计语言可能允许某些类型转换，即自动类型转换(coercion)

代码转换之babel

babel 是一个 JavaScript 编译器。宏观来说，它分3个阶段运行代码：解析(parsing) — 将代码字符串转换成 AST抽象语法树，转译(transforming) — 对抽象语法树进行变换操作，生成(generation) — 根据变换后的抽象语法树生成新的代码字符串。

我们给 babel 一段 js 代码，它修改代码然后生成新的代码返回。它是怎么修改代码的呢？没错，它创建了 AST，遍历树，修改 tokens，最后从 AST中生成新的代码。

参考文章：

Redy语法分析－－抽象语法树简介 blog.chinaunix.net/uid-26750235-id-3139100.html

AST(抽象语法树)超详细 https://blog.csdn.net/weixin_39408343/article/details/95984062

转载本站文章《AST(抽象语法树)》,
请注明出处：https://www.zhoulujun.cn/html/theory/ComputerScienceTechnology/Compiling/2020_0623_8478.html