parser_combinators.js

const lit = (string) =>
  input => {
    if (input.indexOf(string) === 0)
      return [['lit', string], input.substr(string.length)]
    else
      return null
  }

const seq = (tokens) =>
  input => {
    let result = tokens.reduce((state, token) => {
      if (!state) return
      let [matches, input] = state

      let res = token(input)
      if (!res) return

      let [match, remain] = res
      return [matches.concat([match]), remain]
    }, [[], input])

    if (result)
      return [['seq', result[0]], result[1]]
    else
      return null
  }

const rep = (n, token) =>
  input => {
    let matches = [], k = n
    while (true) {
      let res = token(input)
      if (!res) return (k <= 0) ? [['seq', matches], input] : null

      matches.push(res[0])
      input = res[1]
      k -= 1
    }
    return null
  }

const alt = (options) =>
  input => {
    return options.reduce((state, token) => state || token(input), null)
  }


const print = (tree) => console.log(JSON.stringify(tree))


let parser = lit('foo')

print(parser('foo'))
print(parser('food'))
print(parser('a fool'))


parser = seq([
  lit('hello'),
  lit(' '),
  lit('@tuzz')
])

print(parser('hello @tuzz'))


parser = seq([
  lit('computation '),
  alt([lit('cl'), lit('p')]),
  lit('ub')
])

print(parser('computation club'))
print(parser('computation pub'))


let digit  = '0123456789'.split('').map(lit),
    number = rep(1, alt(digit))

print(number('2017'))

const ref = (name) =>
  input => eval(name)(input)

let expr = alt([ref('add'), ref('atom')])

let atom = alt([
  seq([lit('('), expr, lit(')')]),
  number
])

let add = seq([atom, lit(' + '), expr])

print(expr('2017'))
print(expr('2017 + 42'))
print(expr('2017 + 42 + 0'))
print(expr('(2017 + 42) + 0'))
print(expr('2017 + (42 + 0)'))
print(expr('2017 + ((32 + 64) + 0)'))