Рекурсия бизонов, ведущий себя странно со связанным списком - PullRequest
Новая
       39

Рекурсия бизонов, ведущий себя странно со связанным списком

0 голосов
/ 01 апреля 2019

У меня есть связанная со списком структура: 

typedef struct NODE
{
  NODE_TYPES type;
  struct NODE* curr;
  struct NODE* next;
} NODE;

и у меня есть это рекурсивное правило: 

lines: stmt             {
                            root -> next = $1;
                            $1 -> next = NULL;
                            $$ = $1;

                        }
| lines stmt            {
                            $1 -> next = $2;
                            $2 -> next = NULL;
                            $$ = $2;

                        }
;

stmt всегда является указателем на NODE структуру.

root определяется как NODE *root, а затем, в основной функции, выделяется так: root = malloc(sizeof(NODE));

Однако, печатая мой список узлов рекурсивно, начиная с root, я получаю только последний узел обратно. Почему я теряю данные между root и последним узлом?

1 Ответ

2 голосов
/ 01 апреля 2019

Очевидно, проблема была в том, что вы устанавливали семантическое значение stmt, чтобы указывать на локальную переменную, выделенную в стеке. Так как время жизни локальной переменной истекает, как только семантическое действие выполнено, это значение является висящим указателем, и его использование - неопределенное поведение. (Но в этом случае вы, вероятно, обнаружите, что все указатели ссылаются на один и тот же блок памяти, содержимое которого будет меняться при каждом повторном использовании конкретного кадра стека.)

Необходимо убедиться, что значение stmt является указателем на недавно выделенный NODE: 

stmt : /* ... something ... */ 
                  { $$ = malloc(sizeof *$$);
                    $$ = (NODE){/* ... */, .next = NULL; }

Это важно. Нет хорошего способа сделать это без какой-либо функции, которая выделяет кучу нового NODE. Вы можете попытаться уменьшить издержки malloc, сохранив пул NODE s и утилизировав их самостоятельно, но поскольку большинство современных реализаций malloc хорошо справляются с утилизацией небольших выделенных ресурсов фиксированного размера, это преждевременная оптимизация.

Код связанного списка будет работать для простых операторов, но использование глобальной переменной для поддержки заголовка списка не очень масштабируемо. Это сделает невозможным синтаксический анализ составных операторов (например, условных выражений и циклов), поскольку в конечном итоге вы будете использовать root для внутренних списков операторов. Лучше просто построить список естественным путем (который будет обратным) и полностью изменить его в конце: 

stmts: stmt       /* Default action is fine */
     | stmts stmt { $$ = $2; $$->next = $1; }
line : stmts      { $$ = reverse($$); }

В этом простом коде, каждый раз, когда stmts: stmts stmt уменьшается, он помещает новый NODE в перед списка, что, очевидно, создает список в обратном порядке. Таким образом, когда line уменьшается (что будет после того, как все stmt были проанализированы), список необходимо поменять местами. Вы можете повернуть на место: 

NODE* reverse(NODE* last) {
  NODE* next = NULL;
  while (last) {
    NODE* tmp = last->next; 
    last->next = next;
    next = last;
    last = tmp;
  }
  return next;
}

Это полностью устраняет необходимость в глобальном root, поэтому составная инструкция может быть правильно собрана.

...