How do I use goto with swtich in C? (FSM)

Question

Let's say I have this code

switch(x)
{

region_1:

  case a:
      ...
  case b:
      goto region_1:

region_2:
      
  case c:
      ...
  case d:
      goto region_2

  default:
      ...

}

Is it possible in C to have such a recursion-like algorithm? Where from any case I can jump to a label and go though cases again? I need to build a FSM for my grand dad, he' planning to catch fish with it.

Answer 1

Why use a switch at all.

For example, say you want to write an automata that checks if the input matches pattern ab+c+.

Automata:

• S0:
  • a → S1
• S1
  • b → S1
  • c → S2
• S2
  • c → S2
  • EOF → ACCEPT

This could be done with switches, but it could also be implemented using goto:

S0: {
    int c = getch();
    if (c == 'a') goto S1;
    goto ERROR;
}

S1: {
    int c = getch();
    if (c == 'b') goto S1;
    if (c == 'c') goto S2;
    goto ERROR;
}

S3: {
    int c = getch();
    if (c == 'c') goto S2;
    if (c == EOF) goto ACCEPT;
    goto ERROR;
}

ACCEPT: exit(0);
ERROR:  exit(1);

But you could also write that as follows:

while (1) {
   int next_state;

   switch (state) {
      case ERROR:  exit(1);
      case ACCEPT: exit(0);

      case S0: {
         int c = getch();
         if      (c == 'a') { next_state = S1;    }
         else               { next_state = ERROR; }
         break;
      }

      case S1: {
         int c = getch();
         if      (c == 'b') { next_state = S1;    }
         else if (c == 'c') { next_state = S2;    }
         else               { next_state = ERROR; }
         break;
      }

      case S2: {
         int c = getch();
         if      (c == 'c') { next_state = S2;    }
         else               { next_state = ERROR; }
         break;
      }
   }

   state = next_state;
}

But that's really a stepping stone to using tables.

#define TOK_OTHER 0
#define TOK_EOF   1
#define TOK_A     2
#define TOK_B     3
#define TOK_C     4

static int char_to_token_map[] = {
   /*          0  1  2  3   4  5  6  7   8  9  A  B   C  D  E  F */
   /* 0x00 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x10 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x20 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x30 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x40 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x50 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x60 */  0, 2, 3, 4,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,
   /* 0x70 */  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0,  0, 0, 0, 0   
};

static int to_token(int c) {
   if (c >= 128) return 0;
   if (c == EOF) return 1;
   return char_to_token_map[c];
}

#define ERROR  -2
#define ACCEPT -1
#define S0      0
#define S1      1
#define S2      2

static int automata[3][5] {
   /* state   OTHER   EOF     a       b       c       */
   /* -----   ------- ------- ------- ------- ------- */
   /* S0 */ { ERROR   ERROR   S1,     ERROR,  ERROR   },
   /* S1 */ { ERROR,  ERROR,  ERROR,  S1,     S2,     },
   /* S2 */ { ERROR,  ACCEPT, ERROR,  ERROR,  S2,     }
};

int state = S0;
while (1) {
   int new_state;

   switch (state) {
      case ERROR:  exit(1);
      case ACCEPT: exit(0);
      default:     new_state = automata[ state ][ to_token(getch()) ];
   }

   state = new_state;
}

If you need to do anything before switching state, just put a special case in the switch for that state. Or use a table of function pointers indexed by state.