Rendere YACC in uscita un AST (token tree)

Question

E 'possibile fare in modo che YACC (o I'm my case MPPG) emetta un Abstract Syntax Tree (AST).

Tutte le cose che sto leggendo suggeriscono che è semplice far fare a YACC, ma sto facendo fatica a vedere come sai quando spostarti su un nodo nell'albero mentre lo stai costruendo.

Answer 1

Hai guardato the manual (cercare "albero di parse" per trovare il punto)? Suggerisce di mettere la creazione del nodo in un'azione con i discendenti di sinistra e destra di $ 1 e $ 3, o qualunque cosa essi siano. In questo caso, yacc sposterebbe l'albero per tuo conto anziché eseguirlo manualmente.

Answer 2

Ampliando punto di Hao e da the manual, si vuole fare qualcosa di simile al seguente:

Supponendo di avere il vostro albero di sintassi astratta con funzione di node che crea un oggetto nella struttura:

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

Questo codice si traduce in "Quando si analizza l'espressione con un plus, si prendono i discendenti di sinistra e destra $1/$3 e li si usano come argomenti per il nodo." Salvare l'output in $$ (il valore restituito) dell'espressione

$$ (dal manuale):

per restituire un valore, l'azione normalmente imposta la pseudovariable `` $$ '' a un valore .

Answer 3

Le altre risposte propongono di modificare la grammatica, questo non è fattibile quando si gioca con una grammatica C++ (diverse centinaia di regole ..)

Per fortuna, siamo in grado di farlo automaticamente, ridefinendo il debug di macro. In questo codice, stiamo ridefinendo 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] = ' '; 
    } 
} 

le foglie vengono creati appena prima del ritorno nel lexer FLEX