Разобрать дерево используя Bison - PullRequest
Новая
       14

Разобрать дерево используя Bison

2 голосов
/ 16 марта 2012

Я новичок в зубрах.Я пытаюсь реализовать парсер.Основная проблема, с которой я сталкиваюсь, связана с деревом разбора.Я получаю ошибку, связанную с деревом, которую я не могу устранить.Там написано «неизвестное имя типа« дерево »».Вот мой у файл.Я был бы рад, если бы кто-нибудь мог помочь мне разобраться в этом.Мне нужен парсер очень сильно.Заранее спасибо. 

%{
 #include <stdio.h>
 #include <string.h>

 void yyerror(const char *str)
 {
    fprintf(stderr,"error FAIL: %s\n",str);
 }

int yywrap()
{
    return 1;
} 

enum treetype {operator_node, variable_node};
typedef struct tree {
enum treetype nodetype;
union {
 struct {struct tree *left, *right; char operator;} an_operator;
  char *a_variable;
} body;
} tree;
static tree *make_op (tree *l, char o, tree *r) {
tree *result= (tree*) malloc (sizeof(tree));
result->nodetype= operator_node;
result->body.an_operator.left= l;
result->body.an_operator.operator= o;
result->body.an_operator.right= r;
return result;
}
static void printtree (tree *t, int level) {
#define step 4
if (t)
 switch (t->nodetype)
 {
   case operator_node:
    printtree (t->body.an_operator.right, level+step);
    printf ("%*c%c\n", level, ' ', t->body.an_operator.operator);
    printtree (t->body.an_operator.left, level+step);
    break;
   case variable_node:
    printf ("%*c%c\n", level, ' ', t->body.a_variable);
 }
} 

%}

%union {
char* a_variable;
tree* a_tree;
}

%start file
%token <a_variable> TOKDIGIT TOKFLOAT TOKID TOKSEMICOLON TOLCOLON TOKCOMMA TOKUNRECOG   TOKCOMMENT TOKDOT TOKMINUS TOKCOLON
%type <a_tree> field object file ID
%right TOKMINUS

%%

file   :    
   |    object file { printtree($1, 1); }
    ;
object :     field object {$$ = make_op($1, '', $2);}
  |   field {$$ = $1 ; }
    ;
field  :    ID TOKCOLON field {$$ = make_op ($1, ':', $3); }
  | ID TOKCOMMA field {$$ = make_op ($1, ',', $3); }
  | ID TOKSEMICOLON field {$$ = make_op ($1, ';', $3); }
    ;   
ID     :   TOKID { $$ = $1; }
       ;    

%%

1 Ответ

2 голосов
/ 16 марта 2012

Я применил следующий патч к вашему коду, чтобы исправить пару предупреждений от Bison.В вашем правиле верхнего уровня отсутствовало действие для пустого регистра (и, следовательно, ему не удалось назначить $$), а другое правило также не назначало ничего для $$.Т.е. ваши file правила не накапливают объекты в главном дереве, и поэтому ваша yyparse функция не будет возвращать дерево: 

Index: test/test.y
===================================================================
--- test.orig/test.y    2012-03-15 16:34:31.992021757 -0700
+++ test/test.y 2012-03-15 17:00:27.666596757 -0700
@@ -57,8 +57,9 @@

 %%

-file   :    
-   |    object file { printtree($1, 1); }
+file   :   /* empty */ { return NULL; }
+   |    object file { printtree($1, 1); return NULL; }
+        /* TODO: gather the objects into a tree and return */
     ;
 object :     field object {$$ = make_op($1, '', $2);}
   |   field {$$ = $1 ; }

Теперь у вас есть проблемы в грамматике.Основным является то, что ваши field постановки не прекращаются.Они генерируют бесконечные предложения.Каждое из произведений для field производит что-то, что заканчивается field;Расширение грамматики не может быть завершено.

Основная проблема в том, что в вашей грамматике слишком много мест, где имеет место расширение, и над одним и тем же материалом.Ваш file производит ноль или более object.object - это ноль больше экземпляров field.И тогда поле также хочет сгенерировать больше field.

Это означает, что ваш file на самом деле является просто последовательностью field.Последовательность нескольких field -s уже обработана, и она должна обрабатываться только на одном уровне;поле не должно выдавать больше field.

...