How to write cycles through goto, and then convert it to a state machine?

Question

Algorithms

How to write cycles through goto, and then convert it to a state machine?

Answer 1

Let's take a program that has both loops and goto. For example, checking if there is a zero row in the matrix:

void Check(int M[5][5]){
  for(int a=0;a<5;a++){
    for(int b=0;b<5;b++){
      if(M[a][b]!=0) goto L1;
   }
   goto L2;
L1: continue;
  }
  printf("No\n"); return;
L2:
  printf("Yes\n"); 
}

Let's describe all the variables at the beginning, and write the cycles directly by definition.
In addition, let's turn return into a goto on the Return label at the end of the function:

void Check(int M[5][5]){
  int a,b;
  a=0;
  goto Loop1_Check;
Loop1_Body:
  b=0;
  goto Loop2_Check;
Loop2_Body:
      if(M[a][b]!=0) goto L1;
      b++;
Loop2_Check:
      if(b<5) goto Loop2_Body;  
   goto L2;
L1: 
Loop1_End:
   a++;
Loop1_Check:  
  if(a<5) goto Loop1_Body;
  printf("No\n"); goto Return;
L2:
  printf("Yes\n"); 
Return: ;
}

Now, between any two labels, we have a linear sequence in which the if (condition) goto label;
We start the state variable.
We assign some value to this variable to each label, and instead of goto label we write state=label; and instead of if(condition) goto label; - if(condition) state=label; else{ rest of code until next label }. If there was no unconditional goto before any label, we write state=label before it;

void Check(int M[5][5]){
  const int Return=0;
  const int Loop1_Check=1;
  const int Loop1_Body=2;
  const int Loop2_Check=3;
  const int Loop2_Body=4;
  const int L1=5;
  const int L2=6;

  int state;
  int a,b;
  a=0;
  state=Loop1_Check;
Loop1_Body:
  b=0;
 state=Loop2_Check;
Loop2_Body:
      if(M[a][b]!=0) state=L1;
      else{
         b++;
         state=Loop2_Check;
      }
Loop2_Check:
      if(b<5) state=Loop2_Body;  
      else state=L2;
L1: 
      a++;
      state=Loop1_Check;
Loop1_Check:  
  if(a<5) state=Loop1_Body;
  else{
      printf("No\n"); 
      state=Return;
  }
L2:
  printf("Yes\n"); 
  state=Return;
Return: ;
}

(this conversion was non-equivalent).
Now, before the first label, insert while(state!=Return){ switch(state){
and replace each label label: with break; case label:
break; we remove before the first label, and change case Return: to } }

void Check(int M[5][5]){
  const int Return=0;
  const int Loop1_Check=1;
  const int Loop1_Body=2;
  const int Loop2_Check=3;
  const int Loop2_Body=4;
  const int L1=5;
  const int L2=6;

  int state;
  int a,b;
  a=0;
  state=Loop1_Check;
  while(state!=Return){
    switch(state){
      case Loop1_Body:
        b=0;
        state=Loop2_Check;
        break;
      case Loop2_Body:
        if(M[a][b]!=0) state=L1;
        else{
          b++;
          state=Loop2_Check;
        }
        break;
      case Loop2_Check:
        if(b<5) state=Loop2_Body;  
        else state=L2;
        break;
      case L1: 
        a++;
        state=Loop1_Check;
        break;
      case Loop1_Check:  
         if(a<5) state=Loop1_Body;
         else{
            printf("No\n"); 
            state=Return;
         }
         break;
       case L2:
          printf("Yes\n"); 
          state=Return;
          break;
     }
  }
  ;
}

Everything.