json-parser.js

const first = source => {
  if (!source) return 'empty source'
  return [source[0], source.slice(1)]
}

// console.log('first', first('abc'), first(''))

const inject = value => source => [value, source]

// console.log('inject', inject(1)('123'), inject(2)(''))

const isFailed = result => typeof result === 'string'

const map = (parser, f) => source => {
  let result = parser(source)
  if (isFailed(result)) return result
  let [data, rest_source] = result
  return [f(data), rest_source]
}

// console.log('map', map(inject(1), n => n + 3)('test'))

const apply = (parserFn, parserArg) => source => {
  let resultFn = parserFn(source)

  if (isFailed(resultFn)) return resultFn

  let [fn, rest_source_fn] = resultFn
  let resultArg = parserArg(rest_source_fn)

  if (isFailed(resultArg)) return resultArg

  let [arg, rest_source_arg] = resultArg

  return [fn(arg), rest_source_arg]
}

// console.log('apply', apply(inject(n => n + 1), inject(1))('123'))

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

// console.log(
//   'applyAll',
//   applyAll(inject(x => y => x + y), inject(1), inject(2))('123')
// )

const satisfy = predicate => source => {
  let result = first(source)
  if (isFailed(result)) return result
  let [char, rest_source] = result
  if (!predicate(char)) return `Unexpect char ${char}`
  return [char, rest_source]
}

// console.log(
//   'satisfy',
//   satisfy(x => x === '1')('123'),
//   satisfy(x => x === '1')('423')
// )

const digit = satisfy(c => c >= '0' && c <= '9')
const lower = satisfy(c => c >= 'a' && c <= 'z')
const uppper = satisfy(c => c >= 'A' && c <= 'Z')
const char = target => satisfy(c => c === target)
const not = x => satisfy(value => value !== x)

// console.log('digit', digit('1'), digit('a'), digit('A'))
// console.log('lower', lower('1'), lower('a'), lower('A'))
// console.log('uppper', uppper('1'), uppper('a'), uppper('A'))
// console.log('char', char('0')('0'), char('0')('1'))
// console.log('not', not('1')('123'), not('1')('abc'))

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

// console.log('either', either(char('0'), char('1'))('123'))

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

// console.log('oneOf', oneOf(char('0'), char('1'), char('2'))('123'))

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

// console.log('whiteSpace', whiteSpace(' '), whiteSpace('\n'), whiteSpace('\t'), whiteSpace('a'))

const many = parser => {
  let concat = applyAll(
    inject(item => list => [item, ...list]),
    parser,
    source => many(parser)(source)
  )
  return either(concat, inject([]))
}

// console.log('many', many(digit)('123abc'), many(digit)('abc123'))

const many1 = parser => source => {
  let result = many(parser)(source)
  if (isFailed(result)) return result
  let [list, rest_source] = result
  if (list.length === 0) return `At least match once`
  return [list, rest_source]
}

// console.log('many1', many1(digit)('123abc'), many1(digit)('abc123'))

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

// console.log('string', string('123')('1234'), string('123')('abc'))

const letter = either(lower, uppper)

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

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

const integer = either(positiveInteger, negativeInteger)

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

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

const float = either(positiveFloat, negativeFloat)

const number = either(float, integer)

const ignoreFirst = (first, second) =>
  applyAll(inject(_ => value => value), first, second)

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

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

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

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

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

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

const jNumber = number

const jBoolean = map(
  either(string('false'), string('true')),
  result => result === 'true'
)

const jString = map(bracket(char('"'), many(not('"')), char('"')), list =>
  list.join('')
)

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

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

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

const jObject = map(
  bracket(
    aroundBySpace(char('{')),
    either(aroundBySpace(jPairs), inject([])),
    aroundBySpace(char('}'))
  ),
  entries =>
    entries.reduce((obj, [key, value]) => ({ ...obj, [key]: value }), {})
)

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))

optimized for performance

function ParserError(message) {
  this.message = message
}

let error = message => new ParserError(message)
let isFailed = input => input instanceof ParserError

let currentInput
let currentIndex

const first = () => {
  if (currentIndex >= currentInput.length) return error('empty source')

  let value = currentInput.charAt(currentIndex)

  currentIndex += 1

  return value
}

// console.log('first', first('abc'), first(''))

const inject = value => () => value

// console.log('inject', inject(1)('123'), inject(2)(''))

const map = (parser, f) => () => {
  let result = parser()
  if (isFailed(result)) return result
  return f(result)
}

// console.log('map', map(inject(1), n => n + 3)('test'))

const apply = (parserF, parserArg) => () => {
  let f = parserF()

  if (isFailed(f)) return f

  let arg = parserArg()

  if (isFailed(arg)) return arg

  return f(arg)
}

// console.log('apply', apply(inject(n => n + 1), inject(1))('123'))

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

// console.log(
//   'applyAll',
//   applyAll(inject(x => y => x + y), inject(1), inject(2))('123')
// )

const satisfy = predicate => () => {
  let result = first()

  if (isFailed(result)) {
    return result
  }

  if (!predicate(result)) {
    return error(
      `Unexpect char ${result} at: ${currentInput.slice(currentIndex)}`
    )
  }

  return result
}

// console.log(
//   'satisfy',
//   satisfy(x => x === '1')('123'),
//   satisfy(x => x === '1')('423')
// )

const digit = satisfy(c => c >= '0' && c <= '9')
const lower = satisfy(c => c >= 'a' && c <= 'z')
const uppper = satisfy(c => c >= 'A' && c <= 'Z')
const char = target => satisfy(c => c === target)
const not = x => satisfy(value => value !== x)

// console.log('digit', digit('1'), digit('a'), digit('A'))
// console.log('lower', lower('1'), lower('a'), lower('A'))
// console.log('uppper', uppper('1'), uppper('a'), uppper('A'))
// console.log('char', char('0')('0'), char('0')('1'))
// console.log('not', not('1')('123'), not('1')('abc'))

const either = (parserA, parserB) => () => {
  let index = currentIndex
  let resultA = parserA()
  if (!isFailed(resultA)) {
    return resultA
  }
  currentIndex = index
  return parserB()
}

// console.log('either', either(char('0'), char('1'))('123'))

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

// console.log('oneOf', oneOf(char('0'), char('1'), char('2'))('123'))

const whiteSpace = satisfy(
  c => c === ' ' || c === '\r' || c === '\n' || c === '\t'
)

// console.log('whiteSpace', whiteSpace(' '), whiteSpace('\n'), whiteSpace('\t'), whiteSpace('a'))

const many = parser => () => {
  let results = []

  while (true) {
    let index = currentIndex
    let result = parser()

    if (isFailed(result)) {
      currentIndex = index
      break
    }

    results[results.length] = result
  }

  return results
}

// console.log('many', many(digit)('123abc'), many(digit)('abc123'))

const many1 = parser => () => {
  let list = many(parser)()
  if (list.length === 0) return error(`At least match once`)
  return list
}

// console.log('many1', many1(digit)('123abc'), many1(digit)('abc123'))

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

// console.log('string', string('123')('1234'), string('123')('abc'))

const letter = either(lower, uppper)

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

const negative = _ => x => -x

const negativeInteger = applyAll(inject(negative), char('-'), positiveInteger)

const integer = either(positiveInteger, negativeInteger)

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

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

const float = either(positiveFloat, negativeFloat)

const number = either(float, integer)

const ignoreFirst = (first, second) =>
  applyAll(inject(_ => value => value), first, second)

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

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

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

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

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

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

const jNumber = number

const jBoolean = map(
  either(string('false'), string('true')),
  result => result === 'true'
)

const not_quote = not('"')

const jString = () => {
  let left = char('"')()

  if (isFailed(left)) return left

  let result = ''

  while (true) {
    let index = currentIndex
    let content = not_quote()

    if (isFailed(content)) {
      currentIndex = index
      break
    }

    result += content
  }

  let right = char('"')()

  if (isFailed(right)) return right

  return result
}

// const jString = map(bracket(char('"'), many(not('"')), char('"')), list =>
//   list.join('')
// )

const jArray = bracket(
  aroundBySpace(char('[')),
  either(
    separateBy(aroundBySpace(jValue), aroundBySpace(char(','))),
    inject([])
  ),
  aroundBySpace(char(']'))
)

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

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

const jObject = map(
  bracket(
    aroundBySpace(char('{')),
    either(aroundBySpace(jPairs), inject([])),
    aroundBySpace(char('}'))
  ),
  Object.fromEntries
)

const run = (parser, input) => {
  currentInput = input
  currentIndex = 0
  return parser()
}

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

console.time('applicative parser combinators')

let result1 = run(jValue, source)

console.log('json', result1)

console.timeEnd('applicative parser combinators')

console.time('native json parser')

let result2 = JSON.parse(source)

console.log('native', result2)

console.timeEnd('native json parser')

console.log('equal', JSON.stringify(result1) === JSON.stringify(result2))