《手把手教你编写PHP编译器》-引入zend_ast

, Comments

细心的小伙伴会发现，在我们实现算数表达式的时候，直接在语法分析的过程（也就是调用bison的阶段）对表达式进行了求值。现在，我们来引入抽象语法树的概念。在php-src里面，对应的就是zend_ast结构了。

我们先来编写一下zend_language_parser.y文件，以让我们对整个过程有一个清晰的认识。

首先，我们需要定义一个union：

1
2
3
%union {
    zend_ast *ast;
}

这个是什么呢？实际上，这个是YYSTYPE，也就是yylval。而yylval我们会在词法分析的时候用到。如果我们不定义这个union的话，那么YYSTYPE默认是int类型。那么，我们在词法分析的时候，就只能够使用yylval去接收int类型的token了。但是，我们现在在词法分析的时候，会去为T_LNUMBER生成一个zend_ast，并且赋值给yylval，以便在语法分析的阶段，直接使用这个这个zend_ast。（实际上，我们也可以把这一步放到语法分析来做，但是，没有必要。）

我们需要对token定义做一些修改：

1
2
%token <ident> T_ECHO    "'echo'"
%token <ast> T_LNUMBER   "integer"

这里%token <ast> T_LNUMBER里面的ast就是说明了我们的T_LNUMBER这个token的值类型是ast。

OK，除了声明token的类型之外，我们还需要对文法里面的非终结符进行声明：

1
2
3
4
%type <ast> top_statement statement
%type <ast> expr
%type <ast> scalar
%type <ast> top_statement_list

现在，让我们看看我们的语法规则：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
start:
    top_statement_list  { CG(ast) = $1; }
;

top_statement_list:
        top_statement_list top_statement { $$ = zend_ast_list_add($1, $2); }
    |   %empty { $$ = zend_ast_create_list(0, ZEND_AST_STMT_LIST); }
;

top_statement:
    statement                       { $$ = $1; }
;

statement:
    T_ECHO expr ';'     { $$ = $2; }
;

expr:
    expr '+' expr   { $$ = zend_ast_create_binary_op(ZEND_ADD, $1, $3); }
|   expr '-' expr   { $$ = zend_ast_create_binary_op(ZEND_SUB, $1, $3); }
|   expr '*' expr   { $$ = zend_ast_create_binary_op(ZEND_MUL, $1, $3); }
|   expr '/' expr   { $$ = zend_ast_create_binary_op(ZEND_DIV, $1, $3); }
|   '(' expr ')'    { $$ = $2; }
|   scalar { $$ = $1; }
;

scalar:
    T_LNUMBER   { $$ = $1; }
;

这里的规则和php-src是保持一致的，但是可能会有一点不同（一些目前没有必要的东西被我删了）。

可以看到，我们在最顶层，也即是非终结符start的那条规则里，它的动作是把ast赋值给CG(ast)。熟悉PHP内核的小伙伴应该是能够立马知道这个CG(ast)是做什么的。这个CG(ast)保存的是，在编译PHP代码阶段的所有zend_ast。

我们接着看：

1
2
3
4
top_statement_list:
        top_statement_list top_statement { $$ = zend_ast_list_add($1, $2); }
    |   %empty { $$ = zend_ast_create_list(0, ZEND_AST_STMT_LIST); }
;

它表达的含义一句话来总结就是，定义了一个ZEND_AST_STMT_LIST类型的zend_ast，然后这个zend_ast下面有多个子zend_ast，这些一个个的子zend_ast对应的就是我们PHP代码里的一条条语句（其实也不一定是一条条，例如for循环啥的，这种我们就不太好形容为条。反正大概就是一个语句的意思）。

1
2
3
statement:
    T_ECHO expr ';'     { $$ = $2; }
;

表示我们的语句包含echo语句。

1
2
3
4
5
6
7
8
9
10
11
12
expr:
    expr '+' expr   { $$ = zend_ast_create_binary_op(ZEND_ADD, $1, $3); }
|   expr '-' expr   { $$ = zend_ast_create_binary_op(ZEND_SUB, $1, $3); }
|   expr '*' expr   { $$ = zend_ast_create_binary_op(ZEND_MUL, $1, $3); }
|   expr '/' expr   { $$ = zend_ast_create_binary_op(ZEND_DIV, $1, $3); }
|   '(' expr ')'    { $$ = $2; }
|   scalar { $$ = $1; }
;

scalar:
    T_LNUMBER   { $$ = $1; }
;

这一段和我们前面的文章类似，但是，不同的地方在规则对应的动作，之前因为token的值都是int类型，所以，我们可以直接进行表达式的运算，但是，现在由于我们的token变成了ast类型，所以，我们就不能直接进行四则运算了（实际上，因为我们的语言是C++，所以我们可以对运算符进行重载，然而，这已经超出了我们教程的范围，所以我们就不去支持重载了，留给小伙伴们当作练习吧）。我们现在改为调用zend_ast_create_binary_op函数，而这个函数就是通过两个子zend_ast节点来生成一个四则运算的zend_ast，具体的函数实现我们后面会说。

改完了语法文件之后，我们就业需要改改词法文件：

1
2
3
4
5
[0-9]+ {
    int64_t lnum = atoi(yytext);
    yylval.ast = zend_ast_create_lnum(lnum);
    return T_LNUMBER;
}

我们上面说了，yylval是一个union类型的了，所以，我们得使用yylval.ast来接收token的值。而zend_ast_create_lnum函数就是用来把数字变成zend_ast的。

OK，我们现在可以来看具体的函数实现了。不过在这之前，我们需要先设计好我们的zend_ast结构，我们和php-src的保持一致：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef uint16_t zend_ast_kind;
typedef uint16_t zend_ast_attr;

struct _zend_ast {
    zend_ast_kind kind;
    zend_ast_attr attr;
    zend_ast *child[1];
};

typedef struct _zend_ast_list {
    zend_ast_kind kind;
    zend_ast_attr attr;
    uint32_t children;
    zend_ast *child[1];
} zend_ast_list;

typedef struct _zend_ast_lnum {
    zend_ast_kind kind;
    zend_ast_attr attr;
    int64_t lnum;
} zend_ast_lnum;

前面的_zend_ast和_zend_ast_list是php-src里面的，小伙伴们可以在网上找到它们的区别。而_zend_ast_lnum是我自己引入的，表示这个zend_ast存了一个lnum的整数值。在php-src里面，这一块应该是zend_ast_zval，也就是存了一个zval。因为我们这篇文章还不想引入zval这个东西（因为我们的表达式都是整形值，所以没必要搞一个zval），所以我先简单处理了。

现在，让我们来看看函数实现了。

首先是zend_ast_create_list，我们在文件Zend/zend_ast.cc里面来进行定义：

1
2
3
4
5
6
7
8
9
10
11
zend_ast *zend_ast_create_list(uint32_t init_children, zend_ast_kind kind) {
    zend_ast *ast;
    zend_ast_list *list;

    ast = (zend_ast *) malloc(zend_ast_list_size(4));
    list = (zend_ast_list *) ast;
    list->kind = kind;
    list->children = 0;

    return ast;
}

这个函数实现非常简单，首先，malloc出一块zend_ast的内存，然后，设置它的kind和children。其中kind对应这个zend_ast的类型，children表示这个zend_ast有一个子zend_ast。

然后是zend_ast_list_add函数：

1
2
3
4
5
zend_ast *zend_ast_list_add(zend_ast *ast, zend_ast *op) {
    zend_ast_list *list = zend_ast_get_list(ast);
    list->child[list->children++] = op;
    return (zend_ast *) list;
}

这个函数就是设置zend_ast_create_list函数创建出来的zend_ast的child。设置一个children加一。所以，有几条语句，我们的这个children就是几了。

最后，是我们的zend_ast_create_binary_op函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
static inline zend_ast *zend_ast_create_binary_op(uint32_t opcode, zend_ast *op0, zend_ast *op1) {
    switch (opcode)
    {
    case ZEND_ADD:
        std::cout << "create + zend_ast" << std::endl;
        break;
    case ZEND_SUB:
        std::cout << "create - zend_ast" << std::endl;
        break;
    case ZEND_MUL:
        std::cout << "create * zend_ast" << std::endl;
        break;
    case ZEND_DIV:
        std::cout << "create / zend_ast" << std::endl;
        break;
    default:
        std::cout << "unknow operator" << std::endl;
        break;
    }
    return zend_ast_create_2(ZEND_AST_BINARY_OP, opcode, op0, op1);
}

zend_ast *zend_ast_create_2(zend_ast_kind kind, zend_ast_attr attr, zend_ast *child1, zend_ast *child2) {
    zend_ast *ast;

    ast = (zend_ast *) malloc(zend_ast_size(2));
    ast->kind = kind;
    ast->attr = attr;
    ast->child[0] = child1;
    ast->child[1] = child2;

    return ast;
}

这个zend_ast_create_binary_op实际上做的一件事情就是创建一个包含两个子ast的zend_ast，然后设置zend_ast的kind为ZEND_AST_BINARY_OP，并且设置对应的运算类型（即加、减、乘、除），最后设置运算符操作的两个子ast。

最后，我们编写一个打印ast的函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void dump_ast(zend_ast *ast)
{
    if (ast->kind == ZEND_AST_LNUM) {
        zend_ast_lnum *ast_lnum = (zend_ast_lnum *) ast;
        std::cout << "kind: " << ast_lnum->kind << ", attr: " << ast_lnum->attr << ", value: " << ast_lnum->lnum << std::endl;
    } else {
        std::cout << "kind: " << ast->kind << ", attr: " << ast->attr << std::endl;
    }
}

void dump_compiler_globals()
{
    zend_ast *ast;
    std::deque<zend_ast *> queue;

    queue.push_back(CG(ast));

    while (!queue.empty())
    {
        ast = queue.front();

        if (ast->kind == ZEND_AST_STMT_LIST) {
            zend_ast_list *ast_list = (zend_ast_list *) ast;
            for (size_t i = 0; i < ast_list->children; i++)
            {
                queue.push_back(ast_list->child[i]);
            }
        } else if (ast->kind == ZEND_AST_BINARY_OP) {
            queue.push_back(ast->child[0]);
            queue.push_back(ast->child[1]);
        }
        dump_ast(ast);
        queue.pop_front();
    }

    return;
}

这个也很简单，实际上就是一个树的层次遍历。

OK，做完了这些工作之后，我们重新编译我们的yaphp（记得修改我们的CMakeLists）。

然后编写如下yaphp代码：

1
echo 1 + 2 * 3;

输出结果如下：

1
2
3
4
5
6
7
8
create * zend_ast
create + zend_ast
kind: 129, attr: 0
kind: 515, attr: 1
kind: 65, attr: 0, value: 1
kind: 515, attr: 3
kind: 65, attr: 0, value: 2
kind: 65, attr: 0, value: 3

这个ast的输出大概如下图：

1
2
3
4
        stmt_list
    +
1       *
    2       3

符合我们的预期。

codinghuangPHP Developer

PHP开发者~