vlambda博客
学习文章列表

编译器"吸星大法"之抽象语法树(AST)

概述

    说到这个话题我相信部分朋友应该会有点蒙,这玩意是啥?,笔者个人认为AST几乎无处不在,这么说可能又有部分朋友又不理解了,OK ,本文会带各位做一个初步的了解,以及实际案例和实战应用,打个委婉的比喻我们可以说AST就像“九阳神功”-内功心法,有了这套心法,自己创造一门武学也是轻车熟路。

上段说到其“内功心法”无处不在,这里笔者先简单举几个常见的例子如下:


  • Druid

    Druid提供SQL完整解析功能,根据不同的SQL关键字生成语法树进而进行处理

  • 模板引擎(例如FTL ,  HTTL , Velocity etc . .)

    解析模板引擎的时候会首先进行分词生成tokens,然后语义或者文本处理,接着生成树形结构,随后使用对应设计模式对其进行访问,最后渲染,渲染的过程就是值填充的过程。

  • ASM

    ASM是一款字节码修改工具,像我们spring,JDK的动态代理底层就是ASM,所以基本可以理解为java使用动态代理的地方都会用到。

  • JSON解析引擎(以fastjson为代表)

    对JSON关键字解析的时候会用到ASM的包


当然除此之外很多地方,比如我们的编译器底层解析代码的时候也是站在AST的肩膀上,再比如我们熟知的javascript脚本解析器在解析js脚本的时候会生成抽象语法树,然后使用访问者模式(后文实例讲解的时候会有说明)对其进行访问,汇总一句话,"但凡文本指令解析说透了都是对AST的处理"。


心法提炼

接下来我们开始以一个模板引擎案例简单诠释一下AST的用法,一个优秀的模板引擎几乎都会用到语法解析,在诠释之前我们先来看看流程图:


上图为编译原理虎皮书里边的借鉴,描述编译器的基本流程,我们只需要关注前端编译生成语法树之前的部分


流程梳理如下:

首先会进行词法分析(Lexical Analysis),我们俗称为“分词”,之后经语法分析(Syntax Analysis)也就是检查是否符合定义的语法,如果不符合报错,之后经语义分析(Semantic Analysis),意思就是通过对应文档发现对应词的潜在意思和意义,和中文的一词多义很相似,语义分析我们这边没有语义文档,本文不作讲解。


PS: 当我们熟悉上述流程之后接下来我们以HTTL为例,通过源码调试进一步说明AST的重要性,对于HTTL模板引擎感兴趣的可以去看下,我个人觉得是一个很好的学习案例,把个武学招式,分招分式的简化到了极致



编译器"吸星大法"之抽象语法树(AST)


附上官网链接:http://httl.github.io/zh/

据官网数据报告得出HTTL在效率方面几乎接近于JAVA硬编码,远高于其他流行模板引擎。


接下来我们开始边调试代码边讲解,代码结构如下:

编译器"吸星大法"之抽象语法树(AST)

HTTL采用模块依赖,所以我们剑指核心心法,也就是上图红色框内容,分包详细解释见官网(例如SPI),这里我们主要讲AST包,因为要调试源码笔者首先想到的是测试用例,

编译器"吸星大法"之抽象语法树(AST)

看到这里某些读者可能会发现liangfei字眼,没错这就是梁飞大神的作品,当年阿里风声水起的亿级dubbo SOA架构,直到现在ali-cloud-dubbo的集成,后来作为apache基金会的顶级项目孵化,一直阿里一直都没有放弃过dubbo,而dubbo的主要开发就是梁飞,打个广告 _ _ ! 我的偶像


直接运行测试用例:

编译器"吸星大法"之抽象语法树(AST)

运行之后进我之前打好的初始化断点如下:

编译器"吸星大法"之抽象语法树(AST)

上图会进行set操作,既然是初始化,简单说明一下,因为HTTL需要一个BEAN容器,但是为了减少依赖和重IOC框架引入,HTTL自己实现了一个beanFactory,作为各插件对象的核心通过SPI整合,这和spring 的容器很相似,对于这里之所以会调用set方法,其实就很好理解了,IOC容器通过反射注入对象调用set方法,我们继续。

编译器"吸星大法"之抽象语法树(AST)

当我们断点到这里的时候,我们可以看到我们的目标是hello.httl的处理,我们看看hello.httl脚本代码如下。

<!--#macro(hello(String name))-->Hello, ${name}!<!--#end--><!--#macro(welcome(String name))-->Welcome to hangzhou, ${name}!<!--#end-->

HTTL会把每一个httl文件都看成一个resource

编译器"吸星大法"之抽象语法树(AST)

我们可以看到有这么多resource的实现,ok,我们测试用例用的就是ClasspathResource,说明一下继续。

编译器"吸星大法"之抽象语法树(AST)

我们可以看到正确的加载了resource ,

编译器"吸星大法"之抽象语法树(AST)

这里不多说,毕竟文件加载不是我们的重点,

编译器"吸星大法"之抽象语法树(AST)

当代码走到240 line的时候就会通过流读到其模板内容,

编译器"吸星大法"之抽象语法树(AST)

我们可以看到当前classpathResource没有实现该方法,很显然调用的是抽象父类的方法,我们进去看看。

编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

这样我们就拿到了模板内容了,接下来就是我们需要睁大眼睛的“内功心法”。

编译器"吸星大法"之抽象语法树(AST)

走过滤器之后会看到一个解析的过程,我标注了该过程是生成AST的核心所在,也是武学精髓所在,我们开始。

编译器"吸星大法"之抽象语法树(AST)

我们可以看到有三个方法,顺序是先走scan  === > clean ====> trim,对应开篇的流程图,这里的clean , trim 属于语义分析部分,这里我们先过,详细看scan是如何做的,如下

编译器"吸星大法"之抽象语法树(AST)

走到这里会进行分词,因为分词的代码比较多,我直接写好注释贴出如下:

/** * 分词采用状态机模式根据不同关键字进行分词, * 让我想起了fastjson的解析,也是用的状态机模式 * @param charStream * @param offset * @param errorWithSource * @return * @throws ParseException */ public List<Token> scan(String charStream, int offset, boolean errorWithSource) throws ParseException { List<Token> tokens = new ArrayList<Token>(); // 解析时状态  StringBuilder buffer = new StringBuilder(); // 缓存字符 StringBuilder remain = new StringBuilder(); // 残存字符 int pre = 0; // 上一状态 int state = 0; // 当前状态 char ch; // 当前字符
// 逐字解析 ---- int i = 0; int p = 0; for (; ; ) { if (remain.length() > 0) { // 先处理残存字符 ch = remain.charAt(0); remain.deleteCharAt(0); } else { // 没有残存字符则读取字符流 if (i >= charStream.length()) { break; } ch = charStream.charAt(i++); offset++; }
buffer.append(ch); // 将字符加入缓存 state = next(state, ch); // 从状态机图中取下一状态,状态机图采用二维数据装饰 if (state <= ERROR) { throw new ParseException("DFAScanner.state.error, error code: " + (ERROR - state) + (errorWithSource ? ", source: " + charStream : ""), offset - buffer.length()); } if (state <= POP) { int n = -(state % POP); int e = (state - n) / POP - 1; if (p <= 0) { throw new ParseException("DFAScanner.mismatch.stack" + (errorWithSource ? ", source: " + charStream : ""), offset - buffer.length()); } p--; if (p == 0) { state = e; if (state == 0) { state = BREAK; } } else { state = n; continue; } } else if (state <= PUSH) { p++; state = PUSH - state; continue; } if (state <= BREAK) { // 负数表示接收状态 int acceptLength; if (state <= BACKSPACE) { acceptLength = buffer.length() + state - BACKSPACE;//状态回退,回退所有空白符,退回的字符将重新读取 if (acceptLength > 0) { int space = 0; for (int s = acceptLength - 1; s >= 0; s--) { if (Character.isSpaceChar(buffer.charAt(s))) { space++; } else { break; } } acceptLength = acceptLength - space; } } else { acceptLength = buffer.length() + state - BREAK; } if (acceptLength < 0 || acceptLength > buffer.length()) throw new ParseException("DFAScanner.accepter.error" + (errorWithSource ? ", source: " + charStream : ""), offset - buffer.length()); if (acceptLength != 0) { String message = buffer.substring(0, acceptLength); Token token = new Token(message, offset - buffer.length(), pre); tokens.add(token);// 完成接收 } if (acceptLength != buffer.length()) //没有结束,比如"(hello),jack",httl会在读到','之后的'j'的时候回到分片状态 //那么会把"(hello)",作为第一个token,而','作为残存记录,开始状态回退state.BREAK从新读取 remain.insert(0, buffer.substring(acceptLength)); // 将未接收的缓存记入残存 buffer.setLength(0); // 清空缓存 state = 0; // 回归到初始状态 } pre = state; } // 接收最后缓存中的内容 if (buffer.length() > 0) { String message = buffer.toString(); tokens.add(new Token(message, offset - message.length(), pre)); } return tokens; }

那么分词成功之后我们可以看到如下:

编译器"吸星大法"之抽象语法树(AST)

我们继续。

编译器"吸星大法"之抽象语法树(AST)

接下来我们会经过syntax analysis ,篇幅限制代码就不贴了,最终我们会把这13个TOKEN转换成我们各自语法node,如下:

编译器"吸星大法"之抽象语法树(AST)

我们可以看到对应生成你了不同指令节点,文本节点text,这些指令在我们编写解析器引擎的时候自己可以定义,我们看看HTTL定义了哪些指令

编译器"吸星大法"之抽象语法树(AST)

解释一下指令都继承AbstractNode,其作为Node的子类存在,我们也可以很明显的看出来,Expression(表达式),statement(域),而表达式又包括Operator,比如上图的一元操作符UnaryOpertator(类似 (e) -> e )等,和对应指令Directive。

分词语法分析之后会生成抽象语法树:

编译器"吸星大法"之抽象语法树(AST)

其中reduce方法就是生成语法树的简单逻辑:


private BlockDirective reduce(List<Statement> directives) throws ParseException { LinkedStack<BlockDirectiveEntry> directiveStack = new LinkedStack<BlockDirectiveEntry>(); RootDirective rootDirective = new RootDirective(); directiveStack.push(new BlockDirectiveEntry(rootDirective)); for (Statement directive : directives) { if (directive == null) continue; Class<?> directiveClass = directive.getClass(); // 弹栈 if (directiveClass == EndDirective.class || directiveClass == ElseDirective.class) { if (directiveStack.isEmpty()) throw new ParseException("Miss #end directive.", directive.getOffset()); BlockDirective blockDirective = directiveStack.pop().popDirective(); if (blockDirective == rootDirective) throw new ParseException("Miss #end directive.", directive.getOffset()); EndDirective endDirective; if (directiveClass == ElseDirective.class) { endDirective = new EndDirective(directive.getOffset()); } else { endDirective = (EndDirective) directive; } blockDirective.setEnd(endDirective); } // 设置树 if (directiveClass != EndDirective.class) { // 排除EndDirective if (directiveStack.isEmpty()) throw new ParseException("Miss #end directive.", directive.getOffset()); directiveStack.peek().appendInnerDirective(directive); } // 压栈 if (directive instanceof BlockDirective) directiveStack.push(new BlockDirectiveEntry((BlockDirective) directive)); } BlockDirective root = directiveStack.pop().popDirective(); if (!directiveStack.isEmpty()) { // 后验条件 throw new ParseException("Miss #end directive." + root.getClass().getSimpleName(), root.getOffset()); } return root; }   

编译器"吸星大法"之抽象语法树(AST)

如果上图我们可以看到对比的结果,通过stack的特性进行一个节点的子节点的组装,举个例子:我们要读1 + 3 * 4 这个Operator,1先入栈接着 + 号,然后3  发现 * 号比 + 号优先级高 继续入栈,遇到4 的时候出栈3 和 * 号做操作 3 * 4 = 12 随后在出栈+ 号 和 1 做 1  + 12 操作 = 13 ,其实理解就是先处理的那个操作符作为树的一个根节点,其子节点作为要参数,和这里的 BlockDirectiveEntry很像,因为要处理根的子节点所以入栈出栈都是在根上。

继续,

编译器"吸星大法"之抽象语法树(AST)

到这里我们的抽象语法树就生成了,我们以JSON 的方式打印看看树的结构如下:

编译器"吸星大法"之抽象语法树(AST)

有经验的同学应该有感觉,MAP结构 ,树,JSON,其实是可以互相转换的,我们大体可以看出指令记录了内容,名字,和类型,以及对于子节点和offset字符偏移量。

那么接下来就需要对语法树进行访问了:

编译器"吸星大法"之抽象语法树(AST)

247行代码对语法树的访问和处理,进去

编译器"吸星大法"之抽象语法树(AST)

这里的使用的提前编译,也就是说每个模板会提前编译成字节码,也这就是官网为什么说HTTL极致的优化,在模板渲染的时候一个模板可以对应多个业务,所以静态模板只需要提前编译一次就可以了,不同的只是渲染的过程,

编译器"吸星大法"之抽象语法树(AST)

以上为官网的描述,其实在这里就可以提现了,我们继续

编译器"吸星大法"之抽象语法树(AST)

进去之后我们会走到这个方法,410行代码会生成一个不存在的名字,也就是需要运行时编译生成的类的名字,然后会走catch ,我们看看catch部分如下:

编译器"吸星大法"之抽象语法树(AST)

走到446行代码就开始了不同Node对于最后生成的动态编译类不同功能的组装,既然要组装类,那么肯定需要进行之前Node语法树的访问(能访问才能处理嘛),访问用到了访问者模式(有时间的可以先去看看,可能篇幅有限不会讲很细),也就是开篇说到的ASM在运行时访问每个类结构的时候用的方式

ok,我们debug进去,此时我们的root就是一开始的rootDirectve


编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

我们可以看到进去之后会直接调用visitor.visit(this),在进去走visit方法,也就是如上图方法,那么这里的this是什么,其实就是刚刚rootDirective,这里就是访问者模式比较怪异的地方,抽象Node对象会准备一个accept方法接收访问者,而该方法会直接调用型参访问者对象的visit方法,传this,其实这里已经是访问者模式的精髓了,访问者模式访问者提供具体处理功能方法,被访问者对象只需要提供需要被处理的哪些功能,我们继续。

编译器"吸星大法"之抽象语法树(AST)

因为root节点不需要处理,所以直接返回true,到这里我们一级一级返回,

编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

46行返回true会走到47行代码,继续往下,会递归遍历,走到49行代码

编译器"吸星大法"之抽象语法树(AST)

我们以其中一个Text指令为例说明,继续

编译器"吸星大法"之抽象语法树(AST)

这里会调用compiledVisitor的对应型参的指定方法如下

编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

最后会生成一段字符串存入CompileVisitor的全局变量StringBuilder内,这只是其中一个节点的处理,这不是重点我们跳过,节点(#marco)处理完就可以开始预编译流程了,预编译会调用CompileVisitor.compile方法

编译器"吸星大法"之抽象语法树(AST)

编译器"吸星大法"之抽象语法树(AST)

package httl.spi.translators.templates;
import httl.test.model.*;import httl.test.method.*;import java.util.*;import httl.*;import httl.util.*;
public final class Template__macros_hello_httl_hello_comment_UTF_8_1580988759389_writer extends httl.spi.translators.templates.WriterTemplate {
private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[0], new Class[0]);private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[0], new Class[0]);private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[0], new Class[0]);private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[0], new Class[0]);private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[0], new Class[0]);private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final char[] $TXT1 = httl.util.CharCache.getAndRemove("2");private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final String $TXT2 = httl.util.StringCache.getAndRemove("1");private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final char[] $TXT3 = httl.util.CharCache.getAndRemove("3");private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});private static final java.util.Map $VARS = new httl.util.OrderedMap(new String[] {"name"}, new Class[] {java.lang.String.class});
private final httl.spi.methods.TypeMethod $httl_spi_methods_TypeMethod;private final httl.spi.methods.CodecMethod $httl_spi_methods_CodecMethod;private final httl.spi.methods.LangMethod $httl_spi_methods_LangMethod;private final httl.spi.methods.FileMethod $httl_spi_methods_FileMethod;private final httl.spi.methods.MessageMethod $httl_spi_methods_MessageMethod;

public Template__macros_hello_httl_hello_comment_UTF_8_1580988759389_writer(httl.Engine engine, httl.spi.Interceptor interceptor, httl.spi.Compiler compiler, httl.spi.Switcher filterSwitcher, httl.spi.Switcher formatterSwitcher, httl.spi.Filter filter, httl.spi.Formatter formatter, httl.spi.Converter mapConverter, httl.spi.Converter outConverter, java.util.Map functions, java.util.Map importMacros, httl.Resource resource, httl.Template parent, httl.Node root) { super(engine, interceptor, compiler, filterSwitcher, formatterSwitcher, filter, formatter, mapConverter, outConverter, functions, importMacros, resource, parent, root); this.$httl_spi_methods_TypeMethod = (httl.spi.methods.TypeMethod) functions.get(httl.spi.methods.TypeMethod.class); this.$httl_spi_methods_CodecMethod = (httl.spi.methods.CodecMethod) functions.get(httl.spi.methods.CodecMethod.class); this.$httl_spi_methods_LangMethod = (httl.spi.methods.LangMethod) functions.get(httl.spi.methods.LangMethod.class); this.$httl_spi_methods_FileMethod = (httl.spi.methods.FileMethod) functions.get(httl.spi.methods.FileMethod.class); this.$httl_spi_methods_MessageMethod = (httl.spi.methods.MessageMethod) functions.get(httl.spi.methods.MessageMethod.class);}
protected void doRenderWriter(httl.Context $context, java.io.Writer $output) throws java.lang.Exception { httl.spi.Filter $filter = getFilter($context, "filter"); httl.spi.Filter filter = $filter; httl.spi.formatters.MultiFormatter $formatter = getFormatter($context, "formatter"); httl.spi.formatters.MultiFormatter formatter = $formatter; java.lang.String name = (java.lang.String) $context.get("name"); $output.write($TXT1); $output.write(doFilter(filter, $TXT2, formatter.toString($TXT2, name))); $output.write($TXT3);}
public String getName() { return "/macros/hello.httl#hello";}
public java.util.Map getVariables() { return $VARS;}
protected java.util.Map getMacroTypes() { return new httl.util.OrderedMap(new String[0], new Class[0]);}
public boolean isMacro() { return true;}
public int getOffset() { return 0;}
}

最后生成的字节码预编译类对应#marco指令如上

编译器"吸星大法"之抽象语法树(AST)

生成之后会缓存起来直接返回

到这里基本就完了,最终会生成对应的模板类

Template__macros_hello_httl_hello_comment_UTF_8_1580988759389_writer),然后就准备开始渲染流程了,渲染的过程是根据运行时数据填充到预编译类里边之后,把内存的值,渲染到模板中替换,最后调用对应运行的是模板的render方法如下

生成的模板类在内存中进行渲染,263行代码。(这里UnsafeByteStream去掉了无用锁,由HTTL提供)


总结一下:

通过这么久代码调试我们可以了解到AST的基本流程,HTTL是比较典型的案例,当然在Druid里边也会有但是较复杂,另外编译引擎在解析一门编程语言的时候,基本流程都是开篇的那个图,除了AST之外我们还讲到了访问者的设计模式用于访问AST,以及词法分析器的分词工作,类比FastJson,用的都是状态机模式,Pattern也可以做但是不太方便,所以看完本篇文章之后应该对AST有一个简单的场景认识。