Skip to content

Instantly share code, notes, and snippets.

@absurdhero
Last active March 20, 2018 11:44
Show Gist options
  • Star 2 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save absurdhero/24e6b0ed914b0499a38f to your computer and use it in GitHub Desktop.
Save absurdhero/24e6b0ed914b0499a38f to your computer and use it in GitHub Desktop.
monadic parser combinator in Kotlin
package net.raboof.parser
// based on http://blogs.msdn.com/b/lukeh/archive/2007/08/19/monadic-parser-combinators-using-c-3-0.aspx
data class Result<TInput, TValue>(val value: TValue, val rest: TInput)
class Parser<TInput, TValue>(val f: (TInput) -> Result<TInput, TValue>?) {
operator fun invoke(input: TInput): Result<TInput, TValue>? = f(input)
infix fun or(other: Parser<TInput, TValue>): Parser<TInput, TValue> {
return Parser({ input -> this(input) ?: other(input) })
}
infix fun and(other: Parser<TInput, TValue>): Parser<TInput, TValue> {
return Parser({ input ->
val result = this(input)
if (result == null) {
null
} else {
other(result.rest)
}
})
}
// like and() but ignores the both the type and value of the first parser
infix fun <TValue2> then(other: Parser<TInput, TValue2>): Parser<TInput, TValue2> {
return Parser({ input ->
val result = this(input)
if (result == null) {
null
} else {
other(result.rest)
}
})
}
fun filter(pred: (TValue) -> Boolean): Parser<TInput, TValue> {
return Parser({ input ->
val result = this(input)
if (result == null || !pred(result.value)) {
null
} else {
result
}
})
}
fun <TValue2> map(selector: (TValue) -> TValue2): Parser<TInput, TValue2> {
return Parser({ input ->
val result = this(input)
if (result == null) {
null
} else {
Result(selector(result.value), result.rest)
}
})
}
fun <TIntermediate, TValue2> mapJoin(
selector: (TValue) -> Parser<TInput, TIntermediate>,
projector: (TValue, TIntermediate) -> TValue2
): Parser<TInput, TValue2> {
return Parser({ input ->
val res = this(input)
if (res == null) {
null
} else {
val v = res.value
val res2 = selector(v)(res.rest)
if (res2 == null) null
else Result(projector(v, res2.value), res2.rest)
}
})
}
fun <TValue2> withResult(selector: (Result<TInput, TValue>) -> Result<TInput, TValue2>?): Parser<TInput, TValue2> {
return Parser({ input ->
val result = this(input)
if (result == null) {
null
} else {
selector(result)
}
})
}
}
abstract class Parsers<TInput> {
public fun <TValue> succeed(value: TValue): Parser<TInput, TValue> {
return Parser({ input -> Result(value, input) })
}
public fun <TValue> repeat(parser: Parser<TInput, TValue>): Parser<TInput, List<TValue>> {
return repeat1(parser) or succeed<List<TValue>>(emptyList())
}
public fun <TValue> repeat1(parser: Parser<TInput, TValue>): Parser<TInput, List<TValue>> {
return parser.mapJoin({ v -> repeat(parser) }, { v: TValue, l: List<TValue> -> arrayListOf(v) + l })
}
}
abstract class CharParsers<TInput>() : Parsers<TInput>() {
// implement anyChar to read a character from a sequence
abstract val anyChar: Parser<TInput, Char>
public fun char(ch: Char): Parser<TInput, Char> {
return anyChar.filter({ c -> c == ch })
}
public fun char(predicate: (Char) -> Boolean): Parser<TInput, Char> {
return anyChar.filter(predicate)
}
public val whitespace: Parser<TInput, List<Char>> = repeat(char(' ') or char('\t') or char('\n') or char('\r'));
public val nonWhitespace: Parser<TInput, Char> = anyChar.filter { input -> input != ' ' }
public fun wsChar(ch: Char) = whitespace then char(ch)
}
@absurdhero
Copy link
Author

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment