a naive json parser implemented by parser combinator

naive-json-parser.js

// parser combinator

const fail = () => []

const failed = list => list.length === 0

const of = value => input => [value, input]

const bind = (parser, f) => input => {
  let result = parser(input)
  if (failed(result)) return fail()
  let [value, remain] = result
  return f(value)(remain)
}

const apply = (parserF, parserA) =>
  bind(parserF, f => bind(parserA, value => of(f(value))))

const map = (parser, f) => apply(of(f), parser)

const applyAll = (...args) => args.reduce(apply)

const item = input => {
  if (input.length === 0) return fail()
  return [input[0], input.slice(1)]
}

const sequence = (parserA, parserB) =>
  applyAll(of(a => b => [a, b]), parserA, parserB)

const satisfy = predicate =>
  bind(item, value => (predicate(value) ? of(value) : fail))

const char = x => satisfy(value => value === x)

const digit = satisfy(value => value >= '0' && value <= '9')

const lower = satisfy(value => value >= 'a' && value <= 'z')

const upper = satisfy(value => value >= 'A' && value <= 'Z')

const either = (parserA, parserB) => input => {
  let resultA = parserA(input)
  if (!failed(resultA)) return resultA
  return parserB(input)
}

const letter = either(lower, upper)

const alphanum = either(letter, digit)

const string = str => {
  if (str.length === 0) return of('')
  return applyAll(of(x => xs => x + xs), char(str[0]), string(str.slice(1)))
}

const many = parser =>
  either(
    applyAll(of(item => list => [item, ...list]), parser, input =>
      many(parser)(input)
    ),
    of([])
  )

const some = parser => input => {
  let result = many(parser)(input)
  if (failed(result)) return fail()
  let [value] = result
  if (value.length === 0) return fail()
  return result
}

const word = apply(of(list => list.join('')), some(letter))

const identifier = applyAll(
  of(x => list => x + list.join('')),
  lower,
  many(alphanum)
)

const optionalFirst = (before, parser) => input => {
  let result = before(input)
  if (failed(result)) {
    return parser(input)
  }
  let [_, remain] = result
  return parser(remain)
}

const optionalSecond = (parser, second) => input => {
  let result = parser(input)
  if (failed(result)) return fail()
  let [value, remain] = result
  let result1 = second(remain)
  if (failed(result1)) return result
  let [_, remain1] = result1
  return [value, remain1]
}

const separateBy = (parser, separator) =>
  applyAll(
    of(item => list => [item, ...list]),
    parser,
    many(optionalFirst(separator, parser))
  )

const bracket = (open, parser, close) =>
  applyAll(of(_1 => x => _2 => x), open, parser, close)

const oneOf = (...args) => args.reduce(either)

const notFirst = (first, parser) => input => {
  let result = first(input)
  if (failed(result)) return parser(input)
  return result
}

const not = x => satisfy(value => value !== x)

const whiteSpace = oneOf(char(' '), char('s'), char('\n'), char('\t'))

const positiveInteger = map(some(digit), list => Number(list.join('')))

const negativeInteger = applyAll(of(_ => x => -x), char('-'), positiveInteger)

const integer = either(positiveInteger, negativeInteger)

const positiveFloat = applyAll(
  of(a => b => c => Number(a + b + c)),
  map(some(digit), list => list.join('')),
  char('.'),
  map(some(digit), list => list.join(''))
)

const negativeFloat = applyAll(of(_ => x => -x), char('-'), positiveFloat)

const float = either(positiveFloat, negativeFloat)

const number = either(float, integer)

const aroundBy = (parser, surround) =>
  applyAll(of(_1 => x => _2 => x), many(surround), parser, many(surround))

const aroundBySpace = parser => aroundBy(parser, whiteSpace)

const identity = x => x

// parse json

const toNull = () => null

const toNumber = identity

const toString = list => list.join('')

const toArray = identity

const toObject = entries =>
  entries.reduce((obj, [key, value]) => ({ ...obj, [key]: value }), {})

const jValue = input => oneOf(jNull, jNumber, jString, jArray, jObject)(input)

const jNull = map(string('null'), toNull)

const jNumber = map(either(float, integer), toNumber)

const jString = map(bracket(char('"'), many(not('"')), char('"')), toString)

const jArray = map(
  bracket(
    aroundBySpace(char('[')),
    separateBy(aroundBySpace(jValue), aroundBySpace(char(','))),
    aroundBySpace(char(']'))
  ),
  toArray
)

const jKey = notFirst(string('""'), jString)

const jPair = applyAll(
  of(key => _ => value => [key, value]),
  jKey,
  aroundBySpace(char(':')),
  jValue
)

const jPairs = separateBy(jPair, aroundBySpace(char(',')))

const jObject = map(
  bracket(
    aroundBySpace(char('{')),
    either(aroundBySpace(jPairs), of([])),
    aroundBySpace(char('}'))
  ),
  toObject
)

console.log('null', jValue('null'))
console.log('string', jString('""'), jString('"123123"'))
console.log(
  'number',
  jNumber('0'),
  jNumber('123'),
  jNumber('-123'),
  jNumber('0.11'),
  jNumber('-0.11')
)

console.log('array', jArray('[ 1, 2, 3, "123", [4, 5, 6] ]'))

console.log('object', jObject('{}'), jObject(`{ "a": 1 }`))

let result = jValue(
  JSON.stringify({
    a: 1,
    b: 2,
    c: [
      1,
      2,
      {
        d: 3
      }
    ]
  })
)

console.log('json', JSON.stringify(result, null, 2))

const NUMBER = Symbol('number')
const ADDITION = Symbol('addition')
const SUBTRACTION = Symbol('subtraction')
const MULTIPLICATION = Symbol('multiplication')
const DIVISION = Symbol('division')
const NEGATIVE = Symbol('negative')

const toX = type => data => ({ type, data })

const toAddition = toX(ADDITION)
const toSubtraction = toX(SUBTRACTION)
const toMultiplication = toX(MULTIPLICATION)
const toDivision = toX(DIVISION)
const toNegative = toX(NEGATIVE)

const arithmetic = input =>
  oneOf(
    group,
    negative,
    addition,
    subtraction,
    multiplication,
    division,
    map(number, x => toX(NUMBER)([x]))
  )(input)

const addition = applyAll(
  of(_ => x => y => toAddition([x, y])),
  aroundBySpace(char('+')),
  aroundBySpace(arithmetic),
  aroundBySpace(arithmetic)
)

const subtraction = applyAll(
  of(_ => x => y => toSubtraction([x, y])),
  aroundBySpace(char('-')),
  aroundBySpace(arithmetic),
  aroundBySpace(arithmetic)
)

const multiplication = applyAll(
  of(_ => x => y => toMultiplication([x, y])),
  aroundBySpace(char('*')),
  aroundBySpace(arithmetic),
  aroundBySpace(arithmetic)
)

const division = applyAll(
  of(_ => x => y => toDivision([x, y])),
  aroundBySpace(char('/')),
  aroundBySpace(arithmetic),
  aroundBySpace(arithmetic)
)

const negative = applyAll(
  of(_ => x => toNegative([x])),
  aroundBySpace(char('-')),
  arithmetic
)

const group = bracket(
  aroundBySpace(char('(')),
  arithmetic,
  aroundBySpace(char(')'))
)

const interpreter = ast => {
  if (typeof ast === 'number') return ast
  let { type, data } = ast
  let [x, y] = data
  let result
  switch (type) {
    case NUMBER:
      result = x
      break
    case NEGATIVE:
      result = -interpreter(x)
      break
    case ADDITION:
      result = interpreter(x) + interpreter(y)
      break
    case SUBTRACTION:
      result = interpreter(x) - interpreter(y)
      break
    case MULTIPLICATION:
      result = interpreter(x) * interpreter(y)
      break
    case DIVISION:
      result = interpreter(x) / interpreter(y)
      break
  }
  return result
}

const [ast] = arithmetic(`-(+ 1 (* 3 (/ 4 2)))`)

console.log('ast', JSON.stringify(ast, null, 2))
console.log('result', interpreter(ast))