From cdd4b58aa58320a1a0dfd259b7a1301f3ef60998 Mon Sep 17 00:00:00 2001 From: Matthew Hall Date: Mon, 20 Mar 2023 23:12:40 +1300 Subject: Separate files for practical tests + BF parser/interpreter finished --- spec/practical/bf_spec.cr | 157 +++++++++++++++++++++++++++++++++++++++++++ spec/practical/words_spec.cr | 39 +++++++++++ spec/practical_spec.cr | 146 ---------------------------------------- 3 files changed, 196 insertions(+), 146 deletions(-) create mode 100644 spec/practical/bf_spec.cr create mode 100644 spec/practical/words_spec.cr delete mode 100644 spec/practical_spec.cr 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 + diff --git a/spec/practical/words_spec.cr b/spec/practical/words_spec.cr new file mode 100644 index 0000000..5155881 --- /dev/null +++ b/spec/practical/words_spec.cr @@ -0,0 +1,39 @@ +require "../spec_helper" + +include Parcom + +describe "Text surrounded by whitespace" do + ws_char = Parser(Char, Char).satisfy { |c| c.whitespace? } + normal_char = Parser(Char, Char).satisfy { |c| !c.whitespace? } + + word = normal_char.some.map { |cs| cs.join } + ws = ws_char.some + + words = ws.optional >> word.sep_by(ws) << ws.optional + + good_strings = { + "test with no trailing whitespace", + " test with whitespace in the front", + "test with whitespace in the back", + " test surrounded by whitespace ", + } + + good_strings.each do |s| + tokens = Tokens.from_string(s) + result = words.parse(tokens) + + result.value.should eq(s.strip.split(/\s+/)) + result.tokens.empty?.should be_true + end + + bad_strings = { + "", + " \t \n ", + } + + bad_strings.each do |s| + tokens = Tokens.from_string(s) + expect_raises(ParserFail) { words.parse(tokens) } + end +end + diff --git a/spec/practical_spec.cr b/spec/practical_spec.cr deleted file mode 100644 index f992a15..0000000 --- a/spec/practical_spec.cr +++ /dev/null @@ -1,146 +0,0 @@ -require "./spec_helper" - -include Parcom - -describe "Text surrounded by whitespace" do - ws_char = Parser(Char, Char).satisfy { |c| c.whitespace? } - normal_char = Parser(Char, Char).satisfy { |c| !c.whitespace? } - - word = normal_char.some.map { |cs| cs.join } - ws = ws_char.some - - words = ws.optional >> word.sep_by(ws) << ws.optional - - good_strings = { - "test with no trailing whitespace", - " test with whitespace in the front", - "test with whitespace in the back", - " test surrounded by whitespace ", - } - - good_strings.each do |s| - tokens = Tokens.from_string(s) - result = words.parse(tokens) - - result.value.should eq(s.strip.split(/\s+/)) - result.tokens.empty?.should be_true - end - - bad_strings = { - "", - " \t \n ", - } - - bad_strings.each do |s| - tokens = Tokens.from_string(s) - expect_raises(ParserFail) { words.parse(tokens) } - end -end - -enum BFOpType - BFAdd - BFShift - BFByteIn - BFByteOut - BFLoopStart - BFLoopEnd -end - -alias BFOp = { - type: BFOpType, - amount: Int32, -} - -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::BFLoopStart, amount: 0} - end - - loop_end = Parser(Char, Char).token(']').map do |_| - {type: BFOpType::BFLoopEnd, amount: 0} - end - - read_block = Parser(Char, Char).token(',').some.map do |cs| - {type: BFOpType::BFByteIn, amount: cs.size} - end - - write_block = Parser(Char, Char).token('.').some.map do |cs| - {type: BFOpType::BFByteOut, 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::BFShift, 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::BFAdd, 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) - puts result - chars = Tokens.new(result.value) - bf_token.some.parse(chars) - end - - tokens = Tokens.from_string(hello_world_str) - result = tokenizer.parse(tokens) - puts result - # TODO: find a good way to verify this result -end - -- cgit v1.2.1