内容简介:baiyan全部视频:原视频地址:
【PHP源码学习】2019-03-21 AST
baiyan
全部视频: https://segmentfault.com/a/11...
原视频地址: http://replay.xesv5.com/ll/24...
引入
- 抽象语法树(AST)是 PHP 7中新引入的,在许多其他语言中早已有实现。
- 为什么要有AST这种东西呢?因为文本类型的数据对计算机并不友好,需要将其转换成数据结构,才能更加方便地对词法分析得到的token进行操作。
- 例:a = b + c,怎么用抽象语法树来表达?
- 那么使用中序遍历就可以得到上述表达式。
-
拓展:对于树的中序遍历,有递归与非递归两种方式:
- 递归中序遍历很简单,递归访问左子树、根节点、右子树即可
-
非递归中序遍历:借助栈
- 碰到等号压栈,然后往左子树走 - 将a压栈,a没有左右子树,a出栈(a) - 等号出栈(a =) - 将它的右子树加号压栈 - 加号有左子树,将b压栈 - b没有左右子树,b出栈(a = b) - 加号出栈(a = b +) - 加号有右子树c,将c压栈 - c没有左右子树,c出栈(a = b + c)
- 树的层序遍历:借助队列,此处不展开
- 回到AST, 那么如果在PHP中,让你去实现一个AST,你会怎么实现?
- AST结点的设计第一版:
struct Tree { char type //结点类型,表示是运算符还是操作数 Tree *left //左孩子 Tree *right //右孩子 }
- 存在的问题:因为不是所有表达式都是二元表达式,故不可以全部都用二叉树表示(如foreach循环中foreach($a as $k => $v)至少需3个结点来表示$a/$k/$v等词法单元),故需要在此基础上做一些扩展。
- 第二版:
struct Tree { char type //结点类型,表示是运算符还是操作数 int children //有多少个孩子 Tree child[] //用一个数组存储所有孩子 }
PHP中AST的重要结构与概念
struct _zend_ast { zend_ast_kind kind; /* 结点类型,相当于我们上面的type */ zend_ast_attr attr; /* 先忽略 */ uint32_t lineno; /* 行号(进行语法分析的时候需要记录代码所在行号) */ zend_ast *child[1]; /* 柔性数组,存储孩子结点*/ };
- 这样一看,好像并没有存储有多少个孩子的字段。注意这个kind字段,它是zend_ast_kind类型,看下这个类型的定义:
typedef uint16_t zend_ast_kind;
- 它是一个uint16类型,足以存储所有类型了,那么具体有哪些类型呢?
- 在PHP中,AST的结点是按照如下代码所示分类存储的,这些分类用枚举类型来表示:
enum _zend_ast_kind { /* special nodes 特殊类型结点*/ ZEND_AST_ZVAL = 1 << ZEND_AST_SPECIAL_SHIFT, (1 << 6 = 64) ZEND_AST_ZNODE, (65) /* declaration nodes 定义类型结点*/ ZEND_AST_FUNC_DECL, ZEND_AST_CLOSURE, ZEND_AST_METHOD, ZEND_AST_CLASS, /* list nodes LIST类型结点*/ ZEND_AST_ARG_LIST = 1 << ZEND_AST_IS_LIST_SHIFT,(1 << 7 = 128) ZEND_AST_ARRAY, ZEND_AST_ENCAPS_LIST, ZEND_AST_EXPR_LIST, ZEND_AST_STMT_LIST, ZEND_AST_IF, ZEND_AST_SWITCH_LIST, ZEND_AST_CATCH_LIST, ZEND_AST_PARAM_LIST, ZEND_AST_CLOSURE_USES, ZEND_AST_PROP_DECL, ZEND_AST_CONST_DECL, ZEND_AST_CLASS_CONST_DECL, ZEND_AST_NAME_LIST, ZEND_AST_TRAIT_ADAPTATIONS, ZEND_AST_USE, /* 0 child nodes 0个孩子结点*/ ZEND_AST_MAGIC_CONST = 0 << ZEND_AST_NUM_CHILDREN_SHIFT,(0 << 8 = 0) ZEND_AST_TYPE, /* 1 child node 1个孩子结点*/ ZEND_AST_VAR = 1 << ZEND_AST_NUM_CHILDREN_SHIFT,(1 << 8 = 256) ZEND_AST_CONST, ZEND_AST_UNPACK, ZEND_AST_UNARY_PLUS, ZEND_AST_UNARY_MINUS, ZEND_AST_CAST, ZEND_AST_EMPTY, ZEND_AST_ISSET, ZEND_AST_SILENCE, ZEND_AST_SHELL_EXEC, ZEND_AST_CLONE, ZEND_AST_EXIT, ZEND_AST_PRINT, ZEND_AST_INCLUDE_OR_EVAL, ZEND_AST_UNARY_OP, ZEND_AST_PRE_INC, ZEND_AST_PRE_DEC, ZEND_AST_POST_INC, ZEND_AST_POST_DEC, ZEND_AST_YIELD_FROM, ZEND_AST_GLOBAL, ZEND_AST_UNSET, ZEND_AST_RETURN, ZEND_AST_LABEL, ZEND_AST_REF, ZEND_AST_HALT_COMPILER, ZEND_AST_ECHO, ZEND_AST_THROW, ZEND_AST_GOTO, ZEND_AST_BREAK, ZEND_AST_CONTINUE, /* 2 child nodes 2个孩子结点*/ ZEND_AST_DIM = 2 << ZEND_AST_NUM_CHILDREN_SHIFT,(2 << 8 = 512) ZEND_AST_PROP, ZEND_AST_STATIC_PROP, ZEND_AST_CALL, ZEND_AST_CLASS_CONST, ZEND_AST_ASSIGN, ZEND_AST_ASSIGN_REF, ZEND_AST_ASSIGN_OP, ZEND_AST_BINARY_OP, ZEND_AST_GREATER, ZEND_AST_GREATER_EQUAL, ZEND_AST_AND, ZEND_AST_OR, ZEND_AST_ARRAY_ELEM, ZEND_AST_NEW, ZEND_AST_INSTANCEOF, ZEND_AST_YIELD, ZEND_AST_COALESCE, ZEND_AST_STATIC, ZEND_AST_WHILE, ZEND_AST_DO_WHILE, ZEND_AST_IF_ELEM, ZEND_AST_SWITCH, ZEND_AST_SWITCH_CASE, ZEND_AST_DECLARE, ZEND_AST_USE_TRAIT, ZEND_AST_TRAIT_PRECEDENCE, ZEND_AST_METHOD_REFERENCE, ZEND_AST_NAMESPACE, ZEND_AST_USE_ELEM, ZEND_AST_TRAIT_ALIAS, ZEND_AST_GROUP_USE, /* 3 child nodes 3个孩子结点*/ ZEND_AST_METHOD_CALL = 3 << ZEND_AST_NUM_CHILDREN_SHIFT, ZEND_AST_STATIC_CALL, ZEND_AST_CONDITIONAL, ZEND_AST_TRY, ZEND_AST_CATCH, ZEND_AST_PARAM, ZEND_AST_PROP_ELEM, ZEND_AST_CONST_ELEM, /* 4 child nodes 4个孩子结点*/ ZEND_AST_FOR = 4 << ZEND_AST_NUM_CHILDREN_SHIFT, ZEND_AST_FOREACH, };
- 先忽略上面特殊节点、定义结点和LIST类型结点这几个类型,主要关注下面0个子结点、1个子结点的类型,这样,我们根据_zend_ast中存储的kind数值,再对照这个类型表,就可以知道它有几个子结点了。
- 我们再看LIST类型,它是怎么存储子结点数量的呢?会转成一个专门的结构体用来存储LIST类型的结点:
/* Same as zend_ast, but with children count, which is updated dynamically */ /*与zend_ast结点的功能相同但是多了一个子结点的计数,它会被动态地更新*/ typedef struct _zend_ast_list { zend_ast_kind kind; zend_ast_attr attr; uint32_t lineno; uint32_t children; zend_ast *child[1]; } zend_ast_list;
- 我们看这个结构体,除了uint32_t类型的children子结点计数字段,其余与我们上述zend_ast结构体一摸一样。
- 这样,在基本的zend_ast结构体中,kind字段只需要存一个数字,代表它是什么类型,就可以直接得出是LIST类型(孩子结点个数存在对应的zend_ast_list结构体中)有0个、1个、2个孩子结点等等。
- 再关注特殊类型中的ZEND_AST_ZVAL类型,它代表AST中结点变量或者常量的 值 (如变量$a的值就为字符串"a",常量1的值为1,均存在这个zval中,下文会讲)
/* Lineno is stored in val.u2.lineno */ /* Lineno 字段存储在zval中的 val.u2.lineno中 */ typedef struct _zend_ast_zval { zend_ast_kind kind; zend_ast_attr attr; zval val; } zend_ast_zval;
- 最后剩下的就是定义类型,包括类、函数等定义,会转成如下结构存储定义类型的信息:
/* Separate structure for function and class declaration, as they need extra information. */ /* 为函数和类设计的特殊结构,它们需要额外的描述信息 */ typedef struct _zend_ast_decl { zend_ast_kind kind; zend_ast_attr attr; /* Unused - for structure compatibility */ uint32_t start_lineno; //类和函数是一个区间,所以记录开始行号和结束行号 uint32_t end_lineno; uint32_t flags; unsigned char *lex_pos; zend_string *doc_comment; zend_string *name; zend_ast *child[4]; } zend_ast_decl;
PHP中AST实现示例
简单的赋值与表达式示例
- 我们看下面一段PHP代码,看下它的AST结构是什么样的:
<?php $a = 1; $b = $a + 2;
- 利用gdb调试这段代码,并在zend_compile处打一个断点。这里会进行词法分析和语法分析(注意词法分析和语法分析是同时执行的,解析出一个token就开始进行语法分析,而不是串行执行的),并查看compiler_globals.ast字段,这个字段就是生成的抽象语法树指针了,我们打印它的内容:
- 我们看到这里的kind的值为132,对应 ZEND_AST_STMT_LIST(表达式)类型,属于LIST这个大类,它就是我们的根节点了。然而LIST是专门用zend_ast_list结构体来表示的,所以我们强转一下:
- 可以看到,它有两个孩子结点,发现两个孩子的kind值均为517,即ZEND_AST_ASSIGN(赋值)类型。这里我们选择 第一个kind值为517 的结点,它属于2 child nodes大类,说明它又有两个孩子结点,打印它的 第一个孩子结点 (后面会打印第二个孩子结点),我们按照这一个结点深度优先去调试:
- 它的kind值是256,代表ZEND_AST_VAR(变量)类型,属于1 child nodes大类,那么我们继续深度优先打印它的唯一一个孩子结点:
- 它的kind值是64,代表ZEND_AST_ZVAL类型,属于特殊类型。上面我们讲过,PHP使用一个zend_ast_zval结构体来专门保存这种类型,强转一下:
- 它的kind值是64,zval字段中可以看到type值是6(字符串类型),我们深入看一下这个zend_string的内容:
- 可以看到它的字符串值是”a“
- 回到上面第二个加粗的部分,我们这次打印 第二个孩子结点 :
- 它的kind值也是64,属于ZEND_AST_ZVAL类型,同样将其强转一下:
- 我们发现,它的type值是4(整型),那么我们直接看zval中的lval字段,值为1,说明它直接存储的是$a = 1;这个表达式中的常量值1
- 那么我们画出现在的AST结构图(AST结点以”类型(值)“的形式表示,下同):
- 目前为止,第二个kind值为517类型的结点我们还没有看,我们继续往下走:
- 我们发现它的kind值是256,也是一个ZEND_AST_VAR(变量)类型,它有一个孩子结点,打印:
- 同样地,它的唯一一个孩子结点也是一个ZEND_AST_ZVAL类型,强转并打印其中的zval字段,发现其type是字符串类型,我们继续打印该字符串的内容:
- 可以看到它的字符串值是”b“
- 我们可以画出当前AST的结构:
- 然后继续打印kind为517的第二个孩子结点:
- 它的kind是520,查表得到它是ZEND_AST_BINARY_OP类型,它也属于2 child nodes大类,有两个孩子结点,它代表二元操作(加减乘除等)。所以到底表示加减乘除中的哪一个呢,这时候需要它的attr字段来细化到底是哪种运算,这里attr = 1代表加法运算。那么我们继续打印 其中一个孩子结点 :
- 它的子结点是256,即ZEND_AST_VAR(变量)类型,打印其唯一一个孩子结点,仍为ZEND_AST_ZVAL类型,强转并打印其内容为”a“
- 我们看kind是520的 第二个孩子结点 :
- 我们发现它就是一个ZEND_AST_ZVAL类型,值为2
- 那么我们可以画出完整的AST:
- 那么通过中序遍历,就可以得到最终的代码
带括号表达式示例
- 我们看下面一段带括号的PHP表达式代码,看下它的AST结构:
<?php $a = (1+2)*3;
- 我们利用和上方一样的方式,访问它的根节点,发现也是一个LIST类型,有1个子结点,这个子节点的类型是ZEND_AST_ASSIGN,它有2个孩子结点,我们打印 其中一个孩子结点 :
- 它的类型是ZEND_AST_VAR类型,有一个孩子结点,继续打印:
- 它的类型也是一个ZEND_AST_ZVAL类型,其类型是字符串,值为a
- 那么可以画出当前AST的结构:
- 回到517(ZEND_AST_ASSIGN)的另一个孩子结点,观察它的值:
- 可以看到,它是ZEND_AST_BINARY_OP类型,attr值为3,代表*,它有2个孩子结点,将他们全部打印出来:
- 可以看到,第一个孩子是一个ZEND_AST_BINARY_OP类型,代表+,它也有两个孩子结点,分别为ZEND_AST_ZVAL,值为1和2,而第二个孩子就是值为3的ZEND_AST_ZVAL。这里没有表示括号的结点,是因为AST已经表示了该表达式的优先级,所以无需额外存储,现在我们可以画出AST的完整结构:
- 视频中还有foreach的案例,限于篇幅不再贴图,其分析方法都是类似的,只是多了几个新的类型
- 在PHP中,任何代码都可以被转成唯一的一个AST,根节点往往都是132(LIST)类型
以上所述就是小编给大家介绍的《【PHP源码学习】2019-03-21 AST》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
云计算安全与隐私
Tim Mather、Subra Kumaraswamy、Shahed Latif / 刘戈舟、杨泽明、刘宝旭 / 机械工业出版社华章公司 / 2011-6 / 65.00元
《云计算安全与隐私》可以使你明白当把数据交付给云计算时你所面临的风险,以及为了保障虚拟基础设施和网络应用程序的安全可以采取的行动。本书是由信息安全界知名专家所著,作者在书中给出许多中肯的忠告和建议。本书的读者对象包括:IT职员、信息安全和隐私方面的从业人士、业务经理、服务提供商,以及投资机构等。阅读本书你会了解直到现在还严重匮乏的云计算安全方面的详尽信息。 《云计算安全与隐私》主要内容包括:......一起来看看 《云计算安全与隐私》 这本书的介绍吧!
URL 编码/解码
URL 编码/解码
HEX CMYK 转换工具
HEX CMYK 互转工具