use strict;
# Translates a push-down automaton into a Splinter program.
# The first line gives the input to the PDA, as a sequence of
# characters each of which is either 0 or 1. (Splinter has no way to
# accept input, so the input is compiled literally into the program in
# the N splinter.)
# The rest of the program is a set of states, of the form
# number command if0 if1
# The number is the state number (must start at 0 for the first state,
# and increment from there); the if0, if1 and ifempty are the states
# to switch to if there are a 0 or 1 at the top of stack respectively,
# and there are five commands available:
# 0 push a 0
# 1 push a 1
# , push one bit of input (doesn't push anything on EOF)
# ! pop one bit
# . pop one bit and output it
# The states if0, if1 and ifempty depend on what is TOS after the
# command (if any) is run. The stack starts empty, and the program
# ends when the stack is empty at the end of a command (as there is no
# way to continue); trying to output or pop an empty stack does
# nothing (but the program will end immediately afterwards because the
# stack will be empty). Comments after # on a line are accepted.
# The program works by compiling the program to a six-splinter
# program. (Using fewer splinters is likely to be possible.)
# The code for the states are stored using Z, A, and B, like this:
# ZA state 0
# ZBA state 1
# ZBBA state 2
# and so on. (It could be made more efficient using Huffman coding,
# but that would make the compiler more complex.)
# Input is stored in N, and O and I represent 0 and 1 on the stack.
# Example program (that does paren matching of 1 and 0):
# 1101011000 # The input string (this can be easily changed)
# 0 1 1 1 # Start with a 1 as an end-of-stack marker
# 1 0 2 2 # Push a 0 to help us detect EOF
# 2 1 3 3 # and a 1 to help us detect EOF
# 3 , 9 4 # Read one bit of input
# 4 ! 6 5 # The stack is (top)0 on EOF, (top)10 on non-EOF now
# 5 ! 1 1 # not EOF: repeat with an extra 0 on the stack
# 6 ! 7 7 # Pop the stack; there's now 0 on top for error or 1 on top if right
# 7 . 8 8 # Write out 1 for success, or 0 for failure
# 8 ! 8 8 # Quit by looping until there's an empty stack
# 9 ! 10 10 # Stack is now (top)10 00...00 1
# 10 ! 11 11 # Stack is now (top)0 00...00 1
# 11 ! 2 12 # Loop again removing one 0 if there were 0s
# 12 0 7 7 # Error out (0 when there were no 0s in the 00...0)
undef $/;
$_=<>;
s/\#.*$//gm; # remove comments
s/\s*$//gm; # and trailing whitespace
m/^\n/s and die "At least one character of input must be given";
m/^[01]+\n/s or die "Input must consist only of 0 and 1";
my @lines = split /\n/;
# Generate the input independently from everything else to prove that
# I'm not cheating by preevaluating the program
my $inputstr = "N{}";
my @inchars = split //, shift @lines; # get the input string
$inputstr = "N{$inputstr}" . pop @inchars while scalar(@inchars);
$inputstr =~ s/1/I/g;
$inputstr =~ s/0/O/g;
# Generate code for each state separately
my $statenum = 0;
my @states;
for $_(@lines)
{
my ($i,$o);
m/^$/ and next; # ignore blank lines
m/^(\d+) ([01!,.]) (\d+) (\d+)$/ or die "Invalid line '$_' in program";
$1 == $statenum or die "State numbers are not in sequence";
$o = 'Z' . ('B'x$3) . 'AO';
$i = 'Z' . ('B'x$4) . 'AI';
$2 eq '0' and $states[$statenum]=$o
or $2 eq '1' and $states[$statenum]=$i
or $2 eq '!' and $states[$statenum]="O{O{$o}I{$i}}I{O{$o}I{$i}}"
or $2 eq ',' and $states[$statenum]="O{$o}I{$i}N"
or $2 eq '.' and $states[$statenum]="O{\\0O{$o}I{$i}}I{\\1O{$o}I{$i}}"
or die '$2 has become invalid during and/or/and sequence';
$statenum++;
}
# Compress all the states into three splinters
my $statesplinters="A{}";
$statesplinters = "B{$statesplinters}A{" . (pop @states) . "}"
while scalar(@states);
print "N{$inputstr}Z{$statesplinters}ZA\\\n";