Как реализовать оператор return * в C?

Question

Я читал о рекурсивных синтаксических анализаторах восхождения-спуска здесь .

В разделе 2.1 они описывают оператор return *,

Наше расширение C происходит с операторами return. Мы использовали нотацию return * k, чтобы указать, что функция k-уровня должна быть возвращена. То есть return * 1 идентичен обычному оператору C return и просто возвращает управление вызывающей стороне текущей функции; return * 2 означает, что управление должно быть возвращено вызывающей стороне вызывающей стороны и так далее. Наконец, return * 0 следует интерпретировать как нулевое утверждение. Мы оставляем эмуляцию конструкции return * k на языках, в которых отсутствует эта операция, в качестве простого упражнения для читателя.

Как я могу реализовать такие операторы return * в моем собственном коде или эмулировать это поведение, используя goto заявления или / и указатель? Есть ли языки, которые предоставляют эту функцию по умолчанию?

Answer 1

Вы можете использовать setjmp() и longjmp() для эмуляции этого многоуровневого возврата, если вы заботитесь о поддержании стека jmp_buf s при каждом вызове функции.

Пример :

#include <stdio.h>
#include <setjmp.h>
#include <assert.h>

#define MAXDEPTH 10
jmp_buf stack[MAXDEPTH];
int sp = 0;

#define CALL(f)                                                                \
  do {                                                                         \
    assert(sp < MAXDEPTH);                                                     \
    if (setjmp(stack[sp++]) == 0) {                                            \
      f;                                                                       \
    }                                                                          \
  } while (0)
#define RETLEVEL(n)                                                            \
  do {                                                                         \
    if ((n) > 0) {                                                             \
      sp -= (n);                                                               \
      assert(sp >= 0 && sp < MAXDEPTH);                                        \
      longjmp(stack[sp], 1);                                                   \
    }                                                                          \
  } while (0)
#define RETURN                                                                 \
  do {                                                                         \
    sp -= 1;                                                                   \
    assert(sp >= 0);                                                           \
    return;                                                                    \
  } while (0)

void f3(void) {
  printf("In f3(), sp is %d, returning back 2 levels\n", sp);
  RETLEVEL(2);
}

void f2(void) {
  printf("In f2(), calling f3(), sp is %d\n", sp);
  CALL(f3());
  printf("Returning from f2(), sp is %d\n", sp);
  RETURN;
}

void f1(void) {
  printf("In f1(), calling f2(), sp is %d\n", sp);
  CALL(f2());
  printf("Returning from f1(), sp is %d\n", sp);
  RETURN;
}

int main(void) {
  printf("In main(), calling f1(), sp is %d\n", sp);
  CALL(f1());
  printf("Returning from main(), sp is now %d\n", sp);
  return 0;
}

При компиляции и запуске это выдает:

In main(), calling f1(), sp is 0
In f1(), calling f2(), sp is 1
In f2(), calling f3(), sp is 2
In f3(), sp is 3, returning back 2 levels
Returning from f1(), sp is 1
Returning from main(), sp is now 0

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

---

Что касается языков со встроенным многоуровневым возвратом ... tcl приходит на ум с return -level N. Любой язык с продолжениями, такими как схема или сопрограммы, вероятно, может легко имитировать его.

Answer 2

Решение setjmp, предложенное @Shawn, должно работать, если оно не переполняет стек setjmp (и помните, что для рекурсивных синтаксических анализаторов может потребоваться достаточно большой стек), но оно накладывает довольно значительные издержки на каждый вызов для небольшой оптимизации возвратов, которые пропускают несколько кадров стека.

В модели рекурсивного всплытия количество пропущенных кадров мало, часто равно 0. Таким образом, накладные расходы будут большими, а экономия - небольшой.

Вы могли бы написать несколько более быстрое решение, используя libunwind (см. unw_step() и unw_resume()), но обратите внимание, что unw_step обрабатывает стек вызовов как связанный список (что он и делает is), и, следовательно, может перешагивать только один кадр стека за раз. Таким образом, вы в конечном итоге с oop вокруг unw_step звонков. Кроме того, вы должны убедиться, что вызов функции не был встроен.

Более простое и быстрое решение - просто обернуть CALL и RETURN в макросы, как подсказывает @shawn, и использовать возвращаемое в противном случае неиспользуемое возвращаемое значение для подсчета раскручивания: (Немного изменено для использования variadi c макросы)

#include <stdio.h>

int sp = 0;

#define CALL(f, ...)                            \
  do {                                          \
    ++sp;                                       \
    RETLEVEL(f(__VA_ARGS__));                   \
  } while (0)

#define RETLEVEL(n)                             \
  for ( int n__ = n; n__ > 0 && sp > 0; ) {     \
    --sp;                                       \
    return n__ - 1;                             \
  }
#define RETURN RETLEVEL(1)

int f3(void) {
  printf("In f3(), sp is %d, returning back 2 levels\n", sp);
  RETLEVEL(2);
}

int f2(void) {
  printf("In f2(), calling f3(), sp is %d\n", sp);
  CALL(f3);
  printf("Returning from f2(), sp is %d\n", sp);
  RETURN;
}

int f1(void) {
  printf("In f1(), calling f2(), sp is %d\n", sp);
  CALL(f2);
  printf("Returning from f1(), sp is %d\n", sp);
  RETURN;
}

int main(void) {
  printf("In main(), calling f1(), sp is %d\n", sp);
  CALL(f1);
  printf("Returning from main(), sp is now %d\n", sp);
  return 0;
}