I did an interpreter in an '84 recently.

I stored the commands and parameters in the EEPROM area, as
(command)(parm)(parm)....
Each command may have zero, one or N bytes of paramter
I used a register to point to the current command. (0-63 bytes)
I also have an "execute/scan" flag

Starting from reset, the first command is in byte zero, so I load that
value from EEPROM, and then jump to the command engine, with the execute
flag set to execute.

In the execute mode, the command engine simply uses the parm bytes, does
it's thing, and exits with the pointer set to the next command, which of
course follows the first (and it's parms) immediately.

Scan only becomes useful when you branch. I used a simple "skip"
command, followed by the number of commands to skip. Some other commands
also caused branching, like "Skip N if input is active" where N could be
+ or -

In order to branch forward, we simply scan commands until we locate the
Nth command. Starting wherever we currently are, we set a register to
the number of commands to skip, and look at the next command (This is
always the next byte in EEPROM, as the current command would have
interpreted it's parms already.) We set the execute/scan flag to scan,
and call the appropriate command engine. Each command engine knows
wether the command has a parameter, and how long it is. In the case of a
variable length command parm, then the command engine scans forward till
it finds a null (end of parm marker) and returns the address of the next
command (null address +1) In the case of fixed length commands, it
simply increments the pointer and returns.
After each command returns, we decrement the skip register, and when it
is zero, we set the execute/scan flag to execute, and call the next
command.

Branching in reverse is a little more interesting, actually, you can't,
because the parms are variable length. How would you know to find the
previous command? (Without wasting memory on flags!)

What I did to implement this is to dedicate another register to hold the
current command number.
This is incremented during scan or execute. When I encounter a negative
skip, then I subtract the appropriate number from the current command
register, set thc scan/execute flag to scan, and then start from zero
and scan forward to command X-N, and set the scan/execute flag back to
execute, and carry on.

The commands are sanity checked, in that any address that's outside the
EEPROM causes a reset to zero. Something like Skip -10 at command 5
would be trapped this way, without the skip command engine having to
test the parm for positional sanity.

The parms are the responsibility of the command engines, and in this
implementation, I relied on a PC loader program to convert user input to
binary, and to sanity-check the values, so the command engines simply
"shut up and soldier"

I wedged this interpreter engine, an ASCII to morse converter, and a
bunch of fun commands, a uart (to talk to the loader) all into an '84.
You can see the docs for this system at www.agrelo.com/upll.html