ELVM付属のbrainf*ckコンパイラをJavaScriptに移植

bfopt.js

/*
 * original code: https://github.com/shinh/elvm/blob/master/tools/bfopt.cc
 * usage:
 *   compile and run
 *   $ node bfopt.js src.bf
 *   compile only
 *   $ node bfopt.js -c src.bf
 */

const MEM_SIZE = 30000;
const fs = require('fs');

class Loop {
  constructor() {
    this.reset(null);
  }

  reset(out) {
    if (out) {
      out.push(...this.code);
    }

    this.code = [];
    this.addsub = new Map();
    this.ptr = 0;
    this.hasIo = false;
  }
}

function mergeOps(add, sub, code, start) {
  let r = 0;
  let i = start;
  while (i < code.length) {
    if (code[i] === add) {
      r++;
    } else if (code[i] === sub) {
      r--;
    } else {
      break;
    }
    i++;
  }
  return [r, i - 1];
}

function parse(src) {
  const code = src.replace(/#.*?\n/g, '').replace(/[^+-<>.,\[\]]/g, '');
  const ops = [];
  let curLoop = new Loop();
  const loopStack = [];

  for (let i = 0; i < code.length; i++) {
    const c = code[i];
    let op = { op: null, arg: 0, loop: null };

    switch (c) {
      case '+':
      case '-': {
        [op.arg, i] = mergeOps('+', '-', code, i);
        if (op.arg) {
          op.op = 'OP_MEM';
          curLoop.addsub.set(curLoop.ptr, (curLoop.addsub.get(curLoop.ptr) || 0) + op.arg);
        } else {
          op = null;
        }
        break;
      }

      case '>':
      case '<': {
        [op.arg, i] = mergeOps('>', '<', code, i);
        if (op.arg) {
          op.op = 'OP_PTR';
          curLoop.ptr += op.arg;
        } else {
          op = null;
        }
        break;
      }

      case '.':
      case ',': {
        op.op = c;
        curLoop.hasIo = true;
        break;
      }

      case '[': {
        curLoop.reset(ops);
        op.op = c;
        loopStack.push(ops.length);
        break;
      }

      case ']': {
        if (loopStack.length === 0) {
          throw new Error('Unmatched close bracket');
        }

        if (!curLoop.hasIo && curLoop.ptr === 0 && curLoop.addsub.get(0) === -1) {
          op.op = 'OP_LOOP';
          op.loop = curLoop;
          curLoop = new Loop();
          curLoop.hasIo = true;
        } else {
          curLoop.reset(ops);
          op.op = c;
          op.arg = loopStack[loopStack.length - 1];
          ops[op.arg].arg = ops.length;
        }
        loopStack.pop();
        break;
      }

      default:
        op = null;
    }

    if (op) {
      curLoop.code.push(op);
    }
  }

  curLoop.reset(ops);

  if (loopStack.length > 0) {
    throw new Error('Unmatched open bracket');
  }

  return ops;
}

function compile(ops) {
  let code = `
const fs = require('fs');
class Reader {
  constructor() {
    this.buf = null;
  }
  getchar() {
    if (this.buf === null) {
      this.buf = Array.from(fs.readFileSync(process.stdin.fd));
    }
    if (this.buf.length) {
      return this.buf.shift();
    } else {
      return 0;
    }
  }
}
function bfmain() {
  const mem = new Uint8Array(${MEM_SIZE});
  const output = [];
  const reader = new Reader();
  let mp = 0;
`;

  for (const op of ops) {
    switch (op.op) {
      case 'OP_MEM':
        if (op.arg) {
          code += `mem[mp] += ${op.arg};\n`;
        }
        break;

      case 'OP_PTR':
        if (op.arg) {
          code += `mp += ${op.arg};\n`;
        }
        break;

      case '.':
        code += 'output.push(mem[mp]);\n';
        break;

      case ',':
        code += 'mem[mp] = reader.getchar();\n';
        break;

      case '[':
        code += 'while (mem[mp]) {\n';
        break;

      case ']':
        code += '}\n';
        break;

      case 'OP_LOOP': {
        /*
         brainf*ckの言語仕様通りに行儀良く変換するなら以下のforループで生成するコードを
         if (mem[mp]) { } で括るべきだが、mem[mp]==0の場合for内で生成するコードの右辺が
         全て0になり何もしない事になるので分岐を省略している。
         (ELVMのbfバックエンドの生成するbfコードだと分岐を省略した方が多くの場合速いっぽい)
         なおbfコードの書き方次第ではmem[mp]==0かつmp+p<0という状況になって
         メモリの範囲外アクセスが起こり得るので、別の言語に移植する際は注意が必要。
         JavaScriptのTypedArrayの範囲外アクセスは単に無視される(!)ので問題は起きない。
         */
        // code += 'if (mem[mp]) {\n';
        for (const [p, d] of op.loop.addsub.entries()) {
          if (p !== 0) {
            code += `mem[mp + ${p}] += mem[mp] * ${d};\n`;
          }
        }
        code += 'mem[mp] = 0;\n';
        // code += '}\n';
        break;
      }
    }
  }

  code += `
  process.stdout.write(Uint8Array.from(output));
}
bfmain();
`;
  return code;
}

function main(argv) {
  let compile_only = false;
  if (argv[0] == "-c") {
    compile_only = true;
    argv.shift();
  }
  const src = fs.readFileSync(argv[0], 'utf-8');
  const ops = parse(src);
  const compiled = compile(ops);
  if (compile_only) {
    process.stdout.write(compiled);
  } else {
    eval(compiled);
  }
}

if (process.argv.length < 3) {
  console.log("usage: node bfopt.js [-c] src.bf");
} else {
  main(process.argv.slice(2));
}

$ time node bfopt.js mandelbrot.bf
AAAAAAAAAAAAAAAABBBBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDEGFFEEEEDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
A                                                                                                 PLJHGGFFEEEDDDDDDDCCCCCCCCCCCCC
ADEEEEFFFGHIGGGGGGHHHHIJJLNY                                                                        TJHGFFEEEDDDDDDDCCCCCCCCCCCCC
ACDDDDDDDDDDEFFFFFFFGGGGHIKZOOPPS                                                                      HGFEEEDDDDDDCCCCCCCCCCCCCC
ABCDDDDDDDDDDDEEEEEFFFFFGIPJIIJKMQ                   VX                                                 HFFEEDDDDDDCCCCCCCCCCCCCC
AACCDDDDDDDDDDDDEEEEEEEEEFGGGHHKONSZ                QPR                                                NJGFEEDDDDDDCCCCCCCCCCCCCC
AACCCDDDDDDDDDDDDDEEEEEEEEEFGGGHIJMR              RMLMN                                                 NTFEEDDDDDDCCCCCCCCCCCCCB
AABCCCCCDDDDDDDDDDDDEEEEEEEFFGGHIJKOU  O O   PR LLJJJKL                                                OIHFFEDDDDDCCCCCCCCCCCCCCB
AABCCCCCCCCDDDDDDDDDDDEEEEEEFFFHKQMRKNJIJLVS JJKIIIIIIJLR                                               YNHFEDDDDDCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCDDDDDDDDDDEEEEFFHLKHHGGGGHHMJHGGGGGGHHHIKRR                                           UQ L HFEDDDDCCCCCCCCCCCCCCBB
AAABCCCCCCCCCCCCCCCCCDDDDDDDEEFJIHFFFFFFFFFFFFFFGGGGGGHIJN                                            JHHGFEEDDDDCCCCCCCCCCCCCBBB
AAAABCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEEFFFFFFGGHYV RQU                                     QMJHGGFEEEDDDCCCCCCCCCCCCCBBBB
AAAABBCCCCCCCCCCCCCCCCCCCCCCCCCDDDDEEEEEEEEEEEEEEEFFFFFFGHIJKLOT                                     [JGFFEEEDDCCCCCCCCCCCCCBBBBB
AAAAABBCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDEEEEEEEEEEEEFFFFFGHHIN                                 Q     UMWGEEEDDDCCCCCCCCCCCCBBBBBB
AAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDEEEEEEEEEFFFFGH O    TN S                       NKJKR LLQMNHEEDDDCCCCCCCCCCCCBBBBBBB
AAAAAABBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDEEEEEEFFGHK   MKJIJO  N R  X      YUSR PLV LHHHGGHIOJGFEDDDCCCCCCCCCCCCBBBBBBBB
AAAAAAABBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEEFGGHIIHHHHHIIIJKMR        VMKJIHHHGFFFFFFGSGEDDDDCCCCCCCCCCCCBBBBBBBBB
AAAAAAABBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEFFFFFFGGGGHIKP           KHHGGFFFFEEEEEEDDDDDCCCCCCCCCCCBBBBBBBBBBB
AAAAAAAABBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEFFFFFGGHJLZ         UKHGFFEEEEEEEEDDDDDCCCCCCCCCCCCBBBBBBBBBBBB
AAAAAAAAABBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGQPUVOTY   ZQL[MHFEEEEEEEDDDDDDDCCCCCCCCCCCBBBBBBBBBBBBBB
AAAAAAAAAABBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDDEEEEEEFFGHIJKS  X KHHGFEEEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBB
AAAAAAAAAAABBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEEFGGHHIKPPKIHGFFEEEDDDDDDDDDCCCCCCCCCCBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAABBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDDDEEEEEFFGHIMTKLZOGFEEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAABBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDDDEEEEFFFI KHGGGHGEDDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBB
AAAAAAAAAAAAAAABBBBBBBBBBBBBCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCDDDDDDDDDDEEEFGIIGFFEEEDDDDDDDDCCCCCCCCCBBBBBBBBBBBBBBBBBBBBBBBBBB

real    0m2.860s
user    0m4.452s
sys     0m0.100s