Как управлять списком элементов грамматики в абстрактном синтаксическом дереве, генерируемом Bison - PullRequest
Новая
       114

Как управлять списком элементов грамматики в абстрактном синтаксическом дереве, генерируемом Bison

0 голосов
/ 23 октября 2019

Я делаю переводчик с Java на Python с помощью инструментов flex и bison. Правила бизонов относятся к ограничению грамматики Java. В дополнение к созданию правил в зубрах, я также создал Абстрактное Синтаксическое Дерево как Промежуточное Представление. Соответствующие узлы AST были созданы в семантических действиях вместе с правилами бизонов.

Моя проблема касается управления списками элементов (или рекурсией) в правилах бизонов.

Предоставление переводчикаВ следующем текстовом файле синтаксический анализ завершается без синтаксических ошибок, но когда я пересекаю AST в предварительном порядке для целей тестирования, может показаться, что пересечение останавливается в первом дочернем узле списка и, следовательно, не циклически повторяется на остальныхпотомки списков.

ТЕКСТОВЫЙ ФАЙЛ НА ВХОДЕ: 

import java.util.*;
class table {
   int a;
   int c;
}
class ball {
   int a;
}

Я включил в него грамматические правила бизонов: 

Program
       : ImportStatement ClassDeclarations      { set_parse_tree($$ = program_new($1,$2,2));}
       ;

ImportStatement
               :  IMPORT LIBRARY SEMICOLON  {$$ = import_new($2,1); printf("Type di import: %d \n", $$->type);}
               |  %empty                    {$$ = import_new(NULL,0); }
               ;


ClassDeclarations
                 : ClassDeclaration                     { $$ = list_new(CLASS_DECLARATIONS,$1,NULL,2);  }
                 | ClassDeclarations ClassDeclaration   { list_append( $$ = $1, list_new(CLASS_DECLARATIONS,$2,NULL,2)); }
                 ;

ClassDeclaration
                : CLASS NameID LBRACE FieldDeclarations RBRACE        { $$ = classDec_new($2,$4,2); }
                | PUBLIC CLASS NameID LBRACE FieldDeclarations RBRACE { $$ = classDec_new($3,$5,2);}
                ;

FieldDeclarations
                 : FieldDeclaration                    {$$ = list_new(FIELD_DECLARATIONS,$1,NULL,2); }
                 | FieldDeclarations FieldDeclaration  { list_append( $$ = $1, list_new(FIELD_DECLARATIONS,$2,NULL,2)); }
                 ;

FieldDeclaration
                : VariableFieldDeclaration           {$$ = fieldDec_new($1,NULL,NULL,3);}
                | PUBLIC VariableFieldDeclaration    {$$ = fieldDec_new($2,NULL,NULL,3);}
                | MethodFieldDeclaration             {$$ = fieldDec_new(NULL,$1,NULL,3);}
                | ConstructorDeclaration             {$$ = fieldDec_new(NULL,NULL,$1,3);}
                ;

VariableFieldDeclaration
                        : Type VariableDeclarations SEMICOLON   {$$ = variableFieldDec_new($1,$2,2);}
                        ;

VariableDeclarations
                     : VariableDeclaration                              {$$ = list_new(VARIABLE_DECLARATIONS,$1,NULL,2); }
                     | VariableDeclarations COMMA VariableDeclaration   { list_append( $$ = $1, list_new(VARIABLE_DECLARATIONS,$3,NULL,2)); }     
                     ;

VariableDeclaration
                   : NameID                                              {$$ = varDec_new($1,NULL,NULL,NULL,NULL,5);}
                   | NameID ASSIGNOP ExpressionStatement                 {$$ = varDec_new($1,$3,NULL,NULL,NULL,5);}
                   | NameID LSBRACKET RSBRACKET                          {$$ = varDec_new($1,NULL,NULL,NULL,NULL,5); }
                   | LSBRACKET RSBRACKET NameID                          {$$ = varDec_new($3,NULL,NULL,NULL,NULL,5); }
                   | NameID LSBRACKET RSBRACKET ASSIGNOP NEW Type LSBRACKET Dimension RSBRACKET      {$$ = varDec_new($1,NULL,$6,$8,NULL,5); } 
                   | LSBRACKET RSBRACKET NameID  ASSIGNOP NEW Type LSBRACKET Dimension RSBRACKET     {$$ = varDec_new($3,NULL,$6,$8,NULL,5); }
                   | NameID LSBRACKET RSBRACKET ASSIGNOP LBRACE VariableInitializers RBRACE    {$$ = varDec_new($1,NULL,NULL,NULL,$6,5); }
                   | LSBRACKET RSBRACKET NameID  ASSIGNOP LBRACE VariableInitializers RBRACE    {$$ = varDec_new($3,NULL,NULL,NULL,$6,5); }
                   | NameID LSBRACKET RSBRACKET ASSIGNOP LBRACE RBRACE   {$$ = varDec_new($1,NULL,NULL,NULL,NULL,5); }
                   | LSBRACKET RSBRACKET NameID  ASSIGNOP LBRACE RBRACE  {$$ = varDec_new($3,NULL,NULL,NULL,NULL,5); }
                   ;

Type
    : INT               {$$ = typeId_new($1,1);} 
    | CHAR              {$$ = typeId_new($1,1);}
    | FLOAT             {$$ = typeId_new($1,1);}
    | DOUBLE            {$$ = typeId_new($1,1);} 
    ;

NameID
      : ID          {$$ = nameID_new($1, 1);}    
      ;

В общей структуреузел ast:

  • тип каждого узла,
  • структура объединения, содержащая различные структуры каждого возможного узла,
  • целочисленная переменная(numLeaf), который представляет максимально возможное количество листьев для каждого родительского узла (он передается из зубра в семантических действиях как последний параметрeter of functions)
  • массив указателей (leafVet) на структуры, у которых будет количество листьев в качестве размера, и каждое местоположение будет содержать указатель на возможный дочерний элемент (если дочерний элемент отсутствует, он будетбыть NULL).

Эти две последние переменные используются для управления пересечением дерева. Я буду циклически повторять каждый вектор для передачи дочерним элементам каждого узла.

Я думаю, что проблема в основном связана со структурами списков (ClassDeclarations, FieldDeclarations, VariableDeclarations ...). Структура каждого списка выглядит следующим образом, и эта структура является частью объединения возможных структур каждого узла.

СПИСОК СТРУКТУР: 

struct {
        int type;
        struct ast_node *head; //pointer to the head of the list
        struct ast_node *tail; //pointer to the tail of the list
} list;

Функции, которые относятся к созданию спискаузлы следующие: 

static ast_node *newast(int type)
{
    ast_node *node = malloc(sizeof(ast_node));
    node->type = type;
    return node;
}

ast_list *list_new(int type, ast_node *head, ast_list *tail, int numLeaf)
{
    ast_list *l = newast(AST_LIST); //allocates memory for the AST_LIST type node
    l->list.type = type;
    l->list.head = head;
    l->list.tail = tail;
    l->numLeaf = numLeaf;
    l->LeafVet[0] = head;
    l->LeafVet[1] = tail;
    return l;
}

void list_append(ast_list *first, ast_list *second)
{
    while (first && first->list.tail)
    {
        first = first->list.tail;
    }
    if (first)
    {
        first->list.tail = second;
    }
    first->numLeaf = 2;
}

Я думаю, что ошибка может быть в функции list_append, потому что, когда я бегу по дереву предварительного заказа, ему удается войти в первый листовой узел списков, но не происходитс остальными листовыми узлами. В частности, ссылаясь на исходный текстовый файл, пересечение останавливается после достижения узла NameID объекта VariableDeclaration (если быть точным, он останавливается на первой переменной первого класса) без каких-либо ошибок. Сразу после этого он должен проанализировать второй конечный узел fieldDeclarations, так как существует второе объявление переменной (variableFieldDeclaration), но при попытке вывести ненулевые листовые номера каждого списка я всегда получаю 1, так что может показаться, что добавление списков делаетне работает должным образом.

Ошибка также может быть в алгоритме пересечения, который я пишу ниже: 

void print_ast(ast_node *node) //ast preorder
{
  int leaf;
  leaf = node->numLeaf;
  printf("Num leaf: %d \n",leaf);

  switch(node->type)
    {
        case AST_LIST:
        break;

        case AST_PROGRAM:
        break;

        case AST_IMPORT:    
            printf("Import: %s \n", node->import.namelib);
        break;

        case AST_CLASSDEC:
            printf("name class: %s\n", node->classDec.nameClass->nameID.name);
        break;

        case AST_TYPEID:        
        break;

        case AST_VARFIELDDEC:                 
        break;

        case AST_VARDEC:
        break;

        case AST_FIELDDEC:
        break;

        case AST_NAMEID:
            printf("Il valore della variabile e': %s \n", node->nameID.name);
        break;

        default:            
            printf("Error in node selection!\n");
            exit(1);
    }

  for (int i=0; i<leaf; i++)
  { 
      if(node->LeafVet[i] == NULL ){
         continue;
      } else{
         printf("%d \n", node->LeafVet[i]->type);
         print_ast(node->LeafVet[i]);
      }
   }

}

Я надеюсь, что вы можете мне помочь, большое спасибо.

...