simple parser and interpreter : brainfuck implementation in pure javascript

bf.js

"use strict";

// this is a very simple and basic showcase of a parser
// and interpreter example which implements brainfuck

// license : unlicense

// UNLICENSE

// This is free and unencumbered software released into the public domain.

// Anyone is free to copy, modify, publish, use, compile, sell, or
// distribute this software, either in source code form or as a compiled
// binary, for any purpose, commercial or non-commercial, and by any
// means.

// In jurisdictions that recognize copyright laws, the author or authors
// of this software dedicate any and all copyright interest in the
// software to the public domain. We make this dedication for the benefit
// of the public at large and to the detriment of our heirs and
// successors. We intend this dedication to be an overt act of
// relinquishment in perpetuity of all present and future rights to this
// software under copyright law.

// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
// IN NO EVENT SHALL THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR
// OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
// ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.

// For more information, please refer to <http://unlicense.org/>


/* define token types */

const SHIFT_RIGHT = 0;
const SHIFT_LEFT = 1;
const INC = 2;
const DEC = 3;
const OUTPUT = 4;
const INPUT = 5;
const LOOP_START = 6;
const LOOP_END = 7;

// define a token mapping, on a more complex parser ( such as markdown for example )
// ud use a switch case and parse everything based on a case-by-case basis, such as
// if u encouter `<` u read til the end of >, same with other things

const TOKEN_MAPPING = {
    ">": SHIFT_RIGHT,
    "<": SHIFT_LEFT,
    "+": INC,
    "-": DEC,
    ".": OUTPUT,
    ",": INPUT,
    "[": LOOP_START,
    "]": LOOP_END,
};

// https://esolangs.org/wiki/Brainfuck
// just reads everything character by character and ignore
// everything else that isnt in TOKEN_MAPPING -- treat as comment
//
// if ur parsing markdown so to say u could parse <https://ari.lt/> into like
// [[INLINE_LINK_START, null], [DATA, "https://ari.lt/"], [INLINE_LINK_START, null]]

function parse_brainfuck(bf) {
    let idx = 0;
    let tokens = [];

    while (idx < bf.length) {
        // ud replace this part with a switch case
        // if ur doing more complex parsing, esp as this
        // parser doesnt keep any data as markdown has no
        // concept of data besides the memory array

        if (TOKEN_MAPPING[bf[idx]] !== undefined)
            tokens.push(TOKEN_MAPPING[bf[idx]]);

        // increment the current character index
        // ud most likely keep this in a character-by-character
        // parser basis

        ++idx;
    }

    return tokens;
}

// does not impolement errors and bound checking
// u can implement it by extending this if u want

function run_ast(ast) {
    let p = 0;
    let stack = [];
    let memory = new Array(30000).fill(0);

    for (let idx = 0; idx < ast.length; ++idx) {
        let token = ast[idx];

        // self-explanatory interpretation of the ast

        switch (token) {
            case SHIFT_RIGHT:
                ++p;
                break;

            case SHIFT_LEFT:
                --p;
                break;

            case INC:
                ++memory[p];
                break;

            case DEC:
                --memory[p];
                break;

            case OUTPUT:
                console.log(String.fromCharCode(memory[p]));
                break;

            case INPUT:
                memory[p] = prompt("input")[0].charCodeAt(0);
                break;

            case LOOP_START:
                stack.push(idx);
                break;

            case LOOP_END:
                if (memory[p] !== 0) idx = stack[stack.length - 1];
                else stack.pop();
                break;
        }
    }

    return [memory, stack, p];
}

function main() {
    // https://esolangs.org/wiki/Brainfuck#Hello,_World!

    let ast = parse_brainfuck(`
 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
`);

    console.log(ast);

    let [memory, stack, p] = run_ast(ast);

    console.log("--- memory dump ---");

    for (let mem = 0; mem < memory.length; ++mem)
        if (memory[mem] !== 0)
            console.log(`non-zero slot ${mem} : ${memory[mem]}`);

    console.log("--- stack dump ---");

    for (let stk = 0; stk < stack.length; ++stk)
        console.log(`slot ${stk} : ${stack[stk]}`);

    console.log(`--- vm finished on p = ${p} ---`);
}

// document.addEventListener("DOMContentLoaded", main);
main();