"Mini Compiler"

mini-compiler.ts

const operators = ['=', '+', '-', '*', '/', '>', '<', '>=', '<=', '==', '!=']

function isOp(v: string) {
  for (let i = 0; i < operators.length; i++) {
    if (operators[i] == v) return true
  }
  return false
}

function isNum(v: any) {
  return !isNaN(parseFloat(v)) && isFinite(v)
}

type TokenType = 'NUM' | 'LPAREN' | 'RPAREN' | 'OP' | 'EOL' | 'EOF'

interface Token {
  type: TokenType,
  value?: string
}

function tokenize(str: string): Token[] {
  const tokens: Token[] = []

  str = str.trim()
  let s = ''
  for (let index = 0; index < str.length; index++) {
    s += str[index]
    const peek = str[index + 1]

    if (isNum(s.trim()) && !isNum(peek)) {
      tokens.push({
        type: 'NUM',
        value: s.trim()
      })
      s = ''
    }

    if (s.trim() === '(' || s.trim() === ')') {
      s.trim() === '(' ?
        tokens.push({ type: 'LPAREN' }) :
        tokens.push({ type: 'RPAREN' })
      s = ''
    }

    if (isOp(s.trim()) && !isOp(peek)) {
      tokens.push({ type: 'OP', value: s.trim() })
      s = ''
    }

    if (s === ';' || s === '\n') {
      tokens.push({ type: 'EOL' })
      s = ''
    }

    if (index === (str.length - 1)) {
      tokens.push({ type: 'EOF' })
      s = ''
    }
  }

  return tokens
}

interface ASTNode {
  evaluate: () => number | boolean
}

type Operator = 'ADD' | 'SUB' | 'MUL' | 'DIV' |
  'LESS_THAN' | 'GREATER_THAN' | 'LESS_EQUAL'| 'GREATER_EQUAL' | 'EQUAL_EQUAL' | 'BANG_EQUAL'

function useBinary(left: ASTNode, operator: Operator, right: ASTNode): ASTNode {
  function evaluate(): number | boolean {
    switch (operator) {
      case 'ADD':
        // @ts-ignore
        return left.evaluate() + right.evaluate()
      case 'SUB':
        // @ts-ignore
        return left.evaluate() - right.evaluate()
      case 'MUL':
        // @ts-ignore
        return left.evaluate() * right.evaluate()
      case 'DIV':
        // @ts-ignore
        return left.evaluate() / right.evaluate()
      case 'LESS_THAN':
        // @ts-ignore
        return left.evaluate() < right.evaluate()
      case 'GREATER_THAN':
        // @ts-ignore
        return left.evaluate() > right.evaluate()
      case 'LESS_EQUAL':
        // @ts-ignore
        return left.evaluate() <= right.evaluate()
      case 'GREATER_EQUAL':
        // @ts-ignore
        return left.evaluate() >= right.evaluate()
      case 'EQUAL_EQUAL':
        // @ts-ignore
        return left.evaluate() == right.evaluate()
      case 'BANG_EQUAL':
        // @ts-ignore
        return left.evaluate() != right.evaluate()
    }
  }
  return { evaluate }
}

function useLiteral(value: string): ASTNode {
  function evaluate() {
    return Number(value)
  }
  return { evaluate }
}

function useGrouping(expr: ASTNode): ASTNode {
  function evaluate() {
    return expr.evaluate()
  }
  return { evaluate }
}

function compile(str: string) {
  let index = 0
  const tokens = tokenize(str)

  function current() {
    return tokens[index]
  }

  function add() {
    const left = sub()
    if (current().value === '+') {
      index++
      return useBinary(left, 'ADD', sub())
    }
    return left
  }

  function sub() {
    const left = mul()
    if (current().value === '-') {
      index++
      return useBinary(left, 'SUB', mul())
    }
    return left
  }

  function mul(): ASTNode {
    const left = all()
    if (current().value === '*') {
      index++
      return useBinary(left, 'MUL', all())
    }
    return left
  }

  function all(): ASTNode {
    const left = primary()
    switch (current().value) {
      case '>=':
        index++
        return useBinary(left, 'GREATER_EQUAL', add())
      case '<=':
        index++
        return useBinary(left, 'LESS_EQUAL', add())
      case '==':
        index++
        return useBinary(left, 'EQUAL_EQUAL', add())
      case '>':
        index++
        return useBinary(left, 'GREATER_EQUAL', add())
      case '<':
        index++
        return useBinary(left, 'LESS_THAN', add())
      case '!=':
        index++
        return useBinary(left, 'BANG_EQUAL', add())
      default:
        break
    }
    return left
  }

  function primary(): ASTNode {
    const curr = current()
    index++
    if (curr.type === 'NUM')
      return useLiteral(curr.value)
    if (curr.type === 'LPAREN') {
      const expr = add()
      index++
      return useGrouping(expr)
    }
  }

  function parse() {
    const asts: ASTNode[] = []
    while (current().type !== 'EOF') {
      const ast = add()
      if (ast) {
        asts.push(ast)
      }
    }

    for (const ast of asts) {
      console.log(ast.evaluate())
    }
  }

  parse()
}

const str = `
    (1+2)+3;
    4+(5-2);
`

compile(str)