Как движок PHP строит AST

Сначала давайте посмотрим на поток кода PHP:

До седьмой версии PHP генерировал OPcodes прямо внутри парсера. В PHP 7 появилась новая абстракция кода — AST.
Теперь мы можем разделить парсинг и компиляцию.

В этом посте я хочу поговорить о части Lexer + Parser.

PHP использует re2c для создания лексера и Bison для создания парсера. Если вы не знаете об этих инструментах, я рекомендую прочитать этот пост.

Давайте начнем с лексера.
Основная функция лексера — разбор кода на лексемы.

Модуль PHP 8 tokenizer предоставляет нам класс PhpToken для разбора кода на лексемы.
Это очень похоже на внутренний лексер PHP.

Давайте напишем lexer.php и используем его для разбора файла test.php.

lexer.php

<?php

$code = file_get_contents($argv[1]);

$tokens = PhpToken::tokenize($code);

foreach ($tokens as $token) {
    echo $token->getTokenName() . " ";
}
Вход в полноэкранный режим Выход из полноэкранного режима

test.php

<?php

$a = 1;

echo $a;
Войти в полноэкранный режим Выход из полноэкранного режима

Вывод lexer.php:

php lexer.php test.php
T_OPEN_TAG 
T_WHITESPACE 
T_VARIABLE T_WHITESPACE = T_WHITESPACE T_LNUMBER ; 
T_WHITESPACE 
T_ECHO T_WHITESPACE T_VARIABLE ;
Вход в полноэкранный режим Выход из полноэкранного режима

Я поместил содержимое test.php и вывод lexer.php в одно и то же место для лучшего сравнения:

<?php    |   T_OPEN_TAG
         |   T_WHITESPACE
$a = 1;  |   T_VARIABLE T_WHITESPACE = T_WHITESPACE T_LNUMBER ;
         |   T_WHITESPACE
echo $a; |   T_ECHO T_WHITESPACE T_VARIABLE ;
Вход в полноэкранный режим Выход из полноэкранного режима

Как лексер PHP разбирает код на лексемы?

re2c — это генератор лексера с открытым исходным кодом. Он использует регулярные выражения для распознавания лексем.

Код лексера PHP находится в файле zend_language_scanner.l
Основная функция, которая распознает код и возвращает токен — lex_scan:
zend_language_scanner.l

int ZEND_FASTCALL lex_scan(zval *zendlval, zend_parser_stack_elem *elem)
{

...

/*!re2c
re2c:yyfill:check = 0;
LNUM    [0-9]+(_[0-9]+)*
DNUM    ({LNUM}?"."{LNUM})|({LNUM}"."{LNUM}?)
EXPONENT_DNUM   (({LNUM}|{DNUM})[eE][+-]?{LNUM})
HNUM    "0x"[0-9a-fA-F]+(_[0-9a-fA-F]+)*
BNUM    "0b"[01]+(_[01]+)*
ONUM    "0o"[0-7]+(_[0-7]+)*

...

<ST_IN_SCRIPTING>"exit" {
    RETURN_TOKEN_WITH_IDENT(T_EXIT);
}

<ST_IN_SCRIPTING>"const" {
    RETURN_TOKEN_WITH_IDENT(T_CONST);
}

<ST_IN_SCRIPTING>"return" {
    RETURN_TOKEN_WITH_IDENT(T_RETURN);
}

...

*/
Вход в полноэкранный режим Выход из полноэкранного режима

После lexer у нас есть токены, но нам нужен parser, чтобы собрать AST.

Bison — это генератор контекстно-свободного синтаксического анализатора с открытым исходным кодом.
Он может генерировать синтаксический анализатор из БНФ.

Пример Bison BNF:

line:
  %empty
|  expr { printf("%d", $1); }
;

expr:
    TOK_NUMBER    { $$ = $1; }
|   expr '+' expr { $$ = $1 + $3; }
|   expr '-' expr { $$ = $1 - $3; }
;
Войти в полноэкранный режим Выход из полноэкранного режима

Код парсера находится в файле zend_language_parser.y.

Например, эта часть анализирует атрибуты PHP (#[Attribute])
zend_language_parser.y

attribute_decl:
        class_name
            { $$ = zend_ast_create(ZEND_AST_ATTRIBUTE, $1, NULL); }
    |   class_name argument_list
            { $$ = zend_ast_create(ZEND_AST_ATTRIBUTE, $1, $2); }
;
Вход в полноэкранный режим Выйти из полноэкранного режима

Когда парсер находит PHP-атрибут, он вызывает функцию zend_ast_create.
zend_ast.c

ZEND_API zend_ast *zend_ast_create(zend_ast_kind kind, ...)
Вход в полноэкранный режим Выход из полноэкранного режима

zend_ast_create — это одна из нескольких функций, которые помогают создать узел AST.

PHP представляет узел AST как структуру _zend_ast для простых узлов, и несколько более сложных структур для других узлов.
zend_ast.h

struct _zend_ast {
    zend_ast_kind kind; /* Type of the node (ZEND_AST_* enum constant) */
    zend_ast_attr attr; /* Additional attribute, use depending on node type */
    uint32_t lineno;    /* Line number */
    zend_ast *child[1]; /* Array of children (using struct hack) */
};
Вход в полноэкранный режим Выход из полноэкранного режима

Основной функцией парсера является yyparse. Вам не нужно ее писать — Bison сгенерирует ее сам;
Каждый раз, когда yyparse нужно получить следующий токен, она вызывает функцию лексера yylex.
У нас уже есть функция лексера lex_scan.

Как парсер и лексер работают вместе?

У Bison есть параметр api.prefix:

zend_language_parser.y

%define api.prefix {zend}
Войти в полноэкранный режим Выйти из полноэкранного режима

Это означает, что все префиксы функций будут zend вместо yy:

У нас есть функция zendlex в
zend_compile.c

int ZEND_FASTCALL zendlex(zend_parser_stack_elem *elem)
Вход в полноэкранный режим Выход из полноэкранного режима

она вызывает уже известную функцию lex_scan из zend_language_scanner.l

А zendparse вызывается в функции zend_compile_string_to_ast.
zend_language_scanner.l

ZEND_API zend_ast *zend_compile_string_to_ast(zend_string *code, zend_arena **ast_arena, zend_string *filename)
Вход в полноэкранный режим Выход из полноэкранного режима

В финале мы имеем цепочку вызовов:

zend_compile_string_to_ast() -> zendparse() -> zendlex() -> lex_scan()
Вход в полноэкранный режим Выход из полноэкранного режима

Теперь мы можем вызвать функцию zend_compile_string_to_ast и получить настоящий PHP AST.
Я написал функцию get_ast, чтобы получить AST из zend_compile_string_to_ast, разобрать его и сохранить в простой структуре _node_ast, чтобы мы могли легко экспортировать его в PHP с помощью FFI.
mrsuh/ast.c

node_ast *get_ast(char *input)
Вход в полноэкранный режим Выход из полноэкранного режима

mrsuh/ast.h

struct _node_ast {
    const char *kind;
    const char *attr;
    const char *value;
    int lineno;
    int children;
    node_ast *child[100];
};
Вход в полноэкранный режим Выход из полноэкранного режима

После компиляции я включил его в PHP
mrsuh/Parser.php

<?php

self::$libc = FFI::cdef(
"
typedef struct _node_ast node_ast;

struct _node_ast {
    const char *kind;
    const char *attr;
    const char *value;
    int lineno;
    int children;
    node_ast *child[100];
};

node_ast *get_ast(char *input);
",
__DIR__ . "ast_linux.so");
Вход в полноэкранный режим Выйти из полноэкранного режима

и перевел структуру C в класс PHP Node.
mrsuh/Node.php

<?php

namespace MrsuhPhpAst;

final class Node
{
    public string $kind   = "";
    public string $value  = "";
    public int    $lineno = 0;
    /** @var Node[] */
    public array $children = [];
}
Вход в полноэкранный режим Выход из полноэкранного режима

Давайте разберем некоторый код в AST:

mrsuh/parse.php

<?php

require __DIR__. '/vendor/autoload.php';

use MrsuhPhpAstParser;
use MrsuhPhpAstPrinter;

$code = <<<'CODE'
<?php

namespace App;

class Test
{
    public function test($foo)
    {
        var_dump($foo);
    }
}
CODE;

$node = Parser::parse($code);
Printer::print($node);
Вход в полноэкранный режим Выход из полноэкранного режима

mrsuh/parse.php выход:

php parse.php
[001] ZEND_AST_STMT_LIST
[003]   ZEND_AST_NAMESPACE
[003]     ZEND_AST_ZVAL "App"
[005]   ZEND_AST_CLASS "Test"
[006]     ZEND_AST_STMT_LIST
[007]       ZEND_AST_METHOD "test"
[007]         ZEND_AST_PARAM_LIST
[007]           ZEND_AST_PARAM
[007]             ZEND_AST_ZVAL "foo"
[008]         ZEND_AST_STMT_LIST
[009]           ZEND_AST_CALL
[009]             ZEND_AST_ZVAL "var_dump"
[009]             ZEND_AST_ARG_LIST
[009]               ZEND_AST_VAR
[009]                 ZEND_AST_ZVAL "foo"
Вход в полноэкранный режим Выход из полноэкранного режима

Полный код парсера находится здесь.

Никита Попов уже имеет парсер php-ast, который использует функцию zend_compile_string_to_ast и php-parser, который использует модуль PHP tokenizer в качестве лексера и PHP версию YACC в качестве генератора парсера.

Ниже я показал результаты работы трех библиотек для этого кода:

<?php

$a = 1;

echo $a;
Вход в полноэкранный режим Выход из полноэкранного режима

mrsuh/php-ast

[001] ZEND_AST_STMT_LIST
[003]   ZEND_AST_ASSIGN
[003]     ZEND_AST_VAR
[003]       ZEND_AST_ZVAL "a"
[003]     ZEND_AST_ZVAL "1"
[005]   ZEND_AST_STMT_LIST
[005]     ZEND_AST_ECHO
[005]       ZEND_AST_VAR
[005]         ZEND_AST_ZVAL "a"
Вход в полноэкранный режим Выход из полноэкранного режима

nikic/php-ast

AST_STMT_LIST
    0: AST_ASSIGN
        var: AST_VAR
            name: "a"
        expr: 1
    1: AST_ECHO
        expr: AST_VAR
            name: "a"
Войти в полноэкранный режим Выйти из полноэкранного режима

nikic/PHP-Parser

array(
    0: Stmt_Expression(
        expr: Expr_Assign(
            var: Expr_Variable(
                name: a
            )
            expr: Scalar_LNumber(
                value: 1
            )
        )
    )
    1: Stmt_Echo(
        exprs: array(
            0: Expr_Variable(
                name: a
            )
        )
    )
)
Войти в полноэкранный режим Выйти из полноэкранного режима

Как по мне, все выглядит очень похоже.

Есть дополнительные ресурсы, если вы хотите узнать больше:

  • https://www.codeproject.com/Articles/1035799/Generating-a-High-Speed-Parser-Part-re-c
  • https://www.cs.montana.edu/techreports/1011/Wickland.pdf
  • https://www.youtube.com/watch?v=Z7uLTS55Ifo

Оцените статью
devanswers.ru
Добавить комментарий