bronen.ts

// EXAMPLE: (1 (2 3 *) +)
// ((1 (2 3 +) +) 4 +)

const exhaustive = <A>(x: never): A => x;

// interpreter

type Expression =
  | { tag: "literal"; value: number }
  | { tag: "operation"; operation: Operation };
type OperationTag = "add" | "sub" | "mul" | "div";
type Operation = {
  tag: OperationTag;
  left: Expression;
  right: Expression;
};

const evalOperation = (operation: Operation): number => {
  const left = evalExpression(operation.left);
  const right = evalExpression(operation.right);
  if (operation.tag === "add") {
    return left + right;
  } else if (operation.tag === "sub") {
    return left - right;
  } else if (operation.tag === "mul") {
    return left * right;
  } else if (operation.tag === "div") {
    return left / right;
  } else {
    return exhaustive(operation.tag);
  }
};
const evalExpression = (expression: Expression): number => {
  if (expression.tag === "literal") {
    return expression.value;
  } else if (expression.tag === "operation") {
    return evalOperation(expression.operation);
  } else {
    return exhaustive(expression);
  }
};

// parser
type Token =
  | { tag: "number"; value: number }
  | { tag: "plus" }
  | { tag: "dash" }
  | { tag: "star" }
  | { tag: "bar" }
  | { tag: "left" }
  | { tag: "right" };

const shift = (tokens: Token[]): Token => {
  const token = tokens.shift();
  if (typeof token === "undefined") {
    throw new Error("EOF");
  }
  return token;
};
const parseOperation = (tag: OperationTag, tokens: Token[]): Operation => {
  const left = parseExpression(tokens);
  const right = parseExpression(tokens);
  return { tag: tag, left, right };
};
const parseExpression = (tokens: Token[]): Expression => {
  const token = shift(tokens);
  if (token.tag === "number") {
    return { tag: "literal", value: token.value };
  } else if (token.tag === "plus") {
    const operation = parseOperation("add", tokens);
    return { tag: "operation", operation };
  } else if (token.tag === "dash") {
    const operation = parseOperation("sub", tokens);
    return { tag: "operation", operation };
  } else if (token.tag === "star") {
    const operation = parseOperation("mul", tokens);
    return { tag: "operation", operation };
  } else if (token.tag === "bar") {
    const operation = parseOperation("div", tokens);
    return { tag: "operation", operation };
  } else if (token.tag === "left") {
    const tree = parseExpression(tokens);
    const right = shift(tokens);
    if (right.tag !== "right") {
      throw new Error("Expecetd right parens");
    }
    return tree;
  } else if (token.tag === "right") {
    throw new Error("Unexpected right parens");
  } else {
    return exhaustive(token);
  }
};

// lexer
const lexer = (source: string): Token[] => {
  const spaces = /\s/;
  const number = /\d/;
  const tokens: Token[] = [];
  for (let i = 0; i < source.length; i++) {
    const char = source[i];
    if (spaces.test(char)) {
    } else if (number.test(char)) {
      let valueString = char;
      for (; number.test(source[i + 1]); i++) {
        const char = source[i + 1];
        valueString = valueString + char;
      }
      const value = parseInt(valueString);
      if (isNaN(value)) {
        throw new Error(`"${valueString}" is not a number`);
      }
      tokens.push({ tag: "number", value });
    } else if (char === "+") {
      tokens.push({ tag: "plus" });
    } else if (char === "-") {
      tokens.push({ tag: "dash" });
    } else if (char === "*") {
      tokens.push({ tag: "star" });
    } else if (char === "/") {
      tokens.push({ tag: "bar" });
    } else if (char === "(") {
      tokens.push({ tag: "left" });
    } else if (char === ")") {
      tokens.push({ tag: "right" });
    } else {
      throw new Error("Unexpected char");
    }
  }
  return tokens;
};

// driver

const evalDump = (source: string) => {
  const tokens = lexer(source);
  const tree = parseExpression(tokens);
  const value = evalExpression(tree);
  console.log(value);
};

evalDump("1");
evalDump("2");
evalDump("+ 1 2");
evalDump("+ (+ 1 2) 3");