Parsers.kt

import java.util.*
import kotlin.properties.Delegates

interface Location{
    fun consume(ch: Char): Location
}
data class SimplestLocation(val position: Int): Location {
    override fun consume(ch: Char) = SimplestLocation(position + 1)
}

interface Reader {
    open val next: Char
    open val rest: Reader

    open val eof: Boolean
    open val locus: Location
}

data class StringReader(val inner: String, val current: Int = 0): Reader{
    override val next by lazy {  inner[current] }
    override val rest by lazy { this.copy(current = current + 1) }
    override val eof = (inner.length <= current )
    override val locus = SimplestLocation(current)
}

interface Result<out T> { open val next: Reader }
data class Success<out T>(val value: T, override val next: Reader): Result<T>
data class Failure(override val next: Reader): Result<Nothing>

fun <T, U> Result<T>.map(f: (T) -> U): Result<U> =
        when(this){
            is Success -> Success(f(value), next)
            else -> Failure(next)
        }

fun <T, U> Result<T>.flatMap(f: (T) -> Result<U>): Result<U> =
        when(this){
            is Success -> {
                val res = f(value)
                when(res) {
                    is Success -> res
                    else -> Failure(next)
                }
            }
            else -> Failure(next)
        }

fun <T> Result<T>.filter(p: (T) -> Boolean): Result<T> =
        when(this){
            is Success -> if(p(value)) this else Failure(next)
            else -> this
        }

fun <T, U> Result<T>.chain(c: (Reader) -> Result<U>) = c(next)
fun <T, U> Result<T>.chainSuccess(c: (Reader) -> Result<U>) =
        when(this){
            is Success -> chain(c)
            else -> this
        }
fun <T> Result<T>.backtrackFailure(bt: Reader) =
        when(this){
            is Success -> this
            else -> Failure(bt)
        }

class SimpleParsers {

    interface Parser<out T>: ((Reader) -> Result<T>) {
        open val name: String
    }

    fun<T> mkParser(name: String, lam: (Reader) -> Result<T>) = object: Parser<T> {
        override fun invoke(r: Reader) = lam(r);
        override val name = name

        override fun toString() = name
    }

    fun <T> pure(v: T): Parser<T> = mkParser("nothing"){ r -> Success(v, r) }
    fun fail(): Parser<Nothing> = mkParser("nothing"){ r -> Failure(r) }

    fun any(): Parser<Char> = mkParser("any character") {
        r -> if(!r.eof) Success(r.next, r.rest) else Failure(r)
    }
    fun eof(): Parser<Unit> = mkParser("eof") {
        r -> if(r.eof) Success(Unit, r) else Failure(r)
    }

    fun<T> Parser<T>.ignore(): Parser<Unit> = mkParser(this.name){ r -> this(r).map{ Unit }}
    fun<T> Parser<T>.knownAs(name: String): Parser<T> = mkParser(name, this)
    fun<T> Parser<T>.filter(pred: (T) -> Boolean) =
            mkParser(name) { r -> this(r).filter(pred) }
    fun<T, U> Parser<T>.map(f: (T) -> U) =
            mkParser(name) { r -> this(r).map(f) }
    fun<T, U> Parser<T>.flatMap(f: (T) -> Parser<U>) =
            mkParser(name) {
                r ->
                    val res0 = this@flatMap(r)
                    when(res0){
                        is Success -> f(res0.value)(res0.next).backtrackFailure(r)
                        else -> Failure(r)
                    }
            }

    operator fun<T, U> Parser<T>.plus(rhv: Parser<U>) =
            mkParser("($name + ${rhv.name})"){
                r -> this(r).chainSuccess(rhv).backtrackFailure(r)
            }

    infix fun<T> Parser<T>.or(rhv: Parser<T>) =
            mkParser("($name | ${rhv.name})"){ r ->
                val res = this(r)
                when(res) {
                    is Success -> res
                    else -> rhv(r)
                }
            }

    fun<T> Parser<T>.many(): Parser<List<T>> =
            mkParser("($name)*"){ r ->
                val con: MutableList<T> = ArrayList()
                var input = r
                var result = this(r)
                while(result is Success) {
                    con.add(result.value)
                    input = result.next
                    result = this(input)
                }
                Success(con, input)
            }

    fun<T> Parser<T>.many1(): Parser<List<T>> =
            mkParser("($name)+"){ r ->
                val con: MutableList<T> = ArrayList()
                var input = r
                var result = this(r)
                if(result is Failure) result
                else {
                    while(result is Success) {
                        con.add(result.value)
                        input = result.next
                        result = this(input)
                    }
                    Success(con, input)
                }
            }

    // derived parsers

    fun empty() = pure(Unit).knownAs("<empty>")
    fun char(c: Char) = any().filter{ it == c }.knownAs("'$c'")
    operator fun Char.invoke() = char(this)
    fun range(from: Char, to: Char) = any().filter { it >= from && it <= to }.knownAs("'$from'-'$to'")

    fun<T> lazyP(f: () -> Parser<T>): Parser<T> = mkParser("{lazy}"){ r -> f()(r)}
    fun<T> fixP(f: (Parser<T>) -> Parser<T>): Parser<T> {
        fun inner(): Parser<T> = lazyP{ f(inner()) }
        return inner().knownAs("{fix}")
    }
}

fun rec(): SimpleParsers.Parser<Unit> = with(SimpleParsers()) {
    val lp = '('()
    val rp = ')'()
    (lp + lazyP { rec() } + rp).ignore() or empty()
}

fun rec2(): SimpleParsers.Parser<Unit> = with(SimpleParsers()) {
    val lp = '('()
    val rp = ')'()
    fixP { (lp + it + rp).ignore() or empty() }
}

fun main(args: Array<String>) {
    val p = with(SimpleParsers()){
        ('_'() or range('a', 'z')).many1() + range('0', '9').many() + eof()
    }
    println(p)

    val parens = with(SimpleParsers()){ rec2() + eof() }
    println(parens)

    while(true) {
        val line = readLine()
        if(line == null) return
        println(parens(StringReader(line)))
    }
}