Вывод YACC в AST (дерево токенов) - PullRequest
Новая
       82

Вывод YACC в AST (дерево токенов)

12 голосов
/ 04 июня 2009

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

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

Ответы [ 3 ]

6 голосов
/ 27 апреля 2011

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

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

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

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

$$ (из руководства):

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

5 голосов
/ 04 июня 2009

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

1 голос
/ 13 февраля 2013

Другие ответы предлагают изменить грамматику, это невозможно при игре с грамматикой 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

...