Separate files for practical tests + BF parser/interpreter finished

1 files changed, 157 insertions, 0 deletions

diff --git a/spec/practical/bf_spec.cr b/spec/practical/bf_spec.cr
new file mode 100644
index 0000000..cd14c59
--- /dev/null
+++ b/spec/practical/bf_spec.cr
@@ -0,0 +1,157 @@
+require "../spec_helper"
+
+include Parcom
+
+enum BFOpType
+  Add
+  Shift
+  ByteIn
+  ByteOut
+  LoopStart
+  LoopEnd
+end
+
+alias BFOp = {
+  type: BFOpType,
+  amount: Int32,
+}
+
+def find_jumps(ops : Array(BFOp)) : Hash(Int32, Int32)
+  jumps = {} of Int32 => Int32
+  stack = [] of Int32
+
+  ops.each_index do |i|
+    if ops[i][:type] == BFOpType::LoopStart
+      stack << i
+    end
+
+    if ops[i][:type] == BFOpType::LoopEnd
+      jumps[i] = stack.pop
+      jumps[jumps[i]] = i
+    end
+  end
+
+  jumps
+end
+
+def interpret_bf(ops : Array(BFOp)) : Array(Char)
+  jumps = find_jumps(ops)
+  mem = Hash(Int32, Int32).new(0)
+  i_ptr = 0
+  m_ptr = 0
+  output = [] of Char
+  while i_ptr < ops.size
+    op = ops[i_ptr]
+    case op[:type]
+      in BFOpType::Add
+        mem[m_ptr] = (mem[m_ptr] + op[:amount]) % 256
+      in BFOpType::Shift
+        m_ptr += op[:amount]
+      in BFOpType::ByteIn
+        raise "Test suite for BF simulation does not support input instruction"
+      in BFOpType::ByteOut
+        c = mem[m_ptr].chr
+        op[:amount].times { output << c }
+      in BFOpType::LoopStart
+        i_ptr = jumps[i_ptr] if mem[m_ptr] == 0
+      in BFOpType::LoopEnd
+        i_ptr = jumps[i_ptr] unless mem[m_ptr] == 0
+    end
+    i_ptr += 1
+  end
+  output
+end
+
+describe "brainfuck parser" do
+  # From https://esolangs.org/wiki/Brainfuck#Examples
+  hello_world_str = "1 +++++ +++               Set Cell #0 to 8
+ 2 [
+ 3     >++++               Add 4 to Cell #1; this will always set Cell #1 to 4
+ 4     [                   as the cell will be cleared by the loop
+ 5         >++             Add 4*2 to Cell #2
+ 6         >+++            Add 4*3 to Cell #3
+ 7         >+++            Add 4*3 to Cell #4
+ 8         >+              Add 4 to Cell #5
+ 9         <<<<-           Decrement the loop counter in Cell #1
+10     ]                   Loop till Cell #1 is zero
+11     >+                  Add 1 to Cell #2
+12     >+                  Add 1 to Cell #3
+13     >-                  Subtract 1 from Cell #4
+14     >>+                 Add 1 to Cell #6
+15     [<]                 Move back to the first zero cell you find; this will
+16                         be Cell #1 which was cleared by the previous loop
+17     <-                  Decrement the loop Counter in Cell #0
+18 ]                       Loop till Cell #0 is zero
+19 
+20 The result of this is:
+21 Cell No :   0   1   2   3   4   5   6
+22 Contents:   0   0  72 104  88  32   8
+23 Pointer :   ^
+24 
+25 >>.                     Cell #2 has value 72 which is 'H'
+26 >---.                   Subtract 3 from Cell #3 to get 101 which is 'e'
+27 +++++ ++..+++.          Likewise for 'llo' from Cell #3
+28 >>.                     Cell #5 is 32 for the space
+29 <-.                     Subtract 1 from Cell #4 for 87 to give a 'W'
+30 <.                      Cell #3 was set to 'o' from the end of 'Hello'
+31 +++.----- -.----- ---.  Cell #3 for 'rl' and 'd'
+32 >>+.                    Add 1 to Cell #5 gives us an exclamation point
+33 >++.                    And finally a newline from Cell #6"
+
+  bf_chars = Set{'+', '-', '.', ',', '<', '>', '[', ']'}
+  other = Parser(Char, Char).satisfy { |c| !bf_chars.includes?(c) }
+  bf_char = Parser(Char, Char).satisfy { |c| bf_chars.includes?(c) }
+
+  char_body = bf_char.some.sep_by(other.some).map(&.flatten)
+  just_bf_chars = other.many >> char_body << other.many
+
+  loop_start = Parser(Char, Char).token('[').map do |_|
+    {type: BFOpType::LoopStart, amount: 0}
+  end
+
+  loop_end = Parser(Char, Char).token(']').map do |_|
+    {type: BFOpType::LoopEnd, amount: 0}
+  end
+
+  read_block = Parser(Char, Char).token(',').some.map do |cs|
+    {type: BFOpType::ByteIn, amount: cs.size}
+  end
+
+  write_block = Parser(Char, Char).token('.').some.map do |cs|
+    {type: BFOpType::ByteOut, amount: cs.size}
+  end
+
+  shift_block = (Parser.token('<') | Parser.token('>')).some.map do |cs|
+    left_count = cs.count { |c| c == '<' }
+    right_count = cs.size - left_count
+    {type: BFOpType::Shift, amount: right_count - left_count}
+  end
+
+  add_block = (Parser.token('+') | Parser.token('-')).some.map do |cs|
+    minus_count = cs.count { |c| c == '-' }
+    plus_count = cs.size - minus_count
+    {type: BFOpType::Add, amount: plus_count - minus_count}
+  end
+
+  bf_token = Parser.first_of([
+    loop_start,
+    loop_end,
+    read_block,
+    write_block,
+    shift_block,
+    add_block,
+  ])
+
+  tokenizer = Parser(Char, Array(BFOp)).new("BF tokenizer") do |tokens|
+    result = just_bf_chars.parse(tokens)
+    chars = Tokens.new(result.value)
+    bf_token.some.parse(chars)
+  end
+
+  tokens = Tokens.from_string(hello_world_str)
+  result = tokenizer.parse(tokens)
+
+  exec_result = interpret_bf(result.value)
+  exec_result.should eq("Hello World!\n".chars)
+end
+