path: root/js/scripting-lang/lang.js

// The goal here is less to make anything useful...or even something that works, but to learn what parts an interpreted languages needs to have to function.

// Define the types of tokens
const TokenType = {
    NUMBER: 'NUMBER',
    PLUS: 'PLUS',
    IDENTIFIER: 'IDENTIFIER',
    ASSIGNMENT: 'ASSIGNMENT',
    FUNCTION: 'FUNCTION',
    LEFT_PAREN: 'LEFT_PAREN',
    RIGHT_PAREN: 'RIGHT_PAREN',
    LEFT_BRACE: 'LEFT_BRACE',
    RIGHT_BRACE: 'RIGHT_BRACE',
    SEMICOLON: 'SEMICOLON',
};

// Lexer
function lexer(input) {
    const tokens = [];
    let current = 0;

    while (current < input.length) {
        let char = input[current];

        if (/\d/.test(char)) {
            let value = '';
            while (/\d/.test(char)) {
                value += char;
                char = input[++current];
            }
            tokens.push({
                type: TokenType.NUMBER,
                value
            });
            continue;
        }

        if (char === '+') {
            tokens.push({
                type: TokenType.PLUS
            });
            current++;
            continue;
        }

        if (/[a-z]/i.test(char)) {
            let value = '';
            while (/[a-z]/i.test(char)) {
                value += char;
                char = input[++current];
            }
            tokens.push({
                type: TokenType.IDENTIFIER,
                value
            });
            continue;
        }

        if (char === ':') {
            tokens.push({
                type: TokenType.ASSIGNMENT
            });
            current++;
            continue;
        }

        if (char === '=') {
            tokens.push({
                type: TokenType.EQUAL
            });
            current++;
            continue;
        }

        if (input.slice(current, current + 2) === 'if') {
            tokens.push({
                type: TokenType.IF
            });
            current += 2;
            continue;
        }

        if (input.slice(current, current + 4) === 'else') {
            tokens.push({
                type: TokenType.ELSE
            });
            current += 4;
            continue;
        }

        if (char === '(') {
            tokens.push({
                type: TokenType.LEFT_PAREN
            });
            current++;
            continue;
        }

        if (char === ')') {
            tokens.push({
                type: TokenType.RIGHT_PAREN
            });
            current++;
            continue;
        }

        if (char === '{') {
            tokens.push({
                type: TokenType.LEFT_BRACE
            });
            current++;
            continue;
        }

        if (char === '}') {
            tokens.push({
                type: TokenType.RIGHT_BRACE
            });
            current++;
            continue;
        }

        if (input.slice(current, current + 8) === 'function') {
            tokens.push({
                type: TokenType.FUNCTION
            });
            current += 8;
            continue;
        }

        if (char === ';') {
            tokens.push({ type: TokenType.SEMICOLON });
            current++;
            continue;
        }

        current++;
    }

    return tokens;
}

// Parser
function parser(tokens) {
    let current = 0;

    function walk() {
        if (current >= tokens.length) {
            return null; // Return null when there are no more tokens
        }

        let token = tokens[current];

        if (token.type === TokenType.NUMBER) {
            current++;
            return {
                type: 'NumberLiteral',
                value: token.value,
            };
        }

        if (token.type === TokenType.PLUS) {
            current++;
            return {
                type: 'PlusExpression',
                left: walk(),
                right: walk(),
            };
        }

        if (token.type === TokenType.IDENTIFIER) {
            current++;
            return {
                type: 'Identifier',
                value: token.value,
            };
        }

        if (token.type === TokenType.ASSIGNMENT) {
            current++;
            return {
                type: 'AssignmentExpression',
                name: tokens[current - 2].value,
                value: walk(),
            };
        }

        if (token.type === TokenType.IF) {
            current++;
            let node = {
                type: 'IfExpression',
                test: walk(),
                consequent: walk(),
                alternate: tokens[current].type === TokenType.ELSE ? (current++, walk()) : null,
            };
            return node;
        }

        if (token.type === TokenType.FUNCTION) {
            current++;
            let node = {
                type: 'FunctionDeclaration',
                name: tokens[current++].value,
                params: [],
                body: [],
            };
            while (tokens[current].type !== TokenType.RIGHT_PAREN) {
                node.params.push(tokens[current++].value);
            }
            current++; // Skip right paren
            while (tokens[current].type !== TokenType.RIGHT_BRACE) {
                node.body.push(walk());
            }
            current++; // Skip right brace
            return node;
        }

        if (token.type === TokenType.IDENTIFIER && tokens[current + 1].type === TokenType.LEFT_PAREN) {
            current++;
            let node = {
                type: 'FunctionCall',
                name: token.value,
                args: [],
            };
            current++; // Skip left paren
            while (tokens[current].type !== TokenType.RIGHT_PAREN) {
                node.args.push(walk());
            }
            current++; // Skip right paren
            return node;
        }

        if (token.type === TokenType.SEMICOLON) {
            current++;
            return;
        }

        throw new TypeError(token.type);
    }

    let ast = {
        type: 'Program',
        body: [],
    };

    while (current < tokens.length) {
        const node = walk();
        if (node !== null) {
            ast.body.push(node);
        }
    }

    return ast;
}

// Interpreter
function interpreter(ast) {
    let globalScope = {};

    function evalNode(node) {
        switch (node.type) {
            case 'NumberLiteral':
                return parseInt(node.value);
            case 'PlusExpression':
                return evalNode(node.left) + evalNode(node.right);
            case 'AssignmentExpression':
                globalScope[node.name] = evalNode(node.value);
                return;
            case 'Identifier':
                return globalScope[node.value];
            case 'IfExpression':
                return evalNode(node.test) ? evalNode(node.consequent) : node.alternate ? evalNode(node.alternate) : undefined;
            case 'FunctionDeclaration':
                globalScope[node.name] = function() {
                    let localScope = Object.create(globalScope);
                    for (let i = 0; i < node.params.length; i++) {
                        localScope[node.params[i]] = arguments[i];
                    }
                    let lastResult;
                    for (let bodyNode of node.body) {
                        lastResult = evalNode(bodyNode);
                    }
                    return lastResult;
                };
                return;
            case 'FunctionCall':
                if (globalScope[node.name] instanceof Function) {
                    let args = node.args.map(evalNode);
                    return globalScope[node.name].apply(null, args);
                }
                throw new Error(`Function ${node.name} is not defined`);
            default:
                throw new Error(`Unknown node type: ${node.type}`);
        }
    }

    return evalNode(ast.body[0]);
}

// Usage
// const tokens = lexer('2 + 2');
// const ast = parser(tokens);
// const result = interpreter(ast);
// console.log(result); // 4

// const tokens2 = lexer('x : 2 + 2');
// const ast2 = parser(tokens2);
// const result2 = interpreter(ast2);
// console.log(result2); 

const fs = require('fs');

// Read the input from a file
const input = fs.readFileSync('input.txt', 'utf-8');

// Usage
const tokens = lexer(input);
const ast = parser(tokens);
const result = interpreter(ast);
console.log(result);