Парсинг с помощью PHP, Bison и re2c

Движок PHP использует Bison и re2c для разбора кода в AST.
Я покажу вам, как мы можем использовать эти инструменты с PHP и без него для разбора любого структурированного текста.

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

Пример простого лексера:

lexer.l

#include <stdio.h>

const char *lex(const char *s)
{
    /*!re2c
        re2c:yyfill:enable = 0;
        re2c:define:YYCTYPE = char;
        re2c:define:YYCURSOR = s;

        [0-9]+ { return "TOK_NUMBER"; }
        *      { return "TOK_ANY"; }
    */

    return "";
}

int main(int argc, char *argv[])
{
    printf("%sn", lex(argv[1]));

    return 0;
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Лексер читает stdin, определяет token с помощью регулярного выражения и печатает token.

re2c заменяет блок /*!re2c ... */ блоком с реальным кодом:

re2c lexer.l > lexer.c
Вход в полноэкранный режим Выход из полноэкранного режима

Код лексера после re2c:
lexer.c

#line 1 "lexer.l"
#include <stdio.h>

const char *lex(const char *s)
{

#line 9 "<stdout>"
{
    char yych;
    yych = *s;
    switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': goto yy2;
        default: goto yy1;
    }
yy1:
    ++s;
#line 11 "lexer.l"
    { return "TOK_ANY"; }
#line 30 "<stdout>"
yy2:
    yych = *++s;
    switch (yych) {
        case '0':
        case '1':
        case '2':
        case '3':
        case '4':
        case '5':
        case '6':
        case '7':
        case '8':
        case '9': goto yy2;
        default: goto yy3;
    }
yy3:
#line 10 "lexer.l"
    { return "TOK_NUMBER"; }
#line 49 "<stdout>"
}
#line 12 "lexer.l"


    return "";
}

int main(int argc, char *argv[])
{
    printf("%sn", lex(argv[1]));

    return 0;
}
Вход в полноэкранный режим Выход из полноэкранного режима

Давайте скомпилируем и протестируем его:

gcc lexer.c -o lexer
Войти в полноэкранный режим Выход из полноэкранного режима
./lexer 123
TOK_NUMBER
Войти в полноэкранный режим Выход из полноэкранного режима
./lexer test
TOK_ANY
Войти в полноэкранный режим Выйти из полноэкранного режима

Неплохо. Теперь мы можем распознавать числа.

Следующая часть — это синтаксический анализ.

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

Простой пример Bison:

parser.y

%code top {
  #include <ctype.h>  /* isdigit. */
  #include <stdio.h>  /* printf. */

  int yylex();
  void yyerror(char const *);
}

%define api.header.include {"parser.h"}

%define api.value.type {double}
%token TOK_NUMBER
%type  expr

%left '-' '+'

%% /* The grammar follows. */
input:
  %empty
| expr 'n'  { printf ("%.10gn", $1); }
;

expr:
  TOK_NUMBER    { $$ = $1; }
| expr '+' expr { $$ = $1 + $3; }
| expr '-' expr { $$ = $1 - $3; }
;

%%

int yylex()
{
    int c;

    /* Ignore white space, get first nonwhite character.  */
    while ((c = getchar()) == ' ' || c == 't')
    {
        continue;
    }

    if (c == EOF)
    {
        return YYEOF;
    }

    /* Char starts a number => parse the number. */
    if (c == '.' || isdigit(c))
    {
        ungetc(c, stdin);
        if (scanf("%lf", &yylval) != 1)
        {
            return YYUNDEF;
        }

        return TOK_NUMBER;
    }

    return c;
}

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

int main()
{
    return yyparse();
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Основной функцией парсера является yyparse. Bison генерирует ее сам.
Каждый раз, когда парсеру нужен следующий токен, он вызывает функцию yylex.
Функция yylex читает слово, распознает token, сохраняет слово в yyval и возвращает token.

Мы изменили тип yyval для хранения числа double.

%define api.value.type {double}
Вход в полноэкранный режим Выход из полноэкранного режима

Грамматика Bison говорит:

  • разбирать текст с числами и знаками (например, 1 + 2 - 3);
  • посчитайте;
  • выведите результат.
input:
  %empty
| expr 'n'  { printf ("%.10gn", $1); }
;

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

Создайте синтаксический анализатор и скомпилируйте его:

bison --header -o parser.c parser.y
gcc parser.c -o parser
Войти в полноэкранный режим Выйти из полноэкранного режима
./parser
1 + 7
8
Войти в полноэкранный режим Выйти из полноэкранного режима

Работает!

Давайте объединим Bison и re2c для разбора простых математических выражений в AST.

Сначала нам понадобится структура узлов AST и функции для создания этой структуры:
ast.c

typedef struct parser_ast {
    const char* kind;
    const char* value;
    struct parser_ast* children[2];
} parser_ast;

parser_ast* create_ast(const char* kind, const char* value);

parser_ast* create_ast_operation(const char* kind, parser_ast* left, parser_ast* right);
Вход в полноэкранный режим Выйти из полноэкранного режима

Нам нужен тип char* для TOK_NUMBER и тип parser_ast* для AST.
Тип yyval стал структурой parser_t:
ast.c

typedef union parser_t {
    char* number;
    parser_ast* ast;
} parser_t;
Вход в полноэкранный режим Выйти из полноэкранного режима

Давайте перепишем parser.y с новым типом yyval и функциями AST:
parser.y

%require "3.8"

%code top {
  #include <stdio.h>  /* fprintf. */
  #include "ast.h"

  int yylex(char **content);
  void yyerror(char **content, char const *);
  parser_ast *ast = NULL;
}

%param {char **content}

%define api.header.include {"parser.h"}
%define api.value.type {parser_t}

%token <number> TOK_NUMBER
%type  <ast> expr

%left '-' '+'

%%

line:
  %empty
|  expr { ast = $1; }
;

expr:
    TOK_NUMBER    { $$ = create_ast("NUMBER", $1); }
|   expr '+' expr { $$ = create_ast_operation("OPERATION_PLUS", $1, $3); }
|   expr '-' expr { $$ = create_ast_operation("OPERATION_MINUS", $1, $3); }
;

%%

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

parser_ast* parse(char *content) {

    yyparse(&content);

    return ast;
}

int main(int argc, char *argv[])
{
    ast = parse(argv[1]);
    if (ast == NULL) {
       return 1;
    }

    dump_ast(ast, 0);

    return 0;
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Новая грамматика создает структуру parser_ast с функциями AST:
parser.y

expr:
    TOK_NUMBER    { $$ = create_ast("NUMBER", $1); }
|   expr '+' expr { $$ = create_ast_operation("OPERATION_PLUS", $1, $3); }
|   expr '-' expr { $$ = create_ast_operation("OPERATION_MINUS", $1, $3); }
Вход в полноэкранный режим Выход из полноэкранного режима

Перепишем функцию yylex с помощью re2c и нового типа yyval:
lexer.l

#include "ast.h"
#include "parser.h"
#include <stdio.h> // sprintf
#include <stdlib.h> // malloc

int yylex(char **content)
{
    for(;;) {
        char *last = *content;
        /*!re2c
            re2c:define:YYCTYPE  = char;
            re2c:define:YYCURSOR = *content;
            re2c:yyfill:enable   = 0;
            [+-]                { return *(*content-1); }
            [0-9]+                {
                                    int size = *content-last;
                                    yylval.number = (char *)malloc(size);
                                    sprintf(yylval.number, "%.*s", size, last);
                                    return TOK_NUMBER;
                                  }
            [ t]+                { continue; }
            [x00]                { return YYEOF; }
        */
    }

    return YYUNDEF;
}
Вход в полноэкранный режим Выйти из полноэкранного режима

Для дампа AST нам нужна функция помощи:
ast.c

void dump_ast(parser_ast* ast, int indent) {
    for(int i = 0; i < indent; i++) {
        printf(" ");
    }

    printf("%s", ast->kind);

    if(ast->value != "") {
        printf(" "%s"", ast->value);
    }
    printf("n");

    for(int i = 0; i < 2; i++) {
        if(ast->children[i] != NULL) {
            dump_ast(ast->children[i], indent + 2);
        }
    }
}
Войти в полноэкранный режим Выйти из полноэкранного режима

Теперь мы можем скомпилировать все файлы в один и протестировать его:

bison --header -o parser.c parser.y
re2c lexer.l > lexer.c
gcc ast.c lexer.c parser.c -o parser
Войти в полноэкранный режим Выйти из полноэкранного режима
./parser "10 - 20 + 30"
OPERATION_PLUS
  OPERATION_MINUS
    NUMBER "10"
    NUMBER "20"
  NUMBER "30"
Войти в полноэкранный режим Выйти из полноэкранного режима

Круто. Но я хочу использовать его с PHP.
Мне нужно скомпилировать общую библиотеку:

gcc -fPIC -shared -I . -o library_linux.so ast.c lexer.c parser.c
Вход в полноэкранный режим Выход из полноэкранного режима

Пришло время включить library_linux.so в PHP с помощью FFI:
parse.php

<?php

$libc = FFI::cdef('
typedef struct parser_ast {
    const char* kind;
    const char* value;
    struct parser_ast* children[2];
} parser_ast;
parser_ast* parse(char *content);
', __DIR__ . "/library_linux.so");

function dump($ast, int $indent = 0): void
{
    $node = $ast[0];
    printf("%s%s%sn",
        (str_repeat(' ', $indent)),
        $node->kind,
        $node->value ? sprintf(" "%s"", $node->value) : ''
    );
    for ($i = 0; $i < 2; $i++) {
        if ($node->children[$i] !== null) {
            dump($node->children[$i], $indent + 2);
        }
    }
}

$ast = $libc->parse($argv[1]);
dump($ast);
Вход в полноэкранный режим Выход из полноэкранного режима
php parse.php "10 - 20 + 30"
OPERATION_PLUS
  OPERATION_MINUS
    NUMBER "10"
    NUMBER "20"
  NUMBER "30"
Войти в полноэкранный режим Выйти из полноэкранного режима

И все снова работает!

Я разместил исходный код на GitHub.

Надеюсь, он будет полезен для вас!

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