Algoritmo para reescribir la semántica de goto modificada

Question

Tengo un gran grupo de código heredado en un antiguo lenguaje de scripts auto-concebido que compilamos/traducimos a javascript.

Ese idioma tiene un salto condicional, saltando a una etiqueta. La diferencia con la declaración goto común es que no son posibles saltos hacia atrás. No hay sentencias if anidadas ni bucles en ese idioma.

Como goto no existe en javascript, estoy buscando un algoritmo que transforme goto mylabel y mylabel: en una estructura semánticamente equivalente.

Pensé en usar ifs pero no me pareció trivial debido a la anidación arbitraria de las etiquetas goto.

Ejemplo:

if cond1 goto a 
do something1 
if cond2 goto b 
do something2 
a: 
do something3 
if cond3 goto c 
do something4 
c: 
do something5 
b: 

podría reescribirse como:

lbl_b=false; 
lbl_c=false; 

lbl_a = cond1; 
if (!cond1) { 
    do something1; 
    lbl_b = cond2; 
    if (!lbl_b) { 
    do something2; 
    } 
} 
if (!lbl_b) { 
    do something3; 
    lbl_c = cond3; 
    if (!lbl_c) { 
    do something4; 
    } 
    do something5; 
} 

Sin embargo, no fue capaz de derivar un algoritmo general de eso.

Answer 1

Esto generalmente se llama Goto Remoción, tuvimos una vez un estudiante trabajo donde la tarea era implementarlo para C. En general, tienes que trabajar con bucles (lamentablemente no pusimos ese trabajo en línea). Pero como tiene la restricción de que solo puede avanzar, es relativamente fácil:

Analice una vez todas las líneas y recopile todas las etiquetas. Crea para cada etiqueta una bandera "skip_to_label". Inicialice al principio todas las banderas en falso. Cuando cumpla con el goto condicional para la etiqueta X, antepondrá cada línea, hasta la línea de la etiqueta con "if not skip_to_label" y establecerá el indicador en verdadero.

Esto ya debería ser suficiente y funciona, pero por supuesto no es muy óptimo.

Cómo puede optimizarlo: en lugar de preparar el if, simplemente mantenga un conjunto de indicadores para cada línea, y en lugar de establecer algo en falso, simplemente agregue para las líneas el indicador corrosponding en el conjunto.

Ahora puede hacer lo mismo para un grupo que contiene todas las líneas, donde el conjunto no cambia, y la condición son las banderas booleanas del conjunto.

Ejemplo con su código dado:

set     your code 
empty     if cond1 goto a 
skip_to_a,    do something1 
skip_to_a,    if cond2 goto b 
skip_to_a, skip_to_b do something2 
skip_to_a, skip_to_b a: 
skip_to_b    do something3 
skip_to_b, skip_to_c if cond3 goto c 
skip_to_b, skip_to_c do something4 
skip_to_b, skip_to_c c: 
skip_to_b    do something5 
skip_to_b    b: 

Ahora se escribe delante de cada línea, ya sea el caso (s) o se inicia en la parte superior y crea un bloque if, siempre y cuando el conjunto se mantiene igual .

Así que cuando se empieza a obtener su primera en vacío, es un Goto condicional así que en lugar configura su bandera

if cond1 goto skip_to_a=true; 

ahora los cambios en los reglajes, y presentarle su bloque con el caso del conjunto:

if (!skip_to_a) BEGIN 
    do something1 
    if cond2 skip_to_b=true; 
    END 

siguiente cambio en el conjunto, por lo que si el bloque nuevo:

if (!skip_to_a and !skip_to_b) BEGIN 
    do something2 
    END 

y así sucesivamente (te supongo ge ahora la idea).

EDITAR: Como se puede ver muy bien con los sistemas en el ejemplo que en general no es posible modelar con ifs anidados, como por ejemplo, las líneas con skip_to_a y las que tienen skip_to_b se superponen, pero ninguna contiene la otra completa.

Answer 2

que podría hacer algo así como el seguimiento del estado de Goto en un bucle while, pero no se vería demasiado bonita:

var goto = null ; 

do { 
    if(goto == null && cond1) goto = 'a' ; 
    if(goto == null) do_something(1) ; 
    if(goto == null && cond2) goto = 'b' ; 
    if(goto == null) do_something(2) ; 
    if(goto == null || goto == 'a') goto = null; 
    if(goto == null) do_something(3) ; 
    if(goto == null && cond3) goto = 'c' ; 
    if(goto == null) do_something(4) ; 
    if(goto == null || goto == 'c') goto = null ; 
    if(goto == null) do_something(5) ; 
    if(goto == null || goto == 'b') goto = null ; 
} while(goto != null) 

Answer 3

Compilación a otro idioma suele ser más difícil de lo necesario. Un método más simple sería, no compilar al otro idioma, sino interpretar el código en javascript. De esta forma, sería fácilmente posible generar su declaración de goto con cualquier tipo de semántica que desee.

Sin embargo, si lo hace así, tendría que mover toda la lógica de análisis en su código de JavaScript, lo que podría ser feo. Otro método sería para compilar un formato más fácil de interpretar, es decir, el código de bytes, por lo que se puede calcular previamente todo lo que necesita desde el analizador, todas las posiciones de la etiqueta etc.

Answer 4

Una solución alternativa sería convertir cada etiqueta en un método que contenga el código desde el inicio de esa etiqueta hasta el comienzo de la siguiente etiqueta, seguido de una llamada a la función generada para la siguiente etiqueta.

El pro para esto es que un goto puede ser reemplazado por una simple llamada a un método. El inconveniente es que, para scripts largos o bucles, puede terminar con grandes cantidades de llamadas.

Usando este método, un simple algoritmo sería:

goto_label_count := 0 // Find out how many methods we need to generate 
For each line: 
    if line is goto 
     goto_label_count := goto_label_count + 1 

Write function head 
Write "goto0();" 

goto_count := 0 // Generate code 
For each line: 
    if line is goto 
     if goto_count > 0 
      write "goto"+goto_count+"();" // produce call to last goto found 
     write function header for corresponding goto //("goto"+goto_count+"()") 
     goto_count := goto_count + 1 
    else 
     translate normally 
Generate end of code 

Esto puede llegar a causar problemas adicionales. Por ejemplo, ¿qué hay de alcance para las variables? Pero, al menos, es un enfoque alternativo que espero que haga que tu mente comience a lo largo de más pistas. ;)