乐趣区

关于后端:PHP7内核实现原理词法和语法分析

词法剖析应用正则表达式辨认出 Token,语法分析应用 BNF 范式辨认出 Token 间的档次组合关系。

词法剖析

词法剖析次要目标是从源代码中辨认出一个个的 Token,个别应用正则表达式来辨认 Token

LNUM    [0-9]+
DNUM    ([0-9]*"."[0-9]+)|([0-9]+"."[0-9]*)
EXPONENT_DNUM    (({LNUM}|{DNUM})[eE][+-]?{LNUM})
HNUM    "0x"[0-9a-fA-F]+
BNUM    "0b"[01]+
LABEL    [a-zA-Z_\x80-\xff][a-zA-Z0-9_\x80-\xff]*
WHITESPACE [\n\r\t]+
TABS_AND_SPACES [\t]*
TOKENS [;:,.\[\]()|^&+-/*=%!~$<>?@]
ANY_CHAR [^]
NEWLINE ("\r"|"\n"|"\r\n")

有了正则表达式,接下来就是根据正则来一个个字符匹配验证,可应用 NFA 和 DFA 来辨认一段文本是否满足正则表达式,如对于正则 (a|b)*abb 举例:

NFA 不确定有穷自动机

因为在 0 地位,接到 a 有可能向 1 走,也有可能循环,走到哪是不确定的。

DFA 确定有穷自动机

在之前根底上做了改良,演进方向确定了。

将正则转换为有穷自动机比较复杂,然而又有法则可循,可由工具代替,如 re2c

re2c

re2c 能够解析正则,生成 C 语言实现的 DFA。相似的词法分析器还有 Lex(Lexical Analyzar),与 re2c 相似,也是通过正则生成 C 语言 DFA 代码,C 语言解析正则个别应用 regex.h 库。

如下代码中,char *scan 中定义了一系列正则,针对输出的内容做类型判断,保留为 a.l 文件

#include <stdio.h>

char *scan(char *p){
#define YYCTYPE char
#define YYCURSOR p
#define YYLIMIT p
#define YYMARKER q
#define YYFILL(n)
    /*!re2c
      [0-9]+ {return "number";}
      [a-z]+ {return "lower";}
      [A-Z]+ {return "upper";}
      [^] {return "unkown";}
     */
}

int main(int argc, char* argv[])
{printf("%s\n", scan(argv[1]));

    return 0;
}

应用 re2c a.l -o a.c -i 解析正则生成 C 语言的 DFA:

/* Generated by re2c 2.0.3 on Tue Jun  8 16:57:11 2021 */
#include <stdio.h>

char *scan(char *p){
#define YYCTYPE char
#define YYCURSOR p
#define YYLIMIT p
#define YYMARKER q
#define YYFILL(n)

{
    YYCTYPE yych;
    if (YYLIMIT <= YYCURSOR) YYFILL(1);
    yych = *YYCURSOR;
    switch (yych) {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':    goto yy4;
    case 'A':
    case 'B':
    case 'C':
    case 'D':
    case 'E':
    case 'F':
    case 'G':
    case 'H':
    case 'I':
    case 'J':
    case 'K':
    case 'L':
    case 'M':
    case 'N':
    case 'O':
    case 'P':
    case 'Q':
    case 'R':
    case 'S':
    case 'T':
    case 'U':
    case 'V':
    case 'W':
    case 'X':
    case 'Y':
    case 'Z':    goto yy7;
    case 'a':
    case 'b':
    case 'c':
    case 'd':
    case 'e':
    case 'f':
    case 'g':
    case 'h':
    case 'i':
    case 'j':
    case 'k':
    case 'l':
    case 'm':
    case 'n':
    case 'o':
    case 'p':
    case 'q':
    case 'r':
    case 's':
    case 't':
    case 'u':
    case 'v':
    case 'w':
    case 'x':
    case 'y':
    case 'z':    goto yy10;
    default:    goto yy2;
    }
yy2:
    ++YYCURSOR;
    {return "unkown";}
yy4:
    ++YYCURSOR;
    if (YYLIMIT <= YYCURSOR) YYFILL(1);
    yych = *YYCURSOR;
    switch (yych) {
    case '0':
    case '1':
    case '2':
    case '3':
    case '4':
    case '5':
    case '6':
    case '7':
    case '8':
    case '9':    goto yy4;
    default:    goto yy6;
    }
yy6:
    {return "number";}
yy7:
    ++YYCURSOR;
    if (YYLIMIT <= YYCURSOR) YYFILL(1);
    yych = *YYCURSOR;
    switch (yych) {
    case 'A':
    case 'B':
    case 'C':
    case 'D':
    case 'E':
    case 'F':
    case 'G':
    case 'H':
    case 'I':
    case 'J':
    case 'K':
    case 'L':
    case 'M':
    case 'N':
    case 'O':
    case 'P':
    case 'Q':
    case 'R':
    case 'S':
    case 'T':
    case 'U':
    case 'V':
    case 'W':
    case 'X':
    case 'Y':
    case 'Z':    goto yy7;
    default:    goto yy9;
    }
yy9:
    {return "upper";}
yy10:
    ++YYCURSOR;
    if (YYLIMIT <= YYCURSOR) YYFILL(1);
    yych = *YYCURSOR;
    switch (yych) {
    case 'a':
    case 'b':
    case 'c':
    case 'd':
    case 'e':
    case 'f':
    case 'g':
    case 'h':
    case 'i':
    case 'j':
    case 'k':
    case 'l':
    case 'm':
    case 'n':
    case 'o':
    case 'p':
    case 'q':
    case 'r':
    case 's':
    case 't':
    case 'u':
    case 'v':
    case 'w':
    case 'x':
    case 'y':
    case 'z':    goto yy10;
    default:    goto yy12;
    }
yy12:
    {return "lower";}
}

}

int main(int argc, char* argv[])
{printf("%s\n", scan(argv[1]));

    return 0;
}

可见其解决逻辑是依据输出的字符做 switch case 判断,解决完一个字符,作为以后字符指针的 YYCURSOR+1,持续判断下一个字符,配合 goto 语法,流转到下一种状态。

测试的输入:

 测试数字
> ./a 1
number

测试小写字母
> ./a x
lower

测试大写字母
> ./a Z
upper

语法分析

语法分析目标是对源代码进行档次剖析,将源程序分组分层,用语法树来示意,如代码 a = b + c * 2 通过语法分析后失去的后果:

如何更标准的表白语法,能够应用 BNF 范式即巴科斯范式。

巴科斯范式

巴科斯范式(BNF 范式)应用递归思维表白语法标准,目标是对语法的进行形象形容。看起来很像伪代码,如果满足标准后,可执行一个 action,action 放在 {} 里。

expr: expr PLUS term {语义动作}
| term {语义动作}
;

可应用 bisn 做语法解析:巴科斯范式的逆波兰记号计算器的例子:

%{
#define YYSTYPE double
#include <stdio.h>
#include <math.h>
#include <ctype.h>
int yylex (void);
void yyerror (char const *);
%}

%token NUM

%%
input:    /* empty */
     | input line
    ;

line:     '\n'
    | exp '\n'      {printf ("\t%.10g\n", $1); }
;

exp:      NUM           {$$ = $1;}
   | exp exp '+'   {$$ = $1 + $2;}
    | exp exp '-'   {$$ = $1 - $2;}
    | exp exp '*'   {$$ = $1 * $2;}
    | exp exp '/'   {$$ = $1 / $2;}
     /* Exponentiation */
    | exp exp '^'   {$$ = pow($1, $2); }
    /* Unary minus    */
    | exp 'n'       {$$ = -$1;}
;
%%

#include <ctype.h>

int yylex (void) {
       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-input.  */
       if (c == EOF) return 0;

       /* Return a single char.  */
       return c;
}

void yyerror (char const *s) {fprintf (stderr, "%s\n", s);
}

int main (void) {return yyparse ();
}

PHP 中的词法语法实现

词法剖析的 Token 正则规定在 Zend/zend_language_scanner.l 中定义

语法分析的 BNF 范式在 Zend/zend_language_parser.y 中定义

能够应用 token_get_all 函数来获取一段 PHP 代码的 Token,如:

<?php
$lan = '<?php $a = 1; echo $a;';

$tokens = token_get_all($lan);
foreach ($tokens as $token) {if (is_array($token)) {echo "Line" . $token[2] . ":" . token_name($token[0]) . " " .  $token[1] . PHP_EOL;
    }
}

输入的 Tokens 为:

Line1 : T_OPEN_TAG <?php
Line1 : T_VARIABLE $a
Line1 : T_WHITESPACE
Line1 : T_WHITESPACE
Line1 : T_LNUMBER 1
Line1 : T_WHITESPACE
Line1 : T_ECHO echo
Line1 : T_WHITESPACE
Line1 : T_VARIABLE $a

可参考:https://www.cnblogs.com/yanlingyin/archive/2012/04/17/2451717… 比照增强认知。

其中如针对 $a = 1; 这段代码,通过 re2c 和 bison 的词法语法分析后,失去的 AST 构造大抵如下:

PHP 5 中没有 AST,词法语法分析后,间接失去 op_array 交给虚拟机执行。PHP 7 中减少了 AST。

整体的过程图示:

zendparse() 就是词法语法分析,之后生成 AST。

compile_file() 中的 yyparse 函数一直调用 yylex 来获取 token,之后退出到 AST 中

Zend 虚拟机编译执行 AST

即词法语法解析生成 AST,并交给编译器生成 op_array 和符号表与指令集,最初交给执行引擎执行 opcode。

参考:

PHP 的词法解析器 re2c:http://www.phppan.com/2011/09/php-lexical-re2c/

re2c User manual:https://re2c.org/manual/manual_c.html

本文由 mdnice 多平台公布

退出移动版