Rendre une sortie YACC un AST (arborescence de jetons)

Question

Est-il possible de rendre YACC (ou je suis mon cas MPPG) en sortie un arbre de syntaxe abstraite (AST). Toutes les choses que je suis en train de lire suggèrent qu'il est simple de faire YACC, mais j'ai du mal à voir comment savoir quand remonter un nœud dans l'arbre en le construisant.

Answer 1

Avez-vous regardé the manual (cherchez "arbre d'analyse" pour trouver l'endroit)? Il suggère de mettre la création de noeuds dans une action avec vos descendants gauche et droit étant 1 $ et 3 $, ou quoi qu'ils puissent être. Dans ce cas, yacc se déplacerait vers le haut de l'arbre en votre nom plutôt que de le faire manuellement.

Answer 2

expansion sur le point de Hao et de the manual, vous voulez faire quelque chose comme ce qui suit:

En supposant que vous avez votre arbre de syntaxe abstraite avec fonction node qui crée un objet dans l'arborescence:

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

Ce code se traduit par "Lors de l'analyse de l'expression avec un plus, prenez les descendants gauche et droit $1/$3 et utilisez-les comme arguments pour le noeud.Enregistrer la sortie à $$ (la valeur de retour) de l'expression

$$ (du manuel):

Pour retourner une valeur, l'action normalement définit la pseudovariable `` $$ '' à une valeur .

Answer 3

Les autres réponses proposent de modifier la grammaire, ce n'est pas faisable lorsque vous jouez avec un C++ Grammer (plusieurs centaines de règles ..)

Heureusement, nous pouvons le faire automatiquement, en redéfinissant le débogage macros. Dans ce code, nous redéfinissons YY_SYMBOL_PRINT actived avec 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] = ' '; 
    } 
} 

les feuilles sont créés juste avant le retour dans le FLEX lexer