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

细心的小伙伴会发现,在我们实现算数表达式的时候,直接在语法分析的过程(也就是调用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_listphp-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的内存,然后,设置它的kindchildren。其中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_astchild。设置一个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实际上做的一件事情就是创建一个包含两个子astzend_ast,然后设置zend_astkindZEND_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

符合我们的预期。