Implementing goto in an ast

Question

Background: As a short project over winter break, I'm trying to implement a programming language called Axe (designed for graphing calculators) using Python and PLY. A brief note: the language allows only global variables and makes heavy use of pointers.

I'm trying to implement goto in this language, but have no idea how to do it.

My general method is to first use PLY to parse the code into an ast, then walk through it executing as I go.

For example, the statement

If 3
    Disp 4
    Disp 6
End

...would turn into...

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

...which I would execute recursively (I added indents for readability).

Because the ast is a tree, I'm not sure how to jump between different nodes. I've considered perhaps converting the tree to a flat-ish array ['IF', ['CONDITION', 3], ['DISP', 4], ['DISP', 6]] so that I can use the indices of the flat-ish array to go to specific lines in the code, but this seems to lack a certain elegance and almost feels like a step backwards (although I could be wrong).

I've looked at this, but was unable to understand how it worked.

Any help or hints would be appreciated.

Answer 1

"execute recursively" doesn't fit well with goto. For goto to work, you need a PC, a "program counter" and each statement in your program must have a distinct address. As it is executed, the address of each statement is assigned to the PC. When goto is encountered, the target address of the goto (it's argument) is put into the PC and the execution resumes from there.

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

• Flatten your AST into a sequence where you can assign a distinct address to each statement

• Add a "skip" mode to your interpreter. When goto is encountered, throw a GotoException which breaks out of all of the stack frames and goes back to the root. Process statements (skip them without executing) until you reach the target address.

I think you can imagine that this implementation of goto isn't very performant and probably brittle to implement.

Answer 2

I've considered perhaps converting the tree to a flat-ish array ... but this seems to lack a certain elegance and almost feels like a step backwards (although I could be wrong).

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

A calculator (like other simple machines) is flat.

However. Flattening out your AXE syntax tree is not completely necessary.

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

Then a "GOTO" simply searches the tree for that label and resumes execution at that label.

Answer 3

You can also flatten the AST to a directed graph (the control flow graph). An example of how this can be done to produce a networkx graph that can be traversed by the interpreter can be found here. Note that you'll have to write some AST classes for that purpose.