文档章节

何为抽象语法树(AST)

黑客画家
 黑客画家
发布于 2018/03/19 21:23
字数 1129
阅读 620
收藏 0

什么是语法树?

      我们知道人类语言上,无论什么语种,都会有「主语」「动词」「宾语」「标点符号」来描述一个现实世界所发生的事件。
      而在计算机编程语言上,无论什么语种,都会有「类型」「运算符」「流程语句」「函数」「对象」等概念来表达计算机中存在内存中的0和1,以及背后运算与逻辑。

语法树,计算机描述世界真理的树状结构。

      不同的语言,都会配之不同的语法分析器,而语法分析器是把源代码作为字符串读入、解析,并建立语法树的程序。语法的设计和语法分析器的实现是决定语言外在表现的重要因素。
      什么是语法树?摘自Wiki一段:

在计算机科学中,抽象语法树(abstract syntax tree 或者缩写为 AST),或者语法树(syntax tree),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都表示源代码中的一种结构。之所以说语法是「抽象」的,是因为这里的语法并不会表示出真实语法中出现的每个细节。

一则简单的例子

      如果我们需要让计算机帮忙算一下 「1加2再乘以3」的结果,该怎么表达呢?
现在我们大多数的现代编程语言,都是使用「中缀表达式」的方式来编写运算,比如JavaScript:

 

1

 

(1 + 2) * 3

      而FORTH语言则使用「后缀表达式」,这基本上与日语中的语序是一致的:

 

1

 

1 2 + 3 *

     LISP语言使用的「前缀表达式」:

 

1

 

( * (+ 1 2) 3)

      我们再看一下这三种表达式的语法树:

                  表达式语法树比较

      可以看出,对于这三种简单的语言,它们只是在这个语法树上按不同的规则遍历而已。三者的代码看起来差别很大,但实际上所用的树结构是相同的。

先来看看Python的语法树

       通过Python语言自带的库文件ast,我们可以查看特定的代码被转换成怎样的语法树。


>>> import ast
>>> ast.dump(ast.parse("(1 + 2) * 3"))
'Module(
	body=[
		Expr(
			value=BinOp(
				left=BinOp(
					left=Num(n=1), 
					op=Add(), 
					right=Num(n=2)
				), 
				op=Mult(), 
				right=Num(n=3)
			)
		)
	]
)'

         BinOp op = Mult()表示乘法运算,与*相对应;
         BinOp op = Add()表示加法运算,与+相对应;
         Num n = 1既为数值1。

           Python语法树

再窥视一下JavaScript的语法树

在语法复杂的语言中,语法树是包含很多细节的语法结果表达式,我们需要靠语法树把这种形式以更简洁的形式表达出来。

     Javascript 有不少工具可以把代码构造出清晰的语法树,比如 esprimav8SpiderMonkeyUglifyJSAST explorer等。

       这里,我使用「esprima」来探讨一下JavaScript运算(1 + 2) * 3的语法树。

javascript code:

 

1

 

(1 + 2)* 3;

ast for json:


{
    "type": "Program",
    "body": [
        {
            "type": "ExpressionStatement",
            "expression": {
                "type": "BinaryExpression",
                "operator": "*",
                "left": {
                    "type": "BinaryExpression",
                    "operator": "+",
                    "left": {
                        "type": "Literal",
                        "value": 1,
                        "raw": "1"
                    },
                    "right": {
                        "type": "Literal",
                        "value": 2,
                        "raw": "2"
                    }
                },
                "right": {
                    "type": "Literal",
                    "value": 3,
                    "raw": "3"
                }
            }
        }
    ],
    "sourceType": "script"
}

    body表示程序体,而程序体中包含了一则表达式ExpressionStatement, 表达式体里包含了操作符 *,以及左右两边表达式,其中右边是数字3,而左边表达式还包含一层表达式,里面是一个+ 操作符,以及左右两边分别为12的数字。

        javascript语法树

       如果还没有看懂,你可以到这里看一下这段代码所生成的语法树:AST for (1 + 2)* 3;*%203%0A)

我们可以利用语法树做些什么?

      看到这里你可能会问,知道语法是又有什么用呢?跟我日常编写代码貌似半毛钱关系都没有。其实语法树还是很有用的,想一下如果想做「语法高亮」、「关键字匹配」、「作用域判断」、以及「代码压缩」等等,都是最好把代码解构成语法树之后再去各种操作,当然仅仅解构还不够,还需要提供各种函数去遍历与修改语法树。

     

     注:这里还有一个go版本的在线语法树生成demo

     AST通常经过词法、语法分析之后产生,关于这方面的可以参考另一篇文章:Lex和YACC学习笔记

 

参考

http://huang-jerryc.com/2016/03/15/%E4%BD%95%E4%B8%BA%E8%AF%AD%E6%B3%95%E6%A0%9

© 著作权归作者所有

共有 人打赏支持
黑客画家
粉丝 139
博文 197
码字总数 509458
作品 0
杭州
高级程序员
私信 提问
Typescript编译原理(一)

首先, 的 地址:github.com/Microsoft/T… 。各位可先行下载。其编译部分位于 目录下。 其中分为以下几个关键部分, Scanner 扫描器() Parser 解析器() Binder 绑定器() Checker 检查...

王三麻子
2018/12/22
0
0
JavaScript中的 抽象语法树 AST

AST 抽象语法树(Abstract Syntax Tree)也称为AST语法树,指的是源代码语法所对应的树状结构。也就是说,一种编程语言的源代码,通过构建语法树的形式将源代码中的语句映射到树中的每一个节...

TokenYang
2017/12/22
0
0
从AST编译解析谈到写babel插件

之前一直在掘金上看到一些关于面试写babel插件的文章,最近也在学,以下就是学习后的总结。 关键词:AST编译解析, babel AST编译解析 AST[维基百科]:在计算机科学中,抽象语法树(Abstract ...

Zenquan
2018/07/25
0
0
【PHP7源码分析】PHP7语言的执行原理

我们常用的高级语言有很多种,比较出名的有CC++、Python、 PHP、Go、Pascal等。而这些语言根据运行的方式不同,大体分为两种:编译型语言和解释型语言。 其中,编译型语言包括CC++、Pascal、...

陈雷_顺风车
2018/08/16
0
0
精读《手写 SQL 编译器 - 语法树》

1 引言 重回 “手写 SQL 编辑器” 系列。之前几期介绍了 词法、文法、语法的解析,以及回溯功能的实现,这次介绍如何生成语法树。 基于 《回溯》 一文介绍的思路,我们利用 JS 实现一个微型 ...

黄子毅
2018/08/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CentOS5.11配置Let's Encrypt免费证书

安装环境: [root@WQ02 opt]# lsb_release -aLSB Version::core-4.0-amd64:core-4.0-ia32:core-4.0-noarch:graphics-4.0-amd64:graphics-4.0-ia32:graphics-4.0-noarch:printing-4.0-amd6......

m_lm
24分钟前
1
0
看看Canonical分享的2018年的十大Linux Snap

导读 Linux在2018年最令人耳目一新的一个方面是Snaps的普及。 Canonical透露,集装箱化的包装已经取得了巨大的成功。今天,Ubuntu制造商分享了2018年的十大Snap。 随着2018年即将结束,我发现...

问题终结者
36分钟前
2
0
天啦噜!在家和爱豆玩"剪刀石头布",阿里工程师如何办到?

阿里妹导读:如今,90、00后一代成为消费主力,补贴、打折、优惠等“价格战”已很难建立起忠诚度,如何与年轻人建立更深层次的情感共鸣?互动就是一种很好的方式,它能让用户更深度的参与品牌...

阿里云官方博客
今天
1
0
聊聊flink的Table API及SQL Programs

序 本文主要研究一下flink的Table API及SQL Programs 实例 // for batch programs use ExecutionEnvironment instead of StreamExecutionEnvironmentStreamExecutionEnvironment env = Stre......

go4it
今天
3
0
mysqldump应用

备份单个库/表数据或库/表结构 命令行下具体用法如下: mysqldump -u用戶名 -p密码 -d 数据库名 表名 > 备份文件名 1、导出数据库为dbname的表结构(其中用戶名為root,密码为dbpasswd,生成的...

阿dai
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部