Pregunta Cómo implementar LOOP en un intérprete de lenguaje similar a FORTH escrito en C


Estoy escribiendo un lenguaje simple basado en pila en C y me preguntaba cómo debería implementar una estructura de bucle de algún tipo y / o símbolos de búsqueda anticipada. Dado que el código es un poco largo para esta página (más de 200 líneas) lo puse en un repositorio GitHub.

EDITAR: El programa principal está en archivo. stack.c.

EDITAR: El código solo toma entrada en words, algo así como FORTH. Usa scanf y trabaja de izquierda a derecha. Entonces usa una serie de ifs y strcmps para decidir qué hacer. Eso es realmente.


5
2017-08-04 22:34


origen


Respuestas:


El enfoque de Forth es agregar una pila de bucles separada junto con la pila de datos. A continuación, define las operaciones que funcionan con esta pila de bucles. Por ejemplo:

5 0 DO I . LOOP

Imprimirá

0 1 2 3 4

La forma en que esto funciona es:

  • DO mueve el índice (0) y el control (5) a la pila de bucles.
  • I copia la parte superior de la pila de bucles a la pila de datos.
  • LOOP incrementa el índice (parte superior de la pila de bucles). Si el índice es menor que el control (uno debajo de la parte superior de la pila de bucles), entonces vuelve a ejecutar los comandos desde DO de regreso LOOP. Si el índice es> =, entonces aparece el índice y el control de la pila de bucles, y el control se reanuda normalmente.

9
2017-08-04 22:44



La forma obvia de agregar estructuras de control a un lenguaje basado en pila es agregar una "pila de control". Describiré el mecanismo Postscript porque eso es lo que sé, pero Forth tiene un comportamiento análogo (con sutiles diferencias, sin duda).

El bucle controlado más simple es el repeat lazo. Técnicamente, un infinito. loop Es más sencillo, pero para usarlo se requiere una explícita. exit Mandar, y explicar que complicaría las cosas.

La sintaxis para repetir es:

int proc  **repeat**  -

Entonces cuando el repeat comando comienza espera encontrar un procedimiento en la parte superior de la pila de operandos (este es el cuerpo del bucle que se ejecutará), y un entero justo debajo del procedimiento (el número de veces para ejecutar el procedimiento).

Como también hay una pila de ejecución (creo que Forth la llama la pila de "retorno"), un comando puede "ejecutar" otros comandos presionándolos en la pila de ejecución, programando así otros comandos que se ejecutarán inmediatamente después de que se termine el comando actual , pero antes de reanudar la llamada del comando actual. Esa es una frase larga, pero la idea clave está ahí.

Como ejemplo concreto, supongamos que el intérprete se está ejecutando desde el flujo de entrada. Y las pilas se ven así:

operand: -empty-
execute: <stdin>

Los tipos de usuario 2 {(Hello World!\n) print} repeat.

El entero 2 se empuja en la pila.

operand: 2
execute: <stdin>

El cuerpo del procedimiento citado (*) se empuja en la pila.

operand: 2 {(Hello World!\n) print}
execute: <stdin>

los repeat comando se ejecuta.

operand: 2 {(Hello World!\n) print}
execute: <stdin> repeat

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push quoted proc on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

La ejecución del procedimiento de repetición (una vez) deja las pilas así:

operand: -empty-
execute: <stdin> repeat {(Hello World!\n) print} 1 **{(Hello World!\n) print}**

El intérprete ejecuta el procedimiento en la parte superior de la pila ejecutiva, imprime "Hello World!", Luego encuentra un número entero que empuja en la pila op.

operand: 1
execute: <stdin> repeat {(Hello World!\n) print}

El intérprete ejecuta un procedimiento de cotización presionando la pila de operaciones.

operand: 1 {(Hello World!\n) print}
execute: <stdin> repeat

¡Y estamos de vuelta al principio! Listo para la siguiente iteración (o terminación si el entero ha caído a cero).

Espero que esto ayude.

Editar;

Después de mirar su código, tengo una sugerencia diferente, tal vez un trampolín hacia algo como lo describí anteriormente. Creo que deberías olvidar el código por un tiempo y enfocarte en las estructuras de datos. Tienes una buena tabla para las variables, ¡pero todos los comandos son literales incorporados dispersos a través del código!

Si hace que su tabla mantenga los tipos de registros variables, puede usar el mismo mecanismo de búsqueda para ambos (e incluso pasar a un hash o un árbol de búsqueda ternario (mi favorito actual)). Tengo en mente algo como esto:

struct object {
    int type;
    union {
        int i;
        void (*command)(context *);
    } u;
};

struct dict {
    int sz;
    struct rec {
        char *key;
        object val;
    }  data[]; //think resizable!
};

De esta manera cada comando va en su propia función. La bonificación es: pequeñas funciones. Debe intentar que sus funciones sean lo suficientemente pequeñas para poder ver todo el contenido en la pantalla al mismo tiempo. Escanear todo de una vez permite que su cerebro derecho realice parte del trabajo de detección de áreas problemáticas.

Entonces necesitarás otro tipo para mantener secuencias de comandos. Una matriz o lista debería funcionar. Cuando puedes definir secuencias, puedes repetir secuencias mucho más fácilmente.

La ventaja aquí es que solo estás a una construcción de Turing Complete. Secuencias, iteraciones, decisiones (o selección): ¡eso es todo lo que necesita para programar cualquier función computable!


*. Como descubrió el comentarista, Postscript en realidad no tiene el mismo concepto de citando que uso aquí en mi descripción. Aquí estoy tomando prestado el concepto de la terminología de Lisp. Postscript tiene en su lugar una literal / ejecutable bandera que se puede configurar cvx  cvlit o probado xcheck. Se ejecutará una matriz ejecutable en la pila de ejecución. Así que para el cuerpo-procedimiento "citado", en realidad es un literal procedimiento-cuerpo (es decir, una matriz). Debido a esto, repeat También debe empujar una llamada a cvx Para ser ejecutado antes de la siguiente iteración. Por lo tanto, un pseudocódigo más correcto para la implementación postscript de repeat es:

Repeat: expects operands: int proc
    if int<0 Error
    if int==0 return //do nothing
    push `repeat` itself on exec stack
    push 'cvx' on the exec stack
    push cvlit(proc) on exec stack
    push int-1 on exec stack
    push "executable" proc on exec stack

Esto realiza los cambios de bandera necesarios para pasar el procedimiento como datos en la pila de ejecución.

Otra forma en que he visto implementada esta estructura de control es con dos funciones, repeat el mismo punto de entrada y un operador de continuación interno que en teoría no necesita un nombre. Creo que ghostscript lo llama algo así como @ repeat-continue @. Con una función de continuación separada, no tiene que ser tan cuidadoso con el orden de las cosas en la pila, y no necesita manipular el literal bandera. En su lugar, puede almacenar algunos datos persistentes abajo la llamada recursiva en la pila exec; Pero tienes que limpiarlo también.

Así que una alternativa repeat sería:

int proc  **repeat**  -
    if int<0 Error
    if int==0 return //do nothing
    push null on exec stack   <--- this marks our "frame"
    push int-1 on exec stack
    push proc on exec stack
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

La continuación también tiene un trabajo más simple.

@repeat-continue
    peek proc from exec stack
    peek int from exec stack
    if int==0 clear-to-null and return
    push '@repeat-continue' on exec stack
    push executable proc on exec stack

Finalmente, el exit el operador está íntimamente conectado a los bucles, borra la pila de ejecutivos hasta el "marco" del operador de bucle. Para el estilo de 2 funciones, este es un null objeto o similar. Para el estilo de 1 función, este es el propio operador de bucle.


6
2017-08-05 05:31



Su lenguaje no tiene nada que ver con Forth, así que no copie las estructuras de bucle de Forth (solo compilación, una distinción sin sentido para su idioma).

Mirando su código, agregue until como una palabra de reinicio-evaluación condicional. Es decir, agrégala como una palabra normal junto a tu range y jump, pídale que haga estallar la pila, y si la parte superior de la pila era verdadera, establezca stack.c's cmd De regreso al principio.

0
dup . 1 + dup 5 > until
.

, en tu idioma, producirá la salida. 0 1 2 3 4 5 6, a lo largo de tres evaluaciones, y reevaluando la segunda línea varias veces. Esto supone que usted preserva el estado en todas las evaluaciones y que la evaluación está orientada a la línea. Usted podría minar LSE64 Para más ideas como esta.


2
2017-08-05 02:32



Aquí hay una publicación de blog en la que DO / LOOP, BEGIN / UNTIL, WHILE / REPEAT, etc. están implícitos en mi pequeño proyecto TransForth: http://blogs.msdn.com/b/ashleyf/archive/2011/02/06/loopty-do-i-loop.aspx

Sin embargo, desde entonces he cambiado de opinión y confío totalmente en la recursión sin palabras semejantes.

Espero que ayude, diviértete!


1
2017-08-09 21:34