21 tiny-compiler

tiny-compiler.js

// tiny-compiler
// a coding practice based on mgechev/tiny-compiler: https://github.com/mgechev/tiny-compiler/blob/master/tiny.js
// accepting expression like 'mul 2 3'(operator prefixed) and evaluate result
// (or transpile it into normal arithmetic expression (operator in the middle))

const OPERATIONS = ['add', 'sub', 'mul', 'div']

const OP_MAP = {
  add: (a, b) => a + b,
  sub: (a, b) => a - b,
  mul: (a, b) => a * b,
  div: (a, b) => a / b
}

const OP_TRANSPILE_MAP = {
  add: '+',
  sub: '-',
  mul: '×',
  div: '÷'
}

const Op = Symbol('op')
const Num = Symbol('num')

const lexer = str => str.split(' ')
                    .map(part => part.trim())
                    .filter(part => part.length)
                    .map((part) => {
                      if (OPERATIONS.indexOf(part) > -1) {
                        return {val: part, type: Op}
                      } else {
                        return {val: part, type: Num}
                      }
                    })

// context-free grammer for original expression:
// EXPR -> NUM | OP EXPR EXPR
// OP -> add | sub | mul | div
// NUM -> [0-9]*

// AST node definition:
/* 

Node {
  type: Op | Num
  value: add | sub | mul | div | [0-9]*
  left: NumNode | OperationNode (only for type Op)
  right: NumNode | OperationNode (only for type Op)
}

*/

const parser = tokens => {
  var c = 0
  var peek = () => tokens[c]
  var accept = () => tokens[c++]

  var number = () => {
    return {val: parseInt(accept().val)}
  }
  var operation = () => {
    return {val: accept().val}
  }

  var expression = () => {
    if (!peek()) {
      return null
    }
    if (peek().val.match(/[0-9]/)) {
      return number()
    } else {
      var op = operation()
      var expr1 = expression()
      var expr2 = expression()
      return {val: op.val, left: expr1, right: expr2}
    }
  }
  return expression()
}

const evaluator = ast => {
  var eval = node => {
    if (OPERATIONS.indexOf(node.val) > -1) {
      var op = OP_MAP[node.val]
      return op(eval(node.left), eval(node.right))
    } else {
      return node.val
    }
  }
  return eval(ast)
}

const transpiler = ast => {
  var eval = node => {
    if (OPERATIONS.indexOf(node.val) > -1) {
      var op = OP_TRANSPILE_MAP[node.val]
      return `(${eval(node.left)} ${op} ${eval(node.right)})`
    } else {
      return node.val
    }
  }
  return eval(ast)
}

var test = 'div mul 5 2 mul 2 add 3 sub 3 1'
console.log(transpiler(parser(lexer(test))))
// ((5 × 2) ÷ (2 × (3 + (3 - 1))))
console.log(evaluator(parser(lexer(test))))
// 1