I really like your conversion from the stack-based code to the graphical format. One suggestion though: You don't show the stack-based code for the graph shown, so it's not as easy as one would like to see how they tie together.

As far as code pointers go, I'll leave that to monks better-versed in Perl than I.

Anyway, on to your other question: Assuming that by "conventional code" you mean a more algebraic form, then here's my take on it:

The most trivial form is to build it by parenthesizing every expression as you encounter it. Suppose, for example, you have the following bit of code:

[1] push 3
[2] push 5
[3] add
[4] push 7
[5] push 9
[6] add
[7] mul
[8] print
[download]

#!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack] : '-nil-') . "', "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($operator eq 'push') {
                push @stack, $operand;
        }
        elsif ($operator eq 'print') {
                print "out: '" . (pop @stack) . "'\n";
        }
        elsif ($operator eq 'add') {
                my $lhs = pop @stack;
                my $rhs = pop @stack;
                push @stack, '(' . $lhs . ' + ' . $rhs . ')';
        }
        elsif ($operator eq 'mul') {
                my $lhs = pop @stack;
                my $rhs = pop @stack;
                push @stack, '(' . $lhs . '*' . $rhs . ') ';
        }
}
__DATA__
push 3
push 5
add
push 7
push 9
add
mul
print
[download]

root@swill ~/PerlMonks
$ ./stack_to_infix.pl
TOS='-nil-', stmt = 'push 3'
TOS='3', stmt = 'push 5'
TOS='5', stmt = 'add'
TOS='(5 + 3)', stmt = 'push 7'
TOS='7', stmt = 'push 9'
TOS='9', stmt = 'add'
TOS='(9 + 7)', stmt = 'mul'
TOS='((9 + 7)*(5 + 3)) ', stmt = 'print'
out: '((9 + 7)*(5 + 3)) '

root@swill ~/PerlMonks
$
[download]

--roboticus

bsb:

OK ... I've toyed around with the code and did a version with the extra parenthesis removal. Here ya go:

#!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

sub binop {
        my $op = shift;
        my $prec = shift;

        my $lh = pop @stack;
        my ($lhop, $lhprec) = ($$lh[0], $$lh[1]);

        my $rh = pop @stack;
        my ($rhop, $rhprec) = ($$rh[0], $$rh[1]);

        # Wrap operand(s) with lower precedence
        $lhop = '(' . $lhop . ')' if $prec > $lhprec;
        $rhop = '(' . $rhop . ')' if $prec > $rhprec;

        push @stack, [ $lhop . $op . $rhop, $prec ];
}

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($operator eq 'push') {
                # A constant is atomic, so it has high precedence so
                # we don't wrap it
                push @stack, [$operand, 999];
        }
        elsif ($operator eq 'print') {
                my $op = pop @stack;
                my ($operand, $prec) = ($$op[0], $$op[1]);
                print "out: '" . $operand . "'\n";
        }
        elsif ($operator eq 'add') {
                binop '+', 1;
        }
        elsif ($operator eq 'mul') {
                binop '*', 2;
        }
}
__DATA__
push 3
push 5
add
push 7
push 9
add
mul
print
[download]

Which gives us:

root@swill ~/PerlMonks
$ ./stack_to_infix2.pl
TOS='-nil-' stmt = 'push 3'
TOS='3' stmt = 'push 5'
TOS='5' stmt = 'add'
TOS='5+3' stmt = 'push 7'
TOS='7' stmt = 'push 9'
TOS='9' stmt = 'add'
TOS='9+7' stmt = 'mul'
TOS='(9+7)*(5+3)' stmt = 'print'
out: '(9+7)*(5+3)'

root@swill ~/PerlMonks
$
[download]

--roboticus

P.S. I don't like my code for getting arguments off the stack, but all my attempts at simplifying it failed miserably. I'm sure it's something simple, but I haven't figured it out. What's a better way to do the following? (Or is my problem a bit earlier and I'm pushing the wrong thing on the stack?)

    my $op = pop @stack;
    my ($operand, $prec) = ($$op[0], $$op[1]);
[download]

How about

my ($operand, $prec) =
   map { $_->[0], $_->[1] }
   pop @stack;
[download]

It seems to do what you want.

Cheers,

JohnGG

OK ... now for a quick round of golf. Here's a version that's a bit tighter and easier to expand:

#!/usr/bin/perl -w
use strict;
use warnings;

my @stack = ();

sub binop {
        my ($op,   $prec)   = @_;
        my ($rhop, $rhprec) = @{pop @stack};
        my ($lhop, $lhprec) = @{pop @stack};

        # Wrap operand(s) with lower precedence
        $lhop = '(' . $lhop . ')' if $prec > $lhprec;
        $rhop = '(' . $rhop . ')' if $prec > $rhprec;

        push @stack, [ $lhop . $op . $rhop, $prec ];
}

my %handlers = (
        'push'  => sub { push @stack, [shift, 999]; },
        'print' => sub { print "out: '" . ${@{pop @stack}}[0] . "'\n";
+ },
        'add'   => sub { binop '+', 1; },
        'mul'   => sub { binop '*', 2; }
);

while (<DATA>) {
        chomp;

        print "TOS='" . (@stack ? $stack[$#stack][0] : '-nil-') . "' "
        .       "stmt = '" . $_ . "'\n";

        my ($operator, $operand) = split;
        if ($handlers{$operator}) {
                $handlers{$operator}->($operand);
        }
        else {
                print "Unknown operator: '$operator' for line '$_'\n";
        }
}
__DATA__
push 3
push 5
add
push apples
add
push oranges
push 9
push bananas
push peels
mul
add
add
mul
print
[download]

Which gives us:

TOS='-nil-' stmt = 'push 3'
TOS='3' stmt = 'push 5'
TOS='5' stmt = 'add'
TOS='3+5' stmt = 'push apples'
TOS='apples' stmt = 'add'
TOS='3+5+apples' stmt = 'push oranges'
TOS='oranges' stmt = 'push 9'
TOS='9' stmt = 'push bananas'
TOS='bananas' stmt = 'push peels'
TOS='peels' stmt = 'mul'
TOS='bananas*peels' stmt = 'add'
TOS='9+bananas*peels' stmt = 'add'
TOS='oranges+9+bananas*peels' stmt = 'mul'
TOS='(3+5+apples)*(oranges+9+bananas*peels)' stmt = 'print'
out: '(3+5+apples)*(oranges+9+bananas*peels)'
[download]

--roboticus

You don't show the stack-based code for the graph shown, so it's not as easy as one would like to see how they tie together

Actually, most of the operations do something to the stack, sometimes conditionally, and the textual description is the only source of information. I suppose that I could add some notation like "-2" for something that pops two items. I'll think about your suggestion.

Thanks for the conversion code, I thought that I'd be bumping into the Halting Problem but maybe your technique would work for most or even all of the VDBE code encountered in practice. There are loops, conditionals and off-stack state used by the opcodes so I think the Halting Problem is lurking there somewhere.

create table tape (cur_state, scanned, write, move, next_state);
[download]