Jump to content
Search In
  • More options...
Find results that contain...
Find results in...

BrainF*** interpreter optimization C/C++

I'm trying to improve my BF interpreter to do more than basic optimizations. My language of choice is c/c++;

Currently I have 2 instructions for replacing sequences of '<', '>', '+' and '-':

ADD(n) ~ *ptr += n //It's an interpreter it doesn't generate C code I just use it as an example
JMP(n) ~ ptr += n

 

 

I want to add more complex instructions:

ZRO(offset)            *(ptr+offset) = 0
ADD(n, offset)         *(ptr+offset) += n     //makes the current ADD(n) obsolete because i can do ADD(n, 0)
MUL(n, offset)         *(ptr+offset) += *ptr * n
MUL(n, offset, diff)   *(ptr+offset+diff) += *(ptr+diff) * n  //slightly better than MUL(n, offset)

 

[+]          equivalent to ZRO(0)

[+--]        equivalent to ZRO(0)

>[-]<        equivalent to ZRO(1)
 

 

>>>++<<<     equivalent to ADD(+2, +3)
<<->>        equivalent to ADD(-1, -2)

 

[->+<]           equivalent to MUL(1, 1) ZRO(0)
[->+++<]         equivalent to MUL(3, 1) ZRO(0)
[->+++>--<<]      equivalent to MUL(3, 1) MUL(-2, 2) ZRO(0)


>>[->+<]<<       equivalent to MUL(1, 1, 2) ZRO(2)

 

Is there a simple way i can match these patterns? Regex is probably not powerful enough. Can i create a context free language to generate the patterns?

 

Edited by shadow_ray
small corrections

ಠ_ಠ  if i said something stupid please let me know

Link to post
Share on other sites

Jeezzz i forgot about loops. 😕 I also need two jump instructions. Jump if *ptr is zero and jump if *ptr is not zero.

ಠ_ಠ  if i said something stupid please let me know

Link to post
Share on other sites

You coud probably make a context free language for some simpler situations.

Eg: ADD(+x, offset) is something like:

>offset +x <offset

(assuming positive offset, it's reversed for a negative offset)

 

However, it doesn't cover situations where you have inter-weaved + and -

eg. +---++--+++--+-+-+-

 

Generally, it should be something like:

ADD(x, offset)

>offset w <offset , where the number of "+" in w minus the number of "-" in w is equal to x

 

That's pretty complicated and kinda useless (why would you do ++++--- instead of just +?).

 

Still, you could contract addition and subtraction. Instead of incrementing/decrementing by 1 at a time, just add/subtract the exact value needed

 

+++--+-+--+ is equivalent to adding 1.

 

That would make your job easier and it would be a pretty nice optimization.

 

[-] should cell a cell to 0 immediately and you can recognize it easily.

 

ZERO(offset) would just be

>offset ZERO(0) <offset

 

For jumps I suggest making a jump table.  Eg. precomputing where a loop will and and where you should go back at the end of the loop.

 

 

 

i5 4670k @ 4.2GHz (Coolermaster Hyper 212 Evo); ASrock Z87 EXTREME4; 8GB Kingston HyperX Beast DDR3 RAM @ 2133MHz; Asus DirectCU GTX 560; Super Flower Golden King 550 Platinum PSU;1TB Seagate Barracuda;Corsair 200r case. 

Link to post
Share on other sites
  • 2 weeks later...
On 1/26/2021 at 9:46 PM, Nineshadow said:

You coud probably make a context free language for some simpler situations.

Eg: ADD(+x, offset) is something like:

>offset +x <offset

This is where I got stuck. I don't know how to 😞

On 1/26/2021 at 9:46 PM, Nineshadow said:

However, it doesn't cover situations where you have inter-weaved + and -

eg. +---++--+++--+-+-+-

Yeah I can do a preprocessing step where i get rid of these, it doesn't seem to be too hard.

 

Currently I've a working regex based approach. I match patterns in a particular order. Each matched BF code segment can be translated to a bytecode segment and the original BF code will be replaced in a way that it cannot be matched later. At the end i match basic BF instructions like \++ (one or more +)  so I can be sure that every BF instruction got translated. The problem with this approach is that the compilation process is kinda slow for huge programs due to excessive regex use.

ಠ_ಠ  if i said something stupid please let me know

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

×