Implementing goto in ast

Question

Background: As a short project over the winter break, I am trying to implement a programming language called Ax (designed for graphing calculators) using Python and PLY. Short note: the language only allows global variables and uses pointers heavily.

I am trying to implement goto in this language but don’t know how to do it.

My general method is to first use PLY to parse the code in ast, and then go through it, performing when I go.

For example, the statement

If 3 Disp 4 Disp 6 End 

... will turn into ...

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

... which I would do recursively (I added padding for readability).

Since ast is a tree, I'm not sure how to jump between different nodes. I suggested that perhaps converting the tree to a flat-ish array ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]] so that I can use the array indices flat-ish to go to specific lines of code, but it doesn’t seem to have a certain elegance and almost feels like a step back (although I could be wrong).

I looked through this one but couldn't figure out how it works.

Any help or tips would be appreciated.

Answer 1

"execute recursively" is not suitable for goto . For goto to work, you need a PC, a “program counter,” and each operator in your program must have a separate address. As it is completed, the address of each operator is assigned to the PC. When goto is encountered, the goto destination address (its argument) is placed on the PC, and execution resumes from there.

This is almost impossible to achieve with a recursive stack based approach. You have two options:

• Flatten your AST in a sequence where you can assign a separate address for each operator

• Add a skip mode to your interpreter. When goto occurs, throw a GotoException that breaks out of all the frames of the stack and returns to the root. Process statements (skip them without execution) until you reach the destination address.

I think you can imagine that this goto implementation is not very efficient and probably fragile to implement.

Answer 2

I thought it might be converting the tree to a flat array ... but this does not seem to have a certain elegance and almost looks like a step back (although I could be wrong).

You are wrong. Machine code is always flat. Languages ​​like C flatten to create machine code.

The calculator (like other simple machines) is flat.

However. Aligning the AX syntax tree is not completely necessary.

You just need to apply the labels of the programming source to each node in your tree.

Then "GOTO" simply searches for a tree for this label and resumes execution on that label.

Answer 3

You can also flatten AST to a directed graph (control flow graph). An example of how this can be done to create a networkx graph that can go through the interpreter can be found here . Note that you will need to write some AST classes for this purpose.