Hacer que la salida YACC sea un AST (árbol de tokens)

Question

¿Es posible hacer que YACC (o mi caso MPPG) genere un Árbol de sintaxis abstracta (AST)?

Todo lo que estoy leyendo sugiere que es muy fácil hacer que YACC haga esto, pero estoy luchando por saber cómo saber cuándo mover un nodo en el árbol mientras lo construye.

Answer 1

¿Ha mirado the manual (busque "árbol de análisis sintáctico" para encontrar el lugar)? Sugiere poner la creación de nodos en una acción con sus descendientes izquierdo y derecho de $ 1 y $ 3, o lo que sea que sean. En este caso, yacc se movería por el árbol en su nombre en lugar de hacerlo manualmente.

Answer 2

Ampliando el punto de Hao y desde the manual, que desea hacer algo como lo siguiente:

Asumiendo que tiene su árbol de sintaxis abstracta con la función node que crea un objeto en el árbol:

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

Este código se traduce en "Al analizar expresiones con un signo más, tome los descendientes izquierdo y derecho $1/$3 y utilícelos como argumentos para el nodo. Guarde el resultado en $$ (el valor de retorno) de la expresión.

$$ (del manual):

para devolver un valor, la acción normalmente establece el pseudovariable `` $$ '' a algún valor .

Answer 3

Las otras respuestas proponen modificar la gramática, esto no es factible cuando se juega con una gramática de C++ (varios cientos de reglas ..)

Afortunadamente, podemos hacerlo de forma automática, mediante la redefinición de la depuración macros. En este código, estamos redefiniendo YY_SYMBOL_PRINT actived con 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] = ' '; 
    } 
} 

las hojas se crean justo antes del regreso en el léxico FLEX