# 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 SED script debugger/indenter/tokenizer/HTMLizer
### original script: http://www2.eng.cam.ac.uk/~er258/code/sed/brainf__k.sed