抽象语法树_编译原理抽象语法树 - CSDN
精华内容
参与话题
  • AST(抽象语法树)超详细

    万次阅读 多人点赞 2019-07-16 10:08:21
    首先来一个比较形象的,转载自:AST-抽象语法树,讲述了为什么需要讲源代码转化为AST,总结就是:AST不依赖于具体的文法,不依赖于语言的细节,我们将源代码转化为AST后,可以对AST做很多的操作,...

    自己研究的东西会用到AST,就自己通过查阅资料,整理一下。

    本文目录

    第一部分:AST的作用

    第二部分:AST的流程

    第三部分: Eclipse AST的获取与访问


    第一部分:AST的作用

    首先来一个比较形象的,转载自:AST-抽象语法树,讲述了为什么需要讲源代码转化为AST,总结就是:AST不依赖于具体的文法,不依赖于语言的细节,我们将源代码转化为AST后,可以对AST做很多的操作,包括一些你想不到的操作,这些操作实现了各种各样形形色色的功能,给你带进一个不一样的世界。

    原文为:

    抽象语法树简介

    (一)简介

    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套括号被隐含在树的结构中,并没有以节点的形式呈现。抽象语法树并不依赖于源语言的语法,也就是说语法分析阶段所采用的上下文无文文法,因为在写文法时,经常会对文法进行等价的转换(消除左递归,回溯,二义性等),这样会给文法分析引入一些多余的成分,对后续阶段造成不利影响,甚至会使合个阶段变得混乱。因些,很多编译器经常要独立地构造语法分析树,为前端,后端建立一个清晰的接口。

    抽象语法树在很多领域有广泛的应用,比如浏览器,智能编辑器,编译器。

     

    (二)抽象语法树实例

     

    (1)四则运算表达式

    表达式: 1+3*(4-1)+2

    抽象语法树为:

     

    (2)xml

    代码2.1:

     

    1. <letter>
    2.   <address>
    3.     <city>ShiChuang</city>
    4.   </address>
    5.   <people>
    6.     <id>12478</id>
    7.     <name>Nosic</name>
    8.   </people>
    9. </letter>

     

    抽象语法树

     

     

     

     

    (3)程序1

    代码2.2

     

    1. while b != 0
    2. {
    3.     if a > b
    4.         a = a-b
    5.     else
    6.         b = b-a
    7. }
    8. return a

     

    抽象语法树

     

    (4)程序2

    代码2.3

     

    1. sum=0
    2. for i in range(0,100)
    3.     sum=sum+i
    4. end

     

    抽象语法树

     

    (三)为什么需要抽象语法树

    当在源程序语法分析工作时,是在相应程序设计语言的语法规则指导下进行的。语法规则描述了该语言的各种语法成分的组成结构,通常可以用所谓的前后文无关文法或与之等价的Backus-Naur范式(BNF)将一个程序设计语言的语法规则确切的描述出来。前后文无关文法有分为这么几类:LL(1),LR(0),LR(1), LR(k) ,LALR(1)等。每一种文法都有不同的要求,如LL(1)要求文法无二义性和不存在左递归。当把一个文法改为LL(1)文法时,需要引入一些隔外的文法符号与产生式。

    例如,四则运算表达式的文法为:

    文法1.1

     

    1. E->T|EAT
    2. T->F|TMF
    3. F->(E)|i
    4. A->+|-
    5. M->*|/

     

    改为LL(1)后为:

    文法1.2

     

    1. E->TE'
    2. E'->ATE'|e_symbol
    3. T->FT'
    4. T'->MFT'|e_symbol
    5. F->(E)|i
    6. A->+|-
    7. M->*|/

    例如,当在开发语言时,可能在开始的时候,选择LL(1)文法来描述语言的语法规则,编译器前端生成LL(1)语法树,编译器后端对LL(1)语法树进行处理,生成字节码或者是汇编代码。但是随着工程的开发,在语言中加入了更多的特性,用LL(1)文法描述时,感觉限制很大,并且编写文法时很吃力,所以这个时候决定采用LR(1)文法来描述语言的语法规则,把编译器前端改生成LR(1)语法树,但在这个时候,你会发现很糟糕,因为以前编译器后端是对LL(1)语树进行处理,不得不同时也修改后端的代码。

    抽象语法树的第一个特点为:不依赖于具体的文法。无论是LL(1)文法,还是LR(1),或者还是其它的方法,都要求在语法分析时候,构造出相同的语法树,这样可以给编译器后端提供了清晰,统一的接口。即使是前端采用了不同的文法,都只需要改变前端代码,而不用连累到后端。即减少了工作量,也提高的编译器的可维护性。

    抽象语法树的第二个特点为:不依赖于语言的细节。在编译器家族中,大名鼎鼎的gcc算得上是一个老大哥了,它可以编译多种语言,例如c,c++,java,ADA,Object C, FORTRAN, PASCAL, COBOL等等。在前端gcc对不同的语言进行词法,语法分析和语义分析后,产生抽象语法树形成中间代码作为输出,供后端处理。要做到这一点,就必须在构造语法树时,不依赖于语言的细节,例如在不同的语言中,类似于if-condition-then这样的语句有不同的表示方法

    在c中为:

     

    1. if(condition)
    2. {
    3.     do_something();
    4. }

     

         在fortran中为:

     

    1. If condition then
    2.     do_somthing()
    3. end if

     

    在构造if-condition-then语句的抽象语法树时,只需要用两个分支节点来表于,一个为condition,一个为if_body。如下图:

    在源程序中出现的括号,或者是关键字,都会被丢掉。

     

    第二部分:AST的流程

    此部分让你了解到从源代码到词法分析生成tokens到语法分析生成AST的整个结构,让你对整个流程有一个了解,此部分转载自:详解AST抽象语法树

     

    原文为:

    浅谈 AST

    先来看一下把一个简单的函数转换成AST之后的样子。

    
     
    1. // 简单函数

    2. function square(n) {

    3. return n * n;

    4. }

    5.  
    6. // 转换后的AST

    7. {

    8. type: "FunctionDeclaration",

    9. id: {

    10. type: "Identifier",

    11. name: "square"

    12. },

    13. params: [

    14. {

    15. type: "Identifier",

    16. name: "n"

    17. }

    18. ],

    19. ...

    20. }

    从纯文本转换成树形结构的数据,每个条目和树中的节点一一对应。

    纯文本转AST的实现

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

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

    第一步:词法分析,也叫扫描scanner

    它读取我们的代码,然后把它们按照预定的规则合并成一个个的标识 tokens。同时,它会移除空白符、注释等。最后,整个代码将被分割进一个 tokens 列表(或者说一维数组)。

    
     
    1. const a = 5;

    2. // 转换成

    3. [{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

    4.  

    当词法分析源代码的时候,它会一个一个字母地读取代码,所以很形象地称之为扫描 - scans。当它遇到空格、操作符,或者特殊符号的时候,它会认为一个话已经完成了。

    第二步:语法分析,也称解析器

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

    
     
    1. [{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]

    2. // 语法分析后的树形形式

    3. {

    4. type: "VariableDeclarator",

    5. id: {

    6. type: "Identifier",

    7. name: "a"

    8. },

    9. ...

    10. }

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

    解析器100%覆盖所有代码结构生成树叫做CST(具体语法树)。

    用例:代码转换之babel

    babel 是一个 JavaScript 编译器。宏观来说,它分3个阶段运行代码:解析(parsing) — 将代码字符串转换成 AST抽象语法树,转译(transforming) — 对抽象语法树进行变换操作,生成(generation) — 根据变换后的抽象语法树生成新的代码字符串。

    我们给 babel 一段 js 代码,它修改代码然后生成新的代码返回。它是怎么修改代码的呢?没错,它创建了 AST,遍历树,修改 tokens,最后从 AST中生成新的代码。

    详解 AST

    前言

    抽象语法树(AST),是一个非常基础而重要的知识点,但国内的文档却几乎一片空白。

    本文将带大家从底层了解AST,并且通过发布一个小型前端工具,来带大家了解AST的强大功能

    Javascript就像一台精妙运作的机器,我们可以用它来完成一切天马行空的构思。

    我们对javascript生态了如指掌,却常忽视javascript本身。这台机器,究竟是哪些零部件在支持着它运行?

    AST在日常业务中也许很难涉及到,但当你不止于想做一个工程师,而想做工程师的工程师,写出vue、react之类的大型框架,或类似webpack、vue-cli前端自动化的工具,或者有批量修改源码的工程需求,那你必须懂得AST。AST的能力十分强大,且能帮你真正吃透javascript的语言精髓。

    事实上,在javascript世界中,你可以认为抽象语法树(AST)是最底层。 再往下,就是关于转换和编译的“黑魔法”领域了。

    人生第一次拆解Javascript

    小时候,当我们拿到一个螺丝刀和一台机器,人生中最令人怀念的梦幻时刻便开始了:

    我们把机器,拆成一个一个小零件,一个个齿轮与螺钉,用巧妙的机械原理衔接在一起…

    当我们把它重新照不同的方式组装起来,这时,机器重新又跑动了起来——世界在你眼中如获新生。

    通过抽象语法树解析,我们可以像童年时拆解玩具一样,透视Javascript这台机器的运转,并且重新按着你的意愿来组装。

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

    
     
    1. function add(a, b) {

    2.    return a + b

    3. }

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

    用力拆开,它成了三块:

    • 一个id,就是它的名字,即add

    • 两个params,就是它的参数,即[a, b]

    • 一块body,也就是大括号内的一堆东西

    add没办法继续拆下去了,它是一个最基础Identifier(标志)对象,用来作为函数的唯一标志,就像人的姓名一样。

    
     
    1. {

    2.    name: 'add'

    3.    type: 'identifier'

    4.    ...

    5. }

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

    
     
    1. [

    2.    {

    3.        name: 'a'

    4.        type: 'identifier'

    5.        ...

    6.    },

    7.    {

    8.        name: 'b'

    9.        type: 'identifier'

    10.        ...

    11.    }

    12. ]

    接下来,我们继续拆开body

    我们发现,body其实是一个BlockStatement(块状域)对象,用来表示是{return a + b}

    打开Blockstatement,里面藏着一个ReturnStatement(Return域)对象,用来表示return a + b

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

    继续打开BinaryExpression,它成了三部分,left,operator,right

    • operator 即+

    • left 里面装的,是Identifier对象 a

    • right 里面装的,是Identifer对象 b

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

    看!抽象语法树(Abstract Syntax Tree),的确是一种标准的树结构。

    那么,上面我们提到的Identifier、Blockstatement、ReturnStatement、BinaryExpression, 这一个个小部件的说明书去哪查?

     

    第三部分: Eclipse AST的获取与访问

     

    此部分教你如何使用eclipse的AST,通过第三部分,你可以队AST的细节进一步的了解。对如何操纵AST有更清楚的理解。此部分转自作者刘伟:【Eclipse AST】AST的获取与访问,此部分提到了访问者模式,通过此模式对AST进行访问,想多了解访问者模式见链接:

    操作复杂对象结构-访问者模式1

    操作复杂对象结构-访问者模式2

    操作复杂对象结构-访问者模式3

    操作复杂对象结构-访问者模式4

    原文为:

    Eclipse中的Eclipse JDT提供了一组访问和操作Java源代码的API,Eclipse AST是其中一个重要组成部分,它提供了AST、ASTParser、ASTNode、ASTVisitor等类,通过这些类可以获取、创建、访问和修改抽象语法树。

           首先需要掌握如何将Java源代码转换为AST,即解析源代码。Eclipse AST提供了ASTParser类用于解析源代码,ASTParser有两种导入源代码的方式,一种是以Java Model的形式,另一种是以字符数组的形式。ASTParser的创建与使用如下:

    ASTParser astParser = ASTParser.newParser(/*API Level*/);
    astParser.setSource(/*Source Code*/);
           参数说明如下:

           ● API Level:Java编程规范(Java Language Specification,简写为JLS),此参数为常量,例如AST.JLS3。

           ● Source Code:方法setSource()针对不同形式的源代码作为参数而进行了重载,主要分类为字符数组形式(char[])和JavaModel形式(ICompilationUnit、IClassFile等)。

           如果传入的字符数组不是完整的一个Java文件,而是一个表达式或语句,又怎么办呢?可以按照以下代码对ASTParser进行设置:

    astParser.setKind(/*Kind of Construct*/);
           其中Kind of Construct是所需解析的代码的类型,包括:

           ● K_COMPILATION_UNIT:编译单元,即一个Java文件

           ● K_CLASS_BODY_DECLARATIONS:类的声明

           ● K_EXPRESSION:单个表达式

           ● K_STATEMENTS:语句块

     

           创建并设定好ASTParser后,便可以开始源代码与AST的转换,代码如下:

    CompilationUnit result = (CompilationUnit) (astParser.createAST(null));
           createAST()方法的参数类型为IProgressMonitor,用于对AST的转换进行监控,不需要的话就填个null即可。本代码示例是以待解析的源代码为一完整的Java文件(对应一个编译单元Compilation Unit)为前提的,所以在转换为AST后直接强制类型转换为CompilationUnit。CompilationUnit是ASTNode的子类,指的就是整个Java文件,也是AST的根节点。

           下面是一个简单的工具类,用于将源代码以字符数组形式解析为AST,其中getCompilationUnit()方法的输入参数为需解析的Java源代码文件路径,返回值为该文件对应的CompilationUnit节点:

    import java.io.BufferedInputStream;
    import java.io.FileInputStream;
    import java.io.FileNotFoundException;
    import java.io.IOException;
     
    import org.eclipse.jdt.core.dom.AST;
    import org.eclipse.jdt.core.dom.ASTParser;
    import org.eclipse.jdt.core.dom.CompilationUnit;
     
    public class JdtAstUtil {
        /**
        * get compilation unit of source code
        * @param javaFilePath 
        * @return CompilationUnit
        */
        public static CompilationUnit getCompilationUnit(String javaFilePath){
            byte[] input = null;
            try {
                BufferedInputStream bufferedInputStream = new BufferedInputStream(new FileInputStream(javaFilePath));
                input = new byte[bufferedInputStream.available()];
                    bufferedInputStream.read(input);
                    bufferedInputStream.close();
            } catch (FileNotFoundException e) {
                e.printStackTrace();
            } catch (IOException e) {
                e.printStackTrace();
            }
     
            
        ASTParser astParser = ASTParser.newParser(AST.JLS3);
            astParser.setSource(new String(input).toCharArray());
            astParser.setKind(ASTParser.K_COMPILATION_UNIT);
     
            CompilationUnit result = (CompilationUnit) (astParser.createAST(null));
            
            return result;
        }
    }
     

            至此便将源代码转化为了AST,接下来要做的就是访问节点,需要学习两个Eclipse AST的核心类:

           ● ASTNode:AST节点类,在上一篇文章和上文中都有提到,由于节点种类太多,在此不一一赘述(后面专门写一篇独立的文章来介绍各种不同类型的ASTNode),但需要明确的是所有的节点类型都是ASTNode的子类,至于某一个节点源代码具体到底是什么节点,可以通过ASTView来查看。

           ● ASTVisitor:AST访问者类,它针对不同类型的节点提供了一系列重载的visit()和endvisit()方法,意思就是访问到该类型的节点时执行visit()方法,访问完该类型节点后执行endvisit()方法。其中,visit()方法需返回boolean类型的返回值,表示是否继续访问子节点。另外ASTVisitor还提供了preVisit()和postVisit()方法,参数类型为ASTNode,也就是说不论哪种类型的节点,访问前后都要分别执行preVisit()和postVisit()。这些方法的具体实现由ASTVisitor的子类负责,如果不需要对所访问到的节点做处理,则无需在ASTVisitor的子类中覆盖这些方法。

           Eclipse AST访问节点这一部分的设计采用了访问者模式,不同类型的节点是待访问的具体元素,ASTNode充当抽象元素角色,ASTVisitor充当抽象访问者,而我们自己写的ASTVisitor的子类充当具体访问者,而程序代码就是对象结构,包含了不同种类的节点供访问者来访问。

          在使用 Eclipse AST访问节点时需要先声明一个类继承自ASTVisitor,即增加具体访问者类,并覆盖相应的方法,编写需执行的操作,实例化这个访问者类后调用ASTNode的accept()方法,将ASTVisitor作为参数传入,就可以执行访问了,此处对应了访问者模式的“双重分派”机制,如果不熟悉的童鞋,可以先学习一下访问者模式,。【操作复杂对象结构——访问者模式】。

           

           下面给出一个示例,实现输出给定Java文件中所声明的类名、方法名和属性名,基本步骤如下:

           (1) 通过ASTView确定类、方法和属性的声明对应的AST节点分别是TypeDeclaration、MethodDeclaration和FieldDeclaration,FieldDeclaration类比较特殊,因为一个FieldDeclaration下可能有多个同类型的属性被声明,形如“privateint a, b;”。

           (2) 创建一个新的访问者子类,继承自ASTVisitor,并覆盖参数类型为TypeDeclaration、MethodDeclaration和FieldDeclaration的visit()方法,由于需要遍历所有节点,因此将返回值都设为true。

           (3) TypeDeclaration、MethodDeclaration可以直接获得相关的名字并输出,而FieldDeclaration需要遍历它的子节点VariableDeclarationFragment,由于FieldDeclaration提供了返回所有VariableDeclarationFragment的方法,因此这里直接采用for循环遍历即可。

           详细代码如下:

    import org.eclipse.jdt.core.dom.ASTVisitor;
    import org.eclipse.jdt.core.dom.FieldDeclaration;
    import org.eclipse.jdt.core.dom.MethodDeclaration;
    import org.eclipse.jdt.core.dom.TypeDeclaration;
     
    public class DemoVisitor extends ASTVisitor {
     
        @Override
        public boolean visit(FieldDeclaration node) {
            for (Object obj: node.fragments()) {
                VariableDeclarationFragment v = (VariableDeclarationFragment)obj;
                System.out.println("Field:\t" + v.getName());
            }
            
            return true;
        }
     
        @Override
        public boolean visit(MethodDeclaration node) {
            System.out.println("Method:\t" + node.getName());
            return true;
        }
     
        @Override
        public boolean visit(TypeDeclaration node) {
            System.out.println("Class:\t" + node.getName());
            return true;
        }
    }
           下面提供一个测试类,对上述解析源代码的工具类(JdtAstUtil)和访问AST的访问者类(DemoVisitor )进行测试:


    import org.eclipse.jdt.core.dom.CompilationUnit;
     
    import com.ast.util.JdtAstUtil;
    import com.ast.visitor.DemoVisitor;
     
    public class DemoVisitorTest {
        
        public DemoVisitorTest(String path) {
            CompilationUnit comp = JdtAstUtil.getCompilationUnit(path);
            
            DemoVisitor visitor = new DemoVisitor();
            comp.accept(visitor);
        }
    }
           提供一个待处理的简单Java源代码文件(ClassDemo.java)如下:


    public class ClassDemo {
        
        private String text = "Hello World!", text2;
        
        public void print(int value) {
            System.out.println(value);
        }
        
        public void input(String value) {
            text2 = value;
        }
    }
           显示结果为:

    图1 测试运行结果

          上述示例代码DemoVisitor还有点小瑕疵,例如TypeDeclaration节点其实不仅表示了类的声明,还包括了接口的声明,实际运用中需要根据情况使用TypeDeclaration提供的isInterface()方法来进行过滤。这也说明了一方面各位开发者需要认真了解各种不同类型的节点具有哪些特性、不同的节点类有哪些方法,另一方面开发者还需要对Java语言本身有较为深入的了解。

           

           OK,本节有关AST的获取和访问就介绍到这里,,大家如果有兴趣的话可以做做如下两个练习:

           (1) 寻找一个类的构造方法、抽象方法和Main方法;

           (2) 统计一个If语句的Then语句块中语句的数量。

           P.S.,本实例工程中需要导入的jar包如下:

           org.eclipse.core.contenttype.jar
           org.eclipse.core.jobs.jar
           org.eclipse.core.resources.jar
           org.eclipse.core.runtime.jar
           org.eclipse.equinox.common.jar
           org.eclipse.equinox.preferences.jar
           org.eclipse.jdt.core.jar
           org.eclipse.osgi.jar

          例如这是我们之前用过的两组使用AST解析Java源文件的jar包(只有版本号不一样):

    展开全文
  • 什么是抽象语法树

    2019-12-24 01:17:30
    前言AST 是抽象语法树的缩写词,表示编程语言的语句和表达式中生成的 token。有了 AST,解释器或编译器就可以生成机器码或者对一条指令求值。小贴士: 通过使用 Bit,你可以将任意...

    前言

    AST 是抽象语法树的缩写词,表示编程语言的语句和表达式中生成的 token。有了 AST,解释器或编译器就可以生成机器码或者对一条指令求值。

    小贴士: 通过使用 Bit,你可以将任意的 JS 代码转换为一个可在项目和应用中共享、使用和同步的 API,从而更快地构建并重用更多代码。试一下吧。

    假设我们有下面这条简单的表达式:

    1 + 2
    

    用 AST 来表示的话,它是这样的:

    + BinaryExpression
     - type: +
     - left_value: 
      LiteralExpr:
       value: 1
     - right_vaue:
      LiteralExpr:
       value: 2
    

    诸如 if 的语句则可以像下面这样表示:

    if(2 > 6) {
        var d  = 90
        console.log(d)
    }
    IfStatement
     - condition
      + BinaryExpression
       - type: >
       - left_value: 2
       - right_value: 6
     - body
      [
        - Assign
            - left: 'd';
            - right: 
                LiteralExpr:
                - value: 90
        - MethodCall:
             - instanceName: console
             - methodName: log
             - args: [
             ]
      ]
    

    这告诉解释器如何解释语句,同时告诉编译器如何生成语句对应的代码。

    看看这条表达式:1 + 2。我们的大脑判定这是一个将左值和右值相加的加法运算。现在,为了让计算机像我们的大脑那样工作,我们必须以类似于大脑看待它的形式来表示它。

    我们用一个类来表示,其中的属性告诉解释器运算的全部内容、左值和右值。因为一个二元运算涉及两个值,所以我们给这个类命名为 Binary:

    class Binary {  
        constructor(left, operator, right) {  
            this.left = left
            this.operator = operator  
            this.right = right
        }  
    }
    

    实例化期间,我们将会把 1 传给第一个属性,把 ADD 传给第二个属性,把 2 传给第三个属性:

    new Binary('1', 'ADD', '2')
    

    当我们把它传递给解释器的时候,解释器认为这是一个二元运算,接着检查操作符,认为这是一个加法运算,紧接着继续请求实例中的 left 值和 right 值,并将二者相加:

    const binExpr = new Binary('1', 'ADD', '2')
    if(binExpr.operator == 'ADD') {  
        return binExpr.left + binExpr.right
    }  
    // 返回 `3`
    

    看,AST 可以像大脑那样执行表达式和语句。

    单数字、字符串、布尔值等都是表达式,它们可以在 AST 中表示并求值。

    23343
    false
    true
    "nnamdi"
    

    拿 1 举例:

    1
    

    我们在 AST 的 Literal(字面量) 类中来表示它。一个字面量就是一个单词或者数字,Literal 类用一个属性来保存它:

    class Literal {  
        constructor(value) {  
            this.value = value
        }  
    }
    

    我们可以像下面这样表示 Literal 中的 1:

    new Literal(1)
    

    当解释器对它求值时,它会请求 Literal 实例中 value 属性的值:

    const oneLit = new Literal(1)  
    oneLit.value
    // `1`
    

    在我们的二元表达式中,我们直接传递了值

    new Binary('1', 'ADD', '2')
    

    这其实并不合理。因为正如我们在上面看到的,1 和 2 都是一条表达式,一条基本的表达式。作为字面量,它们同样需要被求值,并且用 Literal 类来表示。

    const oneLit = new Literal('1')  
    const twoLit = new Literal('2')
    

    因此,二元表达式会将 oneLit 和 twoLit 分别作为左属性和右属性。

    // ...
    new Binary(oneLit, 'ADD', twoLit)
    

    在求值阶段,左属性和右属性同样需要进行求值,以获得各自的值:

    const oneLit = new Literal('1')  
    const twoLit = new Literal('2')  
    const binExpr = new Binary(oneLit, 'ADD', twoLit)
    if(binExpr.operator == 'ADD') {  
        return binExpr.left.value + binExpr.right.value
    }  
    // 返回 `3`
    

    其它语句在 AST 中也大多是用二元来表示的,例如 if 语句。

    我们知道,在 if 语句中,只有条件为真的时候代码块才会执行。

    if(9 > 7) {  
        log('Yay!!')  
    }
    

    上面的 if 语句中,代码块执行的条件是 9 必须大于 7,之后我们可以在终端上看到输出 Yay!!。

    为了让解释器或者编译器这样执行,我们将会在一个包含 condition、 body 属性的类中来表示它。condition 保存着解析后必须为真的条件,body 则是一个数组,它包含着 if 代码块中的所有语句。解释器将会遍历该数组并执行里面的语句。

    class IfStmt {  
        constructor(condition, body) {  
            this.condition = condition
            this.body = body
        }  
    }
    

    现在,让我们在 IfStmt 类中表示下面的语句

    if(9 > 7) {  
        log('Yay!!')  
    }
    

    条件是一个二元运算,这将表示为:

    const cond = new Binary(new Literal(9), "GREATER", new Literal(7))
    

    就像之前一样,但愿你还记得?这回是一个 GREATER 运算。

    if 语句的代码块只有一条语句:一个函数调用。函数调用同样可以在一个类中表示,它包含的属性有:用于指代所调用函数的 name 以及用于表示传递的参数的 args:

    class FuncCall {  
        constructor(name, args) {  
            this.name = name
            this.args = args
        }  
    }
    

    因此,log("Yay!!") 调用可以表示为:

    const logFuncCall = new FuncCall('log', [])
    

    现在,把这些组合在一起,我们的 if 语句就可以表示为:

    const cond = new Binary(new Literal(9), "GREATER", new Literal(7));  
    const logFuncCall = new FuncCall('log', []);
    const ifStmt = new IfStmt(cond, [  
        logFuncCall
    ])
    

    解释器可以像下面这样解释 if 语句:

    const ifStmt = new IfStmt(cond, [  
        logFuncCall
    ])
    function interpretIfStatement(ifStmt) {  
        if(evalExpr(ifStmt.conditon)) {  
            for(const stmt of ifStmt.body) {  
                evalStmt(stmt)  
            }  
        }  
    }
    interpretIfStatement(ifStmt)
    

    输出:

    Yay!!
    

    因为 9 > 7 :)

    我们通过检查 condition 解析后是否为真来解释 if 语句。如果为真,我们遍历 body 数组并执行里面的语句。

    执行 AST

    使用访问者模式对 AST 进行求值。访问者模式是设计模式的一种,允许一组对象的算法在一个地方实现。

    ASTs,Literal,Binary,IfStmnt 是一组相关的类,每一个类都需要携带方法以使解释器获得它们的值或者对它们求值。

    访问者模式让我们能够创建单个类,并在类中编写 AST 的实现,将类提供给 AST。每个 AST 都有一个公有的方法,解释器会通过实现类实例对其进行调用,之后 AST 类将在传入的实现类中调用相应的方法,从而计算其 AST。

    class Literal {  
        constructor(value) {  
            this.value = value
        }
        visit(visitor) {  
            return visitor.visitLiteral(this)  
        }  
    }
    class Binary {  
        constructor(left, operator, right) {  
            this.left = left
            this.operator = operator  
            this.right = right
        }
        visit(visitor) {  
            return visitor.visitBinary(this)  
        }  
    }
    

    看,AST Literal 和 Binary 都有访问方法,但是在方法里面,它们调用访问者实例的方法来对自身求值。Literal 调用 visitLiteral,Binary 则调用 visitBinary。

    现在,将 Vistor 作为实现类,它将实现 visitLiteral 和 visitBinary 方法:

    class Visitor {
        visitBinary(binExpr) {  
            // ...
            log('not yet implemented')  
        }
        visitLiteral(litExpr) {  
            // ...
            log('not yet implemented')  
        }  
    }
    

    visitBinary 和 visitLiteral 在 Vistor 类中将会有自己的实现。因此,当一个解释器想要解释一个二元表达式时,它将调用二元表达式的访问方法,并传递 Vistor 类的实例:

    const binExpr = new Binary(...)  
    const visitor = new Visitor()
    binExpr.visit(visitor)
    

    访问方法将调用访问者的 visitBinary,并将其传递给方法,之后打印 not yet implemented。这称为双重分派。

    • 调用 Binary 的访问方法。

    • 它 (Binary) 反过来调用 Visitor 实例的visitBinary。

    我们把 visitLiteral 的完整代码写一下。由于 Literal 实例的 value 属性保存着值,所以这里只需返回这个值就好:

    class Visitor {
        visitBinary(binExpr) {  
            // ...
            log('not yet implemented')  
        }
        visitLiteral(litExpr) {  
            return litExpr.value
        }  
    }
    

    对于 visitBinary,我们知道 Binary 类有操作符、左属性和右属性。操作符表示将对左右属性进行的操作。我们可以编写实现如下:

    class Visitor {
        visitBinary(binExpr) {  
            switch(binExpr.operator) {  
                case 'ADD':  
                // ...
            }  
        }
        visitLiteral(litExpr) {  
            return litExpr.value
        }  
    }
    

    注意,左值和右值都是表达式,可能是字面量表达式、二元表达式、调用表达式或者其它的表达式。我们并不能确保二元运算的左右两边总是字面量。每一个表达式必须有一个用于对表达式求值的访问方法,因此在上面的 visitBinary 方法中,我们通过调用各自对应的 visit 方法对 Binary 的左属性和右属性进行求值:

    class Visitor {
        visitBinary(binExpr) {  
            switch(binExpr.operator) {  
                case 'ADD':  
                    return binExpr.left.visit(this) + binExpr.right.visit(this)  
            }  
        }
        visitLiteral(litExpr) {  
            return litExpr.value
        }  
    }
    

    因此,无论左值和右值保存的是哪一种表达式,最后都可以进行传递。

    因此,如果我们有下面这些语句:

    const oneLit = new Literal('1')  
    const twoLit = new Literal('2')  
    const binExpr = new Binary(oneLit, 'ADD', twoLit)  
    const visitor = new Visitor()
    binExpr.visit(visitor)
    

    在这种情况下,二元运算保存的是字面量。

    访问者的 visitBinary 将会被调用,同时将 binExpr 传入,在 Vistor 类中,visitBinary 将 oneLit 作为左值,将 twoLit 作为右值。由于 oneLit 和 twoLit 都是 Literal 的实例,因此它们的访问方法会被调用,同时将 Visitor 类传入。对于 oneLit,其 Literal 类内部又会调用 Vistor 类的 visitLiteral 方法,并将 oneLit 传入,而 Vistor 中的 visitLiteral 方法返回 Literal 类的 value 属性,也就是 1。同理,对于 twoLit 来说,返回的是 2。

    因为执行了 switch 语句中的 case 'ADD',所以返回的值会相加,最后返回 3。

    如果我们将 binExpr.visit(visitor) 传给 console.log,它将会打印 3

    console.log(binExpr.visit(visitor))  
    // 3
    

    如下,我们传递一个 3 分支的二元运算:

    1 + 2 + 3
    

    首先,我们选择 1 + 2,那么其结果将作为左值,即 + 3。

    上述可以用 Binary 类表示为:

    new Binary (new Literal(1), 'ADD', new Binary(new Literal(2), 'ADD', new Literal(3)))
    

    可以看到,右值不是字面量,而是一个二元表达式。所以在执行加法运算之前,它必须先对这个二元表达式求值,并将其结果作为最终求值时的右值。

    const oneLit = new Literal(1)  
    const threeLit =new Literal(3)  
    const twoLit = new Literal(2)
    const binExpr2 = new Binary(twoLit, 'ADD', threeLit)  
    const binExpr1 = new Binary (oneLit, 'ADD', binExpr2)
    const visitor = new Visitor()
    log(binExpr1.visit(visitor))
    6
    

    添加 if 语句

    将 if 语句带到等式中。为了对一个 if 语句求值,我们将会给 IfStmt 类添加一个 visit 方法,之后它将调用 visitIfStmt 方法:

    class IfStmt {  
        constructor(condition, body) {  
            this.condition = condition
            this.body = body
        }
        visit(visitor) {  
            return visitor.visitIfStmt(this)  
        }  
    }
    

    见识到访问者模式的威力了吗?我们向一些类中新增了一个类,对应地只需要添加相同的访问方法即可,而这将调用它位于 Vistor 类中的对应方法。这种方式将不会破坏或者影响到其它的相关类,访问者模式让我们遵循了开闭原则。

    因此,我们在 Vistor 类中实现 visitIfStmt:

    class Visitor {  
        // ...
        visitIfStmt(ifStmt) {  
            if(ifStmt.condition.visit(this)) {  
                for(const stmt of ifStmt.body) {  
                    stmt.visit(this)  
                }  
            }  
        }  
    }
    

    因为条件是一个表达式,所以我们调用它的访问方法对其进行求值。我们使用 JS 中的 if 语句检查返回值,如果为真,则遍历语句的代码块 ifStmt.body,通过调用 visit 方法并传入 Vistor,对数组中每一条语句进行求值。

    因此我们可以翻译出这条语句:

    if(67 > 90)
    

    添加函数调用和函数声明

    接着来添加一个函数调用。我们已经有一个对应的类了:

    class FuncCall {  
        constructor(name, args) {  
            this.name = name
            this.args = args
        }  
    }
    

    添加一个访问方法:

    class FuncCall {  
        constructor(name, args) {  
            this.name = name
            this.args = args
        }
        visit(visitor) {  
            return visitor.visitFuncCall(this)  
        }  
    }
    

    给 Visitor 类添加 visitFuncCall 方法:

    class Visitor {  
        // ...
        visitFuncCall(funcCall) {  
            const funcName = funcCall.name
            const args = []  
            for(const expr of funcCall.args)  
                args.push(expr.visit(this))  
            // ...
        }  
    }
    

    这里有一个问题。除了内置函数之外,还有自定义函数,我们需要为后者创建一个“容器”,并在里面通过函数名保存和引用该函数。

    const FuncStore = (  
        class FuncStore {
            constructor() {  
                this.map = new Map()  
            }
            setFunc(name, body) {  
                this.map.set(name, body)  
            }
            getFunc(name) {  
                return this.map.get(name)  
            }  
        }  
        return new FuncStore()  
    )()
    

    FuncStore 保存着函数,并从一个 Map 实例中取回这些函数。

    class Visitor {  
        // ...
        visitFuncCall(funcCall) {  
            const funcName = funcCall.name
            const args = []  
            for(const expr of funcCall.args)  
                args.push(expr.visit(this))  
            if(funcName == "log")  
                console.log(...args)  
            if(FuncStore.getFunc(funcName))  
                FuncStore.getFunc(funcName).forEach(stmt => stmt.visit(this))  
        }  
    }
    

    看下我们做了什么。如果函数名 funcName(记住,FuncCall 类将函数名保存在 name 属性中)为 log,则运行 JS console.log(...),并传参给它。如果我们在函数保存中找到了函数,那么就对该函数体进行遍历,依次访问并执行。

    现在看看怎么把我们的函数声明放进函数保存中。

    函数声明以 fucntion 开头。一般的函数结构是这样的:

    function function_name(params) {  
        // function body
    }
    

    因此,我们可以在一个类中用属性表示一个函数声明:name 保存函数函数名,body 则是一个数组,保存函数体中的语句:

    class FunctionDeclaration {  
        constructor(name, body) {  
            this.name = name
            this.body = body
        }  
    }
    

    我们添加一个访问方法,该方法在 Vistor 中被称为 visitFunctionDeclaration:

    class FunctionDeclaration {  
        constructor(name, body) {  
            this.name = name
            this.body = body
        }
        visit(visitor) {  
            return visitor.visitFunctionDeclaration(this)  
        }  
    }
    

    在 Visitor 中:

    class Visitor {  
        // ...
        visitFunctionDeclaration(funcDecl) {  
            FuncStore.setFunc(funcDecl.name, funcDecl.body)  
        }  
    }
    

    将函数名作为键即可保存函数。

    现在,假设我们有下面这个函数:

    function addNumbers(a, b) {  
        log(a + b)  
    }
    function logNumbers() {  
        log(5)  
        log(6)  
    }
    

    它可以表示为:

    const funcDecl = new FunctionDeclaration('logNumbers', [  
        new FuncCall('log', [new Literal(5)]),  
        new FuncCall('log', [new Literal(6)])  
    ])
    visitor.visitFunctionDeclaration(funcDecl)
    

    现在,我们来调用函数 logNumbers:

    const funcCall = new FuncCall('logNumbers', [])  
    visitor.visitFuncCall(funcCall)
    

    控制台将会打印:

    5
    6
    

    结论

    理解 AST 的过程是令人望而生畏并且非常消耗脑力的。即使是编写最简单的解析器也需要大量的代码。

    注意,我们并没有介绍扫描仪和解析器,而是先行解释了 ASTs 以展示它们的工作过程。如果你能够深入理解 AST 以及它所需要的内容,那么在你开始编写自己的编程语言时,自然就事半功倍了。

    熟能生巧,你可以继续添加其它的编程语言特性,例如:

    • 类和对象

    • 方法调用

    • 封装和继承

    • for-of 语句

    • while 语句

    • for-in 语句

    • 其它任何你能想到的有趣特性

    关于本文译者:@Chor译文:https://segmentfault.com/a/1190000019491986作者:@Chidume Nnamdi原文:https://blog.bitsrc.io/what-is-an-abstract-syntax-tree-7502b71bde27?

     好文 推 荐 

    ☞ JavaScript 运行原理

    ☞ React Hooks: 没有魔法,只是数组

    ☞ 深入理解:React hooks是如何工作的

    好文章,我 在看 

    展开全文
  • 抽象语法树

    热门讨论 2019-03-10 19:56:54
    定义:在计算机科学中,抽象语法树(Abstract Syntax Tree,AST),或简称语法树(Syntax tree),是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构,树上的每个节点都表示源代码中的一种结构...

    定义:在计算机科学中,抽象语法树(Abstract Syntax Tree,AST),或简称语法树(Syntax tree),是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构,树上的每个节点都表示源代码中的一种结构。之所以说语法是“抽象”的,是因为这里的语法并不会表示出真实语法中出现的每个细节。比如,嵌套括号被隐含在树的结构中,并没有以节点的形式呈现;而类似于 if-condition-then 这样的条件跳转语句,可以使用带有两个分支的节点来表示。

    展开全文
  • 详解AST抽象语法树

    万次阅读 多人点赞 2018-12-11 22:01:52
    浅谈 AST 先来看一下把一个简单的函数转换成AST之后的样子。 // 简单函数 function square(n) { return n * n; } // 转换后的AST { type: "FunctionDeclaration", id: { ... pa...

    浅谈 AST

    先来看一下把一个简单的函数转换成AST之后的样子。

    // 简单函数
    function square(n) {
        return n * n;
    }
    
    // 转换后的AST
    {
       type: "FunctionDeclaration",
       id: {
           type: "Identifier",
           name: "square"
       },
       params: [
          {
               type: "Identifier",
               name: "n"
          }
       ],
       ...
    }

    从纯文本转换成树形结构的数据,每个条目和树中的节点一一对应。

    纯文本转AST的实现

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

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

    第一步:词法分析,也叫扫描scanner

    它读取我们的代码,然后把它们按照预定的规则合并成一个个的标识 tokens。同时,它会移除空白符、注释等。最后,整个代码将被分割进一个 tokens 列表(或者说一维数组)。

    const a = 5;
    // 转换成
    [{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]
      
    

    当词法分析源代码的时候,它会一个一个字母地读取代码,所以很形象地称之为扫描 - scans。当它遇到空格、操作符,或者特殊符号的时候,它会认为一个话已经完成了。

    第二步:语法分析,也称解析器

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

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

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

    解析器100%覆盖所有代码结构生成树叫做CST(具体语法树)。

    用例:代码转换之babel

    babel 是一个 JavaScript 编译器。宏观来说,它分3个阶段运行代码:解析(parsing) — 将代码字符串转换成 AST抽象语法树,转译(transforming) — 对抽象语法树进行变换操作,生成(generation) — 根据变换后的抽象语法树生成新的代码字符串。

    我们给 babel 一段 js 代码,它修改代码然后生成新的代码返回。它是怎么修改代码的呢?没错,它创建了 AST,遍历树,修改 tokens,最后从 AST中生成新的代码。

    详解 AST

    前言

    抽象语法树(AST),是一个非常基础而重要的知识点,但国内的文档却几乎一片空白。

    本文将带大家从底层了解AST,并且通过发布一个小型前端工具,来带大家了解AST的强大功能

    Javascript就像一台精妙运作的机器,我们可以用它来完成一切天马行空的构思。

    我们对javascript生态了如指掌,却常忽视javascript本身。这台机器,究竟是哪些零部件在支持着它运行?

    AST在日常业务中也许很难涉及到,但当你不止于想做一个工程师,而想做工程师的工程师,写出vue、react之类的大型框架,或类似webpack、vue-cli前端自动化的工具,或者有批量修改源码的工程需求,那你必须懂得AST。AST的能力十分强大,且能帮你真正吃透javascript的语言精髓。

    事实上,在javascript世界中,你可以认为抽象语法树(AST)是最底层。 再往下,就是关于转换和编译的“黑魔法”领域了。

    人生第一次拆解Javascript

    小时候,当我们拿到一个螺丝刀和一台机器,人生中最令人怀念的梦幻时刻便开始了:

    我们把机器,拆成一个一个小零件,一个个齿轮与螺钉,用巧妙的机械原理衔接在一起…

    当我们把它重新照不同的方式组装起来,这时,机器重新又跑动了起来——世界在你眼中如获新生。

    通过抽象语法树解析,我们可以像童年时拆解玩具一样,透视Javascript这台机器的运转,并且重新按着你的意愿来组装。

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

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

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

    用力拆开,它成了三块:

    • 一个id,就是它的名字,即add

    • 两个params,就是它的参数,即[a, b]

    • 一块body,也就是大括号内的一堆东西

    add没办法继续拆下去了,它是一个最基础Identifier(标志)对象,用来作为函数的唯一标志,就像人的姓名一样。

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

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

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

    接下来,我们继续拆开body

    我们发现,body其实是一个BlockStatement(块状域)对象,用来表示是{return a + b}

    打开Blockstatement,里面藏着一个ReturnStatement(Return域)对象,用来表示return a + b

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

    继续打开BinaryExpression,它成了三部分,left,operator,right

    • operator 即+

    • left 里面装的,是Identifier对象 a

    • right 里面装的,是Identifer对象 b

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

    看!抽象语法树(Abstract Syntax Tree),的确是一种标准的树结构。

    那么,上面我们提到的Identifier、Blockstatement、ReturnStatement、BinaryExpression, 这一个个小部件的说明书去哪查?

    送给你的AST螺丝刀:recast

    输入命令:

    npm i recast -S

    你即可获得一把操纵语法树的螺丝刀

    接下来,你可以在任意js文件下操纵这把螺丝刀,我们新建一个parse.js示意:

    parse.js

    // 给你一把"螺丝刀"——recast
    const recast = require("recast");
    // 你的"机器"——一段代码
    // 我们使用了很奇怪格式的代码,想测试是否能维持代码结构
    const code =
      `
      function add(a, b) {
        return a +
          // 有什么奇怪的东西混进来了
          b
      }
      `
    // 用螺丝刀解析机器
    const ast = recast.parse(code);
    // ast可以处理很巨大的代码文件
    // 但我们现在只需要代码块的第一个body,即add函数
    const add  = ast.program.body[0]
    console.log(add)

    输入node parse.js你可以查看到add函数的结构,与之前所述一致,通过AST对象文档可查到它的具体属性:

    FunctionDeclaration{
        type: 'FunctionDeclaration',
        id: ...
        params: ...
        body: ...
    }

    你也可以继续使用console.log透视它的更内层,如:

    console.log(add.params[0])
    console.log(add.body.body[0].argument.left)

    recast.types.builders 制作模具

    一个机器,你只会拆开重装,不算本事。

    拆开了,还能改装,才算上得了台面。

    recast.types.builders里面提供了不少“模具”,让你可以轻松地拼接成新的机器。

    最简单的例子,我们想把之前的function add(a, b){…}声明,改成匿名函数式声明const add = function(a ,b){…}

    如何改装?

    第一步,我们创建一个VariableDeclaration变量声明对象,声明头为const, 内容为一个即将创建的VariableDeclarator对象。

    第二步,创建一个VariableDeclarator,放置add.id在左边, 右边是将创建的FunctionDeclaration对象

    第三步,我们创建一个FunctionDeclaration,如前所述的三个组件,id params body中,因为是匿名函数id设为空,params使用add.params,body使用add.body。

    这样,就创建好了const add = function(){}的AST对象。

    在之前的parse.js代码之后,加入以下代码

    // 引入变量声明,变量符号,函数声明三种“模具”
    const {variableDeclaration, variableDeclarator, functionExpression} = recast.types.builders
    // 将准备好的组件置入模具,并组装回原来的ast对象。
    ast.program.body[0] = variableDeclaration("const", [
      variableDeclarator(add.id, functionExpression(
        null, // Anonymize the function expression.
        add.params,
        add.body
      ))
    ]);
    //将AST对象重新转回可以阅读的代码
    const output = recast.print(ast).code;
    console.log(output)

    可以看到,我们打印出了

    const add = function(a, b) {
      return a +
        // 有什么奇怪的东西混进来了
        b};

    最后一行

    const output = recast.print(ast).code;

    其实是recast.parse的逆向过程,具体公式为

    recast.print(recast.parse(source)).code === source

    打印出来还保留着“原装”的函数内容,连注释都没有变。

    我们其实也可以打印出美化格式的代码段:

    const output = recast.prettyPrint(ast, { tabWidth: 2 }).code

    输出为

    const add = function(a, b) {
      return a + b;
    };

    现在,你是不是已经产生了“我可以通过AST树生成任何js代码”的幻觉?我郑重告诉你,这不是幻觉。

    实战进阶:命令行修改js文件

    除了parse/print/builder以外,Recast的三项主要功能:

    • run: 通过命令行读取js文件,并转化成ast以供处理。

    • tnt: 通过assert()和check(),可以验证ast对象的类型。

    • visit: 遍历ast树,获取有效的AST对象并进行更改。

    我们通过一个系列小务来学习全部的recast工具库:

    创建一个用来示例文件,假设是demo.js

    demo.js

    function add(a, b) {
      return a + b
    }
    function sub(a, b) {
      return a - b
    }
    function commonDivision(a, b) {
      while (b !== 0) {
        if (a > b) {
          a = sub(a, b)
        } else {
          b = sub(b, a)
        }
      }
      return a
    }

    recast.run —— 命令行文件读取

    新建一个名为read.js的文件,写入

    read.js

    recast.run( function(ast, printSource){
        printSource(ast)
    })

    命令行输入

    node read demo.js

    我们查以看到js文件内容打印在了控制台上。

    我们可以知道,node read可以读取demo.js文件,并将demo.js内容转化为ast对象。

    同时它还提供了一个printSource函数,随时可以将ast的内容转换回源码,以方便调试。

    recast.visit —— AST节点遍历

    read.js

    #!/usr/bin/env node
    const recast  = require('recast')
    recast.run(function(ast, printSource) {
      recast.visit(ast, {
          visitExpressionStatement: function({node}) {
            console.log(node)
            return false
          }
        });
    });

    recast.visit将AST对象内的节点进行逐个遍历。

    注意

    • 你想操作函数声明,就使用visitFunctionDelaration遍历,想操作赋值表达式,就使用visitExpressionStatement。 只要在 AST对象文档中定义的对象,在前面加visit,即可遍历。

    • 通过node可以取到AST对象

    • 每个遍历函数后必须加上return false,或者选择以下写法,否则报错:

    #!/usr/bin/env node
    const recast  = require('recast')
    recast.run(function(ast, printSource) {
      recast.visit(ast, {
          visitExpressionStatement: function(path) {
            const node = path.node
            printSource(node)
            this.traverse(path)
          }
        })
    });

    调试时,如果你想输出AST对象,可以console.log(node)

    如果你想输出AST对象对应的源码,可以printSource(node)

    命令行输入node read demo.js进行测试。

    #!/usr/bin/env node

    在所有使用recast.run()的文件顶部都需要加入这一行,它的意义我们最后再讨论。

    TNT —— 判断AST对象类型

    TNT,即recast.types.namedTypes,就像它的名字一样火爆,它用来判断AST对象是否为指定的类型。

    TNT.Node.assert(),就像在机器里埋好的炸药,当机器不能完好运转时(类型不匹配),就炸毁机器(报错退出)

    TNT.Node.check(),则可以判断类型是否一致,并输出False和True

    上述Node可以替换成任意AST对象,例如TNT.ExpressionStatement.check(),TNT.FunctionDeclaration.assert()

    read.js

    #!/usr/bin/env node
    const recast = require("recast");
    const TNT = recast.types.namedTypes
    recast.run(function(ast, printSource) {
      recast.visit(ast, {
          visitExpressionStatement: function(path) {
            const node = path.value
            // 判断是否为ExpressionStatement,正确则输出一行字。
            if(TNT.ExpressionStatement.check(node)){
              console.log('这是一个ExpressionStatement')
            }
            this.traverse(path);
          }
        });
    });

    read.js

    #!/usr/bin/env node
    const recast = require("recast");
    const TNT = recast.types.namedTypes
    recast.run(function(ast, printSource) {
      recast.visit(ast, {
          visitExpressionStatement: function(path) {
            const node = path.node
            // 判断是否为ExpressionStatement,正确不输出,错误则全局报错
            TNT.ExpressionStatement.assert(node)
            this.traverse(path);
          }
        });
    });

    命令行输入node read demo.js进行测试。

    实战:用AST修改源码,导出全部方法

    exportific.js

    现在,我们希望将demo中的function全部

    我们想让这个文件中的函数改写成能够全部导出的形式,例如

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

    想改变为

    exports.add = (a, b) => {
      return a + b
    }

    除了使用fs.read读取文件、正则匹配替换文本、fs.write写入文件这种笨拙的方式外,我们可以==用AST优雅地解决问题==。

    首先,我们先用builders凭空实现一个键头函数

    exportific.js

    #!/usr/bin/env node
    const recast = require("recast");
    const {
      identifier:id,
      expressionStatement,
      memberExpression,
      assignmentExpression,
      arrowFunctionExpression,
      blockStatement} = recast.types.builders
    recast.run(function(ast, printSource) {
      // 一个块级域 {}
      console.log('\n\nstep1:')
      printSource(blockStatement([]))
    
      // 一个键头函数 ()=>{}
      console.log('\n\nstep2:')
      printSource(arrowFunctionExpression([],blockStatement([])))
    
      // add赋值为键头函数  add = ()=>{}
      console.log('\n\nstep3:')
      printSource(assignmentExpression('=',id('add'),arrowFunctionExpression([],blockStatement([]))))
    
      // exports.add赋值为键头函数  exports.add = ()=>{}
      console.log('\n\nstep4:')
      printSource(expressionStatement(assignmentExpression('=',memberExpression(id('exports'),id('add')),
        arrowFunctionExpression([],blockStatement([])))))
    });

    上面写了我们一步一步推断出exports.add = ()=>{}的过程,从而得到具体的AST结构体。

    使用node exportific demo.js运行可查看结果。

    接下来,只需要在获得的最终的表达式中,把id(‘add’)替换成遍历得到的函数名,把参数替换成遍历得到的函数参数,把blockStatement([])替换为遍历得到的函数块级作用域,就成功地改写了所有函数!

    另外,我们需要注意,在commonDivision函数内,引用了sub函数,应改写成exports.sub

    exportific.js

    #!/usr/bin/env node
    const recast = require("recast");
    const {
      identifier: id,
      expressionStatement,
      memberExpression,
      assignmentExpression,
      arrowFunctionExpression} = recast.types.builders
    recast.run(function (ast, printSource) {
      // 用来保存遍历到的全部函数名
      let funcIds = []
      recast.types.visit(ast, {
        // 遍历所有的函数定义
        visitFunctionDeclaration(path) {
          //获取遍历到的函数名、参数、块级域
          const node = path.node
          const funcName = node.id
          const params = node.params
          const body = node.body
    
          // 保存函数名
          funcIds.push(funcName.name)
          // 这是上一步推导出来的ast结构体
          const rep = expressionStatement(assignmentExpression('=', memberExpression(id('exports'), funcName),
            arrowFunctionExpression(params, body)))
          // 将原来函数的ast结构体,替换成推导ast结构体
          path.replace(rep)
          // 停止遍历
          return false
        }
      })
    
    
      recast.types.visit(ast, {
        // 遍历所有的函数调用
        visitCallExpression(path){
          const node = path.node;
          // 如果函数调用出现在函数定义中,则修改ast结构
          if (funcIds.includes(node.callee.name)) {
            node.callee = memberExpression(id('exports'), node.callee)
          }
          // 停止遍历
          return false
        }
      })
      // 打印修改后的ast源码
      printSource(ast)
    })

    一步到位,发一个最简单的exportific前端工具

    上面讲了那么多,仍然只体现在理论阶段。

    但通过简单的改写,就能通过recast制作成一个名为exportific的源码编辑工具。

    以下代码添加作了两个小改动

    • 添加说明书—help,以及添加了—rewrite模式,可以直接覆盖文件或默认为导出*.export.js文件。

    • 将之前代码最后的 printSource(ast)替换成 writeASTFile(ast,filename,rewriteMode)

    exportific.js

    #!/usr/bin/env node
    const recast = require("recast");
    const {
      identifier: id,
      expressionStatement,
      memberExpression,
      assignmentExpression,
      arrowFunctionExpression} = recast.types.builders
    const fs = require('fs')
    const path = require('path')
    // 截取参数
    const options = process.argv.slice(2)
    //如果没有参数,或提供了-h 或--help选项,则打印帮助
    if(options.length===0 || options.includes('-h') || options.includes('--help')){
      console.log(`
        采用commonjs规则,将.js文件内所有函数修改为导出形式。
    
        选项: -r  或 --rewrite 可直接覆盖原有文件
        `)
      process.exit(0)
    }
    // 只要有-r 或--rewrite参数,则rewriteMode为true
    let rewriteMode = options.includes('-r') || options.includes('--rewrite')
    // 获取文件名
    const clearFileArg = options.filter((item)=>{
      return !['-r','--rewrite','-h','--help'].includes(item)
    })
    // 只处理一个文件
    let filename = clearFileArg[0]
    const writeASTFile = function(ast, filename, rewriteMode){
      const newCode = recast.print(ast).code
      if(!rewriteMode){
        // 非覆盖模式下,将新文件写入*.export.js下
        filename = filename.split('.').slice(0,-1).concat(['export','js']).join('.')
      }
      // 将新代码写入文件
      fs.writeFileSync(path.join(process.cwd(),filename),newCode)
    }
    recast.run(function (ast, printSource) {
      let funcIds = []
      recast.types.visit(ast, {
        visitFunctionDeclaration(path) {
          //获取遍历到的函数名、参数、块级域
          const node = path.node
          const funcName = node.id
          const params = node.params
          const body = node.body
    
          funcIds.push(funcName.name)
          const rep = expressionStatement(assignmentExpression('=', memberExpression(id('exports'), funcName),
            arrowFunctionExpression(params, body)))
          path.replace(rep)
          return false
        }
      })
    
    
      recast.types.visit(ast, {
        visitCallExpression(path){
          const node = path.node;
          if (funcIds.includes(node.callee.name)) {
            node.callee = memberExpression(id('exports'), node.callee)
          }
          return false
        }
      })
    
      writeASTFile(ast,filename,rewriteMode)
    })

    现在尝试一下

    node exportific demo.js

    已经可以在当前目录下找到源码变更后的demo.export.js文件了。

    npm发包

    编辑一下package.json文件

    {
      "name": "exportific",
      "version": "0.0.1",
      "description": "改写源码中的函数为可exports.XXX形式",
      "main": "exportific.js",
      "bin": {
        "exportific": "./exportific.js"
      },
      "keywords": [],
      "author": "wanthering",
      "license": "ISC",
      "dependencies": {
        "recast": "^0.15.3"
      }
    }

    注意bin选项,它的意思是将全局命令exportific指向当前目录下的exportific.js

    这时,输入npm link 就在本地生成了一个exportific命令。

    之后,只要哪个js文件想导出来使用,就exportific XXX.js一下。

    这是在本地的玩法,想和大家一起分享这个前端小工具,只需要发布npm包就行了。

    同时,一定要注意exportific.js文件头有

    #!/usr/bin/env node

    否则在使用时将报错。

    接下来,正式发布npm包!

    如果你已经有了npm 帐号,请使用npm login登录

    如果你还没有npm帐号 https://www.npmjs.com/signup 非常简单就可以注册npm

    然后,输入
    npm publish

    没有任何繁琐步骤,丝毫审核都没有,你就发布了一个实用的前端小工具exportific 。任何人都可以通过

    npm i exportific -g

    全局安装这一个插件。

    提示:在试验教程时,请不要和我的包重名,修改一下发包名称。

    结语

    我们对javascript再熟悉不过,但透过AST的视角,最普通的js语句,却焕发出精心动魄的美感。你可以通过它批量构建任何javascript代码!

    童年时,这个世界充满了新奇的玩具,再普通的东西在你眼中都如同至宝。如今,计算机语言就是你手中的大玩具,一段段AST对象的拆分组装,构建出我们所生活的网络世界。

    所以不得不说软件工程师是一个幸福的工作,你心中住的仍然是那个午后的少年,永远有无数新奇等你发现,永远有无数梦想等你构建。

    项目代码:https://github.com/wanthering/exportific

     

     

    参考文章:https://segmentfault.com/a/1190000016231512

                      https://github.com/CodeLittlePrince/blog/issues/19

    展开全文
  • 解释抽象语法树

    千次阅读 2014-06-04 14:28:15
    解释抽象语法树   创建了抽象语法树之后,有两个选择:解释或编译。解释,简单地说,就是遍历树,同时执行操作;编译,就是改变成其他形式,对于机器执行来说可能更简单,通常可能更快。这一小节先讨论如何解释...
  • AST抽象语法树

    千次阅读 2018-09-16 13:54:23
    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套...
  • 【转】抽象语法树简介(AST)

    万次阅读 2013-01-08 09:18:58
    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套括
  • 详细介绍了antlr抽象语法树的构建,搞软件工程的相关人士可参考使用
  • 抽象语法树手动生成--java实现

    万次阅读 2018-06-05 21:02:26
    ManualAST.javapackage sch.cauc.edu.token; import org.eclipse.jdt.core.dom.AST; import org.eclipse.jdt.core.dom.Assignment; import org.eclipse.jdt.core.dom.Block; import org.eclipse.jdt.core.dom.Expre...
  • python抽象语法树Abstract Syntax Tree is a very strong features in Python. Python AST module allows us to interact with Python code itself and modify it. 抽象语法树是Python中非常强大的功能。 Python AST...
  • GCC抽象语法树

    千次阅读 2013-09-04 17:12:45
    #include #include #include #include #include #include using namespace std; const int LINE=99999; const int BUF_SIZE=1000; int totalline=0; //总行数 int useful[LINE]= {0};...const int STYP
  • AST 抽象语法树

    千次阅读 2019-04-26 12:57:23
    AST 抽象语法树简介 AST(Abstract Syntax Tree)是源代码的抽象语法结构树状表现形式,Webpack、ESLint、JSX、TypeScript 的编译和模块化规则之间的转化都是通过 AST 来实现对代码的检查、分析以及编译等操作。 ...
  • AST-抽象语法树

    万次阅读 2015-05-14 09:49:50
    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌
  • Python随笔(四)抽象语法树AST

    千次阅读 2019-06-13 05:23:14
    为什么80%的码农都做不了架构师?>>> ...
  • C 语言 抽象语法树AST

    千次阅读 2018-12-05 13:51:15
    抽象语法树(abstract syntax code,AST)是源代码的抽象语法结构的树状表示,树上的每个节点都表示源代码中的一种结构,这所以说是抽象的,是因为抽象语法树并不会表示出真实语法出现的每一个细节,比如说,嵌套...
  • Java抽象语法树AST浅析与使用

    千次阅读 2019-10-30 11:48:09
    Java抽象语法树AST浅析与使用概述作用Java项目模型对象AST模型对象AST试图具体使用 概述 抽象语法树(Abstract Syntax Tree, AST)是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的结构,树的每个节点...
  • 编译抽象语法树

    千次阅读 2014-06-06 15:35:14
    编译抽象语法树   对大多数开发人员来说,编译就意谓着产生本地代码,给人感觉就是一个字,难。但是,并不一定要产生本地代码,对于 DSL,通常产生其他更加通用的编程语言。.NET 框架提供几个把抽象语法树编译成...
  • 什么是抽象语法树? 在计算机科学中,抽象语法和抽象语法树其实是源代码的抽象语法结构的树状表现形式 在线编辑器 我们常用的浏览器就是通过将js代码转化为抽象语法树来进行下一步的分析等其他操作。所以将js转化为...
  • 抽象语法树是什么 在计算机科学中,抽象语法树(abstract syntax tree 或者缩写为 *AST*),或者语法树(*syntax tree*),是源代码的抽象语法结构的树状表现形式,这里特指编程语言的源代码。树上的每个节点都...
  • 试了下解析TPCH里面的Q9,解释如下: hive> explain insert overwrite table q9_product_type_profit  > select   > nation, o_year, sum(amount) as sum_profit  > from   > ( ... >
1 2 3 4 5 ... 20
收藏数 53,608
精华内容 21,443
关键字:

抽象语法树