PHP, Bison 및 re2c로 구문 분석

PHP 엔진은 Bison 및 re2c를 사용하여 코드를 AST로 구문 분석합니다.
이러한 도구PHP를 사용하거나 사용하지 않고 구조화된 텍스트를 구문 분석하는 방법을 보여 드리겠습니다.

re2c은 오픈 소스 어휘 분석기 생성기입니다. 정규식을 사용하여 토큰을 인식합니다.

간단한 렉서 예제:

렉서.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("%s\n", lex(argv[1]));

    return 0;
}

Lexer는 정규식을 사용하여 stdin를 읽고 결정하고token 인쇄합니다token.
re2c는 /*!re2c ... */ 블록을 실제 코드로 대체합니다.

re2c lexer.l > lexer.c

이후의 Lexer 코드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("%s\n", 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 ("%.10g\n", $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, "%s\n", s);
}

int main()
{
    return yyparse();
}

주요 파서 기능은 yyparse 입니다. Bison에서 직접 생성합니다.
파서는 다음 토큰이 필요할 때마다 yylex 함수를 호출합니다.yylex 함수는 단어를 읽고, 단어의 token를 인식하고, 단어를 yyval에 저장하고 token를 반환합니다.
yyval 번호를 저장하기 위해 double 유형을 변경했습니다.

%define api.value.type {double}

들소 문법 말한다:

숫자와 기호로 텍스트를 구문 분석합니다(예: 1 + 2 - 3 ).

계산;

결과를 인쇄합니다.

input:
  %empty
| expr '\n'  { printf ("%.10g\n", $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 유형이 필요하고 AST에는 parser_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, "%s\n", 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 와 함께 사용하고 싶습니다.shared 라이브러리를 컴파일해야 합니다.

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%s\n",
        (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에 소스 코드를 게시했습니다.

그것이 당신에게 유용하기를 바랍니다!