Parser combinator library simplifies constructing complex parsers from simpler ones. Features include tokenization, combinators for chaining and transforming parsers, and grammar definitions for language parsing. Ideal for building interpreters and compilers.
A nice parser combinator library for Kotlin JVM, JS, and Multiplatform projects
val booleanGrammar = object : Grammar<BooleanExpression>() {
val id by regexToken("\\w+")
val not by literalToken("!")
val and by literalToken("&")
val or by literalToken("|")
val ws by regexToken("\\s+", ignore = true)
val lpar by literalToken("(")
val rpar by literalToken(")")
val term by
(id use { Variable(text) }) or
(-not * parser(this::term) map { Not(it) }) or
(-lpar * parser(this::rootParser) * -rpar)
val andChain by leftAssociative(term, and) { l, _, r -> And(l, r) }
override val rootParser by leftAssociative(andChain, or) { l, _, r -> Or(l, r) }
}
val ast = booleanGrammar.parseToEnd("a & !b | b & (!a | c)")
dependencies {
implementation("com.github.h0tk3y.betterParse:better-parse:0.4.4")
}
With multiplatform projects, it's OK to add the dependency just to the commonMain source set, or some other source set if you want it for specific parts of the code.
As many other language recognition tools, better-parse abstracts away from raw character input by
pre-processing it with a Tokenizer, that can match Tokens (with regular expressions, literal values or arbitrary
against an input character sequence.
There are several kinds of supported Tokens:
regexToken("(?:my)?(?:regex)) is matched as a regular expression;literalToken("foo") is matched literally, character to character;token { (charSequence, from) -> ... } is matched using the passed function.A Tokenizer tokenizes an input sequence such as InputStream or a String into a Sequence<TokenMatch>, providing
each with a position in the input.
One way to create a Tokenizer is to first define the Tokens to be matched:
val id = regexToken("\\w+")
val cm = literalToken(",")
val ws = regexToken("\\s+", ignore = true)
A
Tokencan be ignored by setting itsignore = true. An ignored token can still be matched explicitly, but if another token is expected, the ignored one is just dropped from the sequence.
val tokenizer = DefaultTokenizer(listOf(id, cm, ws))
Note: the tokens order matters in some cases, because the tokenizer tries to match them in exactly this order. For instance, if
literalToken("a")is listed beforeliteralToken("aa"), the latter will never be matched. Be careful with keyword tokens! If you match them with regexes, a word boundary\bin the end may help against ambiguity.
val tokenMatches: Sequence<TokenMatch> = tokenizer.tokenize("hello, world")
A more convenient way of defining tokens is described in the Grammar section.
It is possible to provide a custom implementation of a Tokenizer.
A Parser<T> is an object that accepts an input sequence (TokenMatchesSequence) and
tries to convert some (from none to all) of its items into a T. In better-parse, parsers are also
the building blocks used to create new parsers by combining them.
When a parser tries to process the input, there are two possible outcomes:
If it succeeds, it returns Parsed<T> containing the T result and the nextPosition: Int that points to what
it left unprocessed. The latter can then be, and often is, passed to another parser.
If it fails, it reports the failure returning an ErrorResult, which provides detailed information about the failure.
A very basic parser to start with is a Token itself: given an input TokenMatchesSequence and a position in it,
it succeeds if the sequence starts with the match of this token itself
(possibly, skipping some ignored tokens) and returns that TokenMatch, pointing at the next token
with the nextPosition.
val a = regexToken("a+")
val b = regexToken("b+")
val tokenMatches = DefaultTokenizer(listOf(a, b)).tokenize("aabbaaa")
val result = a.tryParse(tokenMatches, 0) // contains the match for "aa" and the next index is 1 for the match of b
Simpler parsers can be combined to build a more complex parser, from tokens to terms and to the whole language.
There are several kinds of combinators included in better-parse:
As a convenient way of defining a grammar of a language, there is an abstract class Grammar, that collects the by-delegated
properties into a Tokenizer automatically, and also behaves as a composition of the Tokenizer and the rootParser.
Note: a Grammar also collects by-delegated Parser<T> properties so that they can be accessed as
declaredParsers along with the tokens. As a good style, declare the parsers inside a Grammar by delegation as well.
To use a parser that has not been constructed yet, reference it with parser { someParser } or parser(this::someParser):
val term by
constParser or
variableParser or
(-lpar and parser(this::term) and -rpar)
A Grammar implementation can override the tokenizer property to provide a custom implementation of Tokenizer.
A Parser<T> can be converted to another Parser<SyntaxTree<T>>, where a SyntaxTree<T>, along with the parsed T
contains the children syntax trees, the reference to the parser and the positions in the input sequence.
This can be done with parser.liftToSyntaxTreeParser().
This can be used for syntax highlighting and inspecting the resulting tree in case the parsed result does not contain the full syntactic structure.
For convenience, a Grammar can also be lifted to that parsing a SyntaxTree with
grammar.liftToSyntaxTreeGrammar().
val treeGrammar = booleanGrammar.liftToSyntaxTreeGrammar()
val tree = treeGrammar.parseToEnd("a & !b | c -> d")
assertTrue(tree.parser == booleanGrammar.implChain)
val firstChild = tree.children.first()
assertTrue(firstChild.parser == booleanGrammar.orChain)
assertTrue(firstChild.range == 0..9)
There are optional arguments for customizing the transformation:
See SyntaxTreeDemo.kt for an example of working with syntax trees.
BooleanExpression.ktSee the benchmarks repository h0tk3y/better-parse-benchmark and feel free to contribute.
map, use, asJust
The map combinator takes a successful input of another parser and applies a transforming function to it. The error results are returned unchanged.
val id = regexToken("\\w+")
val aText = a map { it.text } // Parser<String>, returns the matched text from the input sequence
A parser for objects of a custom type can be created with map:
val variable = a map { JavaVariable(name = it.text) } // Parser<JavaVariable>.
someParser use { ... } is a map equivalent that takes a function with receiver instead. Example: id use { text }.
foo asJust bar can be used to map a parser to some constant value.
optional(...)
Given a Parser<T>, tries to parse the sequence with it, but returns a null result if the parser failed, and thus never fails itself:
val p: Parser<T> = ...
val o = optional(p) // Parser<T?>
and, and skip(...)
The tuple combinator arranges the parsers in a sequence, so that the remainder of the first one goes to the second one and so on.
If all the parsers succeed, their results are merged into a Tuple. If either parser failes, its ErrorResult is returned by the combinator.
val a: Parser<A> = ...
val b: Parser<B> = ...
val aAndB = a and b // This is a `Parser<Tuple2<A, B>>`
val bAndBAndA = b and b and a // This is a `Parser<Tuple3<B, B, A>>`
You can skip(...) components in a tuple combinator: the parsers will be called just as well, but their results won't be included in the
resulting tuple:
val bbWithoutA = skip(a) and b and skip(a) and b and skip(a) // Parser<Tuple2<B, B>>
If all the components in an
andchain are skipped except for oneParser<T>, the resulting parser isParser<T>, notParser<Tuple1<T>>.
To process the resulting Tuple, use the aforementioned map and use. These parsers are equivalent:
val fCall = id and skip(lpar) and id and skip(rpar) map { (fName, arg) -> FunctionCall(fName, arg) }
val fCall = id and lpar and id and rpar map { (fName, _, arg, _) -> FunctionCall(fName, arg) }
val fCall = id and lpar and id and rpar use { FunctionCall(t1, t3) }
val fCall = id * -lpar * id * -rpar use { FunctionCall(t1, t2) } (see operators below)
There are
Tupleclasses up toTuple16and the correspondingandoverloads.
There are operator overloads for more compact and chains definition:
a * b is equivalent to a and b.
-a is equivalent to skip(a).
With these operators, the parser a and skip(b) and skip(c) and d can also be defined as
a * -b * -c * d.
or
The alternative combinator tries to parse the sequence with the parsers it combines one by one until one succeeds. If all the parsers fail,
the returned ErrorResult is an AlternativesFailure instance that contains all the failures from the parsers.
The result type for the combined parsers is the least common supertype (which is possibly Any).
val expr = const or variable or fCall
zeroOrMore(...), oneOrMore(...), N times, N timesOrMore, N..M times
These combinators transform a Parser<T> into a Parser<List<T>>, invokng the parser several times and failing if there was not
enough matches.
val modifiers = zeroOrMore(functionModifier)
val rectangleParser = 4 times number map { (a, b, c, d) -> Rect(a, b, c, d) }
separated(term, separator), separatedTerms(term, separator), leftAssociative(...), rightAssociative(...)
Combines the two parsers, invoking them in turn and thus parsing a sequence of term matches separated by separator matches.
The result is a Separated<T, S> which provides the matches of both parsers (note that terms are one more than separators) and
can also be reduced in either direction.
val number: Parser<Int> = ...
val sumParser = separated(number, plus) use { reduce { a, _, b -> a + b } }
The leftAssociative and rightAssociative combinators do exactly this, but they take the reducing operation as they are built:
val term: Parser<Term>
val andChain = leftAssociative(term, andOperator) { l, _, r -> And(l, r) }
interface Item
class Number(val value: Int) : Item
class Variable(val name: String) : Item
class ItemsParser : Grammar<List<Item>>() {
val num by regexToken("\\d+")
val word by regexToken("[A-Za-z]+")
val comma by regexToken(",\\s+")
val numParser by num use { Number(text.toInt()) }
val varParser by word use { Variable(text) }
override val rootParser by separatedTerms(numParser or varParser, comma)
}
val result: List<Item> = ItemsParser().parseToEnd("one, 2, three, 4, five")
LiftToSyntaxTreeOptions
retainSkipped — whether the resulting syntax tree should include skipped and components;retainSeparators — whether the Separated combinator parsed separators should be included;structureParsers — defines the parsers that are retained in the syntax tree; the nodes with parsers that are
not in this set are flattened so that their children are attached to their parents in their place.
For Parser<T>, the default is null, which means no nodes are flattened.
In case of Grammar<T>, structureParsers defaults to the grammar's declaredParsers.
transformer — a strategy to transform non-built-in parsers. If you define your own combinators and want them
to be lifted to syntax tree parsers, pass a LiftToSyntaxTreeTransformer that will be called on the parsers. When
a custom combinator nests another parser, a transformer implementation should call default.transform(...) on that parser.
ArithmeticsEvaluator.ktSurfaced from shared tags and platforms — no rankings paid for.