Блог

Я пытаюсь создать сканер и анализатор flex bison для деревьев формата файлов Newick, чтобы выполнять с ними операции. Реализованная грамматика объяснение основано на упрощении (метки и длины всегда одного и того же типа, возвращаемые flex) этого примера.

По сути, это анализатор для формата файла, который представляет собой дерево с серией (рекурсивных) поддеревьев и / или листьев. Основное дерево всегда будет заканчиваться на; и указанное дерево и все поддеревья внутри будут содержать ряд узлов между ( и ), с именем и длиной справа от самой правой круглой скобки, заданными name и :length , которые являются необязательными (вы можете не указывать их, поместите один из них(имя или: длина), или оба с именем: длина).

Если в каком-либо узле отсутствует имя или длина, будут применены значения по умолчанию. (например: ‘missingName’ и ‘1’)

Примером может быть (child1:4, child2:6)root:6; , ((child1Of1:2, child2Of1:9)child1:5, child2:6)root:6;

Реализация указанной грамматики следующая (ПРИМЕЧАНИЕ: я перевел свой собственный код, как это было на моем языке, и для ясности было удалено много побочных вещей):

     struct node {
        char* name; /*the node's assigned name, either from the file or from default values*/
        float length; /*node's length*/
    } dataOfNode;
}

 

%start tree
 
%token<dataOfNode> OP CP COMMA SEMICOLON COLON DISTANCE NAME

%type<dataOfNode> tree subtrees recursive_subtrees subtree leaf


%%

tree:   subtrees NAME COLON DISTANCE SEMICOLON          {} // with name and distance    
        | subtrees NAME SEMICOLON                       {} // without distance
        | subtrees COLON DISTANCE SEMICOLON             {} // without name
        | subtrees SEMICOLON                            {} // without name nor distance
        ;
    
    
subtrees:   OP recursive_subtrees CP                    {}
            ;   
        
            
recursive_subtrees: subtree                             {} // just one subtree, or the last one of the list         
                    | recursive_subtrees COMMA subtree  {} // (subtree, subtree, subtree...)        
    

subtree:    subtrees NAME COLON DISTANCE    {   $.NAME= $2.name; $.length = $4.length; $.lengthAcum = $.lengthAcum   $4.length;
                                                } // group of subtrees, same as the main tree but without ";" at the end, with name and distance                                        
            
            | subtrees NAME                 {   $.name= $2.name; $.length = 1.0;}             // without distance                                 
            
            | subtrees COLON DISTANCE       {   $.name= "missingName"; $.length = $3.length;} // without name                             
           
            | subtrees                      {   $.name= "missingName"; $.length = 1.0;}       // without name nor distance                            
            
            | leaf                          {   $.name= $1.name; $.length = $1.length;}       // a leaf
                    
                    
                    
leaf:   NAME COLON DISTANCE {   $.name= $.name; $.length = $3.length;}       // with name and distance
        | NAME              {   $.name= $1.name; $.length = 1.0;}             // without distance
        | COLON DISTANCE    {   $.name= "missingName"; $.length = $2.length;} // without name
        |                   {   $.name= "missingName"; $.length = 1.0;}       // without name nor distance
        ;


%%
 

Теперь, допустим, я хочу различать, кто является родителем каждого поддерева и листа, чтобы я мог рекурсивно накапливать длину родительского поддерева с длиной «самого длинного» дочернего элемента.

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

В основном это вопрос определения структуры данных, в которой вы хотите хранить свои деревья, и построения этого «снизу вверх» в действиях правил. Часть «снизу вверх» является важным следствием того, как работают анализаторы bison — они «снизу вверх», распознают конструкции из листьев грамматики и затем собирают их в более высокие нетерминалы (и, безусловно, в начальный нетерминал, который будет последним выполнением действия). Вы также можете упростить ситуацию, не имея так много избыточных правил. Наконец, IMO всегда лучше использовать символьные литералы для односимвольных токенов, а не имен. Таким образом, вы можете получить:

 %{
struct tree {
    struct tree  *next;     /* each tree is potentially part of a list of (sub)trees */
    struct tree  *subtree;  /* and may contain a subtress */
    const char   *name;
    double       length;
};

struct tree *new_leaf(const char *name, double length);   /* malloc a new leaf "tree" */
void append_tree(struct tree **list, struct tree *t);  /* append a tree on to a list of trees */
%}

%union {
    const char   *name;
    double       value;
    struct tree  *tree;
}

%type<tree> subtrees recursive_subtrees subtree leaf
%token<name> NAME
%token<value> DISTANCE

%%

tree: subtrees leaf ';'  { $2->subtree = $1;  print_tree($2); } 
    ;
    
subtrees: '(' recursive_subtrees ')'  { $ = $2; }
        ;   
            
recursive_subtrees: subtree                         { $ = $1; } // just one subtree, or the last one of the list
                  | recursive_subtrees ',' subtree  { append_tree(amp;($=$1)->next, $3); } // (subtree, subtree, subtree...)
                  ;

subtree: subtrees leaf  { ($=$2)->subtree = $1; }
       | leaf           { $ = $1; }
       ;
                    
leaf: NAME ':' DISTANCE { $ = new_leaf($1, $3);}              // with name and distance
    | NAME              { $ = new_leaf($1, 1.0);}             // without distance
    | ':' DISTANCE      { $ = new_leaf("missingName", $2; }   // without name
    |                   { $ = new_leaf("missingName", 1.0); } // without name nor distance
    ;

%%

struct tree *new_leaf(const char *name, double length) {
    struct tree *rv = malloc(sizeof(struct tree));
    rv->subtree = rv->next = NULL;
    rv->name = name;
    rv->length = length;
    return rv;
}

void append_tree(struct tree **list, struct tree *t) {
    assert(t->next == NULL);  // must not be part of a list yet
    while (*list) list = amp;(*list)->next;
    *list = t;
}