phpast抽象语法树,AST抽象语法树的基本思想
AST抽象语法树的基本思想
前⾔
AST概述
AST结构
AST解析
转换
⽣成
前⾔
在阅读java ORM框架spring data jpa的源码时，发现Hibernate(spring data jpa依赖Hibernate核⼼代码)在底层使⽤了AST抽象语法树，将hql转换为sql，这激发了我研究AST的兴趣。
AST概述
AST(Abstract Syntax Tree)抽象语法树多⽤作编程语⾔的分析和转换，C语⾔编译器将c源码转换为汇编，java编译器将java代码转换为java字节码，还有⼀些⽐较⾼级的⽤法，⽐如同种语⾔代码的优化、不同种语⾔代码的相互转化等。
抽象语法树从术语定义上就能看出，本⾝是⼀种树状的数据结构，“1 + 2”使⽤抽象语法树可以表⽰为：
这样做的⽬的是，将原始语句分解成了单个的语法单元，同时保留了语法单元之间的层次结构，后续通过对语法单元的改造或者替换，重新按照某种规则遍历，即可完成原始语句到⽬标语句的转换。⽐如，以“1 + 2”为例，可以将“+”替换为add，1和2理解为add函数的参数，即可实现原始运算语句到函数调⽤的转换。
AST抽象语法树的使⽤，整体上可以分为三步：
解析：将原始语句解析为抽象语法树
转换：操作抽象语法树节点完成转换
⽣成：根据转换后的抽象语法树⽣成⽬标语句
其中，最重要的是需要理解抽象语法树的结构，这是解析和⽣成抽象语法树的基础。
AST结构
个⼈感觉，理解抽象语法树结构的最佳例⼦是xml格式⽂本，这两种形式的对⽐能够充分显⽰抽象语法树结构是为了表⽰空间或者时间或者逻辑关系上的层次。
ZhongShan
123456
"Tom"
123457
"John"
上⾯构造的xml是⽤来表⽰，有个城市中⼀个公园叫ZhongShan，这个城市住着⼀个⼈，他的id是123456，姓名叫Tom。Tom有⼀个⼉⼦，id是123457，名叫John。这种嵌套的关系⽤AST表⽰，如图：
xml到AST图的转换，实际上是空间层次的对应关系。可能⼤家还是会对逻辑层次关系如果转换成AST有疑问，所以这⾥再以表达式“5-2* (3-1)+4”为例来进⼀步分析这种转换。
如图为“5-2*(3-1)+4”的抽象语法树，其实就是中缀表达式的树形表⽰。这⾥构造的基本逻辑是，越是排在后⾯的运算离根节点越近。括号中的表达式“3-1”最先被运算，因此位于最底层。⽽“+ 4”运算最后执⾏，所以这⾥的“+”位于根节点。表达式的AST图和xml的AST图不同之处在于，这⾥同层还存在顺序关
系，左边的节点优先级要⾼于右边节点的优先级。
通过上述两个例⼦的演⽰，这⾥再介绍代码的抽象语法树似乎就容易理解多了。
while(b > 0)
{
if(a < b)
a = b-a;
else
b = a-b;
}
return a;
在代码的构造抽象语法树之前，⾸先需要明⽩，这些语句之间存在执⾏上的顺序关系，也存在不同层级下的嵌套关系。⽐如上述代
码，while循环语句块由⼤括号包裹，和return语句处于⼀个层级，但while语句块先会被执⾏。⽽while语句块中⼜包含了循环判断“b != 0”和if的判断语句块，这属于while下语句的嵌套。其次，语句结构也更加复杂，⽐如上例中的语句除了表达式、赋值语句之外，还有while、if和对应的判断条件，所以会拆分出更多的语法单元。
statement_list语法单元，⽤来表⽰⼦节点都是并列依次执⾏的语句。while⼦树中包含了while循环的条件判断和if的语句块，if语句块包含了if的条件判断和两个赋值语句。在编译器构造同样类型语法树时，⼀般会使⽤与具体语⾔⽆关的语法单元的命名，这样在后续转换的转换只是对节点采⽤不同的翻译模式⽽已，做到了和具体语⾔的解耦。
AST解析
编程php语言
使⽤AST对原始语句解析时，需要先进⾏词法分析。
词法分析会根据既定的语法单元表，将原始语句分割成⼀维数组语法单元列表(token表)。语法单元表根据场景不同，如上述三个例⼦，可以⾃⾏定义。⼀般⽽⾔，词法分析时会将连续的空格当做分割符，⾃动切分语法单元。
获得token表之后，再使⽤语法分析，将⼀维⽆结构的token表转化为树形结构。在语法分析时，也会验证语法的正确性。如果出现不符合语法的语句，就会抛出错误，编译报错⼀般就是这个阶段的产物。
转换
根据⽬的的不同，AST转换没有⼀套固定的标准，有时候只是对匹配节点简单的替换，有时候可能是
对匹配⼦树结构的调整或者替换。⼀般这个过程包含遍历和转换两步。
抽象语法树可以使⽤⼀般树的遍历⽅法。如果忘记了，可以温习⼀下先序遍历、中序遍历和后序遍历。⽬前使⽤⽐较多的antlr中，使⽤了先序遍历和后序遍历。
⽣成
⽣成是AST解析的逆向⼯程，⽣成过程中也需要⽤到树的遍历。虽然有时候⽣成和转换可能糅合在⼀起同时进⾏，但是⽣成逻辑⽐单纯进⾏转换时要复杂。
在⽣成的遍历过程中，需要对所有不同类型语法单元的节点的所有情况定义不同的处理逻辑，⽽不同类型语法节点下⼦树的遍历顺序也有可能会不同。所以需要为所有情况进⾏枚举。
这种情况的感性认知，可以以上述例⼦中代码语法抽象树为例。在statement_list节点下，⼦树代表的语句块需要按顺序并列，所以在先遍历完while语句块⼦树之后，回到statement_list节点，再到return⼦树下，⽣成return语句需要另起⼀⾏。⽽while节点下需要先考虑条件语句，在不回车换⾏的基础上添加括号，完成while( b > 0 )语句的构造。同理while节点下while体中需要⾃动添加{}…使⽤抽象语法树的⽣成逻辑需要事⽆巨细的列出可能遇到的所有情况和处理⽅式。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。