Выполнение вывода YACC AST (дерево токенов)

Question

Возможно ли, что YACC (или я - мой случай MPPG) выводит абстрактное дерево синтаксиса (AST).

Все, что я читаю, предлагает сделать его простым, чтобы сделать YACC, но я изо всех сил пытаюсь понять, как вы знаете, когда нужно двигаться вверх по узлу в дереве, как ваше здание.

Answer 1

Вы просмотрели the manual (найдите «дерево разбора», чтобы найти место)? Это предполагает создание узла в действии с вашими левыми и правыми потомками, составляющими $ 1 и $ 3, или что бы они ни были. В этом случае yacc будет перемещаться по дереву от вашего имени, а не выполнять его вручную.

Answer 2

Расширяя точки Хао и от the manual, вы хотите сделать что-то вроде следующего:

Предполагая, что у вас есть абстрактное синтаксическое дерево с функцией node, который создает объект в дереве:

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

Этот код переводится как «При анализе выражения с плюсом, возьмите левого и правого потомков $1/$3 и используйте их в качестве аргументов для узла. Сохраните вывод в $$ (возвращаемое значение) выражения.

$$ (из инструкции):

Чтобы вернуть значение, действие обычно устанавливает Псевдопеременную `` $$ '' до некоторой значения.

Answer 3

Другие ответы предлагают изменить грамматику, это не выполнимо при воспроизведении с грамматики C++ (несколько сотен правил ..)

К счастью, мы можем сделать это автоматически, путем переопределения отладки макросы. В этом коде, мы пересматриваем YY_SYMBOL_PRINT Actived с 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] = ' '; 
    } 
} 

листики создаются непосредственно перед ВОЗВРАТ в лексером FLEX