抽象语法树为什么抽象 - 云+社区

腾讯云 · · 1169 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

从具体到抽象

Abstract Syntax Tree抽象语法树(通常被简写成AST)实际上只是一个解析树(parse tree)的一个精简版本。在编译器设计的语境中,"AST" 和 "语法树"(syntax tree)是可以互换的。

什么是解析树呢?我们知道一棵解析树是包含代码所有语法信息的树型结构,它是代码的直接翻译。所以解析树,也被成为具象语法树(Concret Syntax Tree, 简称CST);而抽象语法树,忽略了一些解析树包含的一些语法信息,剥离掉一些不重要的细节,所以它看起并不像解析树那么事无巨细,这也是AST名字中抽象一词的由来。

在继续下一步之前,我们先统一一下文中的概念表达形式,以便更好的理解内容

解析树 = Parse Tree = CST 抽象语法树 = Syntax Tree = AST

我们先分析一段简短的代码js代码:5 + (1 x 12), 回忆一下编译器的工作过程

词法分析

编译的第一个阶段是扫描源代码文本,scanner会从左到右扫描文本,把文本拆成一些单词。然后,这些单词传入分词器,经过一系列的识别器(关键字识别器、标识符识别器、常量识别器、操作符识别器等),确定这些单词的词性,这一过程的产物是token序列。token在机内一般用<type, value>形似的二元组来表示,type表示一个单词种类,value为属性值,比如var这个单词,在js语言里是一个关键字,一种语言的关键字集合是事先可以确定的,所以它的type本身就可表示这个关键字,不再需要属性值, 用二元组表示就是<VAR, ->;再看我们的示例5 + (1 x 12)中, 12也是其中的一个单词, 它实际上是一个常量,用二元组表示就是<CONST, 12>。分词和所使用的语言种类密切相关,分解后的token序列为5, +, (, 1, x, 12, )

<CONST, 5>

<OPT, +>

<SLP, ->

<CONST, 1>

<OPT, *>

<CONST, 12>

<RLP, ->

scanner和分词器所做的工作,构成了编译器的词法分析阶段。

语法分析

分词阶段完成以后,token序列会经过我们的解析器,由解析器识别出代码中的各类短语,会根据语言的文法规则(rules of grammar)输出解析树,这棵树是对代码的树形描述。文法是什么呢?想想我们学英语的过程中,老师是如何教我们划分句子解构的,比如一个简单的英文自然语言例子:

Little girl ate apple

它由【名词短语】和【动词短语】组成, 再往下【名词短语】由【形容词】和【名词构成】,【动词短语】由【动词】和【名词短语】构成。【动词】和【名词】又可以由具体的单词构成。

我们会觉得语言描述冗长,而且并不直观,可以借助一些符号进行描述:

<句子> -> <名词短语><动词短语>

<名词短语> -> <形容词><名词>

<动词短语> -> <动词> <名词短语>

<形容词> -> little

<名词> -> girl | apple

<动词> -> ate

用<>包裹起来的部分称为语法规则,未用<>包括起来的部分(如little、girl等),就是该语言的基本符号。

用更抽象的形式化语言定义,文法可表示为:

  • T表示终结符的集合(如little、girl等,即词法分析中提到的token)
  • N表示非终结符的集合(如<>里包括的部分,表示了语法成分, 因为它们可以推导出其他句子成分,所以称为非终结符)
  • P表示产生式集合(上面分析英语句子的每一条规则都是一个产生式,如<动词短语> -> <动词> <名词短语>, 就是一个产生式)
  • S表示开始符号(S属于N的子元素,是一个特殊的非终结符)

可以看出,文法用简单的符号解决了无穷语言的有穷表述问题。

那么解析树具体长什么样呢?

2 + (12 * 1)根据对应的文法生成的解析树

解析树

你可能会非常疑惑为什么会有EXP->1这种形式的存在,是不是感觉非常冗余?

我们来从文法的角度来解释这个问题,2 + (12 * 1)是一个四则运算的表达式,根据我们小学学过的内容,大家都会很轻易的知道它的运算规则,那我们可以根据前面提到的文法规则公式,用形式语言把这些规则简写出来:

// 每条产生式前面的序号只为了更好的在下文引用,并不是产生式的一部分
1) E -> E + E
2) E -> E * E
3) E -> (E)
4) E -> number

你很快会发现,上图的分析树就是根据这些规则生成的,而EXP->1这种形式正是第四条产生式的一个应用。

总结一下解析树的一些性质

  • 解析树的根节点为文法开始符号
  • 解析树内部节点表示一个产生式的应用
  • 叶节点既可以是非终结符也可以是终结符。从左到右的叶节点得到的符号串成为这颗树的产出(yield)。

精简一棵解析树

我们现在知道具象语法树和抽象语法树的概念,而且知道AST是CST的精简版本,那么AST它是如何生成的呢?

我们现在知道,根据文法规则生成的解析树会非常冗余。我们有过疑问,EXP->1这种结点,是不是看上去有点冗余?我们把这种结点叫做单继承节点,实际上我们并不会关心EXP是什么,只会关心继承它的那个值,这里即1。

压缩单继承节点

另外,我们发现括号似乎也是冗余的,可以隐藏在树的结构中。

去掉括号

甚至,我们可以看到,蓝色方框中的内部结点也不含有关键信息,可以用操作符号(在这里是 + 和 *)把它们替换掉。

将操作符压进内部节点

继续把冗余的层修剪掉,我们可以得到一颗AST树

一颗抽象语法树

我们已经自己压缩了一棵解析树,通过上面几个步骤的精简,可以总结一些解析树和抽象语法树的不同之处:

  1. AST不含有语法细节,比如冒号、括号、分号
  2. AST会压缩单继承节点
  3. 操作符会变成内部节点,不再会以叶子节点出现在树的末端。

有了抽象语法树,我们基于它可以建立清晰的代码描述,非常有利于后续阶段的修改、变换。

本文来自:腾讯云

感谢作者:腾讯云

查看原文:抽象语法树为什么抽象 - 云+社区

1169 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传