Làm cho đầu ra YACC là một AST (cây mã thông báo)

Question

Có thể làm cho YACC (hoặc là trường hợp MPPG của tôi) xuất ra một cây cú pháp trừu tượng (AST).

Tất cả những gì tôi đọc cho thấy nó đơn giản để làm cho YACC làm điều này, nhưng tôi đang đấu tranh để xem làm thế nào bạn biết khi nào để di chuyển lên một nút trong cây như xây dựng nó.

Answer 1

Bạn đã xem số the manual (tìm kiếm "phân tích cây" để tìm vị trí)? Nó cho thấy việc tạo nút trong một hành động với hậu duệ trái và phải của bạn là $ 1 và $ 3, hoặc bất cứ thứ gì có thể. Trong trường hợp này, yacc sẽ di chuyển lên cây thay cho bạn thay vì làm theo cách thủ công.

Answer 2

Mở rộng trên điểm Hao và từ the manual, bạn muốn làm một cái gì đó như sau:

Giả sử bạn có cây cú pháp trừu tượng của bạn với chức năng node mà tạo ra một đối tượng trong cây:

expr : expr '+' expr 
    { 
    $$ = node('+', $1, $3); 
    } 

Mã này dịch thành "Khi phân tích cú pháp biểu thức bằng dấu cộng, hãy lấy hậu duệ bên trái và bên phải $1/$3 và sử dụng chúng làm đối số cho nút. Lưu đầu ra thành $$ (giá trị trả về) của biểu thức.

$$ (từ thủ công):

Để trả về một giá trị, các hành động thường đặt pseudovariable '' $$ '' đối với một số giá trị .

Answer 3

Những câu trả lời khác đề nghị sửa đổi các văn phạm, điều này không thể thực hiện được khi chơi với C++ ngữ pháp (vài trăm quy tắc ..)

May mắn thay, chúng ta có thể làm điều đó tự động, bằng cách xác định lại debug macro. Trong mã này, chúng tôi đang đánh giá lại YY_SYMBOL_PRINT actived với YYDEBUG:

%{ 

typedef struct tree_t { 
    struct tree_t **links; 
    int nb_links; 
    char* type; // the grammar rule 
}; 

#define YYDEBUG 1 
//int yydebug = 1; 

tree_t *_C_treeRoot; 
%} 
%union tree_t 

%start program 

%token IDENTIFIER 
%token CONSTANT 

%left '+' '-' 
%left '*' '/' 
%right '^' 

%% 
progam: exprs { _C_treeRoot = &$1.t; } 
    | 
    | hack 
    ; 

exprs: 
    expr ';' 
    | exprs expr ';' 
    ; 


number: 
    IDENTIFIER 
    | '-' IDENTIFIER 
    | CONSTANT 
    | '-' CONSTANT 
    ; 

expr: 
    number 
    | '(' expr ')' 
    | expr '+' expr 
    | expr '-' expr 
    | expr '*' expr 
    | expr '/' expr 
    | expr '^' expr 
    ; 

hack: 
    { 
    // called at each reduction in YYDEBUG mode 
    #undef YY_SYMBOL_PRINT 
    #define YY_SYMBOL_PRINT(A,B,C,D) \ 
     do { \ 
      int n = yyr2[yyn]; \ 
      int i; \ 
      yyval.t.nb_links = n; \ 
      yyval.t.links = malloc(sizeof *yyval.t.links * yyval.t.nb_links);\ 
      yyval.t.str = NULL; \ 
      yyval.t.type = yytname[yyr1[yyn]]; \ 
      for (i = 0; i < n; i++) { \ 
       yyval.t.links[i] = malloc(sizeof (YYSTYPE)); \ 
       memcpy(yyval.t.links[i], &yyvsp[(i + 1) - n], sizeof(YYSTYPE)); \ 
      } \ 
     } while (0) 

    } 
    ; 
%% 

#include "lexer.c" 


int yyerror(char *s) { 
    printf("ERROR : %s [ligne %d]\n",s, num_ligne); 
    return 0; 
} 


int doParse(char *buffer) 
{ 
    mon_yybuffer = buffer; 
    tmp_buffer_ptr = buffer; 
    tree_t *_C_treeRoot = NULL; 
    num_ligne = 1; 
    mon_yyptr = 0; 

    int ret = !yyparse(); 

    /////////**** 
      here access and print the tree from _C_treeRoot 
    ***/////////// 
} 


char *tokenStrings[300] = {NULL}; 
char *charTokenStrings[512]; 

void initYaccTokenStrings() 
{ 
    int k; 
    for (k = 0; k < 256; k++) 
    { 
     charTokenStrings[2*k] = (char)k; 
     charTokenStrings[2*k+1] = 0; 
     tokenStrings[k] = &charTokenStrings[2*k]; 
    } 
    tokenStrings[CONSTANT] = "CONSTANT"; 
    tokenStrings[IDENTIFIER] = "IDENTIFIER"; 


    extern char space_string[256]; 

    for (k = 0; k < 256; k++) 
    { 
     space_string[k] = ' '; 
    } 
} 

các lá được tạo ra ngay trước khi RETURN trong lexer FLEX