BrainF*** interpreter optimization C/C++

[shadow_ray]

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 January 23, 2021 by shadow_ray
small corrections

[shadow_ray]

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

[Nineshadow]

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.

 

 

 

[shadow_ray]

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.