Last active
March 20, 2018 11:44
-
-
Save absurdhero/24e6b0ed914b0499a38f to your computer and use it in GitHub Desktop.
monadic parser combinator in Kotlin
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is based on Luke Hoban's famous article:
http://blogs.msdn.com/b/lukeh/archive/2007/08/19/monadic-parser-combinators-using-c-3-0.aspx