专栏首页麒思妙想抽象语法树为什么抽象

抽象语法树为什么抽象

从具体到抽象

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. 操作符会变成内部节点,不再会以叶子节点出现在树的末端。

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

本文分享自微信公众号 - 麒思妙想(qicai1612),作者:Lynnic0x00

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-08-13

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Vagrant使用国内镜像安装插件和box镜像

    Vagrant是非常优秀的本地虚拟化管理工具。无奈国内访问速度实在感人。本文分享一些如何使用国内镜像加速的经验,让 Vagrant 的使用更加爽快。

    麒思妙想
  • 基于TensorFlow.js在浏览器上构建深度学习应用

    在前面的章节,我们讨论了各种JavaScript概念和运行在浏览器上的各种深度学习框架。在本章中,我们将所有的知识付诸于实践,证明该技术的潜力。

    麒思妙想
  • 手动编译 Flink 1.9 踩坑实录

    大家期盼已久的1.9已经剪支有些日子了,兴冲冲的切换到跑去编译,我在之前的文章《尝尝Blink》里也介绍过如何编译,本文只针对不同的地方以及遇到的坑做一些说明,...

    麒思妙想
  • 2019诺贝尔经济学奖得主:贫穷的本质是什么?

    2019年诺贝尔经济学奖,颁给了来自麻省理工学院的 阿巴希·巴纳吉(Abhijit Vinayak Banerjee)、艾丝特·杜芙若(Esther Duflo...

    猴子聊数据分析
  • 特别推荐:Web开发常用速查手册大全

    用户4962466
  • 李开复:别再煽动人类对AI的恐慌

    本文经AI新媒体量子位(公众号 ID: QbitAI)授权转载,转载请联系出处 在本届达沃斯论坛上,《人类简史》作者赫拉利教授提出,我们也许是最后一代掌管这个世...

    机器人网
  • 生物信息学算法之Python实现|Rosalind刷题笔记:004 求DNA的反向互补序列

    求 DNA 的反向互补序列分两步:第一是反向,第二是互补。比如序列“ATGC”,反向就是“CGTA”,再互补就是“GCAT”。

    简说基因
  • json学习笔记

    deepcc
  • 【业界】人工智能人才到底有多稀缺?

    Element AI公司研究表明,全球只有2.2万人拥有正确的技能。 ? 每个人都知道,雇佣那些知道如何构建人工智能系统的人的竞争非常激烈。它将一度僵化的学术会...

    AiTechYun
  • 沙龙回顾 | 推荐系统 唯快不破

    本次分享是神盾推荐系统中针对快数据应用场景的架构介绍,分为数据计算和数据分发两个部分。

    腾讯QQ大数据

扫码关注云+社区

领取腾讯云代金券