c - ¿Usar goto o no?

parsing finite-automata

Question

Esta pregunta puede sonar cliché, pero estoy en una situación aquí.

Estoy tratando de implementar un autómata de estado finito para analizar una determinada cadena en C. Cuando comencé a escribir el código, me di cuenta de que el código puede ser más legible si uso etiquetas para marcar los diferentes estados y usar goto para saltar de un estado a otro. otra según el caso.

Usar las rupturas estándar y las variables de marca es bastante engorroso en este caso y es difícil hacer un seguimiento del estado.

¿Qué enfoque es mejor? Más que cualquier otra cosa, me preocupa que pueda dejar una mala impresión en mi jefe, ya que estoy en una pasantía.

Answer 1

Evite goto menos que la complejidad agregada (para evitar) sea más confusa.

En problemas prácticos de ingeniería, hay espacio para el uso de Goto muy escasamente. Académicos y no ingenieros se retuercen innecesariamente con el uso de goto . Dicho esto, si se pinta en un rincón de implementación en el que una gran cantidad de goto es la única salida, reconsidere la solución.

Una solución que funcione correctamente suele ser el objetivo principal. Hacerlo correcto y mantenible (minimizando la complejidad) tiene muchos beneficios para el ciclo de vida. Haga que funcione primero y luego límpielo gradualmente, preferiblemente simplificando y eliminando la fealdad.

Answer 2

Goto no es un mal necesario, y tengo que estar totalmente en desacuerdo con Denis, sí, goto puede ser una mala idea en la mayoría de los casos, pero hay usos. El mayor temor con goto es el llamado "código spagetti", rutas de código no rastreables. Si puede evitar eso y si siempre quedará claro cómo se comporta el código y no salta de la función con un goto, no hay nada en contra de goto. Solo úselo con precaución y si está tentado de usarlo, evalúe realmente la situación y encuentre una solución mejor. Si no puedes hacer esto, puedes usar goto.

Answer 3

No conozco su código específico, pero hay una razón como esta:

typedef enum {
    STATE1, STATE2, STATE3
} myState_e;

void myFsm(void)
{
    myState_e State = STATE1;

    while(1)
    {
        switch(State)
        {
            case STATE1:
                State = STATE2;
                break;
            case STATE2:
                State = STATE3;
                break;
            case STATE3:
                State = STATE1;
                break;
        }
    }
}

no funcionaria para ti? No usa goto , y es relativamente fácil de seguir.

Edición: todos los fragmentos de State = violan DRY, por lo que podría hacer algo como:

typedef int (*myStateFn_t)(int OldState);

int myStateFn_Reset(int OldState, void *ObjP);
int myStateFn_Start(int OldState, void *ObjP);
int myStateFn_Process(int OldState, void *ObjP);

myStateFn_t myStateFns[] = {
#define MY_STATE_RESET 0
   myStateFn_Reset,
#define MY_STATE_START 1
   myStateFn_Start,
#define MY_STATE_PROCESS 2
   myStateFn_Process
}

int myStateFn_Reset(int OldState, void *ObjP)
{
    return shouldStart(ObjP) ? MY_STATE_START : MY_STATE_RESET;
}

int myStateFn_Start(int OldState, void *ObjP)
{
    resetState(ObjP);
    return MY_STATE_PROCESS;
}

int myStateFn_Process(int OldState, void *ObjP)
{
    return (process(ObjP) == DONE) ? MY_STATE_RESET : MY_STATE_PROCESS;
}

int stateValid(int StateFnSize, int State)
{
    return (State >= 0 && State < StateFnSize);
}

int stateFnRunOne(myStateFn_t StateFns, int StateFnSize, int State, void *ObjP)
{
    return StateFns[OldState])(State, ObjP);
}

void stateFnRun(myStateFn_t StateFns, int StateFnSize, int CurState, void *ObjP)
{
    int NextState;

    while(stateValid(CurState))
    {
        NextState = stateFnRunOne(StateFns, StateFnSize, CurState, ObjP);
        if(! stateValid(NextState))
            LOG_THIS(CurState, NextState);
        CurState = NextState;
    }
}

que es, por supuesto, mucho más largo que el primer intento (cosa graciosa acerca de DRY). Pero también es más sólido: si no se devuelve el estado de una de las funciones de estado, se generará una advertencia del compilador, en lugar de ignorar silenciosamente el State = faltante State = en el código anterior.

Answer 4

No hay nada inherentemente malo con goto . La razón por la que a menudo se los considera "tabú" se debe a la forma en que algunos programadores (que a menudo provienen del mundo del ensamblaje) los utilizan para crear un código de "espagueti" que es casi imposible de entender. Si puede usar declaraciones goto mientras mantiene su código limpio, legible y libre de errores, entonces tendrá más poder para usted.

El uso de declaraciones goto y una sección de código para cada estado es definitivamente una forma de escribir una máquina de estados. El otro método es crear una variable que mantendrá el estado actual y usar una instrucción de cambio (o similar) para seleccionar qué bloque de código se ejecutará según el valor de la variable de estado. Vea la respuesta de Aidan Cully para una buena plantilla usando este segundo método.

En realidad, los dos métodos son muy similares. Si escribe una máquina de estado con el método de variable de estado y la compila, el ensamblaje generado puede parecerse al código escrito con el método goto (según el nivel de optimización de su compilador). El método goto puede verse como la optimización de la variable adicional y el bucle del método de la variable de estado. El método que utilice es una cuestión de elección personal, y mientras esté produciendo un código legible y de trabajo, espero que su jefe no piense en usted diferente para usar un método en lugar del otro.

Si está agregando este código a una base de código existente que ya contiene máquinas de estado, le recomendaría que siga la convención que ya esté en uso.

Answer 5

No puedo ver una gran diferencia entre goto y switch. Puede que prefiera switch / while porque le da un lugar garantizado para ejecutarse después del switch (donde podría agregar el registro y la razón de su programa). Con GOTO, usted simplemente sigue saltando de etiqueta en etiqueta, así que para agregar el registro tendría que ponerlo en cada etiqueta.

Pero aparte de eso no debería haber mucha diferencia. De cualquier manera, si no lo dividió en funciones y no todos los estados usan / inicializan todas las variables locales, puede terminar con un caos de código casi espagueti sin saber qué estados cambiaron qué variables y es muy difícil de depurar / razonar. acerca de.

Como nota aparte, ¿puedes analizar la cadena usando una expresión regular? La mayoría de los lenguajes de programación tienen bibliotecas que permiten su uso. Las expresiones regulares a menudo crean un FSM como parte de su implementación. En general, las expresiones regulares funcionan para elementos no anidados arbitrariamente y para todo lo demás hay un generador de analizador (ANTLR / YACC / LEX). En general, es mucho más fácil mantener una gramática / expresión regular que la máquina de estado subyacente. También dijo que estaba en una pasantía y, en general, podrían ofrecerle un trabajo más fácil que un desarrollador senior, por lo que existe una gran posibilidad de que una expresión regular funcione en la cadena. Además, las expresiones regulares generalmente no se enfatizan en la universidad, así que intente utilizar Google para leer sobre ellas.

Answer 6

Te recomendaría el " Libro del dragón ": Compiladores, Principios-Técnicas-Herramientas de Aho, Sethi y Ullman. (Es bastante caro comprarlo, pero seguro que lo encontrará en una biblioteca). Allí encontrará todo lo que necesite para analizar cadenas y construir autómatas finitos. No hay ningún lugar que pueda encontrar con un goto . Normalmente, los estados son una tabla de datos y las transiciones son funciones como accept_space()

Answer 7

Usaría un generador FSM, como Ragel , si quisiera dejar una buena impresión en mi jefe.

El principal beneficio de este enfoque es que puede describir su máquina de estados a un nivel más alto de abstracción y no necesita preocuparse de si usar goto o un interruptor. Sin mencionar, en el caso particular de Ragel, que puede obtener automáticamente diagramas bonitos de su FSM, insertar acciones en cualquier punto, minimizar automáticamente la cantidad de estados y otros beneficios. ¿Mencioné que los FSM generados también son muy rápidos?

Los inconvenientes son que son más difíciles de depurar (la visualización automática ayuda mucho aquí) y que necesita aprender una nueva herramienta (que probablemente no valga la pena si tiene una máquina simple y no es probable que escriba máquinas con frecuencia). )

Answer 8

Usaría una variable que rastrea el estado en el que se encuentra y un interruptor para manejarlos:

fsm_ctx_t ctx = ...;
state_t state = INITIAL_STATE;

while (state != DONE)
{
    switch (state)
    {
    case INITIAL_STATE:
    case SOME_STATE:
        state = handle_some_state(ctx)
        break;

    case OTHER_STATE:
        state = handle_other_state(ctx);
        break;
    }
}

Answer 9

Usar un goto para implementar una máquina de estado a menudo tiene sentido. Si está realmente preocupado por usar un goto, una alternativa razonable es a menudo tener una variable de state que modifique, y una declaración de switch basada en eso:

typedef enum {s0,s1,s2,s3,s4,...,sn,sexit} state;

state nextstate;
int done = 0;

nextstate = s0;  /* set up to start with the first state */
while(!done)
   switch(nextstate)
      {
         case s0:
            nextstate = do_state_0();
            break;
         case s1:
            nextstate = do_state_1();
            break;
         case s2:
            nextstate = do_state_2();
            break;
         case s3:
             .
             .
             .
             .
         case sn:
            nextstate = do_state_n();
            break;
         case sexit:
            done = TRUE;
            break;
         default:
            /*  some sort of unknown state */
            break;
      }