Implementando goto en un ast

Antecedentes: Como un proyecto corto durante las vacaciones de invierno, estoy tratando de implementar un lenguaje de programación llamado Ax (diseñado para las calculadoras gráficas) usando Python y PLY. Una breve nota: el lenguaje solo permite variables globales y hace un uso intensivo de los punteros.Implementando goto en un ast

Estoy tratando de implementar goto en este idioma, pero no tengo ni idea de cómo hacerlo.

Mi método general es utilizar primero PLY para analizar el código en un ast, luego recorrerlo ejecutando sobre la marcha.

Por ejemplo, la declaración

If 3 
    Disp 4 
    Disp 6 
End

... se convertiría en ...

['PROGRAM', 
    ['BLOCK', 
    ['IF', 
     ['CONDITION', 3], 
     ['BLOCK', 
     ['DISP', 4], 
     ['DISP', 6] 
     ] 
    ] 
    ] 
]

... que se lo ejecute de forma recursiva (I añaden guiones para facilitar la lectura).

Como ast es un árbol, no estoy seguro de cómo saltar entre diferentes nodos. He considerado tal vez la conversión del árbol a una matriz plana ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]] para que pueda usar los índices de la matriz plana para ir a líneas específicas en el código, pero esto parece carecer de cierta elegancia y casi se siente como una dar un paso atrás (aunque podría estar equivocado).

Miré this, pero no pude entender cómo funcionó.

Cualquier ayuda o sugerencia sería apreciada.

Fuente

2011-12-27 Michael0x2a

"Jump"? ¿Qué crees que quieres decir con "Jump"? ¿Por qué "saltar" entre los nodos? Proporcione un ejemplo específico donde "saltaría" a un nodo arbitrario. Es difícil encontrar una necesidad sensata de un salto en un lenguaje basado en árboles. –

El lenguaje que elijo implementar contiene declaraciones goto. Quería hacer coincidir las especificaciones, por lo que necesito ir a Goto. Hice esto basado en el árbol porque parecía algo sensato hacer en ese momento. Supongo que fue un error: ¿qué otras formas de idiomas hay? – Michael0x2a

AX realmente * requiere * un GOTO? Parece extraño. Hay un número infinito de "formas" de idiomas: procedurales, funcionales, etc., etc. Entre los lenguajes de procedimiento, Python y Java (entre otros) no tienen GOTO. Es algo bastante raro. –

"ejecutar recursivamente" no encaja bien con goto. Para que goto funcione, necesita una PC, un "contador de programa" y cada declaración en su programa debe tener una dirección distinta. A medida que se ejecuta, la dirección de cada declaración se asigna a la PC. Cuando se encuentra goto, la dirección de destino del goto (su argumento) se coloca en la PC y la ejecución se reanuda desde allí.

Esto es casi imposible de lograr con un enfoque recursivo basado en la pila. Tiene dos opciones:

aplanar su AST en una secuencia donde se puede asignar una dirección distinta a cada declaración
Añadir un modo de "saltar" a su intérprete. Cuando se encuentra goto, arroje un GotoException que se rompe de todos los marcos de pila y vuelve a la raíz. Procesar declaraciones (omitirlas sin ejecutarlas) hasta llegar a la dirección de destino.

creo que se puede imaginar que esta implementación de goto no es de buen calidad y probablemente frágil para poner en práctica.

Fuente

2011-12-27 08:40:42

Ok, ¡gracias por las sugerencias! Creo que voy a ir aplanando el árbol. – Michael0x2a

He considerado tal vez la conversión del árbol a una matriz plana ... pero esto parece carecer de cierta elegancia y casi parece un paso atrás (aunque podría estar equivocado).

Usted está equivocado. El código de máquina siempre es plano. Los idiomas como C se aplanan para crear código de máquina.

Una calculadora (como otras máquinas simples) es plana.

Sin embargo. Aplanar su árbol de sintaxis AX no es completamente necesario.

Simplemente necesita aplicar las etiquetas de fuente de programación a cada nodo de su árbol.

Luego, un "GOTO" simplemente busca en el árbol esa etiqueta y reanuda la ejecución en esa etiqueta.

Fuente

2011-12-27 17:49:18

Ah, buen punto sobre el código de máquina. Supongo que me equivoqué al respecto :) – Michael0x2a

Como el código de máquina es plano, no lo usamos a menudo para programar en la actualidad. Preferimos los lenguajes estructurados y las herramientas de uso para aplanar un lenguaje agradable y estructurado en el mundo plano de la ejecución de la máquina. –

También puede aplanar el AST en un gráfico dirigido (el gráfico de flujo de control). Se puede encontrar un ejemplo de cómo se puede hacer esto para producir un gráfico networkx que puede recorrer el intérprete here. Tenga en cuenta que tendrá que escribir algunas clases de AST para ese fin.

Fuente

2015-03-27 09:47:41

Respuesta

Cuestiones relacionadas