8

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.

Community
  • 1
  • 1
Michael0x2a
  • 58,192
  • 30
  • 175
  • 224
  • "Jump"? What do you think you mean by "Jump"? Why would you "jump" between nodes? Please provide a specific example where you would "jump" to an arbitrary node. It's difficult to find a sensible need for a jump in a tree-based language. – S.Lott Dec 27 '11 at 12:12
  • The language I'm choosing to implement has goto statements in it. I wanted to match the spec, which is why I need goto. I made this tree-based because it seemed like a sensible thing to do at the time. I'm guessing that was a mistake: what other forms of languages are there? – Michael0x2a Dec 27 '11 at 17:38
  • AXE really *requires* a GOTO? Seems odd. There an infinite number of "forms" of languages: procedural, functional, etc., etc. Among procedural languages, Python and Java (among others) have no GOTO. It's a pretty rare thing. – S.Lott Dec 27 '11 at 17:41
  • AST is good at compiling, not at evaluation. Except `goto` there are other problem - loops. How you want to implement loops without some sort of program counter? – werewindle Dec 27 '11 at 18:04
  • It's a low level language. Also, I implemented loops earlier by using a 'while' loop. – Michael0x2a Dec 29 '11 at 16:45

3 Answers3

8

"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.

Aaron Digulla
  • 321,842
  • 108
  • 597
  • 820
3

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.

S.Lott
  • 384,516
  • 81
  • 508
  • 779
  • Ah, good point about the machine code. I guess I was wrong about that then :) – Michael0x2a Dec 29 '11 at 16:48
  • Because machine code is flat, we don't use it often for programming nowadays. We prefer structured languages and use tools to flatten a nice, structured language into the flat world of machine execution. – S.Lott Dec 29 '11 at 16:50
0

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 in the Python package promela. Note that you'll have to write some AST classes for that purpose.

0 _
  • 10,524
  • 11
  • 77
  • 109