解释型语言也需要编译吗？

词法分析（正则表达式分割 找出token）

词法分析入门-NFA(不确定有穷自动机)

0, 1, 2 状态机中间状态(一个圈)
3 状态机最终状态(两个圈)

箭头和字母表示： 每个状态遇到不同的输入迁移到另一个状态

致命缺陷：状态0为不确定状态 可能会一直停在状态0
例如: abb 其实是满足正则表达式的 由于状态0处是不确定的 可能会出现如下情况
0 遇到a 迁移到0 -> 0遇到b 迁移到0 -> 0遇到b 迁移到0 导致一直停留在0状态

词法分析入门-DFA(确定有穷自动机)

对于PHP语言来说 要切分开所有token 可以想像需要大量正则表达式 而且正则表达式比较复杂
我们需要手动去编写DFA吗？
不需要, 有些工具比较完善的帮我们解决了这些事情 ： re2c

使用re2c做词法分析

安装re2c
官网 re2c.org

1
2
3
4
5
6
7
8
9
wget https://github.com/skvadrik/re2c/releases/download/1.1.1/re2c-1.1.1.tar.gz

tar -zxvf re2c-1.1.1.tar.gz

cd re2c-1.1.1

./configure

make && make install

实例：识别输入数字进制

编写文件 integer.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
32
33
#include <stdio.h>
enum num_t { ERR, BIN, OCT, DEC, HEX };
static num_t lex(const char *YYCURSOR)
{
    const char *YYMARKER;
    /*!re2c
        re2c:define:YYCTYPE = char;
        re2c:yyfill:enable = 0;
        end = "\x00";
        bin = '0b'[01]+;
        oct = "0"[0-7]*;
        dec = [1-9][0-9]*;
        hex = '0x'[0-9a-fA-F]+;
        *       { return ERR; }
        bin end { return BIN; }
        oct end { return OCT; }
        dec end { return DEC; }
        hex end { return HEX; }
    */
}
int main(int argc, char ** argv)
{
    for (int i = 1; i < argc; ++i) {
        switch (lex(argv[i])) {
            case ERR: printf("error\n"); break;
            case BIN: printf("binary\n"); break;
            case OCT: printf("octal\n"); break;
            case DEC: printf("decimal\n"); break;
            case HEX: printf("hexadecimal\n"); break;
        }
    }
    return 0;
}

转化为 .c 文件

1
[root@yyl RE2C]# re2c integer.l -o integer.c

编译为可执行文件：

1
[root@yyl RE2C]# g++ integer.c -o integer

测试结果:

1
2
3
4
5
6
7
8
9
10
11
[root@yyl RE2C]# ./integer 0b10
binary
[root@yyl RE2C]# ./integer 1024
decimal
[root@yyl RE2C]# ./integer 0x100a
hexadecimal
[root@yyl RE2C]# ./integer 07
octal
[root@yyl RE2C]# ./integer abc
error
[root@yyl RE2C]#

语法分析

a = b + c * 2

巴科斯范式

使用bison做语法分析

官网：http://ftp.gnu.org/gnu/bison/

下载安装

1
2
3
4
5
6
7
wget http://ftp.gnu.org/gnu/bison/bison-3.4.tar.gz

tar -zxvf bison-3.4.tar.gz

cd bison-3.4.tar.gz

./configure

./configure 途中出现报错信息：checking for GNU M4 that supports accurate traces... configure: error: no acceptable m4 could be found in $PATH.

yum install -y m4 安装m4 问题解决。

继续：

1
2
3
./configure

make && make install

安装完毕！

实战 ： 计算器

编写文件 calc.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
%{
#include <math.h>
#include <ctype.h>
#include <stdio.h>
%}
/* BISON Declarations */
%token NUM
%left '-' '+'
%left '*' '/'
%left NEG     /* negation--unary minus */
%right '^'    /* exponentiation        */
/* Grammar follows */
%%
input:     /*  empty string */
                | input line
;
line:      '\n'
            | exp  '\n'   { printf ("\t%.10g\n", $1); }
;
exp:       NUM                { $$ = $1;           }
        | exp '+' exp         { $$ = $1 + $3;      }
        | exp '-' exp         { $$ = $1 - $3;      }
        | exp '*' exp         { $$ = $1 * $3;      }
        | exp '/' exp         { $$ = $1 / $3;      }
        | '-' exp  %prec NEG  { $$ = -$2;          }
        | exp '^' exp         { $$ = pow ($1, $3); }
        | '(' exp ')'         { $$ = $2;           }
;
%%
yylex ()
{
    int c;
    /* skip white space */
    while ((c = getchar ()) == ' ' || c == '\t')
        ;
    /* process numbers  */
    if (c== '.' || isdigit (c))
    {
        ungetc (c, stdin);
        scanf ("%lf", &yylval);
        return NUM;
    }
    /* return end-of-file */
    if (c == EOF)
        return 0;
    /* return single chars */
    return c;
}
yyerror (s) /* Called by yyparse on error */
    char *s;
{
    printf("%s\n", s);
}
main ()
{
    yyparse ();
}

转换为 .c 文件：

1
[root@yyl BASION]# bison -d calc.y -o calc.c

编译为可执行文件：

1
[root@yyl BASION]# gcc -lm calc.c -o calc

php7中的词法分析和语法分析

Zend/zend_language_scanner.l
Zend/zens_language_parser.y

AST 相关数据结构

_zend_ast
_zend_ast_list
_zend_ast_zval
_zend_ast_decl

zendParse->zendlex->switch(yyn)

生成的AST

$a = 1 AST 语法树

Opcode相关的数据结构

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
struct _zend_op {
	const void *handler;
	znode_op op1;
	znode_op op2;
	znode_op result;
    ...
	zend_uchar opcode;
	zend_uchar op1_type;
	zend_uchar op2_type;
	zend_uchar result_type;
};


struct _zend_op_array{
    ...
    uint32_t last;
	zend_op *opcodes;

	int last_var;
	uint32_t T;
	zend_string **vars;
    ...
}

struct _zend_execute_data {
    const zend_op       *opline;           /* executed opline                */
	zend_execute_data   *call;             /* current call                   */
	...
	zend_array          *symbol_table;
    ...
}
`
struct _zend_vm_stack {
	zval *top;
	zval *end;
	zend_vm_stack prev;
};

zend虚拟机基础