Как расписать циклы через goto, а потом преобразовать в state-машину?

Question

[readical]

Как расписать циклы через goto, а потом преобразовать в state-машину?

Answer 1

[Mrrl]

Возьмём программу, в которой есть и циклы, и goto. Например, проверка, есть ли в матрице нулевая строка:

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"); 
}

Опишем все переменные в начале, а циклы распишем прямо по определению.
Кроме того, return превратим в goto на метку Return в конце функции:

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: ;
}

Теперь между любыми двумя метками у нас находится линейная последовательность, в которой могут встретиться конструкции if(condition) goto label;
Заводим переменную state.
Каждой метке присваиваем какое-нибудь значение этой переменной, и вместо goto label пишем state=label; а вместо if(condition) goto label; - if(condition) state=label; else{ остаток кода до следующей метки }. Если перед какой-нибудь меткой label не было безусловного goto, пишем перед ней state=label;

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: ;
}

(это преобразование было неэквивалентным).
Теперь перед первой меткой вставляем while(state!=Return){ switch(state){
а каждую метку label: заменяем на break; case label:
break; перед первой меткой убираем, а case Return: меняем на } }

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;
     }
  }
  ;
}

Всё.

Comments

[CAMOKPYT]

не читал, но лайк поставил за длину

[Mrrl]

CAMOKPYT: Спасибо. Copy/Paste - великая вещь :)

[readical]

Mrrl: Спасибо Вам огромное.

Есть ли какие-либо работы в этой области?

[Mrrl]

readical: Не знаю. Я это писал по воспоминаниям о курсе "оптимизирующие преобразования программ" примерно 30-летней давности.