摘要:全部視頻原視頻地址引入抽象語(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
摘要:此文用于匯總跟隨陳雷老師及團(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...
摘要:結(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...
摘要:前言使用和進(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 等命令行工具...
閱讀 843·2021-09-07 09:58
閱讀 2700·2021-08-31 09:42
閱讀 2873·2019-08-30 14:18
閱讀 3096·2019-08-30 14:08
閱讀 1843·2019-08-30 12:57
閱讀 2769·2019-08-26 13:31
閱讀 1312·2019-08-26 11:58
閱讀 1065·2019-08-23 18:06