使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並將它們用作節點的參數。將表達式的輸出保存到$$（返回值）。

$$（從手動）：

返回一個值，該動作通常 設置pseudovariable``$$ '' 一些 值。

Answer 3

其他的答案建議修改語法與C++語法（規則幾百..）

幸運玩的時候，這是不可行的，我們可以自動做到這一點，通過重新定義調試宏。 在這段代碼中，我們將重新定義YY_SYMBOL_PRINT與YYDEBUG actived：

%{ 

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詞法分析器