《手把手教你编写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_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

符合我们的预期。

《手把手教你编写PHP编译器》--实现算数表达式

实现算数表达式

这篇文章，我们来用flex和bison实现算数表达式。

几乎所有的编译原理教程都会以这个为例子进行讲解，因为算数表达式的例子是比较复杂一点的，主要是因为它的语法会比其他语法难一点，这其中会涉及到递归，优先级等问题。而关于优先级问题，我们可以使用bison自带的功能来解决，但是，我们也会去讲如何自己手动来实现优先级。

首先，我们来写一下zend_language_scanner.l：

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
%option noyywrap
%option nounput
%option noinput
%{
#include <iostream>
#include "zend_language_parser.h"
%}

%%
echo {
    return T_ECHO;
}

[;(),+*/-] {
    return *yytext;
}

[0-9]+ {
    yylval = atoi(yytext);
    return T_LNUMBER;
}

[#].* /* ignore comment */

[\t\n ]+  /* ignore \t, \n, whitespace */

. {
    std::cerr << "Lexical error. Unrecognized character: '" << *yytext << "'" << std::endl;
    exit(EXIT_FAILURE);
}
%%

我们逐一进行分析。

1
2
3
4
%{
#include <iostream>
#include "zend_language_parser.h"
%}

我们发现，这里有一对：

1
2
3
%{

%}

我们可以在这个地方去引入一些头文件。这里的重点是zend_language_parser.h这个文件，我们在之前的文章已经发现，zend_language_parser.h是由zend_language_parser.y通过bison生成的。那么我们为什么要引入这个头文件呢？因为我们会去使用zend_language_parser.h的一些东西（至于是什么，我们后面会讲）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
%%
echo {
    return T_ECHO;
}

[;(),+*/-] {
    return *yytext;
}

[0-9]+ {
    yylval = atoi(yytext);
    return T_LNUMBER;
}

[#].* /* ignore comment */

[\t\n ]+  /* ignore \t, \n, whitespace */

. {
    std::cerr << "Lexical error. Unrecognized character: '" << *yytext << "'" << std::endl;
    exit(EXIT_FAILURE);
}
%%

我们发现，这里有一对：

1
2
3
%%

%%

我们可以在这里面去定义我们需要解析的token。那么token是什么呢？我们来看这么一个例子。我们有如下php文件：

1
2
3
4
5
6
7
8
9
10
<?php
$tokens = token_get_all('<?php 1 + 2 + 3;');

foreach ($tokens as $token) {
    if (is_array($token)) {
        echo token_name($token[0]), " ('{$token[1]}')", PHP_EOL;
    } else {
        echo $token, PHP_EOL;
    }
}

执行结果如下：

1
2
3
4
5
6
7
8
9
10
11
T_OPEN_TAG ('<?php ')
T_LNUMBER ('1')
T_WHITESPACE (' ')
+
T_WHITESPACE (' ')
T_LNUMBER ('2')
T_WHITESPACE (' ')
+
T_WHITESPACE (' ')
T_LNUMBER ('3')
;

可以发现，从

1
<?php 1 + 2 + 3;

代码里面得到的token包括了T_OPEN_TAG、T_LNUMBER、T_WHITESPACE、+、T_LNUMBER、;。

所以，我们的%% %%里面的一些列正则，实际上做的事情就和PHP类似了。它会根据这些正则表达式，对输入的代码（也就是字符串）进行解析，如果匹配到了某条正则，那么就拿到对应的token。

其中：

1
2
3
[;(),+*/-] {
    return *yytext;
}

表示，如果当前输入的是字符是;(),+*/-里面的某一个，那么，我们直接返回这个字符作为它的token。这和我们上面的PHP代码行为一致，PHP没有为它们单独写一个T_*。

接着，我们来写一下我们的zend_language_parser.y文件：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
%{
#include <stdio.h>
#include <string.h>

extern int yylex(void);
extern int yyparse(void);
extern FILE *yyin;
extern int yylineno;

int yywrap()
{
    return 1;
}

void yyerror(const char *s)
{
    printf("[error] %s, in %d\n", s, yylineno);
}

int main(int argc, char const *argv[])
{
    const char *file = argv[1];
    FILE *fp = fopen(file, "r");

    if(fp == NULL)
    {
        printf("cannot open %s\n", file);
        return -1;
    }

    yyin = fp;
    yyparse();

    return 0;
}
%}

%token T_ECHO T_LNUMBER

%%

statement: %empty
|   T_ECHO additive_expr    { printf("%d\n", $2); }
;

additive_expr: %empty
|   multiplicative_expr                                 {$$ = $1;}
|   additive_expr '+' multiplicative_expr                 {$$ = $1 + $3;}
|   additive_expr '-' multiplicative_expr                 {$$ = $1 - $3;}
;

multiplicative_expr: %empty
|   primary                             {$$ = $1;}
|   multiplicative_expr '*' primary   {$$ = $1 * $3;}
|   multiplicative_expr '/' primary   {$$ = $1 / $3;}

primary: %empty
|   T_LNUMBER    {$$ = $1;}
|   '(' additive_expr ')'    {$$ = $2;}

%%

我们发现，这个文件的结构和zend_language_scanner.l极其相似。在%{ %}中写一点cpp的东西。在%% %%中写一点语法（只不过zend_language_scanner.l是写一些词法）。我们逐一来看。

首先是：

1
2
3
4
int yywrap()
{
    return 1;
}

这在多文件解析的时候会用到。如果返回1，表示我们解析文件完毕。如果返回0，说明我们还有文件需要解析。简单起见，我们先只支持单个文件的解析。

1
2
3
4
void yyerror(const char *s)
{
    printf("[error] %s, in %d\n", s, yylineno);
}

当语法分析出错的时候，会调用这个函数。其中yylineno表示哪一行解析失败了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main(int argc, char const *argv[])
{
    const char *file = argv[1];
    FILE *fp = fopen(file, "r");

    if(fp == NULL)
    {
        printf("cannot open %s\n", file);
        return -1;
    }

    yyin = fp;
    yyparse();

    return 0;
}

表示我们输入一个yaphp文件，然后对这个文件进行解析。yyin里面存了当前要解析的文件。

1
%token T_ECHO T_LNUMBER

定义了两个token。这是提供给zend_language_scanner.l文件使用的。我们可以在文件zend_language_parser.h里面找到这两个token具体会被生成什么：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* Token kinds.  */
#ifndef YYTOKENTYPE
# define YYTOKENTYPE
  enum yytokentype
  {
    YYEMPTY = -2,
    YYEOF = 0,                     /* "end of file"  */
    YYerror = 256,                 /* error  */
    YYUNDEF = 257,                 /* "invalid token"  */
    T_ECHO = 258,                  /* T_ECHO  */
    T_LNUMBER = 259                /* T_LNUMBER  */
  };
  typedef enum yytokentype yytoken_kind_t;
#endif

可以发现，实际上，我们在文件zend_language_parser.y里面定义的token，最终会被生成一个枚举类型的值。这也很好的解释了为什么我们需要在zend_language_scanner.l里面引入头文件zend_language_parser.h。

接着，就是我们的重点了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
statement: %empty
|   T_ECHO additive_expr    { printf("%d\n", $2); }
;

additive_expr: %empty
|   multiplicative_expr                                 {$$ = $1;}
|   additive_expr '+' multiplicative_expr                 {$$ = $1 + $3;}
|   additive_expr '-' multiplicative_expr                 {$$ = $1 - $3;}
;

multiplicative_expr: %empty
|   primary                             {$$ = $1;}
|   multiplicative_expr '*' primary   {$$ = $1 * $3;}
|   multiplicative_expr '/' primary   {$$ = $1 / $3;}

primary: %empty
|   T_LNUMBER    {$$ = $1;}
|   '(' additive_expr ')'    {$$ = $2;}

这就是我们算数表达式的语法了。这里，我们实现了优先级。其中括号()的优先级最高，乘法和除法的优先级其次，加法和减法的优先级最低。

那么，这个优先级是如何去实现的呢？我们可以看到，我们的加法表达式语法嵌套了乘法表达式语法；乘法表达式语法嵌套了我们的括号。

所以，我们通过文法的一个嵌套，实现了优先级。最下面的语法，它的优先级最高，最上面的语法，它的优先级最低。（如果对优先级这一块不太清楚的小伙伴，我建议自己去手写一遍优先级，然后就能够理解为什么了。我始终觉得，虽然我们是使用了bison做语法分析，但是，我们一定要具备没有这类工具，也可以去实现这些语法的能力，因为这是基本功）

好的，现在，让我们来运行一下我们的编译脚本：

1
./rebuild.sh

然后编写测试文件test1.php：

1
echo 2 + 2 * 3 / 2

执行我们的yaphp：

1
2
./build/yaphp tests/test1.php
5

我们发现，这里先计算了2 * 3 / 2，得到3之后，在进行2 + 3的运算，得到5。

我们再来一个例子：

1
echo (2 + 2) * 3 / 2

执行我们的yaphp：

1
2
./build/yaphp tests/test1.php
6

我们发现，这里先计算了(2 + 2)得到4之后，在进行4 * 3 / 2的运算，得到6。

OK，我们算是实现了优先级。但是，这么去写语法规则是非常的难看的，一点也不优雅。

我们来借助bison的能力，实现一下优先级。我们修改一下我们的语法文件：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
%{
#include <stdio.h>
#include <string.h>

extern int yylex(void);
extern int yyparse(void);
extern FILE *yyin;
extern int yylineno;

int yywrap()
{
    return 1;
}

void yyerror(const char *s)
{
    printf("[error] %s, in line %d\n", s, yylineno);
}

int main(int argc, char const *argv[])
{
    const char *file = argv[1];
    FILE *fp = fopen(file, "r");

    if(fp == NULL)
    {
        printf("cannot open %s\n", file);
        return -1;
    }

    yyin = fp;
    yyparse();

    return 0;
}
%}

%token T_ECHO T_LNUMBER

%left '+' '-'
%left '*' '/'
%left '(' ')'

%%

statement: %empty
|   T_ECHO expr    { printf("%d\n", $2); }
;

expr: %empty
|   expr '+' expr                 {$$ = $1 + $3;}
|   expr '-' expr                 {$$ = $1 - $3;}
|   expr '*' expr                 {$$ = $1 * $3;}
|   expr '/' expr                 {$$ = $1 / $3;}
|   '(' expr ')'                  {$$ = $2;}
|   T_LNUMBER                      {$$ = $1;}
;

%%

可以发现，我们这里多了一部分东西：

1
2
3
%left '+' '-'
%left '*' '/'
%left '(' ')'

这实际上就是我们的优先级定义了。自上而下，它的优先级越来越高。我们现在重新编译一下我们的yaphp：

1
./rebuild.sh

然后执行上面的两个例子，我们就可以得到和我们首先优先级一样的结果了。

《手把手教你编写PHP编译器》--准备工作

准备工作

在写代码之前，我们很有必要先把编译C++代码的工作做好。主要涉及到以下几个方面：

1
2
1. 编写CMakeLists
2. 编写一个编译的脚本

编写CMakeLists

因为CMakeLists.txt的内容比较简单，所以我直接贴出我们的CMakeLists.txt文件的内容：

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
38
39
40
41
42
43
44
cmake_minimum_required(VERSION 3.4)
project(yaphp)

set(CMAKE_CXX_STANDARD 11)
set(CMAKE_CXX_COMPILER clang++)

find_package(FLEX REQUIRED)
set(FlexOutput ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_scanner.cc)
if(FLEX_FOUND)
    add_custom_command(
      OUTPUT ${FlexOutput}
      COMMAND ${FLEX_EXECUTABLE}
              --outfile=${FlexOutput}
              ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_scanner.l
      COMMENT "Generating zend_language_scanner.cc"
    )
endif()

find_package(BISON REQUIRED)
set(BisonOutput ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.cc)
if(BISON_FOUND)
    add_custom_command(
      OUTPUT ${BisonOutput}
      COMMAND ${BISON_EXECUTABLE}
              --defines=${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.h
              --output=${BisonOutput}
              ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.y
      COMMENT "Generating zend_language_parser.cc"
    )
endif()

add_executable(yaphp
    ${FlexOutput}
    ${BisonOutput}
)
include_directories(BEFORE ${CMAKE_CURRENT_SOURCE_DIR})
target_compile_options(yaphp PUBLIC ${CMAKE_CXX_FLAGS} -Wall -Wno-deprecated-register -O0 -g)

message(STATUS "summary of build options:
    Install prefix:  ${CMAKE_INSTALL_PREFIX}
    Target system:   ${CMAKE_SYSTEM_NAME}
    Compiler:
      CXX compiler:    ${CMAKE_CXX_COMPILER}
")

我们来讲一下核心的东西，其他不清楚的地方，可以网上搜一下。

首先来看这段代码：

1
project(yaphp)

我们把我们的这个项目叫做yaphp，即表示Yet another php。

然后是这段代码：

1
2
3
4
5
6
7
8
9
10
11
find_package(FLEX REQUIRED)
set(FlexOutput ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_scanner.cc)
if(FLEX_FOUND)
    add_custom_command(
      OUTPUT ${FlexOutput}
      COMMAND ${FLEX_EXECUTABLE}
              --outfile=${FlexOutput}
              ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_scanner.l
      COMMENT "Generating zend_language_scanner.cc"
    )
endif()

这段代码做的事情是，通过flex，让zend_language_scanner.l文件生成zend_language_scanner.cc文件（如果不清楚zend_language_scanner.l的小伙伴不用着急，我们后面会讲）。并且，我们可以看到，我们把zend_language_scanner.l文件放在了Zend目录下，这实际上是和php-src（即php解释器）的一致的。

然后是这段代码：

1
2
3
4
5
6
7
8
9
10
11
12
find_package(BISON REQUIRED)
set(BisonOutput ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.cc)
if(BISON_FOUND)
    add_custom_command(
      OUTPUT ${BisonOutput}
      COMMAND ${BISON_EXECUTABLE}
              --defines=${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.h
              --output=${BisonOutput}
              ${CMAKE_SOURCE_DIR}/src/Zend/zend_language_parser.y
      COMMENT "Generating zend_language_parser.cc"
    )
endif()

这段代码做的事情是，通过bison，让zend_language_parser.y文件生成zend_language_parser.cc文件和zend_language_parser.h文件（如果不清楚zend_language_parser.y的小伙伴不用着急，我们后面会讲）。

然后是这段代码：

1
2
3
4
add_executable(yaphp
    ${FlexOutput}
    ${BisonOutput}
)

表示，我们要把${FlexOutput}和${BisonOutput}编译成yaphp可执行文件。

OK，按照这个CMakeLists.txt的意思，我们来创建对应的文件。首先是文件src/Zend/zend_language_scanner.l：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
%option noyywrap
%option nounput
%option noinput
%{
#include "zend_language_parser.h"
%}

%%
echo {
    return T_ECHO;
}

[;(),+*/-] return *yytext;

[0-9]+ {
    yylval = atoi(yytext);
    return T_NUMBER;
}

[\t\n ]+  /* ignore \t, \n, whitespace */

%%

然后是文件src/Zend/zend_language_parser.y：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
%{
#include <stdio.h>
#include <string.h>

extern int yylex(void);
extern int yyparse(void);
extern FILE *yyin;
extern int yylineno;

int yywrap()
{
    return 1;
}

void yyerror(const char *s)
{
    printf("[error] %s, in line %d\n", s, yylineno);
}

int main(int argc, char const *argv[])
{
    const char *file = argv[1];
    FILE *fp = fopen(file, "r");

    if(fp == nullptr)
    {
        printf("cannot open %s\n", file);
        return -1;
    }

    yyin = fp;
    yyparse();

    return 0;
}
%}

%token T_ECHO T_NUMBER

%%

statement: %empty
|   T_ECHO expr    { printf("%d\n", $2); }
;

expr: %empty
|   T_NUMBER                      {$$ = $1;}
;

%%

然后，我们创建文件tests/test1.php：

1
echo 1

编写编译的脚本

我们创建文件rebuild.sh：

1
2
3
4
#!/bin/bash
__DIR__=$(cd "$(dirname "$0")" || exit 1; pwd); [ -z "${__DIR__}" ] && exit 1

cd "${__DIR__}" && ./clean.sh && mkdir -p build && cd build && cmake .. && make

这段代码很简单，就是先调用clean.sh脚本做一些清理工作，然后调用cmake来生成Makefile，然后调用make来编译代码，生成yaphp。

然后创建文件tools/cleaner.sh：

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
#!/bin/bash
__DIR__=$(cd "$(dirname "$0")" || exit 1; pwd); [ -z "${__DIR__}" ] && exit 1

error(){ echo "[ERROR] $1"; exit 1; }
success(){ echo "[SUCCESS] $1"; exit 0; }
info(){ echo "[INFO] $1";}

workdir="$1"

if ! cd "${workdir}"; then
  error "Cd to ${workdir} failed"
fi

info "Scanning dir \"${workdir}\" ..."

if [ ! -f "./Makefile" ] && [ ! -f "./CMakeLists.txt" ]; then
  error "Non-project dir ${workdir}"
fi

info "CMake build dir will be removed:"

rm -rf -v ./build

info "Following files will be removed:"

find ${workdir}/src/Zend -name zend_language_scanner.cc -print0 | xargs -0 rm -f -v
find ${workdir}/src/Zend -name zend_language_parser.h -print0 | xargs -0 rm -f -v
find ${workdir}/src/Zend -name zend_language_parser.cc -print0 | xargs -0 rm -f -v

success "Clean '${workdir}' done"

这个脚本会清理掉cmake生成的一系列文件。

然后创建文件clean.sh：

1
2
3
4
#!/bin/bash
__DIR__=$(cd "$(dirname "$0")" || exit 1; pwd); [ -z "${__DIR__}" ] && exit 1

"${__DIR__}"/tools/cleaner.sh "${__DIR__}"

OK，现在，所以的事情都做好了，我们只需要执行脚本rebuild.sh：

1
2
3
4
5
./rebuild.sh

# 省略其他的输出
[100%] Linking CXX executable yaphp
[100%] Built target yaphp

现在，你将会在目录build下面看到编译好的yaphp。并且，细心的话，你会发现，在目录src/Zend下面，生成了文件zend_language_scanner.cc、zend_language_parser.h、zend_language_parser.cc。

现在，让我们执行这个yaphp：

1
2
./build/yaphp tests/test1.php
1

我们将会看到，1被打印了出来。

Linux下Mutex的所有者线程先死亡造成其他线程获取锁阻塞的问题

Swoole最近有一个BUG，大概就是Mutex的所有者线程先死亡，造成其他线程获取锁阻塞的问题。具体的iseue在这里。

我们可以用如下代码来对这个问题进行复现：

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
#include <pthread.h>
#include <iostream>
#include <unistd.h>

pthread_mutex_t mutex;

void *handler(void *)
{
    std::cout << "child thread" << std::endl;
    int ret = pthread_mutex_lock(&mutex);
    std::cout << "child ret: " << ret << std::endl;
    pthread_exit(NULL);
}

int main()
{
    pthread_t tid;
    pthread_mutexattr_t attr;
    int ret;

    pthread_mutexattr_init(&attr);
    pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_ERRORCHECK);

    pthread_mutex_init(&mutex, &attr);
    pthread_mutexattr_destroy(&attr);

    pthread_create(&tid, NULL, handler, NULL);

    sleep(2);
    std::cout << "father awake" << std::endl;

    ret = pthread_mutex_lock(&mutex);
    std::cout << "father ret: " << ret << std::endl;
    return 0;
}

这段代码的意思是，主线程创建了子线程之后，立马调用sleep阻塞住。然后子线程去获取锁，然后子线程立马退出，导致锁没有被解开。然后当主线程sleep结束后，尝试获取锁的时候，就会阻塞住。（导致这个现象的原因是，子线程退出后，操作系统并不会把锁解开）

我们可以执行下上面这段代码，执行结果如下：

1
2
3
4
5
6
7
g++ lock.cc -lpthread
./a.out

child thread
child ret: 0
father awake

解决方式如下：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <unistd.h>
#include <pthread.h>
#include <string.h>
#include <errno.h>

pthread_mutex_t lock;

void *dropped_thread(void*)
{
    std::cout << "Setting lock..." << std::endl;
    pthread_mutex_lock(&lock);
    std::cout << "Lock set, now exiting without unlocking..." << std::endl;
    pthread_exit(NULL);
}

int main(int argc, char *argv[])
{
    int ret;
    pthread_t lock_getter;
    pthread_mutexattr_t attr;

    pthread_mutexattr_init(&attr);
    pthread_mutexattr_setrobust(&attr, PTHREAD_MUTEX_ROBUST);
    pthread_mutex_init(&lock, &attr);
    pthread_mutexattr_destroy(&attr);
    pthread_create(&lock_getter, NULL, dropped_thread, NULL);
    sleep(2);

    std::cout << "Inside main" << std::endl;
    std::cout << "Attempting to acquire mutex?" << std::endl;

    ret = pthread_mutex_lock(&lock);
    if (ret == EOWNERDEAD) {
        std::cout << "errno: " << ret << ", error: " << strerror(ret) << std::endl;

        std::cout << "consistent mutex" << std::endl;
        pthread_mutex_consistent(&lock);

        std::cout << "unlock mutex" << std::endl;
        pthread_mutex_unlock(&lock);
    } else {
        std::cout << "errno: " << ret << ", error: " << strerror(ret) << std::endl;
    }
    std::cout << "Attempting to acquire mutex?" << std::endl;
    ret = pthread_mutex_lock(&lock);
    if (ret != 0) {
        std::cout << "errno: " << ret << ", error: " << strerror(ret) << std::endl;
    } else {
        std::cout << "Successfully acquired lock!" << std::endl;
        pthread_mutex_destroy(&lock);
    }

    return 0;
}

执行结果如下：

1
2
3
4
5
6
7
8
9
10
11
12
g++ lock.cc -lpthread
./a.out

Setting lock...
Lock set, now exiting without unlocking...
Inside main
Attempting to acquire mutex?
errno: 130, error: Owner died
consistent mutex
unlock mutex
Attempting to acquire mutex?
Successfully acquired lock!

这里的核心是，我们对这个锁设置了PTHREAD_MUTEX_ROBUST。这样的话，锁的拥有者退出后，其他线程去获取锁的时候，就不会阻塞住了，而是返回错误码EOWNERDEAD。并且，这里还有一个细节就是，在获得了错误码之后，我们需要设置锁的状态为consistent。这样，其他线程就能解开锁了。

《手把手教你编写PHP编译器》--开篇

从今天开始，我打算写一个全新的教程，手把手去实现一个五脏俱全的PHP，教程风格类似于去年我写的手把手编写PHP协程扩展那样，但是会有一点不同，这个教程可能就不会那么直接上那么多代码了，重点是讲解实现的思路。

这个编译器语法会尽可能的和PHP保持一致。并且我希望它是一门静态强类型的语言，你可以在定义一个变量的时候，不声明类型，但是我们会进行类型推导。

教程的知识点我希望和龙书的尽可能吻合，但是也不会和它完全一样，毕竟这本书前面有太多讲解编译器前端的东西了，很多手写解析源代码的，这有一些算法，一旦拿出来讲，估计会起到劝退的效果。这门教程我希望更多的是讲解编译器的后端优化，这一点也和大多数的PHP源码分析教程不同，目前来看，因为PHP的原因，编译器后端的优化除了JIT似乎就没了，而且大多数是去讲解AST生成的。

至于后端的优化，会讲解原理，但是，真正的去实现的时候，我们不会自己去手写，这太费劲了，我们直接使用LLVM，然后开优化，读IR，来验证优化的思路。所以，这门教程，会讲解LLVM的中间表示。但是我们不会去手写LLVM的IR，而是使用LLVM的API来自动生成中间表示。

这门教程是使用C++来开发的，构建工具是CMake，编译器前端工具是flex和bison，编译器后端工具是LLVM。

之前我打算使用PHP来写这门教程。试坑之后，我发现有以下几点问题：

1、如果直接使用PHP-Parser来生成AST，那么我们实现的语法就会受很大的限制了

2、PHP对LLVM的绑定没有看到比较好的。我有想过去写扩展对LLVM包一层，但是这工作量太大了。也想过用FFI来直接搞，但是怕PHP的FFI有问题。所以就干脆直接用C++来完成我们的这门教程了。

我不是一个专门研究编译器的人，这个教程主要是对自己的一个阶段性学习的总结。就和PHP协程扩展开发教程一样，边写边学习，算是对自己这一年的一个总结吧。

CPU占用过高分析

今天遇到了一个hyperf死循环的bug，排查了很久，没有思路。后来峰哥指导，立马定位出了问题。

定位步骤，首先，通过perf top命令来查看系统的cpu占用情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
perf top -p 19732

Samples: 16K of event 'cpu-clock', 4000 Hz, Event count (approx.): 3364648111 lost: 0/0 drop: 0/0
Overhead  Shared Object        Symbol
   9.02%  [kernel]             [k] _raw_spin_unlock_irqrestore
   7.96%  php                  [.] execute_ex
   6.85%  [kernel]             [k] finish_task_switch
   2.82%  php                  [.] ZEND_FETCH_OBJ_R_SPEC_UNUSED_CONST_HANDLER
   2.05%  libpthread-2.17.so   [.] __libc_recv
   1.93%  php                  [.] ZEND_INIT_METHOD_CALL_SPEC_UNUSED_CONST_HANDLER
   1.55%  libc-2.17.so         [.] __memmove_ssse3_back
   1.43%  [vdso]               [.] __vdso_gettimeofday
   1.35%  libc-2.17.so         [.] __memcpy_ssse3_back
   1.31%  php                  [.] zend_leave_helper_SPEC

可以看到，execute_ex这个函数的Overhead非常的高。所以，可以大改猜测是PHP代码的问题。然后，我们找到PHP的进程，用strace看一下进程在做啥事情：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
strace -p 19732

sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42
recvfrom(20, "-", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "-MISCONF Redis is configured to save RDB snapshots, but it is currently not able to persist on disk. Commandsthat may modify the data set are disabled, because this instance is configured to report errors during writes if RDB snapshotting fails (stop-writes-on-bgsave-error option). Please check the Redis logs for details about the RDB error.\r\n", 8192, 0, NULL, NULL) = 346
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$13\r\nqueue:delayed\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 101, 0, NULL, 0) = 101
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*7\r\n$16\r\nZREVRANGEBYSCORE\r\n$14\r\nqueue:reserved\r\n$10\r\n1599474415\r\n$4\r\n-inf\r\n$5\r\nLIMIT\r\n$1\r\n0\r\n$3\r\n100\r\n", 102, 0, NULL, 0) = 102
recvfrom(20, "*", 1, MSG_PEEK, NULL, NULL) = 1
recvfrom(20, "*0\r\n", 8192, 0, NULL, NULL) = 4
recvfrom(20, 0x7f08526509e0, 1, MSG_PEEK, NULL, NULL) = -1 EAGAIN (Resource temporarily unavailable)
sendto(20, "*3\r\n$5\r\nBRPOP\r\n$13\r\nqueue:waiting\r\n$1\r\n2\r\n", 42, 0, NULL, 0) = 42

可以看到，hyperf应该是没有去判断redis是否崩溃，即使redis崩溃了，也在一直循环的读取redis。

面向对象的语义特征

我们知道，编程语言是用来对这个世界建模的，而面向对象则是建模方式中比较推崇的一种方法。我们来说一说面向对象的语义特征，进而让我们理解编程语言的本质。

类型角度

在汇编语言里面，是只支持简单类型的，例如整型。如果我们要实现稍微复杂一点的类型，例如字符串，那么，我们就需要一块内存，然后往这块内存里面挨个的放入字符，然后，我们把这块内存存储的内容，叫做字符串。同样的道理，类也是一种复杂的类型。

作用域角度

分为类的作用域和对象成员的作用域。

对于类来说，如果没有声明命名空间，那么，类的作用域就是根命名空间；如果有命名空间，那么类的作用域就是这个命名空间。

对于对象成员来说，成员的作用域则是这个对象。我们是通过这个对象来找到这个成员的（当然，如果你是静态成员，那么，也可以通过类来找到）。

所以，我们在实现面向对象的时候，必定会把这个对象放入栈帧里面，例如PHP里面的execute_data::This。而我们在方法里面使用的$this，实际上就是当前栈帧的execute_data::This。例如：

1
2
3
4
5
6
7
8
9
10
11
12
class Foo
{
    public $a;

    public $b;

    public function __construct($a, $b)
    {
        $this->a = $a;
        $this->b = $b;
    }
}

我们在构造函数里面，通过$this来访问成员a。那么，我们就是在构造函数的这个栈帧里面，找到$this变量，然后，再查找这个对象的a属性。

使用Visitor模式来解析抽象语法树

我们在生成了AST之后，要做的事情就是去解析它。我们可以对它做很多的操作，比如修改AST的某些节点；对AST执行我们的语义操作，比如碰到+号，表示我们要做加法运算了，这样，我们就可以实现我们自己的语言了。

而visitor模式的思想就是，当我们遍历AST上的每一个节点的时候，都去执行我们注册的所有visitor。这样，我们可以让代码更加的优雅，我们只需要专注于实现当前visitor的功能即可，让AST的结构和对AST的操作解耦。

我以PHP为例，大致介绍下如何通过visitor模式来用PHP实现PHP。我们给我们的这门语言命名为yaphp（实际上，这正是我现在开发的语言，还未开源）。

我们有如下yaphp的代码：

1
2
3
4
5
6
<?php

$a = 1 + 2 + 3 - 4;
$b = 2 * 3;
$c = $a + $b;
var_dump($c);

我们可以得到它的抽象语法树：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
array(
    0: Stmt_Expression(
        expr: Expr_Assign(
            var: Expr_Variable(
                name: a
            )
            expr: Expr_BinaryOp_Minus(
                left: Expr_BinaryOp_Plus(
                    left: Expr_BinaryOp_Plus(
                        left: Scalar_LNumber(
                            value: 1
                        )
                        right: Scalar_LNumber(
                            value: 2
                        )
                    )
                    right: Scalar_LNumber(
                        value: 3
                    )
                )
                right: Scalar_LNumber(
                    value: 4
                )
            )
        )
    )
    1: Stmt_Expression(
        expr: Expr_Assign(
            var: Expr_Variable(
                name: b
            )
            expr: Expr_BinaryOp_Mul(
                left: Scalar_LNumber(
                    value: 2
                )
                right: Scalar_LNumber(
                    value: 3
                )
            )
        )
    )
    2: Stmt_Expression(
        expr: Expr_Assign(
            var: Expr_Variable(
                name: c
            )
            expr: Expr_BinaryOp_Plus(
                left: Expr_Variable(
                    name: a
                )
                right: Expr_Variable(
                    name: b
                )
            )
        )
    )
    3: Stmt_Expression(
        expr: Expr_FuncCall(
            name: Name(
                parts: array(
                    0: var_dump
                )
            )
            args: array(
                0: Arg(
                    name: null
                    value: Expr_Variable(
                        name: c
                    )
                    byRef: false
                    unpack: false
                )
            )
        )
    )
)

这个抽象语法树还是比较简单的。我们大致可以看到，有4条表达式语句。我们逐个来看。

第一条表达式语句：

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
0: Stmt_Expression(
    expr: Expr_Assign(
        var: Expr_Variable(
            name: a
        )
        expr: Expr_BinaryOp_Minus(
            left: Expr_BinaryOp_Plus(
                left: Expr_BinaryOp_Plus(
                    left: Scalar_LNumber(
                        value: 1
                    )
                    right: Scalar_LNumber(
                        value: 2
                    )
                )
                right: Scalar_LNumber(
                    value: 3
                )
            )
            right: Scalar_LNumber(
                value: 4
            )
        )
    )
)

这是一个赋值语句，我们通过这个结构得出，这个AST是右结合的。也就意味着，我们的赋值语句是右结合的。Expr_Assign它的左子树是一个变量的名字，Expr_Assign它的右子树是一个算数表达式。通过这个算数表达式的AST结构，我们可以看成，它是左结合的。

OK，我们可以根据这些节点的类型，写出对应的visitor。

首先是AdditiveExpressionVisitor：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
<?php

declare(strict_types=1);
/**
 * This file is part of Yaphp.
 *
 * @contact  codinghuang@qq.com
 */
namespace Yaphp\NodeVisitor;

use PhpParser\Node;
use PhpParser\Node\Expr;
use PhpParser\Node\Expr\BinaryOp;
use PhpParser\Node\Expr\BinaryOp\Minus;
use PhpParser\Node\Expr\BinaryOp\Plus;
use PhpParser\Node\Expr\Variable;
use PhpParser\Node\Scalar\LNumber;
use PhpParser\NodeVisitorAbstract;
use Yaphp\HandWritten\CompilerGlobals;

class AdditiveExpressionVisitor extends NodeVisitorAbstract
{
    public function enterNode(Node $node)
    {
        if (! ($node instanceof Plus) && ! ($node instanceof Minus)) {
            return;
        }
        switch (get_class($node)) {
            case Plus::class:
            case Minus::class:
                $result = $this->additiveExpression($node);
                $resultNode = new Node\Scalar\LNumber($result);
                break;
            default:
                break;
        }

        return $resultNode;
    }

    protected function additiveExpression(Expr $expr): int
    {
        if (isset($expr->left)) {
            $leftValue = $this->additiveExpression($expr->left);
        }
        if (isset($expr->right)) {
            $rightValue = $this->additiveExpression($expr->right);
        }

        switch (get_class($expr)) {
            case Plus::class:
                return $leftValue + $rightValue;
                break;
            case Minus::class:
                return $leftValue - $rightValue;
                break;
            case Variable::class:
                return CompilerGlobals::getSymbol($expr->name);
                break;
            case LNumber::class:
                return $expr->value;
                break;
            default:
                echo sprintf("Don't support expression %s", $expr->getType());
                exit;
                break;
        }

        return $leftValue + $rightValue;
    }
}

因为，加法和减法我们认为是同一类操作，所以，我们可以把加法和减法写在一个visitor里面。

接着就是AssignVistor：

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
<?php

declare(strict_types=1);
/**
 * This file is part of Yaphp.
 *
 * @contact  codinghuang@qq.com
 */
namespace Yaphp\NodeVisitor;

use PhpParser\Node;
use PhpParser\Node\Expr\Assign;
use PhpParser\Node\Expr\BinaryOp;
use PhpParser\Node\Scalar\LNumber;
use PhpParser\NodeVisitorAbstract;
use Yaphp\HandWritten\CompilerGlobals;

class AssignVistor extends NodeVisitorAbstract
{
    public function leaveNode(Node $node)
    {
        $value = -INF;
        if (! ($node instanceof Assign)) {
            return;
        }
        if ($node->expr instanceof LNumber) {
            $value = $node->expr->value;
        } else if ($node->expr instanceof BinaryOp) {
            $return = (new AdditiveExpressionVisitor)->enterNode($node->expr);
            $value = $return->value;
        }
        CompilerGlobals::setSymbol($node->var->name, $value);
    }
}

可以看到，实现变量就是一个字典，把变量的名字和对应的值存起来即可。目前我们这篇文章不考虑变量的作用域，所以我们把所有的变量通通存在了一个全局变量里面。

第二条表达式语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
1: Stmt_Expression(
    expr: Expr_Assign(
        var: Expr_Variable(
            name: b
        )
        expr: Expr_BinaryOp_Mul(
            left: Scalar_LNumber(
                value: 2
            )
            right: Scalar_LNumber(
                value: 3
            )
        )
    )
)

可以看到，这个结构和加法的算数表达式几乎是一样的。但是，我们认为加法和乘法还是有一定的区别的，所以我们单独给乘法写一个visitor：

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<?php

declare(strict_types=1);
/**
 * This file is part of Yaphp.
 *
 * @contact  codinghuang@qq.com
 */
namespace Yaphp\NodeVisitor;

use PhpParser\Node;
use PhpParser\Node\Expr;
use PhpParser\Node\Expr\BinaryOp\Div;
use PhpParser\Node\Expr\BinaryOp\Mul;
use PhpParser\NodeVisitorAbstract;

class MultiplicativeExpressionVisitor extends NodeVisitorAbstract
{
    public function enterNode(Node $node)
    {
        if (! ($node instanceof Mul) && ! ($node instanceof Div)) {
            return;
        }
        switch (get_class($node)) {
            case Mul::class:
            case Div::class:
                $result = $this->multiplicativeExpression($node);
                $resultNode = new Node\Scalar\LNumber($result);
                break;
            default:
                break;
        }

        return $resultNode;
    }

    protected function multiplicativeExpression(Expr $expr): int
    {
        if (isset($expr->left)) {
            $leftValue = $this->multiplicativeExpression($expr->left);
        }
        if (isset($expr->right)) {
            $rightValue = $this->multiplicativeExpression($expr->right);
        }

        switch (get_class($expr)) {
            case Mul::class:
                return $leftValue * $rightValue;
                break;
            case Div::class:
                return $leftValue / $rightValue;
                break;
            default:
                return $expr->value;
                break;
        }

        return $leftValue * $rightValue;
    }
}

第三条表达式语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2: Stmt_Expression(
    expr: Expr_Assign(
        var: Expr_Variable(
            name: c
        )
        expr: Expr_BinaryOp_Plus(
            left: Expr_Variable(
                name: a
            )
            right: Expr_Variable(
                name: b
            )
        )
    )
)

这是两个变量相加，然后把表达式的结果赋值给一个新的变量。因为，我们把两个变量相加，也放在了AdditiveExpressionVisitor，所以，这里我们无须再实现一个新的visitor了。

我们来看最后一个表达式语句：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
3: Stmt_Expression(
    expr: Expr_FuncCall(
        name: Name(
            parts: array(
                0: var_dump
            )
        )
        args: array(
            0: Arg(
                name: null
                value: Expr_Variable(
                    name: c
                )
                byRef: false
                unpack: false
            )
        )
    )
)

这是一个函数调用了，所以，我们需要实现一个新的FuncCallExpressionVisitor。因为，函数也是可以求值的，所以我们把函数调用visitor归类为expression：

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
38
39
40
<?php

declare(strict_types=1);
/**
 * This file is part of Yaphp.
 *
 * @contact  codinghuang@qq.com
 */
namespace Yaphp\NodeVisitor;

use PhpParser\Node;
use PhpParser\Node\Expr\FuncCall;
use PhpParser\NodeVisitorAbstract;
use Yaphp\HandWritten\CompilerGlobals;

class FuncCallExpressionVisitor extends NodeVisitorAbstract
{
    public function leaveNode(Node $node)
    {
        if (! ($node instanceof FuncCall)) {
            return;
        }

        $functionName = $node->name->parts[0];
        $symbol = $node->args[0]->value->name;

        if (! CompilerGlobals::hasSymbol($symbol)) {
            throw new \Exception(sprintf('not define symbol %s', $symbol), 1);
        }

        if ($functionName === 'var_dump') {
            $this->varDumpHandler(CompilerGlobals::getSymbol($symbol));
        }
    }

    protected function varDumpHandler($symbol)
    {
        var_dump($symbol);
    }
}

这里，我们实现var_dump的方式就非常的简单了。当我们发现，这是一个var_dump函数的时候，我们直接调用var_dump函数即可。

至此，我们就算是实现了我们所有的visitor了。只要我们对AST使用上我们的visitor，我们就可以很愉快的去解析它了。

为什么一定要写注释和测试

最近在公司用PHP重写之前的Lua代码，这份Lua代码量不多，3000行左右。但是，我花了不少时间重写。感触非常大，所以想分享一下。

首先，我说一下这份需要重写的代码问题：

1
2
3
4
1. 没有一个测试。
2. 因为功能不断的在增加，加上对代码质量的不重视，复制粘贴的地方太多了。可能只是改了几个传参而已，但是，却复制了整个函数。
3. 多个地方，本来可以用几句话写完的逻辑，可能是因为当时没想到，逻辑写的非常复杂。并且这段复杂的代码没有注释。
4. 整个项目的注释占比太少了，可以说几乎没有。

我针对这几点来说一下。

第一点，没有一个测试。

这是我认为最严重的问题。我个人认为，一个没有测试的项目，经过无数迭代和多人接手之后，必定是屎山。你代码可以写的不好，但是，你必须要尽可能的写足够的测试，来保证你目前的功能都是正常的。

那么，没有测试的话，会导致什么问题呢？

很明显，你不敢去修改一个你不太熟悉的地方，你不知道这么改对不对，会不会影响其他的代码。所以，你可能就会自己去写一遍。甚至来说，你非常熟悉这份代码了，但是，你没有测试，你也不敢去改，因为你改完之后，你确定不了改完后代码后，整个系统正不正常。毕竟，你怕背锅。久而久之，这份代码极其丑陋。后面，你想改也没动力了。

并且，没有测试的话，你完全不敢去升级你使用的框架，除非你头铁。你知道这个框架有bug了，但是，你不知道升级之后，是否会有api不兼容的问题，导致你的项目出其他的bug。

所以，没有测试，团队的代码会越来越丑陋。（如果是个人的项目，可能你还能撑得住）

你可能有千万个理由说自己没时间写测试。然而，写一个测试其实要不了多少时间，可能比你在postman等工具手动填充参数要的时间还少。我个人觉得，不写测试，是不热爱编程，没有享受敲击键盘的快感，你是一个喜欢手动完成一些任务的人。

第二点，代码质量问题。

我重写的时候，旧代码有太多的复制粘贴了。但是，我在完全重写之前，我是不敢对代码进行优化的。那么，我是怎么做的，我先按照Lua的代码，一字一句的完全翻译完，旧代码复制了几遍，我就重写几遍。然后，我给我重写后的代码编写足够的测试，然后我才敢进行优化。

那么，如果旧代码有测试会怎么样？我完全可以对旧代码进行重构，然后跑一遍测试，看一看测试是否通过。然后，我再按照优化后的代码进行重写。这样，重写的错误率会大大降低。

第三点，简单的逻辑落地在代码上，就变复杂了。

其实，把简单的逻辑写复杂了还能接收，但是，如果没有对这段复杂的代码进行解释，以后就没多少人能够读懂，写代码的人过久了估计也读不懂。所以，我建议，如果代码被你写复杂了，你一定要在旁边写上注释，解释一下这段代码做了什么。以后，就好按照注释进行代码优化。

第四点，没有注释。

很多人可能说，代码就可以表达意思，实际上我觉得并不可以。就算你有一个好的函数名字，你依然会去点开这个函数来看看，看它到底怎么写的。一旦你点进去 ，那么，很可能你就会被里面的代码给整懵了。你不懂这段代码为什么要这么做，即使你有了更好的点子，你也不敢去改。你怕你的想法和这段代码并不完全一致，一些细节，你可能没有考虑到。

还有一些特殊的if条件，我建议也最好注释一下。因为它可能只在某些特殊的场景才会出现，但是随着我们系统的变化，这个场景可能就不会出现了，那么，我们以后完全可以把这个特殊的代码分支给删了。

优化递归下降算法的尾递归

我们在文章递归下降算法左递归问题这篇文章里面，介绍了如何消除左递归。总结起来，就是把非终结符放到终结符的右边，使得我们在推导的过程中，可以消耗掉下一个token。

但是，这种方法有一个问题。还是以1 + 2 + 3这个表达式为例来讲解一下优化手段。

首先，我们的文法规则如下：

1
additive -> intLiteral | intLiteral + additive

按照这个文法，我们将会构造出如下抽象语法树：

1
2
3
    +
1       +
    2       3

我们发现，这棵树是向右倾斜的，那么，我们在解析这个抽象语法树的时候，就必然是先计算2 + 3，得到5之后 ，再计算1 + 5。所以，这是右结合的（注意，结合性和优先级的区别，优先级指的是，无论什么时候，都是先计算，而结合性指的是一种普遍的计算顺序，从哪边到哪边。顺带一提的是，优先级我们可以通过层级嵌套来实现，把优先级高的放在子级，那么，它必然就先计算了）。但是，一般来说，我们的加法表达式都是左结合的。（也有右结合的例子，例如$a = 1 + 2，先计算1 + 2，然后再计算$a = 3）。所以 ，我们需要调整一下这个抽象语法树的结构，我们打算让这棵树向左倾斜，这样的话，就会先计算左边的子树，然后再计算左边的子树。所以，我们期望的结构如下 ：

1
2
3
        +
    +       3
1       2

这样，我们在遍历这棵树的时候，就会先计算1 + 2，然后再计算3 + 3。这是符合我们的预期的。

那么，为什么文法：

1
additive -> intLiteral | intLiteral + additive

生成的AST它是右结合的呢？因为我们的非终结符是在右边，终结符在左边，所以，在一棵子树里面，左节点必然是终结符，右子树必然是一棵递归的树，直到右子树碰到终结符，才停止右子树的生成。

所以，如果我们要让一棵树变成左结合的，我们可以调整一下文法，把非终结符放到左边，终结符放到右边。如下：

1
additive -> intLiteral | additive + intLiteral

当时，我们之前说过了，左递归会造成无限递归。但是，无限循环的前提是，我们使用的是递归下降算法来生成AST。如果我们不用递归下降算法来构造AST，那么我们是可以避免无限递归的。并且，不是所有的算法都不能处理左递归，例如LR算法是可以处理左递归的。

好了，我们现在使用ebnf来改造下这个文法：

1
2
3
additiveExpression -> intLiteral | additiveExpression + intLiteral
->
additiveExpression: intLiteral | intLiteral (+ intLiteral)*

（需要注意的一点事，这里的+不是正则的元符号+的含义，它仅仅是字符串+）

可能这个过程大家会看不懂，我多讲一点推导过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
additiveExpression: intLiteral | additiveExpression + intLiteral + intLiteral + intLiteral ....
->
因为，“+ intLiteral + intLiteral + intLiteral ....” 这部分必须终止，所以，additiveExpression最后一次推导必然是得到intLiteral，因此，additiveExpression -> intLiteral additiveExpression'：

additiveExpression: intLiteral | intLiteral additiveExpression'

所以，我们现在需要解决的问题就是如何用additiveExpression'去推导“+ intLiteral + intLiteral + intLiteral ....”。通过归纳法，我们可以很轻易的得到如下结果：

additiveExpression': + intLiteral additiveExpression' | ε

其中，ε表示空集。这在递归的时候，作为结束条件。我们发现，这是一个尾递归了，那么，我们就可以想到尾递归的优化，我们可以写成一个循环：
->
additiveExpression: intLiteral | intLiteral (+ intLiteral)*

因此，最终，我们把一个左递归的文法转化成了一个没有左递归的文法。

然后，我们可以轻易的写出这个文法的代码：

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
protected function additiveUnRecursiveMode()
{
    /** @var AstNode */
    $child1 = $this->scanner->primary();
    $node = $child1;

    while (true) {
        $token = $this->scanner->peekToken();
        if ($token == null) {
            // 没有token了，所以我们需要终止循环
            break;
        }
        if ($token != Token::ADD) {
            throw new TokenException(sprintf('Token [%s] that are not expected, need a [%s].', $token, Token::ADD), Errno::UN_EXPECTED_TOKEN);
        }
        $this->scanner->readToken();
        $child2 = $this->scanner->primary();
        $node = new AstNode(AstNodeType::ADD_NODE, '+');
        $node->addChildNode($child1);
        $node->addChildNode($child2);
        /**
         * 因为我们希望这棵AST是左结合的，所以，我们把生成的子树作为父节点的左子树
         */
        $child1 = $node;
    }

    // 此处的node是AST的根结点
    return $node;
}