摘要：全部視頻原視頻地址引入抽象語法樹是中新引入的，在許多其他語言中早已有實現。例，怎么用抽象語法樹來表達那么使用中序遍歷就可以得到上述表達式。

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）類型