#!/bin/bash : <<'````````bash' # Programming Exercise 1: Brainfuck-Interpreter ## Implementation Write an efficient interpreter for Brainfuck with 8-bit cells by compiling Brainfuck to bytecode. Unmatched brackets are valid as long as the branch is never taken (i.e., `+[` is a valid program). You can define your bytecode as you like, but focus on efficient generation, optimization, and interpretation. Combine instruction sequences (both sequences of identical operations and loop patterns) and implement super-instructions/combined execution of multiple neighboring instructions as optimization. ## Analysis (write answers as comment in your code) Find suitably large and complex code examples to test the correctness and performance of your submission and document the results. Compare the compile-time and the run-time -- at what point are the optimizations worth the effort? How can more advanced optimizations be implemented? Why is this difficult? Give one Brainfuck code example and explain which optimization could lead to better bytecode. ## Command Line Interface usage: ./brainfuck [-c] program_file Execute a Brainfuck program. -c: print bytecode instead of executing program_file: file that contains the Brainfuck program Note that program_file is not necessarily a regular file, but can also be a pipe as used in the tests below, where you cannot determine the input size without reading it. You can add extra options, e.g., to control optimizations or for debugging. ## Submission - Submission deadline: 2024-10-23 23:59 - Submit using `curl --data-binary "@" 'https://db.in.tum.de/teaching/ws2425/codegen/submit.py?hw=1&matrno='` - Write your solution in a single C++ file. - Include answers to theory questions as comments at the top of the source file. - Make sure your submission passes as many tests as possible from this test script. - No external dependencies, build systems other than Makefile, etc. - If you really, *really* need more than just the C++ file, need to write a Makefile, or want to use C instead, combine all files s.t. this command sequence works: `split-file somedir || cp somedir/brainfuck.cc; cd somedir; bash ` ````````bash set -euo pipefail FAILED=0 testcase() { ./brainfuck "$2" | "${@:3}" || (echo "FAILED: $1"; FAILED=1); } CC=gcc CXX=g++ CFLAGS="-O3 -std=gnu11" CXXFLAGS="-O3 -std=c++20" make brainfuck # NOTE: test cases use cmp to compare stdout with expected output testcase "+." <(echo "+.") cmp - <(echo -ne '\x01') testcase "+-." <(echo "+-.") cmp - <(echo -ne '\x00') testcase "+>." <(echo "+>.") cmp - <(echo -ne '\x00') testcase "3434" <(base64 -d <+>->->+<[[-]<].>.>.>.>.") cmp - <(echo -ne '\x00\x00\x00\x00\x01') testcase "helloworld" <(base64 -d <