# 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 /#@/!bmain 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