初识抽象语法树（AST）

• 基本概念

1. 基本字：阿拉伯数字、大小写拉丁字母、其他字符（~、！、%、&、_、-、+、=、{}、[]、：、；、<、>、，、.、？、/、|、\）、空格符、换行符、制表符等。
2. 关键字（keyword）：提前被定义，并赋予有特殊的含义的单词
3. 保留字： 提前被定义，但还未被赋值（保留字与关键字有时等价）
4. 标识符（identifier）： 由数字、字母、下划线组成，且不能以数字开头，用于给变量、常量、函数、语句块等命名。

• c语言中标识符包括：关键字(如int、while)、预定义标识符(如printf)和用户自定义标识符。

---

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

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

• 词法分析器（scanner）

词法分析器结构

在扫描器的驱动下，预处理子程序将到输入缓冲区中源代码的字符处理后由
扫描缓冲区读入。扫描器在扫描缓冲区中识别单词符号，然后输出。

其中预处理子程序的作用是：

1. 剔除源代码中的空格、回车符、换行符等编辑性字符
2. 区分标号区、捻接续行，给出句末符等等
   

---

现代程序设计语言在最初设计时就遵循了一些规则：

1. 所有基本字都是保留字，不可再作为标识符
2. 基本字作为特殊的标识符处理
3. 基本字、标识符和常数间若没有确定的运算符或界符作间隔，必须使用一个空白符作间隔，一方面避免了超前搜索、方便编译程序进行词法分析，另一方面增加代码的可读性

---

• 词法分析器设计：

1. 确定语言单词规范——单词表
2. 有单词表得到该语言所有字的状态转换图
3. 根据状态转换图实现词法分析器

---

词法分析器会读取代码，它会一个一个字母地读取代码，所以很形象地称之为扫描(scanner)。然后把它们按照预定的规则合并成一个个的标识(tokens)，当它遇到空格、操作符，或者特殊符号的时候，它会认为一个话已经完成了。同时，它会移除空白符、注释等。最后，整个代码将被分割进一个 tokens 列表（或者说一维数组）

//词法分析器典型输入输出
const a = 5;
// 转换成
[{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

---

• 语法分析器（parser）

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

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

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

---

• 语法分析相关概念

1. 巴克斯范式（EBNF）【巴克斯范式（Backus Form）简单例子-from知乎】

EBNF元符号	含义
::=	可解释为，可推导为
|	或
()	一项，一次重复
[]	0次和1次重复
{}	0次或任意多次重复
.	一条生成规则的结束
<>	非终结符
“”	终结符

2. 翻译单元： 什么是翻译单元?

酷文章： ==C实现词法分析及语法分析==

---

现在，我们拆解一个简单的add函数

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

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

用力拆开，它成了三块：

• 一个id，就是它的名字，即add
• 两个params，就是它的参数，即[a, b]
• 一块body，也就是大括号内的一堆东西

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

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

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

• 接下来，我们继续拆开body，我们发现，body其实是一个BlockStatement（块状域）对象，用来表示是

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

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

• 继续打开BinaryExpression，它成了三部分，、、

• 即

• 里面装的，是Identifier对象

• 里面装的，是Identifer对象

就这样，我们把一个简单的add函数拆解完毕，用图表示就是

"add" `s AST

酷文章：

• AST抽象语法树——最基础的javascript重点知识，99%的人根本不了解
• Python词法分析器实现
• 在《Python词法分析器实现》一文中在定义“种别码”是用到“有穷自动机”理论的使用，具体可见 ：
  编译原理：有穷自动机（DFA与NFA）

词法分析器中的预处理程序部分
词法分析器中的词法分析程序部分
词法分析器