初识抽象语法树（AST）

作者: madeirak | 来源:发表于2020-01-01 20:13 被阅读0次

基本概念

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

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

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

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

词法分析器（scanner）

词法分析器结构

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

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

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

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

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

词法分析器设计：

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

词法分析器会读取代码，它会一个一个字母地读取代码，所以很形象地称之为扫描(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% 与源码匹配的。

语法分析相关概念

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

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

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

酷文章： ==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（块状域）对象，用来表示是 $\color{blue}{\{return\ a + b\}}$
打开Blockstatement，里面藏着一个ReturnStatement（Return域）对象，用来表示 $\color{blue}{return\ a + b}$
继续打开ReturnStatement,里面是一个BinaryExpression(二项式)对象，用来表示 $\color{blue}{a + b}$
继续打开BinaryExpression，它成了三部分， $\color{blue}{left}$ 、 $\color{blue}{operator}$ 、 $\color{blue}{right}$
$\color{blue}{operator }$ 即 $\color{blue}{+}$
$\color{blue}{left}$ 里面装的，是Identifier对象 $\color{blue}{a}$
$\color{blue}{right }$ 里面装的，是Identifer对象 $\color{blue}{b}$