diff options
Diffstat (limited to 'spec/practical/bf_spec.cr')
| -rw-r--r-- | spec/practical/bf_spec.cr | 157 |
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 + |