# BrainF*#& interpreter in sed V1.0
# Edward Rosten 2001
#
# The BF code is read as the first input line.
#
# Brainf*!@# is a very simple structured language.
#
# It consists of a data space with a data pointer p, and a program containing
# a selection of the 8 commands avaliable. The data space consists of a linear
# set of bytes. In the original implementation there were 30,000 of these. In
# this implementation, they are added as needed. the commands are:
#
# + increment the byte at location p
# - decrement the byte at location p
# > increment p
# < decrement p
# . Output p
# , read input in to p
# [ start a loop if trhe value at p is nonzero
# ] jump back to the corresponding [
# The following description was extracted from
# http://www.muppetlabs.com/~breadbox/bf/
#
# If p is of type char**, BF translates in to C thus:
# > becomes ++p;
# < becomes --p;
# + becomes ++*p;
# - becomes --*p;
# . becomes putchar(*p);
# , becomes *p = getchar();
# [ becomes while (*p) {
# ] becomes }
# This interpreter has several limitations:
#
# The I/O commands . and , can not output or input bytes directly as in genuine
# BF. They output or input bytes as a pair of hex digits, one pair per line.
# This doesn't mean it isn't turing-complete any more, it just means it is even
# useful.
#
# To keep track of loops, it preprocesses the program and puts a numeric tag at
# the beginning and end of each loop. Currently, this is a 1 byte tag, so the
# interpreter can have a maximum of 256 loops in any one program.
################################################################################
################################################################################
################################################################################
################################################################################
# The interpreter can deal with loops nested up to 255 deep. It keeps track
# of the loops by appending a unique number after corresponding [ and ]
# Commands. This is performed in the preprocessing stage.
#Since (for speed in processing) each [ has a unique number, the interpreter can
#only deal with a total of 255 ['s in a program. This can easily(?) be inceased
#by making the [ counter have 4 digits instead of 2.
#During preprocessing, the program takes the following format:
#ln{...#...}stack
#The loop number is incremented each time a [ is encountered.
#The stack contains a list of loop numbers. The top of the stack (the leftmost
#item) refers to the innermost loop.
#In the preprocessor, the current item is the one after the `#'
s/.*/00{#&}/
:preprocessor
#Check for garbage:
/#[][+<>,.-]/ !{
p
s/.*#\(.\).*/Error: Spurious character `\1' found in input!/
q
}
/#\[/ b found_open
/#]/ b found_close
#If nothing of interest was found, then step through the loop:
s/#\(.\)\(.*\)/\1#\2/
#if we're not at the end, continue the loop...
:end_prep_loop
/#}/ !b preprocessor
# Remove the accounting information:
s/.*{\(.*\)#}.*/\1/
b interpreter
################################################################################
#
# Preprocessor functions
#
################################################################################
################################################################################
#
# Implement found_open. This appends the counter to the stack and increments the
# counter
#
:found_open
#Append the counter to the stack:
s/\(..\).*/&\1/
#Append the counter just after #[, also move the # on.
s/\(..\)\(.*\)#\[\(.*\)/\1\2[\1#\3/
# Add 1 to the lowest digit of the counter.
h
s/.\(.\).*/\1/
y/0123456789ABCDEF/123456789ABCDEF0/
x
G
s/\(.\).\(.*\)\n\(.\)/\1\3\2/
#If this digit is zero, add one to the next digit
/^.0/ !b end_prep_loop
h
s/\(.\).*/\1/
y/0123456789ABCDEF/123456789ABCDEF0/
x
G
s/^.\(.*\)\n\(.\)/\2\1/
b end_prep_loop
################################################################################
#
# implement found_close. This apends the last value on the stack to after the
# current ] and removes the top (leftmost item) from the stack. It also moves
# the # onwards.
#
:found_close
s/^\(.*\)#]\(.*\)\(..\)/\1]\3#\2/
b end_prep_loop
################################################################################
#
# The following is the main program interpreter loop
#
################################################################################
# The # indicates the pointer in the program.
# The @ seperates the program from the data
# The ! indicates the pointer in the data
# The + indicates the end of the data
:interpreter
s/.*/#&@!00%/
:main
#Split apart the program and extract the command and put it at the end.
s/.*#\(.\).*/&\1/
/+$/ b add
/-$/ b sub
/>$/ b right
/<$/ b left
/\.$/ b print
/,$/ b read
/\[$/ b start_while
/]$/ b end_while
:done
#Increment the program pointer.
s/#\(.\)\(.*\)/\1#\2/
#This is to jump past numbers put after ['s and ]'s to keep track of them.
/[][]#[A-Z0-9][A-Z0-9]/ s/#\(..\)\(.*\)/\1#\2/
:more_done
/#@/ !b main
s/.*//
q
#################################################################################
# The commands are implemented below
#
################################################################################
#################################################################################
# Add 1 to the value at the byte pointer
#
:add
#Remove the command
s/.$//
#Extract the number and put it at the end.
s/.*!\(..\).*/&\1/
#Copy the last digit to the hold space
h
s/.*\(.\)/\1/
#`Add' 1 to the digit
y/0123456789ABCDEF/123456789ABCDEF0/
x
G
#We now have ...+XX\nX
s/.\n\(.\)/\1/
#If the last digit is a zero, we have an overflow, so add to the next digit.
/0$/ !b nearly_finished_adding
#Extract the second to last digit to the hold space
h
s/.*\(.\)./\1/
y/0123456789ABCDEF/123456789ABCDEF0/
x
G
#We now have the second to last digit's new value appended at the end.
s/.\(.\)\n\(.\)/\2\1/
#Paste the added number back in.
:nearly_finished_adding
s/!..\(.*\)%\(..\)/!\2\1%/
b done
################################################################################
#
# Subtract 1 from the value at the byte pointer
#
:sub
#Remove the command
s/.$//
#Extract the number and put it at the end.
s/.*!\(..\).*/&\1/
#Copy the last digit to the hold space
h
s/.*\(.\)/\1/
#`Sub' 1 from the digit
y/123456789ABCDEF0/0123456789ABCDEF/
x
G
#We now have ...+XX\nX
s/.\n\(.\)/\1/
#If the last digit is an `F', we have an underflow, so sub from the next digit.
/F$/ !b nearly_finished_subbing
#Extract the second to last digit to the hold space
h
s/.*\(.\)./\1/
y/123456789ABCDEF0/0123456789ABCDEF/
x
G
#We now have the second to last digit's new value appended at the end.
s/.\(.\)\n\(.\)/\2\1/
#Paste the added number back in.
:nearly_finished_subbing
s/!..\(.*\)%\(..\)/!\2\1%/
b done
################################################################################
#
# Implement the `>' command: ie move the pointer to the right
#
:right
#Remove the command
s/.$//
# If we're at the end, then create more space...
/!..%/ s/%/00%/
s/!\(..\)\(.*\)/\1!\2/
b done
################################################################################
#
# Implement the `<' command: ie move the pointer to the left
#
:left
#Remove the command
s/.$//
#If we're at the beginning then add some more space...
/@!/ s/@/@00/
s/\(..\)!\(.*\)/!\1\2/
b done
################################################################################
#
# Implement the `.' command, ie, print the current value at the pointer.
#
:print
s/.$//
h
s/.*!\(..\).*/\1/
p
x
b done
################################################################################
#
# Implement the `,' command. This reads a byte from the keyboard. The input is
# assumed to be in the style of 1 byte per line, 2 hex digits per byte.
#
:read
s/.$//
N
s/!..\(.*\)\n\(..\)/!\2\1/
b done
################################################################################
#
# Implement the [ command. This jumps to the corresponding ] if the value at the
# pointer is zero or continues straight on otherwise.
#
:start_while
s/.$//
#If the value is not 00, then return:
/!00/ !b done
s/\(.*\)#\[\(..\)\(.*\)]\2\(.*\)/\1[\2\3#]\2\4/
b done
################################################################################
#
# Implement the ] commend. this jumps unconditionally back to the matching [
# This function leaves the # in the right place for a new loop
:end_while
s/.$//
#Duplicate the loop number to the beginning of the line and remove the # marker:
s/\(.*\)#]\(..\)\(.*\)/\2\1]\2\3/
#Now put in the new # marker:
s/\(..\)\(.*\)\[\1\(.*\)/\2#[\1\3/
b more_done
### colorized by sedsed, a debugger and code formatter for sed scripts
### original script: http://www2.eng.cam.ac.uk/~er258/code/sed/brainf__k.sed