成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專(zhuān)欄INFORMATION COLUMN

【PHP源碼學(xué)習(xí)】2019-03-21 AST

everfight / 1404人閱讀

摘要:全部視頻原視頻地址引入抽象語(yǔ)法樹(shù)是中新引入的,在許多其他語(yǔ)言中早已有實(shí)現(xiàn)。例,怎么用抽象語(yǔ)法樹(shù)來(lái)表達(dá)那么使用中序遍歷就可以得到上述表達(dá)式。

baiyan

全部視頻:https://segmentfault.com/a/11...

原視頻地址:http://replay.xesv5.com/ll/24...

引入

抽象語(yǔ)法樹(shù)(AST)是PHP7中新引入的,在許多其他語(yǔ)言中早已有實(shí)現(xiàn)。

為什么要有AST這種東西呢?因?yàn)槲谋绢?lèi)型的數(shù)據(jù)對(duì)計(jì)算機(jī)并不友好,需要將其轉(zhuǎn)換成數(shù)據(jù)結(jié)構(gòu),才能更加方便地對(duì)詞法分析得到的token進(jìn)行操作。

例:a = b + c,怎么用抽象語(yǔ)法樹(shù)來(lái)表達(dá)?

那么使用中序遍歷就可以得到上述表達(dá)式。

拓展:對(duì)于樹(shù)的中序遍歷,有遞歸與非遞歸兩種方式:

遞歸中序遍歷很簡(jiǎn)單,遞歸訪問(wèn)左子樹(shù)、根節(jié)點(diǎn)、右子樹(shù)即可

非遞歸中序遍歷:借助棧

- 碰到等號(hào)壓棧,然后往左子樹(shù)走
- 將a壓棧,a沒(méi)有左右子樹(shù),a出棧(a)
- 等號(hào)出棧(a =)
- 將它的右子樹(shù)加號(hào)壓棧
- 加號(hào)有左子樹(shù),將b壓棧
- b沒(méi)有左右子樹(shù),b出棧(a = b)
- 加號(hào)出棧(a = b +)
- 加號(hào)有右子樹(shù)c,將c壓棧
- c沒(méi)有左右子樹(shù),c出棧(a = b + c)

樹(shù)的層序遍歷:借助隊(duì)列,此處不展開(kāi)

回到AST, 那么如果在PHP中,讓你去實(shí)現(xiàn)一個(gè)AST,你會(huì)怎么實(shí)現(xiàn)?

AST結(jié)點(diǎn)的設(shè)計(jì)第一版:

struct Tree {
    char type           //結(jié)點(diǎn)類(lèi)型,表示是運(yùn)算符還是操作數(shù)
    Tree *left           //左孩子
    Tree *right        //右孩子
}

存在的問(wèn)題:因?yàn)椴皇撬斜磉_(dá)式都是二元表達(dá)式,故不可以全部都用二叉樹(shù)表示(如foreach循環(huán)中foreach($a as $k => $v)至少需3個(gè)結(jié)點(diǎn)來(lái)表示$a/$k/$v等詞法單元),故需要在此基礎(chǔ)上做一些擴(kuò)展。

第二版:

struct Tree {
    char type           //結(jié)點(diǎn)類(lèi)型,表示是運(yùn)算符還是操作數(shù)
    int children        //有多少個(gè)孩子
    Tree child[]        //用一個(gè)數(shù)組存儲(chǔ)所有孩子
}
PHP中AST的重要結(jié)構(gòu)與概念
struct _zend_ast {
    zend_ast_kind kind; /* 結(jié)點(diǎn)類(lèi)型,相當(dāng)于我們上面的type */
    zend_ast_attr attr; /* 先忽略 */
    uint32_t lineno;    /* 行號(hào)(進(jìn)行語(yǔ)法分析的時(shí)候需要記錄代碼所在行號(hào)) */
    zend_ast *child[1]; /* 柔性數(shù)組,存儲(chǔ)孩子結(jié)點(diǎn)*/
};

這樣一看,好像并沒(méi)有存儲(chǔ)有多少個(gè)孩子的字段。注意這個(gè)kind字段,它是zend_ast_kind類(lèi)型,看下這個(gè)類(lèi)型的定義:

typedef uint16_t zend_ast_kind;

它是一個(gè)uint16類(lèi)型,足以存儲(chǔ)所有類(lèi)型了,那么具體有哪些類(lèi)型呢?

在PHP中,AST的結(jié)點(diǎn)是按照如下代碼所示分類(lèi)存儲(chǔ)的,這些分類(lèi)用枚舉類(lèi)型來(lái)表示:

enum _zend_ast_kind {
    /* special nodes 特殊類(lèi)型結(jié)點(diǎn)*/
    ZEND_AST_ZVAL = 1 << ZEND_AST_SPECIAL_SHIFT, (1 << 6 = 64)
    ZEND_AST_ZNODE, (65)

    /* declaration nodes 定義類(lèi)型結(jié)點(diǎn)*/
    ZEND_AST_FUNC_DECL,
    ZEND_AST_CLOSURE,
    ZEND_AST_METHOD,
    ZEND_AST_CLASS,

    /* list nodes LIST類(lèi)型結(jié)點(diǎn)*/
    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個(gè)孩子結(jié)點(diǎn)*/
    ZEND_AST_MAGIC_CONST = 0 << ZEND_AST_NUM_CHILDREN_SHIFT,(0 << 8 = 0)
    ZEND_AST_TYPE,

    /* 1 child node 1個(gè)孩子結(jié)點(diǎn)*/
    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個(gè)孩子結(jié)點(diǎn)*/
    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個(gè)孩子結(jié)點(diǎn)*/
    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個(gè)孩子結(jié)點(diǎn)*/
    ZEND_AST_FOR = 4 << ZEND_AST_NUM_CHILDREN_SHIFT,
    ZEND_AST_FOREACH,
};

先忽略上面特殊節(jié)點(diǎn)、定義結(jié)點(diǎn)和LIST類(lèi)型結(jié)點(diǎn)這幾個(gè)類(lèi)型,主要關(guān)注下面0個(gè)子結(jié)點(diǎn)、1個(gè)子結(jié)點(diǎn)的類(lèi)型,這樣,我們根據(jù)_zend_ast中存儲(chǔ)的kind數(shù)值,再對(duì)照這個(gè)類(lèi)型表,就可以知道它有幾個(gè)子結(jié)點(diǎn)了。

我們?cè)倏碙IST類(lèi)型,它是怎么存儲(chǔ)子結(jié)點(diǎn)數(shù)量的呢?會(huì)轉(zhuǎn)成一個(gè)專(zhuān)門(mén)的結(jié)構(gòu)體用來(lái)存儲(chǔ)LIST類(lèi)型的結(jié)點(diǎn):

/* Same as zend_ast, but with children count, which is updated dynamically */
/*與zend_ast結(jié)點(diǎn)的功能相同但是多了一個(gè)子結(jié)點(diǎn)的計(jì)數(shù),它會(huì)被動(dòng)態(tài)地更新*/
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;

我們看這個(gè)結(jié)構(gòu)體,除了uint32_t類(lèi)型的children子結(jié)點(diǎn)計(jì)數(shù)字段,其余與我們上述zend_ast結(jié)構(gòu)體一摸一樣。

這樣,在基本的zend_ast結(jié)構(gòu)體中,kind字段只需要存一個(gè)數(shù)字,代表它是什么類(lèi)型,就可以直接得出是LIST類(lèi)型(孩子結(jié)點(diǎn)個(gè)數(shù)存在對(duì)應(yīng)的zend_ast_list結(jié)構(gòu)體中)有0個(gè)、1個(gè)、2個(gè)孩子結(jié)點(diǎn)等等。

再關(guān)注特殊類(lèi)型中的ZEND_AST_ZVAL類(lèi)型,它代表AST中結(jié)點(diǎn)變量或者常量的(如變量$a的值就為字符串"a",常量1的值為1,均存在這個(gè)zval中,下文會(huì)講)

/* Lineno is stored in val.u2.lineno */
/* Lineno 字段存儲(chǔ)在zval中的 val.u2.lineno中 */
typedef struct _zend_ast_zval {
    zend_ast_kind kind;
    zend_ast_attr attr;
    zval val;
} zend_ast_zval;

最后剩下的就是定義類(lèi)型,包括類(lèi)、函數(shù)等定義,會(huì)轉(zhuǎn)成如下結(jié)構(gòu)存儲(chǔ)定義類(lèi)型的信息:

/* Separate structure for function and class declaration, as they need extra information. */
/* 為函數(shù)和類(lèi)設(shè)計(jì)的特殊結(jié)構(gòu),它們需要額外的描述信息 */
typedef struct _zend_ast_decl {
    zend_ast_kind kind;
    zend_ast_attr attr; /* Unused - for structure compatibility */
    uint32_t start_lineno; //類(lèi)和函數(shù)是一個(gè)區(qū)間,所以記錄開(kāi)始行號(hào)和結(jié)束行號(hào)
    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實(shí)現(xiàn)示例 簡(jiǎn)單的賦值與表達(dá)式示例

我們看下面一段PHP代碼,看下它的AST結(jié)構(gòu)是什么樣的:


利用gdb調(diào)試這段代碼,并在zend_compile處打一個(gè)斷點(diǎn)。這里會(huì)進(jìn)行詞法分析和語(yǔ)法分析(注意詞法分析和語(yǔ)法分析是同時(shí)執(zhí)行的,解析出一個(gè)token就開(kāi)始進(jìn)行語(yǔ)法分析,而不是串行執(zhí)行的),并查看compiler_globals.ast字段,這個(gè)字段就是生成的抽象語(yǔ)法樹(shù)指針了,我們打印它的內(nèi)容:

我們看到這里的kind的值為132,對(duì)應(yīng) ZEND_AST_STMT_LIST(表達(dá)式)類(lèi)型,屬于LIST這個(gè)大類(lèi),它就是我們的根節(jié)點(diǎn)了。然而LIST是專(zhuān)門(mén)用zend_ast_list結(jié)構(gòu)體來(lái)表示的,所以我們強(qiáng)轉(zhuǎn)一下:

可以看到,它有兩個(gè)孩子結(jié)點(diǎn),發(fā)現(xiàn)兩個(gè)孩子的kind值均為517,即ZEND_AST_ASSIGN(賦值)類(lèi)型。這里我們選擇第一個(gè)kind值為517的結(jié)點(diǎn),它屬于2 child nodes大類(lèi),說(shuō)明它又有兩個(gè)孩子結(jié)點(diǎn),打印它的第一個(gè)孩子結(jié)點(diǎn)(后面會(huì)打印第二個(gè)孩子結(jié)點(diǎn)),我們按照這一個(gè)結(jié)點(diǎn)深度優(yōu)先去調(diào)試:

它的kind值是256,代表ZEND_AST_VAR(變量)類(lèi)型,屬于1 child nodes大類(lèi),那么我們繼續(xù)深度優(yōu)先打印它的唯一一個(gè)孩子結(jié)點(diǎn):

它的kind值是64,代表ZEND_AST_ZVAL類(lèi)型,屬于特殊類(lèi)型。上面我們講過(guò),PHP使用一個(gè)zend_ast_zval結(jié)構(gòu)體來(lái)專(zhuān)門(mén)保存這種類(lèi)型,強(qiáng)轉(zhuǎn)一下:

它的kind值是64,zval字段中可以看到type值是6(字符串類(lèi)型),我們深入看一下這個(gè)zend_string的內(nèi)容:

可以看到它的字符串值是”a“

回到上面第二個(gè)加粗的部分,我們這次打印第二個(gè)孩子結(jié)點(diǎn):

它的kind值也是64,屬于ZEND_AST_ZVAL類(lèi)型,同樣將其強(qiáng)轉(zhuǎn)一下:

我們發(fā)現(xiàn),它的type值是4(整型),那么我們直接看zval中的lval字段,值為1,說(shuō)明它直接存儲(chǔ)的是$a = 1;這個(gè)表達(dá)式中的常量值1

那么我們畫(huà)出現(xiàn)在的AST結(jié)構(gòu)圖(AST結(jié)點(diǎn)以”類(lèi)型(值)“的形式表示,下同):

目前為止,第二個(gè)kind值為517類(lèi)型的結(jié)點(diǎn)我們還沒(méi)有看,我們繼續(xù)往下走:

我們發(fā)現(xiàn)它的kind值是256,也是一個(gè)ZEND_AST_VAR(變量)類(lèi)型,它有一個(gè)孩子結(jié)點(diǎn),打?。?/p>

同樣地,它的唯一一個(gè)孩子結(jié)點(diǎn)也是一個(gè)ZEND_AST_ZVAL類(lèi)型,強(qiáng)轉(zhuǎn)并打印其中的zval字段,發(fā)現(xiàn)其type是字符串類(lèi)型,我們繼續(xù)打印該字符串的內(nèi)容:

可以看到它的字符串值是”b“

我們可以畫(huà)出當(dāng)前AST的結(jié)構(gòu):

然后繼續(xù)打印kind為517的第二個(gè)孩子結(jié)點(diǎn):

它的kind是520,查表得到它是ZEND_AST_BINARY_OP類(lèi)型,它也屬于2 child nodes大類(lèi),有兩個(gè)孩子結(jié)點(diǎn),它代表二元操作(加減乘除等)。所以到底表示加減乘除中的哪一個(gè)呢,這時(shí)候需要它的attr字段來(lái)細(xì)化到底是哪種運(yùn)算,這里attr = 1代表加法運(yùn)算。那么我們繼續(xù)打印其中一個(gè)孩子結(jié)點(diǎn)

它的子結(jié)點(diǎn)是256,即ZEND_AST_VAR(變量)類(lèi)型,打印其唯一一個(gè)孩子結(jié)點(diǎn),仍為ZEND_AST_ZVAL類(lèi)型,強(qiáng)轉(zhuǎn)并打印其內(nèi)容為”a“

我們看kind是520的第二個(gè)孩子結(jié)點(diǎn)

我們發(fā)現(xiàn)它就是一個(gè)ZEND_AST_ZVAL類(lèi)型,值為2

那么我們可以畫(huà)出完整的AST:

那么通過(guò)中序遍歷,就可以得到最終的代碼

帶括號(hào)表達(dá)式示例

我們看下面一段帶括號(hào)的PHP表達(dá)式代碼,看下它的AST結(jié)構(gòu):


我們利用和上方一樣的方式,訪問(wèn)它的根節(jié)點(diǎn),發(fā)現(xiàn)也是一個(gè)LIST類(lèi)型,有1個(gè)子結(jié)點(diǎn),這個(gè)子節(jié)點(diǎn)的類(lèi)型是ZEND_AST_ASSIGN,它有2個(gè)孩子結(jié)點(diǎn),我們打印其中一個(gè)孩子結(jié)點(diǎn)

它的類(lèi)型是ZEND_AST_VAR類(lèi)型,有一個(gè)孩子結(jié)點(diǎn),繼續(xù)打?。?/p>

它的類(lèi)型也是一個(gè)ZEND_AST_ZVAL類(lèi)型,其類(lèi)型是字符串,值為a

那么可以畫(huà)出當(dāng)前AST的結(jié)構(gòu):

回到517(ZEND_AST_ASSIGN)的另一個(gè)孩子結(jié)點(diǎn),觀察它的值:

可以看到,它是ZEND_AST_BINARY_OP類(lèi)型,attr值為3,代表*,它有2個(gè)孩子結(jié)點(diǎn),將他們?nèi)看蛴〕鰜?lái):

可以看到,第一個(gè)孩子是一個(gè)ZEND_AST_BINARY_OP類(lèi)型,代表+,它也有兩個(gè)孩子結(jié)點(diǎn),分別為ZEND_AST_ZVAL,值為1和2,而第二個(gè)孩子就是值為3的ZEND_AST_ZVAL。這里沒(méi)有表示括號(hào)的結(jié)點(diǎn),是因?yàn)锳ST已經(jīng)表示了該表達(dá)式的優(yōu)先級(jí),所以無(wú)需額外存儲(chǔ),現(xiàn)在我們可以畫(huà)出AST的完整結(jié)構(gòu):

視頻中還有foreach的案例,限于篇幅不再貼圖,其分析方法都是類(lèi)似的,只是多了幾個(gè)新的類(lèi)型

在PHP中,任何代碼都可以被轉(zhuǎn)成唯一的一個(gè)AST,根節(jié)點(diǎn)往往都是132(LIST)類(lèi)型

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/31407.html

相關(guān)文章

  • 【LNMPR源碼學(xué)習(xí)】筆記匯總

    摘要:此文用于匯總跟隨陳雷老師及團(tuán)隊(duì)的視頻,學(xué)習(xí)源碼過(guò)程中的思考整理與心得體會(huì),此文會(huì)不斷更新視頻傳送門(mén)每日學(xué)習(xí)記錄使用錄像設(shè)備記錄每天的學(xué)習(xí)源碼學(xué)習(xí)源碼學(xué)習(xí)內(nèi)存管理筆記源碼學(xué)習(xí)內(nèi)存管理筆記源碼學(xué)習(xí)內(nèi)存管理筆記源碼學(xué)習(xí)基本變量筆記 此文用于匯總跟隨陳雷老師及團(tuán)隊(duì)的視頻,學(xué)習(xí)源碼過(guò)程中的思考、整理與心得體會(huì),此文會(huì)不斷更新 視頻傳送門(mén):【每日學(xué)習(xí)記錄】使用錄像設(shè)備記錄每天的學(xué)習(xí) PHP7...

    Barrior 評(píng)論0 收藏0
  • PHP源碼學(xué)習(xí)2019-03-27 pass_two函數(shù)詳解筆記

    摘要:結(jié)果和我們?cè)O(shè)想的一致。另外一個(gè)非常重要的工作是通過(guò),設(shè)置對(duì)應(yīng)的,代碼如下其中和之前的對(duì)應(yīng)關(guān)系在中定義的。至此,整個(gè)抽象語(yǔ)法樹(shù)就編譯完成了,最終的結(jié)果為指令集,接下來(lái)就是在虛擬機(jī)上執(zhí)行這些指令。參考資料源碼分析源碼研究之淺談虛擬機(jī) grape 全部視頻:https://segmentfault.com/a/11... 原視頻地址:http://replay.xesv5.com/ll/24...

    PumpkinDylan 評(píng)論0 收藏0
  • PHP-7.1 源代碼學(xué)習(xí):語(yǔ)法分析 之 概述

    摘要:前言使用和進(jìn)行語(yǔ)法分析和詞法分析,本文以語(yǔ)法定義文件為起點(diǎn),使用等命令行工具搜索相關(guān)源碼,以此來(lái)展示探索語(yǔ)法分析源碼思路語(yǔ)法定義文件在源代碼根目錄下通過(guò)命令查找文件我們找到了文件,里面定義了腳本的語(yǔ)法語(yǔ)法分析樹(shù)節(jié)點(diǎn)類(lèi)型在查看具體的語(yǔ)法規(guī)則 前言 php 使用 lex 和 bison 進(jìn)行語(yǔ)法分析和詞法分析,本文以 bison 語(yǔ)法定義文件為起點(diǎn),使用 find, grep 等命令行工具...

    luqiuwen 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<