PHP源码学习20190321-AST

jiezi

6 年前

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

<?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源码学习20190321-AST

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

引入

PHP 中 AST 的重要结构与概念

PHP 中 AST 实现示例

简单的赋值与表达式示例

带括号表达式示例