Skip to content

Instantly share code, notes, and snippets.

@TruncatedDinoSour
Last active January 25, 2024 17:30
Show Gist options
  • Save TruncatedDinoSour/73505e06c35de06371297139c1154cb3 to your computer and use it in GitHub Desktop.
Save TruncatedDinoSour/73505e06c35de06371297139c1154cb3 to your computer and use it in GitHub Desktop.
simple parser and interpreter : brainfuck implementation in pure javascript
"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();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment