【PHP源码学习】2019-03-21 AST

摘要：全部视频原视频地址引入抽象语法树是中新引入的，在许多其他语言中早已有实现。例，怎么用抽象语法树来表达那么使用中序遍历就可以得到上述表达式。

baiyan

全部视频：https://segmentfault.com/a/11...

原视频地址：http://replay.xesv5.com/ll/24...

抽象语法树（AST）是PHP7中新引入的，在许多其他语言中早已有实现。

为什么要有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[]        //用一个数组存储所有孩子
}

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结构是什么样的：

利用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结构：


我们利用和上方一样的方式，访问它的根节点，发现也是一个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）类型